【精品】链表总结.doc

【精品】链表总结 1、查找对单链表进行查找的思路为对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回NULL。 2、插入（后插）假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可。 (p-link=s;s-link=q)，这样就完成了插入操作。 3、删除假如我们已经知道了要删除的结点p的位置，那么要删除p结点时只要令p结点的前驱结点的链域由存储p结点的地址该为存储p的后继结点的地址，并回收p结点即可。 四、循环链表循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。 循环链表的运算与单链表的运算基本一致。 所不同的有以下几点 1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。 此种情况还使用于在最后一个结点后插入一个新的结点。 2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。 而非象单链表那样判断链域值是否为NULL。 #include/*这个头文件在动态的建立结点时要用到*/*这就是表示单链表的一个结点的结构体了，*简单起见没有使用模板之类的复杂东西。 */struct Node/*这个表示结点的值，这里为了简单，就用int型的吧*/int data;/*这是指向结点结构体的一个指针，*这里用它指向该结点的下一个结点，*以此使单个的结点形成链表*/struct Node*next;/*至此链表的结点就定义完了*/int main()/*下面展示如何建立成为一个带头结点的单链表L=12，13，21，24*/struct Node*head=NULL;/*这是链表的头结点*/struct Node*p=NULL,*q=NULL;/*临时指针，建立链表时会用到*/*链表很短，我不用循环，直接建立，可以让你看的更清楚*/*建立头结点*/head=(struct Node*)malloc(sizeof(struct Node);/*指定结点的值*/head-data=12;/*指定下一个结点，现在还没有先给NULL*/head-next表示地址=NULL;/*用q保存刚生成的结点*/q=head;/*第二个结点，建立的方法和第一个一样*/p=(struct Node*)malloc(sizeof(struct Node);p-data=13;p-next=NULL;/*注意，此时需要调整一下上一个结点的next指针，使各结点可以连接起来*/q-next=p;q=p;/*第三个结点*/p=(struct Node*)malloc(sizeof(struct Node);p-data=21;p-next=NULL;q-next=p;q=p;/*第四个结点，差不多应该发现可以写成个循环了吧！*/p=(struct Node*)malloc(sizeof(struct Node);p-data=24;p-next=NULL;q-next=p;q=p;/*到此链表建立完成！*/*用循环来写的话就是*int i=0;*int data=12,13,21,24;*for(i=0;idata=datai;*p-next=NULL;*if(i=0)*head=p;*else*q-next=p;*q=p;*/return0;char a100;#include/*这个头文件在动态的建立结点时要用到*/*这就是表示单链表的一个结点的结构体了，*简单起见没有使用模板之类的复杂东西。 */struct Node/*这个表示结点的值，这里为了简单，就用int型的吧*/int data;/*这是指向结点结构体的一个指针，*这里用它指向该结点的下一个结点，*以此使单个的结点形成链表*/struct Node*next;/*至此链表的结点就定义完了*/int main1()/*下面展示如何建立成为一个带头结点的单链表L=12，13，21，24*/struct Node*head=NULL;/*这是链表的头结点*/struct Node*p=NULL,*q=NULL;/*临时指针，建立链表时会用到*/*链表很短，我不用循环，直接建立，可以让你看的更清楚*/*建立头结点*/head=(struct Node*)malloc(sizeof(struct Node);/*指定结点的值*/head-data=12;/*指定下一个结点，现在还没有先给NULL*/head-next表示地址=NULL;/*用q保存刚生成的结点*/q=head;/*第二个结点，建立的方法和第一个一样*/p=(struct Node*)malloc(sizeof(struct Node);p-data=13;p-next=NULL;/*注意，此时需要调整一下上一个结点的next指针，使各结点可以连接起来*/q-next=p;q=p;/*第三个结点*/p=(struct Node*)malloc(sizeof(struct Node);p-data=21;p-next=NULL;q-next=p;q=p;/*第四个结点，差不多应该发现可以写成个循环了吧！*/p=(struct Node*)malloc(sizeof(struct Node);p-data=24;p-next=NULL;q-next=p;q=p;/*到此链表建立完成！*/*用循环来写的话就是*int i=0;*int data=12,13,21,24;*for(i=0;idata=datai;*p-next=NULL;*if(i=0)*head=p;*else*q-next=p;*q=p;*/return0;/*void main()int j,i;printf(请输入单词n);scanf(%s,a);for(i=0;i50;i+)ai=ai+1;if(ai=(z+1)ai=a;if(ai=0x0a)break;for(j=0;j/对链表的创建，增，删，改，查，排序，逆序等操作#include#includetypedef struct studentchar name10;char sex;int age;int score;structstudent*next;node;node*creat(int*count);/创建链表node*insert(node*head);/增加节点node*delect(node*head);/删除节点node*find(node*head);/查找节点void update(node*head);void print(node*head);/输出函数void main()node*head=NULL,*p=NULL;int n=0,count=0;printf(链表操作n);printf(请选择你的操作n);printf(1创建链表n);printf(2增加节点n);printf(3删除节点n);printf(4改正节点n);printf(5查找节点n);printf(6链表排序n);printf(7链表逆序n);printf(8输出链表n);printf(9退出系统n);scanf(%d,&n);getchar();while (1)if(n9)printf(你的输入错误，请重新输入!n);scanf(%d,&n);elseswitch(n)case1:head=creat(&count);break;/创建链表case2:head=insert(head);break;/增加节点case3:head=delect(head);break;/删除节点printf(链表操作完成!n);node*creat(int*count)char s=0;node*head=NULL,*p,*q;while (1)printf(是否要创建(y/n);scanf(%c,&s);getchar();if(s=y&head=NULL)/链表为空时p=(node*)malloc(sizeof(node);/创建第一个节点printf(请输入学生姓名:);scanf(%s,&p-name);getchar();printf(请输入学生性别:);scanf(%c,&p-sex);getchar();printf(请输入学生年龄:);scanf(%d,&p-age);getchar();printf(请输入学生成绩:);scanf(%d,&p-score);getchar();p-next=NULL;case4:update(head);break;/改正节点case5:p=find(head);break;/查找节点/case6:sort();break;/链表排序/case7:backformation();break;/链表逆序case8:print(head);break;/输出链表信息case9:exit (0);/退出系统n=0;/清除前面的操作printf(请继续选择你的操作!n);scanf(%d,&n);getchar();return head;node*insert(node*head)int n=0;node*p=NULL,*q=NULL;head=p;q=p;*count+;else if(s=y)/链表不为空p=(node*)malloc(sizeof(node);printf(请输入学生姓名:);scanf(%s,&p-name);getchar();printf(请输入学生性别:);scanf(%c,&p-sex);getchar();printf(请输入学生年龄:);scanf(%d,&p-age);getchar();printf(请输入学生成绩:);scanf(%d,&p-score);getchar();p-next=NULL;q-next=p;q=p;*count+;else if(s=n)printf(链表创建结束!n);break;else if(s!=y&s!=n)printf(输入错误，请重新输入!n);printf(请选择插入方式:1链首插入，2链尾插入n);scanf(%d,&n);if(1=n)p=(node*)malloc(sizeof(node);printf(请输入学生姓名:);scanf(%s,&p-name);getchar();printf(请输入学生性别:);scanf(%c,&p-sex);getchar();printf(请输入学生年龄:);scanf(%d,&p-age);getchar();printf(请输入学生成绩:);scanf(%d,&p-score);p-next=head;head=p;else if(2=n)p=q=head;if(p=NULL)/插入节点时，链表为空p=(node*)malloc(sizeof(node);printf(请输入学生姓名:);scanf(%s,&p-name);getchar();printf(请输入学生性别:);scanf(%c,&p-sex);getchar();printf(请输入学生年龄:);scanf(%d,&p-age);getchar();printf(请输入学生成绩:);scanf(%d,&p-score);p-next=head;head=p;elsewhile(p!=NULL)/链表不为空，找链尾,找到后跳出return head;node*delect(node*head)node*p=NULL,*q=NULL;char name10=0;printf(请输入你要删除的学生姓名:);gets(name);p=q=head;if(p=NULL)/链表为空printf(链表为空，不能删除!n);/return head;else if(strcmp(p-name,name)=0)/检查第一个节点，第一个节点就是head=head-next;else if(strcmp(p-name,name)!=0)/第一个节点不是/p=p-next;/注意这个while中不能写成while(p!=NULL&strcmp(p-name,name)!=0)p=(node*)malloc(sizeof(node);printf(请输入学生姓名:);scanf(%s,&p-name);getchar();printf(请输入学生性别:);scanf(%c,&p-sex);getchar();printf(请输入学生年龄:);scanf(%d,&p-age);getchar();printf(请输入学生成绩:);scanf(%d,&p-score);p-next=NULL;q-next=p;q=p;p=p-next;是要找的节点，继续找后面节点,直到找出或链表找完了也没找到q=p;p=p-next;if(strcmp(p-name,name)=0)/&p!=NULL)/找到要删除的节点q-next=p-next;else/if(p=NULL)/没有找到printf(没有找到要删除的节点n);return head;node*find(node*head)node*p=NULL,*q=NULL;char name10=0;printf(请输入你要查找的学生姓名:);gets(name);p=head;if(p=NULL)printf(链表为空!n);else if(strcmp(p-name,name)=0)/检查第一个节点，第一个节点就是printf(你要查找的学生信息如下:n);printf(%-10s%-4c%-4d%-4dn,p-name,p-sex,p-age,p-score);else if(strcmp(p-name,name)!=0)/第一个节点不是/p=p-next;/注意这个while中不能写成while(p!=NULL&strcmp(p-name,name)!=0)while(p-next!=NULL&strcmp(p-name,