03.线性表的链式存储44126

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,线性表,链接存储结构与线性表的操作实现,线性表的存储结构,链式,用一组地址任意的存储单元（地址可以连续也可以不连续），依次存储线性表中的各数据元素。,。,顺序,用一组地址连续的存储单元依次存储线性表中每个数据,元素。,链接存储结构,链接存储结构中的每个存储单元称为“,结点,”，结点包含一个,数据域,和一个,指针域,；,数据域存放数据元素信息；指针域存放后继结点地址；,数据元素之间的逻辑关系通过结点中的,指针,表示；,访问链接存储结构通常由第一个结点开始，逐一访所有结点。,具有,n,个数据元素的线性表对应的,n,个结点通过链接方式链接成一个链表，即为,线性表的链式存储结构,。,内存管理方式,通过指针管理存储单元（这组存储单元的内存地址可以是连续的，也可以是不连续的）,什么是结点？,对应数据元素，是一组数据中的,个体,什么是链表？,对应一组数据，是数据元素的,总体,结点与链表有何关联？,通过链接方式,线性地,关联到一起的所有结点就是链表,线性表与链接存储结构的映射关系,用链式存储结构的结点存储线性表的数据元素,链接存储结构中结点指针域与后继结点的链接关系表示每个数据元素与其直接后继数据元素间的逻辑关系。,单链表,由于链表中每个链结点中仅包含一个指针域，故称这样的链表为线性链表或,单链表,。,单链表的结点结构：,单链表结构：,头指针，保存链表第一个结点的地址,尾结点，指针域的值为空（,NULL,）,数据域,data,指针域,next,带头结点的单链表,在链表的第一个结点之前附设一个结点，称为,头结点,。,带头结点的单链表：头结点的引入使得单链表的头指针永远不为空，从而给插入、删除等操作带来了方便。,头结点：数据域为空，指针域指向第一个结点,头指针，保存链表头结点的地址,结点的数据类型,/,DataType,数据元素的数据类型,typedef,int,DataType,;,struct,Node,/Node,为结点类型名,DataType,data;,/,data,代表数据元素,Node *next;,/,next,为指向下一结点的指针,*head;,/head,为头指针，,指向单链表的头结点,链表,顺序表,/p,、,q,为指向任意结点的指针,空表：,head-next=NULL,表尾：,p-next=NULL,指针后移：,p=p-next,结点连接：,p-next=q,前驱：若,p-next=q,，则,p,指向,q,的前驱结点,单链表的基本操作,/,初始化单链表,int,InitList,(Node*&H),/H,为指向单链表的头指针,H=new Node;,if(!H,),cout,“,初始化错误”,next=NULL;,return 1;,/,判表空,int,ListEmpty(Node,*H),/H,为指向单链表的头指针,if(H,-next),return 0;,else,/,头结点指针域为空,return 1;,/,求单链表中当前元素的个数,int,ListLength,(Node*H),/H,为指向单链表的头指针,Node*p=H-next;,int,total=0;,while(p,),total+;,/,计数器,+1,p=p-next;,/,指针后移,return total;,/,遍历单链表,void,TraverseList(Node,*H),/H,为指向单链表的头指针,Node*p=H-next;,while(p,),cout,datanext;,cout,next;,while(p,),if(p,-data=)break;,p=p-next;,/p,指向下一结点,查找指定结点,查找条件,/,返回第一个与指定值匹配的元素位置,int,Find_item(Node,*H,DataType,item),/H,为指向单链表的头指针,Node*p=H-next;,int,pos=0;,/,结点位序,while(p,),/,从单链表第一个结点开始顺序查找所有结点,pos+;,if(p,-data=item)break;,p=p-next;,if(p)return pos;,/返回位置编号,else return 0;,/,/,查找失败,/,获取单链表中指定位置上的数据元素,int,Find_pos(Node,*H,int,pos,DataType,*item),/H,为指向单链表的头指针,Node*p=H-next;,int,i=1;,/,结点位序,while(p,&i!=pos),p=p-next;i+;,if(,p,=NULL,),/,查找不成功，退出运行,cout,“,位置无效data;,return 1;,链表任意位置插入法,单链表结点的插入是利用修改结点指针域的值，使其指向新的链接位置来完成插入操作，无需移动任何元素。,假定在链表中指定结点之前插入一个新结点，要完成这种插入必须,首先找到所插位置的前一个结点,，再进行插入。假设指针,p,指向待插位置的前驱结点，指针,t,指向新结点。,Node*t,=new Node;t-data=d;,t-next=p-next;,p-next=t;,p,a,1,a,2,d,t,/向线性表指定位置插入一个新元素,int,ListInsert,(Node*H,int,pos,DataType,item),Node*p=H;,int,i=0;,while(,p,),/,查找,pos,的前驱,if(i+1=pos)break;,p=p-next;i+;,if(,p,=NULL,),/,查找不成功，退出运行,cout,“,插入位置无效data=item;,/,t-next=p-next;,/,p-next=t;,/,return 1;,查找,pos,的前驱,p,链表表尾插入法,Node*t,=new Node;t-data=d;t-next=NULL;,last-next=t;,last=t;,head,a,1,d,t,a,n,last,链表表头插入法,在单链表的头结点之后第一个数据结点之前插入一个新结点，,head,指向表头结点，,head-next,表示表头的后继结点，指针,t,指向待插入结点。,Node*t,=new Node;t-data=,a,i,;,t-next=head-next;,head-next=t;,head,a,1,a,i,t,head-next,删除指定位置的结点,首先在单链表中找到被删除位置,i,的,前一个结点,i-1,，并用指针,p,指向,i-1,，指针,t,指向被删除的结点,i,；,将指针,p,所指结点,的指针域,修改为,t,所,指结点,的后继,；,释放被删结点,t,，即,delete(t,),。,t=p-next;,p-next=t-next;,delete t;,p,a,1,a,2,t,a,3,/,从线性表中删除第一个与指定值匹配的元素,int,ListDelete,(Node*H,DataType,item),Node*p=H,*t;,int,i=0;,while(,p-next,),/,查找,pos,的前驱,if(p,-next-data=item)break;,p=p-next;,if(,p,-next=NULL,),/,查找不成功，退出运行,cout,“,删除元素不存在next;,/,t,为被,删除结点,p-next=t-next;,/,删除,t,的链接关系,delete t;,/,释放被删结点,return 1;,/,撤销单链表,void,DestroyList,(Node*&H),/H,为指向单链表的头指针,Node*p;,while(H,),p=H;,H=H-next;,delete p;,其它类型的链表,循环链表,双向链表,双向循环链表,非双向循环链表,循环链表,特点：,链表中最后一个结点的指针域不为空，而是,指向头结点，从而使整个链表形成一个环。,与单链表不同之处：,检测链表是否为空的方法不同。,单链表：,head-next=NULL,单循环链表：,head-next=head,判断是否遍历到链表尾的条件不同。,单链表：,p-next=NULL,单循环链表：,p-next=head,建立空链表的操作不同。,单链表：,head-next=NULL,单循环链表：,head-next=head,带空头结点的单循环链表,空表,head,非空表,head,tail,带尾指针的单循环链表,head,双向链表,特点,:,每个结点中既有指向后继的指针域，又有指向,前驱的指针域。,结点结构：,typedef,struct,DNode,DataType,data;,struct,DNode,*prior,;,struct,DNode,*next,;,;,对称性：,p-prior-next=p=p-next-prior,注意：,操作双向链表时需要同时考虑每个结点两个,方向上的指针域。,带空头结点的双向链表,非空表,head,空表,head,带空头结点的双向循环链表,空表,head,非空表,head,顺序表与链表的比较,顺序存储结构优点,比较简单。,可以实现随机存取，存取速度快。,每个结点只存储元素自身信息，不需额外空间。,顺序存储结构缺点,需要占用一片连续的存储空间，并且需要事先估计存储空间的大小。,插入和删除操作时，需要移动大量的元素，效率较低。,链式存储结构优点,不需占用连续存储空间，使用链表前不用事先估计存储空间大小。,插入和删除操作时，不需要移动大量元素。,链式存储结构缺点,操作算法较复杂。,不能随机存取。,需要额外空间来表示元素间的关系，空间代价较高。,结论,顺序存储结构比较适合于线性表的长度不经常发生变化，不经常进行插入和删除操作，经常进行存取和查询操作。,链式存储结构比较适合于线性表的长度不可预知，需要频繁进行插入和删除操作。,