带头结点的单链表的创建

1、带头结点的单链表的创建、求表长、输出、插入、删除、查找、逆置说明在VC6.0中不能把本代码保存为.c进行编译，应保存为.cpp，原因可能是里边注释是C+的风格,在codeblocks中不存在这个问题#include#include#defineDataTypeint#defineFLAG-1typedefstructNodeDataTypedata;structNode*next;Lnode,*LinkList;LinkListCreat_LinkList()LinkListL;Lnode*s,*r;intx;printf(”建立有表头结点的单链表，以d作为创建链表完成的标志n,FLAG);L

2、=r=s=NULL;L=(Lnode*)malloc(sizeof(Lnode);if(!L)printf(”表头结点开辟失败n);exit(-1);L-next=NULL;scanf(%d,&x);while(x!=FLAG)s=(Lnode*)malloc(sizeof(Lnode);if(!s)printf(”结点开辟失败n);exit(-1);s-data=x;if(NULL=L-next)第一个结点的处理L-next=s;elser-next=s;r=s;scanf(%d,&x);if(r!=NULL)对于非空表，最后结点的指针域放空指针r-next=NULL;returnL;/*有

3、头结点的链表，求表长算法*/intLength_LinkList(LinkListL)Lnode*p;intj;p=L;j=0;while(p-next)p=p-next;j+;returnj;intPrint_LinkList(LinkListL)printf(输出：n);Lnode*s;s=L;while(s-next!=NULL)s=s-next;printf(%3d,s-data);printf(n);return0;/*逆置算法思路：依次取原链表中每个结点，将其作为第一个结点插入到新的链表中去。指针p用来指向原表中当前结点，p为空时结束。*/voidReverse_LinkList(

4、LinkListH)单链表的逆置Lnode*p,*q;p=H-next;/p指向第一个结点H-next=NULL;将原链表置为空表while(p)q=p;p=p-next;q-next=H-next;将当前节点插入到头结点后面H-next=q;return;/*按序号查找*/Lnode*Get_LinkList(LinkListL,inti)Lnode*p;intj=0;p=L;while(p-next!=NULL&jnext;j+;if(j=i)returnp;elsereturnNULL;/*按值查找*/Lnode*Locate_LinkList(LinkListL,DataTypex)L

5、node*p;p=L-next;while(p!=NULL&p-data!=x)p=p-next;returnp;/*插入操作，分为：前插接点、后插结点下面的算法实现在链表的第i个位置上插入一个数值后插结点：设p指向单链表中某结点，s指向待插入值为x的新结点，将*s插入到*p之后，操作：s-next=p-next;p-next=s;前插接点：遇红茶结点不同德是，这种算法要先找到前驱结点*口，然后完成在*q后插入*s,操作：q=L;while(q-next!=p)q=p-next;s-next=q-next;q-next=s;*/intInsert_LinkList(LinkListL,inti

6、,DataTypex)Lnode*p,*s;p=Get_LinkList(L,i-1);if(NULL=p)printf(”前驱结点不存在，不能插入n);return0;elses=(Lnode*)malloc(sizeof(Lnode);s-data=x;s-next=p-next;p-next=s;return1;/*按序号删除结点*/intDel_LinkList(LinkListL,inti)Lnode*p,*s;p=Get_LinkList(L,i-1);if(NULL=p)printf(”你要删除的结点前驱结点不存在n);return-1;elseif(NULL=p-next)pr

7、intf(”第4个结点不存在n,i);return0;elses=p-next;p-next=s-next;free(s);return1;/*按值删除结点,为了使算法清晰，只删除找到的第一个结点*/intRemove_LinkList(LinkListL,DataTypex)Lnode*p,*s;p=Locate_LinkList(L,x);找到要删除的结点if(NULL=p)printf(你要删除的结点不存在n);return-1;s=L;while(s-next!=p)s=s-next;找到要删除结点的前驱s-next=p-next;free(p);return1;intmain()Ln

8、ode*L,*p;intn,m,k;L=Creat_LinkList();Print_LinkList(L);printf(表长(头结点不计算在内)：dn,Length_LinkList(L);printf(按序号查找，请输入你要查找的结点的序号:n);scanf(%d,&n);p=Get_LinkList(L,n);if(NULL=p)printf(”未找到n);elseprintf(”找到了，该结点存放的数据：dn,p-data);printf(”按值查找，请输入你要查找的数据:n);scanf(%d,&n);p=Locate_LinkList(L,n);if(NULL=p)printf(

9、”未找到n);elseprintf(”找到了n);printf(插入结点，请输入你要插入的位置和数值n);scanf(%d%d,&k,&n);m=Insert_LinkList(L,k,n);if(0=m)printf(”前驱结点不存在不能插入n);elseif(1=m)printf(”插入成功n);Print_LinkList(L);printf(”表长(头结点不计算在内)：dn,Length_LinkList(L);printf(按序号删除，请输入你要删除的结点的序号:n);scanf(%d,&n);m=Del_LinkList(L,n);if(-1=m)printf(”你要删除的结点无前驱结点n);elseif(0=m)printf(”你要删除的结点不存在n);elseif(1=m)printf(”删除成功n);Print_LinkList(L);printf(表长(头结点不计算在内)：dn,Length_LinkList(L);printf(按值删除，请输入你要删除的数据:n);scanf(%d,&n);m=Remove_LinkList(L,n);if(-1=m)printf(”你要删除的结点无前驱结点n);elseif(0=m)printf(你要删除的结