1 #include <stdio.h>
2 #include <
malloc.h>
3 /*单链表节点定义*/
4 typedef
struct LNode {
5 int data;
//data中存放节点数据域
6 struct LNode *next;
//指向后继节点的指针
7 }LNode;
//定义单链表节点类型
8
9 /*例2.3开始*/
10 /*A和B是两个单链表（带表头结点），其中元素递增有序，设计一个算法，将A 和B归并成一个按元素值非递减有序的链表C，C由A和B中的节点组成*/
11 void mergeLNodeAsc(LNode *A, LNode *B, LNode *&
C) {
12 LNode *p = A->next;
//p用来跟踪A的最小值节点 A->next表示A链表的开始节点（头结点的下一个） A递增，所以p指向他表示指向A的最小节点，即用p来跟踪A的最小节点
13 LNode *q = B->next;
//q来跟踪B的最小值节点
14 LNode *r;
//r始终指向C的终端节点
15 C = A;
//用A的头结点来做C的头结点
16 C->next =
NULL;
17 free(B);
//B的头结点无用，则释放掉
18 r = C;
//r指向C 因为此时头结点也是终端节点
19 while (p!=NULL&&q!=NULL) {
//当p和q都不空时，选取p和q所指节点中的较小者插入C的尾部
20 if (p->data<=q->
data) {
21 printf(
"p小于q");
22 r->next=p;
//赋值C的节点
23 p = p->next;
//p前移一个
24 r = r->next;
//r前移一个
25
26 }
27 else {
28 printf(
"q小于p");
29 r->next =
q;
30 q = q->
next;
31 r = r->
next;
32 }
33
34 }
35 r->next = NULL;
//这一个其实可以去掉 因为至少会剩下一个插入到C的尾部
36 /*将还有剩余节点的链表插入到C的尾部*/
37 if (p!=
NULL) {
38 r->next =
p;
39 }
40 if (q !=
NULL) {
41 r->next =
q;
42 }
43
44 }
45 /*例2.3结束*/
46
47
48 /*尾插法建立链表C*/
49
50 void createListR(LNode *&C,
int a[],
int n) {
//要改变的变量用引用型
51 LNode *s, *r;
//s用来指向新申请的节点，r始终指向C的终端节点
52 int i;
53 C = (LNode *)
malloc(
sizeof(LNode));
//申请C的头结点空间
54 C->next =
NULL;
55 r = C;
//r指向头结点，因为此时头结点就是终端节点
56 for (i =
0; i < n;++
i) {
57 s = (LNode *)
malloc(
sizeof(LNode));
//s指向新申请的节点
58 s->data = a[i];
//用新申请的节点来接收a的一个元素
59 r->next = s;
//用r来接纳新节点
60 r = r->next;
//用r指向终端节点，以便于接纳下一个到来的节点
61 }
62 r->next = NULL;
//数组a中所有的元素都已经装入链表C中，C的终端节点的指针域为NULL C建立完成
63
64 }
65
66 /*头插法建立链表C*/
67 void createListF(LNode *&C,
int a[],
int n) {
//要改变的变量用引用型
68 LNode *s;
//s用来指向新申请的节点
69 int i;
70 C = (LNode *)
malloc(
sizeof(LNode));
//申请C的头结点空间
71 C->next =
NULL;
72 for (i =
0; i < n; ++
i) {
73 s = (LNode *)
malloc(
sizeof(LNode));
//s指向新申请的节点
74 s->data = a[i];
//用新申请的节点来接收a的一个元素
75 s->next = C->next;
//s所指新节点的指针域next指向C的开始节点
76 C->next = s;
//头结点的指针域next指向s节点，使得s称为新的开始节点
77 }
78
79 }
80
81 /*归并为递减的单链表*/
82
83 void mergeLNodeDesc(LNode *A,LNode *B,LNode *&
C) {
84
85 LNode *p = A->
next;
86 LNode *q = B->
next;
87 LNode *
s;
88 C =
A;
89 C->next =
NULL;
90 free(B);
91 while (p!=NULL&&q!=
NULL) {
92 if (p->data<=q->
data) {
93 s =
p;
94 p=p->
next;
95 s->next=C->
next;
96 C->next =
s;
97 }
98 else {
99 s =
q;
100 q = q->
next;
101 s->next = C->
next;
102 C->next =
s;
103 }
104 }
105 /*必须将剩余元素逐个插入C的头部才能得到最终的递减序列*/
106
107 while (p!=
NULL) {
108 s =
p;
109 p = p ->
next;
110 s ->next = C->
next;
111 C->next =
s;
112 }
113 while (q !=
NULL) {
114 s =
q;
115 q = q->
next;
116 s->next = C->
next;
117 C->next =
s;
118 }
119
120 }
121
122 /*例2.4开始*/
123 /*查找链表C中是否存在一个值为x的节点，若存在，则删除该节点并返回1，否则返回0*/
124
125 int findAndDelete(LNode *C,
int x) {
126 LNode *p, *q;
/*q用来接纳删除的元素 ，p用来指向C的节点*/
127 p =
C;
128 while (p->next!=
NULL) {
129
130 if (p->next->data ==x) {
/*查找的是要删除节点的额前驱节点*/
131 break;
132 }
133 p = p->next;
/*如果当前不是要找的节点 则p向后移*/
134 }
135 /*没找到*/
136 if (p->next ==
NULL) {
137 return 0;
138
139 }
140 else {
141 /*删除部分开始*/
142 q = p->
next;
143 p->next = p->next->
next;
144 free(q);
145 /*删除部分结束*/
146 return 1;
147 }
148
149 }
150 /*例2.4结束*/
151
152 /*打印链表中的元素*/
153 void showLNode(LNode *
C) {
154 LNode *
p;
155 p =
C;
156 while (p->next!=
NULL) {
157 printf(
"C的数据为：%d\n", p->next->
data);
158 p = p->
next;
159 }
160
161 }
162
163 void main() {
164
165 LNode *
C;
166 int a[] = {
1,
2,
3,
4 };
167 int n =
4;
168 createListF(C, a, n);
169 showLNode(C);
// 4 3 2 1
170 findAndDelete(C,
2);
171 showLNode(C);
// 4 3 1
172
173
174 LNode *
D;
175 int b[] = {
1,
2,
3,
4,
5,
6 };
176 int m =
6;
177 createListR(D, b, m);
178 showLNode(D);
// 1 2 3 4 5 6
179
180 findAndDelete(D,
8);
181 showLNode(D);
// 1 2 3 4 5 6
182 printf(
"开始合并数组");
183
184 LNode *
M;
185 int m1[] = {
1,
3,
5 };
186 int m2 =
3;
187 createListR(M, m1, m2);
188 LNode *
N;
189 int n1[] = {
2,
4,
6 };
190 int n2 =
3;
191 createListR(N, n1, n2);
192 LNode *
O;
193 mergeLNodeDesc(M, N,O);
194 showLNode(O);
// 6 5 4 3 2 1
195
196 LNode *
Q;
197 int q1[] = {
1,
3,
5 };
198 int q2 =
3;
199 createListR(Q, q1, q2);
200 LNode *
R;
201 int r1[] = {
2,
4,
6 };
202 int r2 =
3;
203 createListR(R, r1, r2);
204 LNode *
P;
205 mergeLNodeAsc(Q, R, P);
206 showLNode(P);
// 1 2 3 4 5 6
207 }
转载于:https://www.cnblogs.com/dream-to-pku/p/11426001.html
相关资源：JAVA上百实例源码以及开源项目
