首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

16.单向链表的一些基本操作实现(链表反转,链表有环无环判断,链表冒泡排序,链表快速排序)...

作者：Triste夏木_668_365 | 来源：互联网 | 2023-09-24 14:48
运行截图:链表快速排序原理:链表定义structLinkNode{intdata;structLinkNode*pNext;};typedefstructLinkNodeno
  • 运行截图:

  •  

  •  链表快速排序原理:

  •  

  • 链表定义

    struct LinkNode
    {    int data;struct LinkNode *pNext;
    };
    typedef     struct LinkNode node;

     

  • 尾部添加节点

    void addback(node **phead, int data)
    {    //先创建新的结点node *pnew &＃61; (node *)malloc(sizeof(node));pnew->data &＃61; data;pnew->pNext &＃61; NULL;//如果头结点为空if (*phead &＃61;&＃61; NULL){//头结点指向pnew*phead &＃61; pnew;}else{//否则备份首地址,找到最后一个node *ptemp &＃61; *phead;while (ptemp->pNext !&＃61; NULL){ptemp &＃61; ptemp->pNext;}ptemp->pNext &＃61; pnew;}}

     

  • 显示链表

    1 void showall(node *phead)
     2 {
     3 if (phead &＃61;&＃61; NULL)
     4 {
     5 return;
     6 }
     7 else
    8 {
     9 printf("%5d 本节点地址:%p 下一个节点地址:%p\n", phead->data, phead, phead->pNext);
    10 showall(phead->pNext);//跳到下一个节点
    11 }
    12 }

     

  • 反转显示

    void revshowall(node *phead)
    {    if (phead &＃61;&＃61; NULL){return;}else{showall(phead->pNext);//跳到下一个节点printf("%d ,%p,%p\n", phead->data, phead, phead->pNext);}
    }

     

  • 头部插入

    1 void addhead(node **pphead, int data)
     2 {
     3 node *pnew &＃61; (node *)malloc(sizeof(node));
     4 pnew->data &＃61; data;
     5 pnew->pNext &＃61; NULL;//赋值
    6
    7 if (*pphead&＃61;&＃61;NULL)
     8 {
     9 *pphead &＃61; pnew;
    10 }
    11 else
    12 {
    13 pnew->pNext &＃61; *pphead;
    14 *pphead &＃61; pnew;
    15 }
    16 }

     

  • 寻找第一个指定元素的位置

    1 node *searchfirst(node *phead, int finddata)
     2 {
     3 for (node *p &＃61; phead; p !&＃61; NULL; p &＃61; p->pNext)
     4 {
     5 if (p->data &＃61;&＃61; finddata)
     6 {
     7 return p;//返回找到的地址
    8 }
     9 }
    10 return NULL;
    11 }

     

  • 改变第一个指定元素的值

    1 void changefirst(node *phead, int finddata,int newdata)
     2 {
     3 for (node *p &＃61; phead; p !&＃61; NULL; p &＃61; p->pNext)
     4 {
     5 if (p->data &＃61;&＃61; finddata)
     6 {
     7 p->data &＃61; newdata;
     8 }
     9 }
    10 }

     

  • 删除第一个指定元素

    1 void deleteFirst(node **phead, int finddata)
     2 {
     3 node *p1 &＃61; NULL, *p2 &＃61; NULL;//p1向前,p2保存p1的上一个位置
    4 p1 &＃61; *phead;//保存头结点
    5 while (p1 !&＃61; NULL)
     6 {
     7 if (p1->data !&＃61; finddata)
     8 {
     9 p2 &＃61; p1;
    10 p1 &＃61; p1->pNext;
    11 }
    12 else
    13 {
    14 break;
    15 }
    16 }
    17
    18 if (p1 &＃61;&＃61; NULL)
    19 {
    20 return;
    21 }
    22 //如果是头结点
    23 if (p1 &＃61;&＃61; *phead)
    24 {
    25 *phead &＃61; (*phead)->pNext;
    26 free(p1);//头部删除
    27 }
    28 else
    29 {
    30 p2->pNext &＃61; p1->pNext;
    31 free(p1);
    32 }
    33
    34 }

     

  • 插入元素(在找到的元素之前插入)

    1 void insertFirstHead(node **phead, int finddata,int newdata)
     2 {
     3 node *p1 &＃61; NULL, *p2 &＃61; NULL;//p1向前,p2保存p1的上一个位置
    4 p1 &＃61; *phead;//保存头结点
    5 while (p1 !&＃61; NULL)
     6 {
     7 if (p1->data !&＃61; finddata)
     8 {
     9 p2 &＃61; p1;
    10 p1 &＃61; p1->pNext;
    11 }
    12 else
    13 {
    14 break;
    15 }
    16 }
    17
    18 if (p1 &＃61;&＃61; NULL)
    19 {
    20 return;
    21 }
    22
    23
    24 node *pnew &＃61; (node *)malloc(sizeof(node));//新的结点
    25 pnew->data &＃61; newdata;
    26 pnew->pNext &＃61; NULL;//赋值
    27
    28 //如果是头结点
    29 if (p1 &＃61;&＃61; *phead)
    30 {
    31 pnew->pNext &＃61; p1;
    32 *phead &＃61; pnew;
    33 }
    34 else
    35 {
    36 p2->pNext &＃61; pnew;
    37 pnew->pNext &＃61; p1;
    38 }
    39 }

     

  • 插入元素(在找到的元素之后插入)

    1 void insertFirstBack(node **phead, int finddata, int newdata)
     2 {
     3 node *p1 &＃61; NULL, *p2 &＃61; NULL;//p1向前,p2保存p1的上一个位置
    4 p1 &＃61; *phead;//保存头结点
    5 while (p1 !&＃61; NULL)
     6 {
     7 if (p1->data !&＃61; finddata)
     8 {
     9 p2 &＃61; p1;
    10 p1 &＃61; p1->pNext;
    11 }
    12 else
    13 {
    14 break;
    15 }
    16 }
    17
    18 if (p1 &＃61;&＃61; NULL)
    19 {
    20 return;
    21 }
    22
    23 //创建新的结点
    24 node *pnew &＃61; (node *)malloc(sizeof(node));
    25 pnew->data &＃61; newdata;
    26 pnew->pNext &＃61; NULL;//赋值
    27
    28 //如果是头结点
    29 if (p1 &＃61;&＃61; *phead)
    30 {
    31 p1->pNext &＃61; pnew;
    32 }
    33 else
    34 {
    35 pnew->pNext &＃61; p1->pNext;
    36 p1->pNext &＃61; pnew;
    37 }
    38 }

     

  • 链表冒泡排序

    1 void bubblesort(node *phead)
     2 {
     3 for (node *p1 &＃61; phead; p1->pNext !&＃61; NULL; p1 &＃61; p1->pNext)
     4 {
     5 for (node *p2 &＃61; phead; p2 ->pNext !&＃61; NULL; p2 &＃61; p2->pNext)
     6 {
     7
    8 if (p2->data > p2->pNext->data)
     9 {
    10 int tmp &＃61; p2->data;
    11 p2->data &＃61; p2->pNext->data;
    12 p2->pNext->data &＃61; tmp;
    13 }
    14 }
    15 }
    16 }

     

  • 链表分段,返回中间点,用于递归快速排序链表

    1 node *fen(node *pbegin, node *pback)
     2 {
     3 int key &＃61; pbegin->data;//以第一个数据为分段
     4 //核心思想:保证p,q直接的数据都大于等于key,q在p的后面
    5 node *p &＃61; pbegin;//标识第一个节点
    6 node *q &＃61; pbegin->pNext;//游标标识第二个节点
    7
    8 while (q !&＃61; pback)
     9 {
    10 //找到小于key的数据,然后交换
    11 if (q->data < key)
    12 {
    13 //循环下一个节点,并进行赋值(p,q之间的值都大于key)
    14 p &＃61; p->pNext;
    15
    16 int temp &＃61; p->data;
    17 p->data &＃61; q->data;
    18 q->data &＃61; temp;//交换
    19 }
    20 q &＃61; q->pNext;//循环游标
    21 }
    22 int temp &＃61; p->data;
    23 p->data &＃61; pbegin->data;
    24 pbegin->data &＃61; temp;//交换
    25
    26 return p;
    27 }

     

  • 快速排序

    1 void quicksort(node *pbegin,node *pback)
    2 {
    3 if (pbegin !&＃61; pback)
    4 {
    5 node *pfen &＃61; fen(pbegin, pback);//取中间点
    6 quicksort(pbegin, pfen);
    7 quicksort(pfen->pNext, pback);
    8 }
    9 }

     

  • 获取链表的长度

    1 int getnum(node *phead)
     2 {
     3 int i &＃61; 0;
     4 while (phead !&＃61; NULL)
     5 {
     6 i&＃43;&＃43;;
     7 phead &＃61; phead->pNext;
     8 }
     9 return i;
    10 }

     

  • 链表反转

    1 void rewind(node **phead)
     2 {
     3
    4 //备份头节点的地址 位置关系:front back tail
    5 node *front &＃61; *phead;
     6 //back在from的后面
    7 node *back &＃61; (*phead)->pNext;
     8 //反转后头结点的pNext为NULL
    9 (*phead)->pNext &＃61; NULL;
    10 //当后一个不为尾节点
    11 while ( back !&＃61; NULL)
    12 {
    13 //back节点的后一个节点,用于给back节点赋值
    14 node *tail &＃61; back->pNext;
    15 //back节点的pNext为front
    16 back->pNext &＃61; front;
    17 //front移到back节点位置
    18 front &＃61; back;
    19 back &＃61; tail;//back移到tail节点位置
    20 }
    21 *phead &＃61; front;
    22 }

     

  • 递归反转

    1 node *digui_rew(node *phead)
     2 {
     3 //在结尾处返回
    4 if (phead &＃61;&＃61; NULL || (phead)->pNext &＃61;&＃61; NULL)
     5 {
     6 return phead;
     7 }
     8 else
    9 {
    10 node *next &＃61; phead->pNext;
    11 node *head &＃61; digui_rew(next);
    12 next->pNext &＃61; phead;
    13 phead->pNext &＃61; NULL;
    14
    15 //第一步递归返回
    16 return head;
    17 }
    18 }

     

  • 判断链表是否有环(追击相遇,一个一次前进一个,一个一次前进两个,如果有环则一定能相遇)

    1 int isCir(node *phead)
     2 {
     3 node *p1 &＃61; phead;//一次前进一个
    4 node *p2 &＃61; phead;//一次前进两个
    5
    6 int flag &＃61; 0;//0表示没有环
    7 while (p1 !&＃61; NULL && p2 !&＃61; NULL && p2->pNext !&＃61; NULL)
     8 {
     9 p1 &＃61; p1->pNext;
    10 p2 &＃61; p2->pNext->pNext;
    11 if (p1 &＃61;&＃61; p2)
    12 {
    13 flag &＃61; 1;
    14 break;
    15 }
    16 }
    17
    18 return flag;
    19 }

     

  • 有序链表合并,把link2合并到link1

    1 void merge(node **head1, node **head2)
     2 {
     3 //备份head2的头结点地址,一直循环结束
    4 node *p2 &＃61; *head2;
     5 while (p2 !&＃61; NULL)
     6 {
     7 //如果比头节点的值要小,则把p2变成p1的头结点
    8 if (p2->data <(*head1)->data)
     9 {
    10 node *p2tmp &＃61; p2->pNext;//备份p2后一个元素
    11 //把头结点地址*head1传给p2->pNext
    12 p2->pNext &＃61; *head1;
    13 //p2的地址传给*head1
    14 *head1 &＃61; p2;
    15 //向后遍历
    16 p2 &＃61; p2tmp;
    17 }
    18 else
    19 {
    20 //p1是第一个后面的节点的data大于p2->data的节点,核心思想是把P2插入到p1之后
    21 node *p1;
    22 node *p2tmp &＃61; p2->pNext;//备份p2后一个元素
    23 for (p1 &＃61; *head1; p1->pNext !&＃61; NULL; p1 &＃61; p1->pNext)
    24 {
    25 if (p1->pNext->data > p2->data)
    26 {
    27 break;
    28 }
    29 }
    30 p2->pNext &＃61; p1->pNext;
    31 p1->pNext &＃61; p2;
    32
    33 p2 &＃61; p2tmp;
    34 }
    35 }
    36 }

     

  • 链表取中间值

    1 node *findmid(node *phead)
     2 {
     3 if (isCir(phead))
     4 {
     5 return NULL;
     6 }
     7
    8 node *p1 &＃61; phead;
     9 node *p2 &＃61; phead;
    10 while (p1 !&＃61; NULL && p2 !&＃61; NULL && p2->pNext !&＃61; NULL)
    11 {
    12 p1 &＃61; p1->pNext;
    13 p2 &＃61; p2->pNext->pNext;
    14 }
    15 return p1;
    16 }

     

 

完整代码:

1 #include
2 #include
3
4 struct LinkNode
 5 {
 6 int data;
 7 struct LinkNode *pNext;
 8 };
 9 typedef struct LinkNode node;
 10
11 //尾部添加节点
12 void addback(node **phead, int data);
 13 //头部插入
14 void addhead(node **pphead, int data);
 15 //显示链表
16 void showall(node *phead);
 17 //反转显示
18 void revshowall(node *phead);
 19 //寻找第一个元素的位置
20 node *searchfirst(node *phead, int finddata);
 21 //改变第一个元素的值
22 void changefirst(node *phead, int finddata, int newdata);
 23 //删除第一个元素
24 void deleteFirst(node **phead, int finddata);
 25 //插入元素(在找到的元素之前插入)
26 void insertFirstHead(node **phead, int finddata, int newdata);
 27 //插入元素(在找到的元素之后插入)
28 void insertFirstBack(node **phead, int finddata, int newdata);
 29 //链表冒泡排序
30 void bubblesort(node *phead);
 31 //快速排序
32 void quicksort(node *pbegin, node *pback);
 33 //链表分段,返回中间点
34 node *fen(node *pbegin, node *pback);
 35 //获取链表的长度
36 int getnum(node *phead);
 37 //链表反转
38 void rewind(node **phead);
 39 //递归反转
40 void digui_rew(node **phead);
 41 //有序链表合并,把link2合并到link1
42 void merge(node **link1, node **link2);
 43 //链表取中间值
44 node *findmid(node *phead);
 45
46 //尾部添加节点
47 void addback(node **phead, int data)
 48 {
 49 //先创建新的结点
50 node *pnew &＃61; (node *)malloc(sizeof(node));
 51 pnew->data &＃61; data;
 52 pnew->pNext &＃61; NULL;
 53
54 //如果头结点为空
55 if (*phead &＃61;&＃61; NULL)
 56 {
 57 //头结点指向pnew
58 *phead &＃61; pnew;
 59 }
 60 else
61 {
 62 //否则备份首地址,找到最后一个
63 node *ptemp &＃61; *phead;
 64 while (ptemp->pNext !&＃61; NULL)
 65 {
 66 ptemp &＃61; ptemp->pNext;
 67 }
 68 ptemp->pNext &＃61; pnew;
 69 }
 70
71
72 }
 73
74 //显示链表
75 void showall(node *phead)
 76 {
 77 if (phead &＃61;&＃61; NULL)
 78 {
 79 return;
 80 }
 81 else
82 {
 83 printf("%5d 本节点地址:%p 下一个节点地址:%p\n", phead->data, phead, phead->pNext);
 84 showall(phead->pNext);//跳到下一个节点
85 }
 86 }
 87
88 //反转显示
89 void revshowall(node *phead)
 90 {
 91 if (phead &＃61;&＃61; NULL)
 92 {
 93 return;
 94 }
 95 else
96 {
 97 showall(phead->pNext);//跳到下一个节点
98 printf("%d ,%p,%p\n", phead->data, phead, phead->pNext);
 99 }
100 }
101
102 //头部插入
103 void addhead(node **pphead, int data)
104 {
105 node *pnew &＃61; (node *)malloc(sizeof(node));
106 pnew->data &＃61; data;
107 pnew->pNext &＃61; NULL;//赋值
108
109 if (*pphead&＃61;&＃61;NULL)
110 {
111 *pphead &＃61; pnew;
112 }
113 else
114 {
115 pnew->pNext &＃61; *pphead;
116 *pphead &＃61; pnew;
117 }
118 }
119
120 //寻找第一个指定元素的位置
121 node *searchfirst(node *phead, int finddata)
122 {
123 for (node *p &＃61; phead; p !&＃61; NULL; p &＃61; p->pNext)
124 {
125 if (p->data &＃61;&＃61; finddata)
126 {
127 return p;//返回找到的地址
128 }
129 }
130 return NULL;
131 }
132
133 //改变第一个指定元素的值
134 void changefirst(node *phead, int finddata,int newdata)
135 {
136 for (node *p &＃61; phead; p !&＃61; NULL; p &＃61; p->pNext)
137 {
138 if (p->data &＃61;&＃61; finddata)
139 {
140 p->data &＃61; newdata;
141 }
142 }
143 }
144
145 //删除第一个元素
146 void deleteFirst(node **phead, int finddata)
147 {
148 node *p1 &＃61; NULL, *p2 &＃61; NULL;//p1向前,p2保存p1的上一个位置
149 p1 &＃61; *phead;//保存头结点
150 while (p1 !&＃61; NULL)
151 {
152 if (p1->data !&＃61; finddata)
153 {
154 p2 &＃61; p1;
155 p1 &＃61; p1->pNext;
156 }
157 else
158 {
159 break;
160 }
161 }
162
163 if (p1 &＃61;&＃61; NULL)
164 {
165 return;
166 }
167 //如果是头结点
168 if (p1 &＃61;&＃61; *phead)
169 {
170 *phead &＃61; (*phead)->pNext;
171 free(p1);//头部删除
172 }
173 else
174 {
175 p2->pNext &＃61; p1->pNext;
176 free(p1);
177 }
178
179 }
180
181 //插入元素(在找到的元素之前插入)
182 void insertFirstHead(node **phead, int finddata,int newdata)
183 {
184 node *p1 &＃61; NULL, *p2 &＃61; NULL;//p1向前,p2保存p1的上一个位置
185 p1 &＃61; *phead;//保存头结点
186 while (p1 !&＃61; NULL)
187 {
188 if (p1->data !&＃61; finddata)
189 {
190 p2 &＃61; p1;
191 p1 &＃61; p1->pNext;
192 }
193 else
194 {
195 break;
196 }
197 }
198
199 if (p1 &＃61;&＃61; NULL)
200 {
201 return;
202 }
203
204
205 node *pnew &＃61; (node *)malloc(sizeof(node));//新的结点
206 pnew->data &＃61; newdata;
207 pnew->pNext &＃61; NULL;//赋值
208
209 //如果是头结点
210 if (p1 &＃61;&＃61; *phead)
211 {
212 pnew->pNext &＃61; p1;
213 *phead &＃61; pnew;
214 }
215 else
216 {
217 p2->pNext &＃61; pnew;
218 pnew->pNext &＃61; p1;
219 }
220 }
221
222 //插入元素(在找到的元素之后插入)
223 void insertFirstBack(node **phead, int finddata, int newdata)
224 {
225 node *p1 &＃61; NULL, *p2 &＃61; NULL;//p1向前,p2保存p1的上一个位置
226 p1 &＃61; *phead;//保存头结点
227 while (p1 !&＃61; NULL)
228 {
229 if (p1->data !&＃61; finddata)
230 {
231 p2 &＃61; p1;
232 p1 &＃61; p1->pNext;
233 }
234 else
235 {
236 break;
237 }
238 }
239
240 if (p1 &＃61;&＃61; NULL)
241 {
242 return;
243 }
244
245 //创建新的结点
246 node *pnew &＃61; (node *)malloc(sizeof(node));
247 pnew->data &＃61; newdata;
248 pnew->pNext &＃61; NULL;//赋值
249
250 //如果是头结点
251 if (p1 &＃61;&＃61; *phead)
252 {
253 p1->pNext &＃61; pnew;
254 }
255 else
256 {
257 pnew->pNext &＃61; p1->pNext;
258 p1->pNext &＃61; pnew;
259 }
260 }
261
262 //链表冒泡排序
263 void bubblesort(node *phead)
264 {
265 for (node *p1 &＃61; phead; p1->pNext !&＃61; NULL; p1 &＃61; p1->pNext)
266 {
267 for (node *p2 &＃61; phead; p2 ->pNext !&＃61; NULL; p2 &＃61; p2->pNext)
268 {
269
270 if (p2->data > p2->pNext->data)
271 {
272 int tmp &＃61; p2->data;
273 p2->data &＃61; p2->pNext->data;
274 p2->pNext->data &＃61; tmp;
275 }
276 }
277 }
278 }
279
280 //链表分段,返回中间点
281 node *fen(node *pbegin, node *pback)
282 {
283 int key &＃61; pbegin->data;//以第一个数据为分段
284 //核心思想:保证p,q直接的数据都大于等于key,q在p的后面
285 node *p &＃61; pbegin;//标识第一个节点
286 node *q &＃61; pbegin->pNext;//游标标识第二个节点
287
288 while (q !&＃61; pback)
289 {
290 //找到小于key的数据,然后交换
291 if (q->data < key)
292 {
293 //循环下一个节点,并进行赋值(p,q之间的值都大于key)
294 p &＃61; p->pNext;
295
296 int temp &＃61; p->data;
297 p->data &＃61; q->data;
298 q->data &＃61; temp;//交换
299 }
300 q &＃61; q->pNext;//循环游标
301 }
302 int temp &＃61; p->data;
303 p->data &＃61; pbegin->data;
304 pbegin->data &＃61; temp;//交换
305
306 return p;
307 }
308
309 //快速排序
310 void quicksort(node *pbegin,node *pback)
311 {
312 if (pbegin !&＃61; pback)
313 {
314 node *pfen &＃61; fen(pbegin, pback);//取中间点
315 quicksort(pbegin, pfen);
316 quicksort(pfen->pNext, pback);
317 }
318 }
319
320 //获取链表的长度
321 int getnum(node *phead)
322 {
323 int i &＃61; 0;
324 while (phead !&＃61; NULL)
325 {
326 i&＃43;&＃43;;
327 phead &＃61; phead->pNext;
328 }
329 return i;
330 }
331
332 //链表反转
333 void rewind(node **phead)
334 {
335
336 //备份头节点的地址 位置关系:front back tail
337 node *front &＃61; *phead;
338 //back在from的后面
339 node *back &＃61; (*phead)->pNext;
340 //反转后头结点的pNext为NULL
341 (*phead)->pNext &＃61; NULL;
342 //当后一个不为尾节点
343 while ( back !&＃61; NULL)
344 {
345 //back节点的后一个节点,用于给back节点赋值
346 node *tail &＃61; back->pNext;
347 //back节点的pNext为front
348 back->pNext &＃61; front;
349 //front移到back节点位置
350 front &＃61; back;
351 back &＃61; tail;//back移到tail节点位置
352 }
353 *phead &＃61; front;
354 }
355
356 //递归反转
357 node *digui_rew(node *phead)
358 {
359 //在结尾处返回
360 if (phead &＃61;&＃61; NULL || (phead)->pNext &＃61;&＃61; NULL)
361 {
362 return phead;
363 }
364 else
365 {
366 node *next &＃61; phead->pNext;
367 node *head &＃61; digui_rew(next);
368 next->pNext &＃61; phead;
369 phead->pNext &＃61; NULL;
370
371 //第一步递归返回
372 return head;
373 }
374 }
375
376 //判断链表是否有环(追击相遇,一个一次前进一个,一个一次前进两个,如果有环则一定能相遇)
377 int isCir(node *phead)
378 {
379 node *p1 &＃61; phead;//一次前进一个
380 node *p2 &＃61; phead;//一次前进两个
381
382 int flag &＃61; 0;//0表示没有环
383 while (p1 !&＃61; NULL && p2 !&＃61; NULL && p2->pNext !&＃61; NULL)
384 {
385 p1 &＃61; p1->pNext;
386 p2 &＃61; p2->pNext->pNext;
387 if (p1 &＃61;&＃61; p2)
388 {
389 flag &＃61; 1;
390 break;
391 }
392 }
393
394 return flag;
395 }
396
397 //有序链表合并,把link2合并到link1
398 void merge(node **head1, node **head2)
399 {
400 //备份head2的头结点地址,一直循环结束
401 node *p2 &＃61; *head2;
402 while (p2 !&＃61; NULL)
403 {
404 //如果比头节点的值要小,则把p2变成p1的头结点
405 if (p2->data <(*head1)->data)
406 {
407 node *p2tmp &＃61; p2->pNext;//备份p2后一个元素
408 //把头结点地址*head1传给p2->pNext
409 p2->pNext &＃61; *head1;
410 //p2的地址传给*head1
411 *head1 &＃61; p2;
412 //向后遍历
413 p2 &＃61; p2tmp;
414 }
415 else
416 {
417 //p1是第一个后面的节点的data大于p2->data的节点,核心思想是把P2插入到p1之后
418 node *p1;
419 node *p2tmp &＃61; p2->pNext;//备份p2后一个元素
420 for (p1 &＃61; *head1; p1->pNext !&＃61; NULL; p1 &＃61; p1->pNext)
421 {
422 if (p1->pNext->data > p2->data)
423 {
424 break;
425 }
426 }
427 p2->pNext &＃61; p1->pNext;
428 p1->pNext &＃61; p2;
429
430 p2 &＃61; p2tmp;
431 }
432 }
433 }
434
435 //链表取中间值
436 node *findmid(node *phead)
437 {
438 if (isCir(phead))
439 {
440 return NULL;
441 }
442
443 node *p1 &＃61; phead;
444 node *p2 &＃61; phead;
445 while (p1 !&＃61; NULL && p2 !&＃61; NULL && p2->pNext !&＃61; NULL)
446 {
447 p1 &＃61; p1->pNext;
448 p2 &＃61; p2->pNext->pNext;
449 }
450 return p1;
451 }
452
453 void main()
454 {
455 node *phead &＃61; NULL;//头结点不存放数据
456 node *phead2 &＃61; NULL;
457 //尾部插入
458 for (int i &＃61; 1; i <10; i&＃43;&＃43;)
459 {
460 addback(&phead, i);
461 }
462
463 addback(&phead2, -3);
464 addback(&phead2, 16);
465 addback(&phead2, 8);
466
467 merge(&phead, &phead2);
468 printf("合并后的链表:\n");
469 showall(phead);
470
471 //获取中间节点
472 node *mid &＃61; findmid(phead);
473 printf("\n\n中间节点的值:%d\n\n", mid->data);
474 ////头部插入
475 //addhead(&phead, 20);
476 //addhead(&phead, 21);
477 //
478 ////查找第一个并修改
479 //node *pfind &＃61; searchfirst(phead, 4);
480 //pfind->data &＃61; 22;
481
482 ////删除结点
483 //deleteFirst(&phead, 21);
484
485 ////插入结点
486 //insertFirstHead(&phead, 0, 100);
487 //showall(phead);
488 //printf("链表长度:%d", getnum(phead));
489 //printf("\n\n");
490 ////冒泡排序
491 ////bubblesort(phead);
492 ////快速排序
493 //quicksort(phead, NULL);
494 //printf("快速排序后:\n");
495 //showall(phead);
496 //printf("\n\n");
497 ////链表反转
498 ////rewind(&phead);
499 //phead &＃61; digui_rew(phead);
500 //printf("递归链表反转后:\n");
501 //showall(phead);
502
503 ////phead->pNext->pNext &＃61; phead;
504 ////判断是否有环
505 //printf("\n\n链表是否有环:%d\n", isCir(phead));
506 system("pause");
507 }

 

转:https://www.cnblogs.com/xiaochi/p/8393853.html



推荐阅读
author-avatar
Triste夏木_668_365
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有