单链表和循环链表.ppt

线性链表•链表是指用一组任意的存储单元依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置。•链表中结点的逻辑次序和物理次序不一定相同。•为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。1•链表中的结点结构其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。•链表通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。•上述链表的每一个结点只有一个链域，故将这种链表称为单链表（SingleLinked)。•单链表中每个结点的存储地址是存放在其前趋结点的next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即为NULL.2datanext•例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)3•通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。•单链表可由头指针惟一确定4•C语言类型描述typedefstructnode{datatypedata;/*数据元素类型*/structnode*next;/*指针类型*/}node,*lklist;/*结点类型*/•node是结点类型•lklist是指向node类型的指针•lklistp,声明一个指向node类型的指针•*p由两个域组成的记录，用(*p).data和(*p).next表示，通常记成p-data和p-next,分别用来存放数据元素的值和后继结点的地址5•有时，我们在单链表的第一个结点之前附设一个结点，称为头结点•头结点的数据域可以不储存任何信息，也可存储如线性表的长度等附加信息•头结点的指针域存储指向第一个结点的指针。非空表空表6单链表上的一些基本操作1.初始化initiate_lklist(l)定义建立如右图所示的一个空表算法voidinitiate_lklist(lklist&l){l=newnode;l-next=NULL;}7L头结点、尾结点NULL2.求表长length_lklist(l)定义求单链表中结点数目基本思想从头到尾数一遍算法intlength_lklist(lklistl){lklistp=l;/*工作指针p从头结点开始*/intj=0;/*计数器从0开始，因为有头结点*/while(p-next!=NULL)/*p所指结点不是尾结点*/{p=p-next;/*p指向下一个结点，即往下数*/j++;/*计数器加1*/}return(j);}83.按序号查找find_lklist(l,i)定义查找单链表第i个元素，否则返回NULL基本思想从头指针出发，顺链域next逐个往下搜索，直到找到第i个结点为止9•算法node*find_lklist(lklistl,inti){lklistp=l;intj=0;/*初始化*/while((p-next!=NULL)&&(ji))/*p所指不是尾结点且还没找到*/{p=p-next;/*找下一个*/j++;/*记数器加1*/}if(j==i)return(p);/*找到第i个,返回其指针*/elsereturn(NULL);}104.定位locate_lklist(l,x)定义按值查找，返回线性表l中第一个值与x相等的结点序号，否则为0基本思想从头指针出发，顺链域next逐个往下搜索，直到找到值为x的结点为止11算法intlocate_lklist(lklistl,datatypex){lklistp=l;intj=0;/*初始化*/while((p-next!=NULL)&&(p-data!=x))/*p所指不是尾结点且还没找到*/{p=p-next;/*找下一个*/j++;}/*记数器加1*/if(p-data==x)return(j);/*找到x,并返回j*/elsereturn(0);/*没找到,返回0*/}125.读表元get_lklist(l,i)定义求链表l第i个结点的值，若找不到返回NULL基本思想类似按序号查找13算法datatypeget_lklist(lklistl,inti){lklistp=l;intj=0;/*初始化*/while((p-next!=NULL)&&(ji))/*p所指不是尾结点且还没找到*/{p=p-next;/*找下一个*/j++;/*记数器加1*/}if(j==i)return(p-data);/*找到第i个*/else{printf(参数i错或单链表不存在);return(NULL);}}146.插入insert_lklist(l,x,i)定义在线性表l的第i个结点前插入一个数值为e的结点，使之成为第i个结点基本思想找到插入位置生成一个数值为e的新结点修改某些结点的链域15La1…anNULLai…eai-1La1…anNULLai…ai-1s×e•算法voidinsert_lklist(lklist&l,datatypex,inti){lklistp,s;p=find_lklist(l,i-1);/*p指向第i-1个结点*/if(p!=NULL)/*第i-1个结点存在*/{s=newnode;/*生成一个新结点s*/s-data=x;/*新结点的数值是x*/s-next=p-next;/*新结点的后继是原来的第i个结点*/p-next=s;}/*第i-1个结点的后继是新结点*/elseprintf(不存在第i个位置);}167.删除delete_lklist(l,i)定义删除线性表的第i个结点基本思想找到第i个结点从单链表上摘除该结点(修改某些结点的指针域)17La1…anNULLai+1…aiai-1La1…anNULLai+1…ai-1ו算法voiddelete_lklist(lklist&l,inti){lklistp,q;p=find_lklist(l,i-1);/*p指向第i-1个结点*/if((p!=NULL)&&(p-next!=NULL))/*第i-1个结点存在，第i个结点存在*/{q=p-next;/*q指向第i个结点*/p-next=q-next;/*使p的后继结点为第i+1个结点*/deleteq;}/*释放第i个结点*/elseprintf(不存在第i个结点);}18•插入•删除•求表长•初始化O(1)•按序号查找•定位（按值查找）•读表元19O(n)O(n)•单链表的其它操作1.建表create_lklist1定义将一个线性表中的数据元素依次输入并建立该线性表的单链表基本思想初始化表l依次输入各数据元素，并插入到表l中20•算法voidcreate_lklist1(lklist&l){initiate_lklist(l);inti=1;/*插入位置初始化*/intx;scanf(%d,&x);while(x!=0)/*遇0停止建表*/{insert_lklist(l,x,i);i++;scanf(%d,&x);}}21•分析特点利用基本运算时间复杂性查找0+1+2+…+（n-1）=n(n-1)/2O(n2)结论效率不高原因每次插入都从头开始查找到表尾改进用一个工作指针始终指向表尾（称为尾指针），用它指示链入位置22voidcreate_lklist2(lklist&l){lklistq,p;datatypex;l=newnode;p=l;/*尾指针的初值*/scanf(%d,&x);/*输入第一个结点的值*/while(x!=0){q=newnode;/*创建新结点*/q-data=x;p-next=q;/*新结点链入表尾*/p=q;/*工作指针指向尾结点*/scanf(%d,&x);}/*输入下一个结点的值*/p-next=NULL;/*尾指针标志*/}23•分析方法二算法较前者复杂时间效率比前者高，O(n)•结论要求时间效率，用方法二无时间要求，用方法一，简单24循环链表•定义与单链表区别在于其尾结点的链域不是NULL，而是一个指向头结点的指针•特点从表中任一结点出发都能通过后移操作而扫描整个链表•示意图25•循环链表类型说明#definedatatypeinttypedefstructnode{datatypedata;/*数据元素类型*/structnode*next;/*指针类型*/}node,*clklist;/*结点类型*/•node是结点类型•cklist是指向node类型的指针26•基本运算在循环表上的实现类似于在单链表上的实现区别：判断表尾条件不同p-next!=NULL改成p-next!=H,其中H为头指针271.初始化initiate_clklist(l)•算法voidinitiate_clklist(clklist&l){l=newnode;l-next=l;}282.求表长length_clklist(l)•算法intlength_clklist(clklistl){clklistp=l;/*工作指针p从头结点开始*/intj=0;/*计数器清0*/while(p-next!=l)/*p所指结点不是尾结点*/{p=p-next;/*p指向下一个结点，即往下数*/j++;/*计数器加1*/}return(j);}293.按序号查找find_clklist(l,i)•算法node*find_clklist(clklistl,inti){clklistp=l;intj=0;/*初始化*/while((p-next!=l)&&(ji))/*p所指不是尾结点且还没找到*/{p=p-next;/*找下一个*/j++;}/*记数器加1*/if(j==i)return(p);/*找到第i个*/elsereturn(NULL);}304.定位locate_clklist(l,x)•算法intlocate_clklist(clklistl,datatypex){clklistp=l;intj=0;/*初始化*/while((p-next!=l)&&(p-data!=x))/*p所指不是尾结点且还没找到*/{p=p-next;/*找下一个*/j++;}/*记数器加1*/if(p-data==x)return(j);/*找到x*/elsereturn(0);}315.读表元get_clklist(l,i)•算法datatypeget_clklist(clklistl,inti){clklistp=l;intj=0;/*初始化*/while((p-next!=l)&&(ji))/*p所指不是尾结点且还没找到*/{p=p-next;/*找下一个*/j++;/*记数器加1*/}if(j==i)return(p-data);/*找到第i个*/else{printf(参数i错或单链表不存在);return(NULL);}}326、删除delete_clklist(l,i)•算法voiddelete_clklist(clklist&l,inti){clklistp,q;p=find_clklist(l,i-1);/*p指向第i-1个结点*/if((p!=NULL)&&(p-next!=l))/*第i个结点存在*/{q=p-next;/*q指向第i个结点*/p-next=q-next;/*使p的后继结点为第i+1个结点*/deleteq;}/*释放第i个结点*/elseprintf(不存在第i个结点);}337、插入insert_clklist(l,x,i)•算法voidinsert_clklist(clklist&l,datatypex,inti){clklistp,s;p=find_