《數據結構》2.6單鏈表應用舉例，《數據結構》2.6
1 //單鏈表倒置（頭插法，時間復雜度O(n)）
2 /*算法思路:
3 依次取出原鏈表中的每個節點，每次都將其作為第一個節點插入原鏈表中；由於采用頭插法，插入順序與取節點
4 順序正好相反，故可以完成倒置操作。
5 */
6 void reverseList(LinkList h) //reverse：背面、相反、顛倒
7 {
8 LNode *p;
9 p = h->next; //*p指向第一個數據元素節點
10 h->next = NULL; //將原鏈表置為空表
11 while(p)
12 {
13 q = p;
14 p = p->next;
15 q->next = h->next; //將第一個節點插到當前節點的後面（即當前節點插到了頭節點的後面）
16 h->next = q;
17 }
18 }
19
20 //重復節點的刪除（單鏈表中數據域值相同的節點稱為重復節點，時間復雜度O(n*n)）
21 /*算法思路：
22 用指針p指向第一個數據節點，從它的直接後繼節點開始直到鏈表的結束，找到與其值相同的節點並刪除；p指向
23 下一節點，重復上述操作；依此類推；當p指向表尾節點時算法結束。
24 */
25 void del_LinkList(LinkList h)
26 {
27 LNode *p, *q, *r;
28 p = L->next; //p指向第一個節點
29 if(p = NULL) return 0;
30 while(q->next)
31 {
32 q = p;
33 while(q->next) //從p的後繼開始查找重復節點
34 {
35 if(q->next->data == p->data)
36 {
37 r = q->next; //r指向重復節點
38 q->next = r->next;
39 free(r); //刪除r
40 }
41 else
42 q = q->next;
43 }
44 p = p->next; //p指向下一個節點
45 }
46 }
47
48 //單鏈表的合並（頭插法，時間復雜度O(m+n)，合並：merge）
49 //兩個單鏈表A、B中元素均為遞增有序，現將A、B歸並一個按元素值非遞增（允許有相同值）有序單鏈表C，不需要重新申請節點。
50 /*算法思路：
51 利用A、B遞增有序的特點，依次取出當前節點進行比較，將當前值較小者取下，插入C的頭部；由於采用的是
52 頭插法，最先找到的最小值節點將會在C的尾部；依此類推，所以得到的C為非遞增有序的單鏈表。
53 */
54 LinkList merge_LinkList(LinkList A, LinkList B) //A、B均為帶頭節點的單鏈表
55 {
56 LinkList C;
57 LNode *p, *q, *r;
58 p = A->next;
59 q = B->next;
60 c = A; //C的頭節點
61 c->next = NULL;
62 free(B); //釋放B的頭節點
63 while(p && q)
64 {
65 if(p->data < q->data)
66 {
67 r = p; p = p->next;
68 }
69 else
70 {
71 r = q; q = q->next; //從原A、B上取下較小值的節點
72 r->next = C->next; //將第一個節點插到當前節點的後面（即插入到C的頭部）
73 C->next = r;
74 }
75 if(p == NULL) p = q;
76 while(p) //將剩余的節點一個個取下，插入C的頭部
77 {
78 r = p; p = p->next;
79 r->next = C->next;
80 C->next = r;
81 }
82 }
83 }
84
85 //一元多項式的表示及相加時間復雜度O(m+n)
86 /* 在數學上，一個n元多項式可以表示為Pn(x)=p0+p1*x+p2*x^2+…+pn*x^n，該多項式由n+1個系數唯一確定。
87 在計算機裡，可以用一個線性表P來表示，即P=(p0,p1,p2,…pn)，每項的指數i隱含在其系數pi的序號裡。同理，
88 Qm(x)表示為Q=(q0,q1,q2,…qm),設m<n,相加結果Rn(x)表示為R=(p0+q0,p1+q1,p2+q2,…,pm+qm,pm+1,…,pn)。
89 為了有效而合理的利用存儲空間，對於系數為0的所有項全都不存儲，只存儲非0項的系數及其相應的指數。
90 算法思路：
91 設PA和PB分別為兩個參與運算多項式的頭指針，PC為結果鏈表頭指針，指針ha和hb分別指向多項式PA和PB中當前進行比較的節點；
92 比較兩個節點的指數項，進行如下操作。
93 （1）指針ha所指節點的指數值小於指針hb所指節點的指數值，將ha所指節點插入PC鏈尾，指針ha後移一個節點；
94 （2）指針ha所指節點的指數值等於指針hb所指節點的指數值，將ha和hb兩個節點的系數相加，若系數之和為零，則刪除兩節點；
95 若系數之和不為零，則將兩者系數之和賦值給ha所指節點且插入PC鏈尾，刪除hb所指節點；
96 （3）指針ha所指節點的指數值大於指針hb所指節點的指數值，將hb所指節點插入PC鏈尾，指針hb後移一個節點。
97 若PA和PB中有一個鏈表先行比較完畢，那麼另一個未比較完鏈表的余下部分可直接連接到PC鏈表的表尾。
98 */
99 //定義節點
100 typedef struct Lnode
101 {
102 float coef; //系數（coeficient）
103 int exp; //指數（exponent）
104 struct Lnode *next;
105 }Lnode, *LinkList;
106 //多項式相加
107 void Add(Lnode *PA, Lnode *PB, Lnode *PC)
108 {
109 Lnode *ha, *hb, *temp;
110 int sum;
111 ha = PA->next;
112 hb = PB->next;
113 PC = PA; //PC指針最初是指向結果鏈的表頭
114 while(ha != NULL && hb !=NULL)
115 {
116 if(ha->exp < hb->exp)
117 {
118 PC->next = ha; PC = PC->next; ha = ha->next; //PC此時變為移動指針，指向結果鏈當前節點
119 }
120 else if(ha->exp == hb->exp)
121 {
122 sum = ha->coef + ha->coef;
123 if(sum != 0) //如果系數和不為零
124 {
125 ha->coef = sum;
126 PC->next = ha; PC = PC->next; ha = ha->next;
127 temp = hb; hb = hb->next; free(temp);
128 }
129 else //如果系數和為零，則刪除節點ha與hb，並將兩指針分別指向下一個節點
130 {
131 temp = ha; ha = ha->next; free(temp);
132 temp = hb; hb = hb->next; free(temp);
133 }
134 }
135 else //ha=>exp > hb->exp;
136 {
137 PC->next = hb; PC = PC->next; hb = hb->next;
138 }
139 }
140 if(ha != NULL) //將多項式PA中剩余的節點連接到PC中
141 PC->next = ha;
142 else //將多項式PB中剩余的節點連接到PC中
143 PC->next = hb;
144 PC = PA; //PC指針恢復為指向結果鏈表頭
145 free(PB); //釋放掉剩余的PB頭指針
146 }
