首页 > 代码库 > 基本算法——链表的一些基本操作
基本算法——链表的一些基本操作
在简单的算法中，链表是我们经常用到的，同时，链表有时候也是让我们很头痛的一种基本操作。
下面代码中，包含了链表的一些基本操作:
1.链表的建立:(1)头插法 (2)尾插法 (3)有序建立
2.链表的插入
3.链表的删除
4.链表逆置
5.在链表中查找倒数元素
6.在链表中查找中间元素
7.判断链表是否有环
8.有序合并两个链表
声明如下:
1 #ifndef _HEAD_H 2 #define _HEAD_H 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <time.h> 6 typedef struct LINK 7 { 8 int num; 9 struct LINK *next;10 }NODE,*pNODE;11 void link_travers(pNODE head,void (*pFUN)(pNODE p));//用函数（*pFUN）遍历链表12 void link_head(pNODE *head,int size); //头插法建立链表13 void link_last(pNODE *head,int size); //尾插法建立链表14 void link_sortCreat(pNODE *head,int size);//有序建立链表15 void link_expand(pNODE *head,int num); //在链表中插入一个值16 void link_del(pNODE *head,int num); //删除链表中值为num的节点17 void link_reverse(pNODE *head); //链表逆置18 void link_search(pNODE head,int num); //找到链表中倒数元素19 void link_searchMID(pNODE head); //查找中间节点的值20 void link_circle(pNODE head); //判断一个链表是否有环21 void link_greme(pNODE *head1,pNODE *head2); //有序合并两个链表22 23 #endif
实现代码如下:
1 #include "head.h" 2 void link_travers(pNODE head,void (*pFUN)(pNODE p))//遍历链表 3 { 4 while(head) 5 { 6 pFUN(head); 7 head=head->next; 8 } 9 } 10 void link_head(pNODE *head,int size) //头插法 11 { 12 pNODE p; 13 *head=NULL; 14 while(size>0) 15 { 16 size--; 17 p=(pNODE)calloc(1,sizeof(NODE)); 18 p->num=rand()%1000; 19 p->next=*head; 20 *head=p; 21 } 22 } 23 24 void link_last(pNODE *head,int size) //尾插法 25 { 26 pNODE tail,p; 27 *head=tail=NULL; 28 while(size>0) 29 { 30 size--; 31 p=(pNODE)calloc(1,sizeof(NODE)); 32 p->num=rand()%1000; 33 if(*head==NULL) 34 *head=tail=p; 35 else 36 tail=tail->next=p; 37 } 38 } 39 40 void link_sortCreat(pNODE *head,int size) //有序建立 41 { 42 pNODE pC,pP,pnew; 43 while(size>0) 44 { 45 pnew=(pNODE)calloc(1,sizeof(NODE)); 46 pnew->num=rand()%1000; 47 if(*head==NULL) 48 *head=pnew; 49 else 50 { 51 pC=*head; 52 pP=NULL; 53 while(pC!=NULL) 54 { 55 if(pC ->num < pnew ->num) 56 { 57 pP=pC; 58 pC=pC->next; 59 } 60 else 61 break; 62 } 63 if(pP==NULL) 64 { 65 pnew->next=*head; 66 *head=pnew; 67 } 68 else 69 { 70 pnew->next=pC; 71 pP->next=pnew; 72 } 73 } 74 size--; 75 } 76 } 77 78 79 void link_expand(pNODE *head,int num) //增加新值 80 { 81 pNODE pnew; 82 pNODE pP,pC; 83 pnew=(pNODE)calloc(1,sizeof(NODE)); 84 pnew->num=num; 85 if(*head==NULL) 86 *head=pnew; 87 else{ 88 pC=*head; 89 pP=NULL; 90 while(pC) 91 { 92 if(pC->num < pnew->num) 93 { 94 pP=pC; 95 pC=pC->next; 96 } 97 else 98 break; 99 }100 if(pP==NULL)101 {102 pnew->next=*head;103 *head=pnew;104 }105 else106 {107 pnew->next=pC;108 pP->next=pnew;109 }110 }111 printf("插入成功!!\n");112 }113 114 115 void link_del(pNODE *head,int num) //删除值为num的节点116 {117 pNODE pC,pP,ptmp;118 if(*head==NULL)119 printf("链表为空!!删除失败!!\n");120 else121 {122 pC=*head;123 pP=NULL;124 while(pC)125 {126 if(pC->num == num)127 {128 if(pP==NULL)129 {130 ptmp=*head;131 *head=(*head)->next;132 free(ptmp);133 pC=*head;134 }135 else136 {137 ptmp=pC;138 pP->next=pC->next;139 free(ptmp);140 pC=pP->next;141 }142 printf("删除成功!!\n");143 }144 else145 {146 pP=pC;147 pC=pC->next;148 }149 }150 }151 }152 153 154 void link_reverse(pNODE *head) //链表逆置155 {156 pNODE p,pnext;157 if(*head==NULL)158 printf("链表为空!!无法逆置!!\n");159 else160 {161 p=*head;162 *head=NULL;163 while(p)164 {165 pnext=p->next;166 p->next=*head;167 *head=p;168 p=pnext;169 }170 }171 }172 173 void link_search(pNODE head,int num) //查找倒数节点的值174 {175 int i=1;176 pNODE pf,pl;177 if(head==NULL)178 printf("链表为空!!查找失败!!\n");179 else180 {181 pf=pl=head;182 while(pf)183 {184 pf=pf->next;185 if(i>num)186 pl=pl->next;187 i++;188 }189 if(i<=num)190 printf("该链表中没有这么多数据!!查找失败!!\n");191 else192 printf("倒数第%d个元素为%d\n",num,pl->num);193 }194 }195 196 void link_searchMID(pNODE head)197 {198 pNODE pf,pl;199 if(head==NULL)200 printf("该链表为空!!查找失败!!\n");201 else202 {203 pf=pl=head;204 while(pf)205 {206 pf=pf->next;207 if(pf)208 {209 pf=pf->next;210 pl=pl->next;211 }212 }213 printf("该链表的中间节点为:%d",pl->num);214 }215 }216 217 218 void link_circle(pNODE head)219 {220 pNODE pf,pl;221 if(head==NULL)222 printf("该链表为空!!无法判断!!\n");223 else224 {225 pf=pl=head;226 pf=pf->next;227 while(pf)228 {229 pf=pf->next;230 pl=pl->next;231 if(pf==pl)232 printf("该链表有环!!\n");233 }234 if(pf==NULL)235 printf("该链表中没有环!!\n");236 }237 }238 239 void link_greme(pNODE *head1,pNODE *head2)240 {241 pNODE p1,p2,pT;242 if(*head1==NULL&& *head2==NULL)243 printf("两个链表为空!!无法合并!!\n");244 else245 {246 p1=*head1;247 p2=*head2;248 *head1=pT=NULL;249 while(p1 && p2)250 {251 if(p1->num <= p2->num )252 {253 if(pT== NULL)254 *head1=pT=p1;255 else256 pT=pT->next=p1;257 p1=p1->next;258 }259 else260 {261 if(pT== NULL)262 *head1=pT=p2;263 else264 pT=pT->next=p2;265 p2=p2->next;266 }267 }268 if(p1==NULL)269 pT->next=p2;270 if(p2==NULL)271 pT->next=p1;272 }273 }
测试代码如下:
1 #include "head.h" 2 static void print(pNODE p) 3 { 4 printf("%d ",p->num); 5 } 6 int main(int argc,char *argv[]) 7 { 8 pNODE head1,head2; 9 int size,num;10 head1=head2=NULL;11 srand((unsigned)time(NULL));12 printf("请输入链表长度:");13 scanf("%d",&size);14 //link_head(&head1,size); //头插测试15 //link_last(&head1,size); //尾插测试16 link_sortCreat(&head1,size); //有序建立测试17 link_travers(head1,print);18 printf("\n");19 link_sortCreat(&head2,size);20 link_travers(head2,print);21 printf("\n");22 //printf("请输入一个值:");23 //scanf("%d",&num);24 //link_expand(&head1,num); //增加新值测试25 //link_del(&head1,num); //删除值测试26 //link_reverse(&head1); //链表逆置27 //link_search(head1,num); //查找倒数节点的数据28 //link_searchMID(head1); //查找中间节点的数据29 //link_circle(head1); //判断链表是否有环30 //link_greme(&head1,&head2); //合并两个链表31 link_travers(head1,print);32 printf("\n");33 system("pause");34 return 0;35 }
在函数中，我们用一个函数指针实现了对链表的遍历，函数指针在后面的文章中会做简要介绍。
基本算法——链表的一些基本操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。