c3-线性表(二)

1、1线性表线性表( (二二) )执行校长李 伟数据结构数据结构( (第三讲第三讲 ) )2知识回顾知识回顾n 顺序存储的优点有哪些？顺序存储的优点有哪些？n 顺序表中下标与相对地址的关系？顺序表中下标与相对地址的关系？n 在对顺序表进行插入操作中应注意什么？在对顺序表进行插入操作中应注意什么？3教学内容教学内容n 线性表的链式表示和实现线性表的链式表示和实现线性链表线性链表静态链表静态链表循环链表循环链表双向链表双向链表4重点、难点重点、难点n 重点重点 n 难点难点p双向链表的操作双向链表的操作 5线性链表线性链表n 线性表的链式表示和实现线性表的链式表示和实现线性链表线性链表6线性链表线性链

2、表n 链式存储结构链式存储结构p在内存中用一组在内存中用一组任意的任意的存储单元（连续或不连续）存储单元（连续或不连续）来存储线性表的数据元素，来存储线性表的数据元素，p用每个数据元素所带的指针来确定其后继元素的用每个数据元素所带的指针来确定其后继元素的存储位置。存储位置。p这两部分信息组成数据元素的存储映像，称作结这两部分信息组成数据元素的存储映像，称作结点点。n n个结点链接成一个链表。个结点链接成一个链表。7线性链表线性链表n 链式存储结构特点：链式存储结构特点：p逻辑上相邻的数据元素，其物理上不一定相邻；逻辑上相邻的数据元素，其物理上不一定相邻；物理顺序与逻辑顺序不同。物理顺序与逻辑顺

3、序不同。p指针域中的信息指示的是逻辑上的前驱和后继数指针域中的信息指示的是逻辑上的前驱和后继数据元素。据元素。8线性链表线性链表n 结点：结点：数据域数据域+ +指针域指针域( (链域链域) ) pdata域是数据域，用来存放结点的值。pnext是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。p链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。 n 线性链表（单链表）：线性链表（单链表）：链表的每个结点只包含一个指针域。datanext9线性链表线性链表n 例：线性表（例：线性表（a1,a2,ana1,a2,an）的链表示）的链表示 H 头结点头指针指示链表中

4、第一个结点的存储位置，整个链表的存取必须从头指针开始进行。头结点的指针域可以不存储任何信息，也可存储线性表的附加信息，头结点的指针域存储指向第一个结点的指针。 a1 a2 an 由于最后一个数据元素没有直接后继，则线性表中最后一个结点的指针为“空”（ ）。10线性链表线性链表n 例例1： （ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）线）线性链表存储结构：性链表存储结构：存储地址数据域指针域1LI47QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU2531头指针H11线性链表线性链表n用用C语言描述的单链表如下：语

5、言描述的单链表如下：typedef struct LNode ElemType data; Struct LNode *next; LNode, *LinkList;LinkList L; /L是LinkList类型的变量，表示单链表的头指针12线性链表线性链表n 算法算法2.8status GetElem_L(Linklist L,int I, ElemType &e) /L为带头结点的单链表的头指针 /当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p=L-next; j=1; while(p&jnext; +j; if(!p | ji) return ERR

6、OR; e=p-next; return OK; /GetElem_L 对单链表中的结点只能顺序存取，即访问前一个结点后才能接对单链表中的结点只能顺序存取，即访问前一个结点后才能接着访问后一个结点。所以要访问单链表中第着访问后一个结点。所以要访问单链表中第i个元素值，必须从个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第头指针开始遍历链表，依次访问每个结点，直到访问到第i个结个结点为止。同顺序表一样，也需注意存取的位置是否有效。点为止。同顺序表一样，也需注意存取的位置是否有效。13线性链表线性链表n 链表的插入算法的实现链表的插入算法的实现p单链表结点的插入是利用修改结点指针

7、域的值，单链表结点的插入是利用修改结点指针域的值，使其指向新的链接位置来完成的插入操作，而无使其指向新的链接位置来完成的插入操作，而无需移动任何元素。需移动任何元素。p假定在链表中值为假定在链表中值为ai的结点之前插入一个新结点，的结点之前插入一个新结点，要完成这种插入必须首先找到所插位置的前一个要完成这种插入必须首先找到所插位置的前一个结点，再进行插入。假设指针结点，再进行插入。假设指针q指向待插位置的前指向待插位置的前驱结点，指针驱结点，指针s指向新结点，则完成该操作的过程指向新结点，则完成该操作的过程如图所示。如图所示。 14线性链表线性链表 heada1a2.ai-1p.aian(a)

8、找到插入位置qxsheada1a2.ai-1p.aians-next=q-nextq-next=s(c)修改指针域，将新结点s插入关键语句：q上述指针进行相互赋值的语句顺序不能颠倒。上述指针进行相互赋值的语句顺序不能颠倒。s=(LNode *)malloc(sizeof(LNode)；s-data=x；(b)申请新结点s，数据域置xxs15线性链表线性链表n 算法算法2.9void Inselem(LinkList L,int i,int x) LNode *p,*q,*s; int pos=1; p=L; if(iGetlen(L)+1) exit(1); s=(LNode *)malloc

9、(sizeof(LNode); s-data=x; while(posnext; pos+; s-next=q-next; q-next=s; 16线性链表线性链表n 链表的删除运算的实现链表的删除运算的实现p要删除链表中第要删除链表中第i个结点，首先在单链表中找到删个结点，首先在单链表中找到删除位置前一个结点，并用指针除位置前一个结点，并用指针q指向它，指针指向它，指针p指指向要删除的结点。向要删除的结点。p将将*q的指针域修改为待删除结点的指针域修改为待删除结点*p的后继结点的的后继结点的地址。地址。p删除后的结点需动态的释放。删除后的结点需动态的释放。17线性链表线性链表 pheada1

10、a2.ai-1q.aian(a)找到删除位置pheada1.(c)修改指针域，将结点p删除qai-1pai.anai+1关键语句：q-next=p-next；free(p)x=p-data；(b)返回被删除结点数据xai假定删除的结点是值为假定删除的结点是值为aiai的结点。图的结点。图( (c)c)中虚线表中虚线表示删除结点示删除结点* *p p后的指针指向。后的指针指向。18线性链表线性链表n 算法算法2.10void Delelem(LinkList L,int i) int pos=1; LNode *q=L,*p; if(iGetlen(L) exit(1); while(posne

11、xt; pos+; p=q-next; q-next=p-next; free(p);19线性链表线性链表n 算法分析算法分析p在插入和删除算法中，都是先查询确定操作位置，在插入和删除算法中，都是先查询确定操作位置，然后再进行插入和删除操作。然后再进行插入和删除操作。p所以其时间复杂度均为所以其时间复杂度均为O(n)。p另外在算法中实行插入和删除操作时没有移动元另外在算法中实行插入和删除操作时没有移动元素的位置，只是修改了指针的指向，所以采用链素的位置，只是修改了指针的指向，所以采用链表存储方式要比顺序存储方式的效率高。表存储方式要比顺序存储方式的效率高。20线性链表线性链表n 算法算法2.1

12、1void CreateList_L(LinkLinst &L, int n) L=(LinkList)malloc(sizeof(LNODE); L-next=NULL; for(i=n;i0;-i) p =(LinkList)malloc(sizeof(LNODE); scanf(&p-data); p-next=L-next; L-next=p; /createList_L21线性链表线性链表n 算法算法2.12void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) pa=La-next

13、; pb=Lb-next; Lc=pc=La; while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa ? pa : pb; free(Lb); /MergeList_L22静态链表静态链表n 线性表的链式表示和实现线性表的链式表示和实现静态链表静态链表23静态链表静态链表n 静态链表：静态链表：p用数组描述的链表起名叫静态链表。p这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。24循环链表循环链表n 线性表的

14、链式表示和实现线性表的链式表示和实现循环链表循环链表25循环链表循环链表n 循环链表：循环链表：p仍为单链表，只是修改最后一个结点的指针域的仍为单链表，只是修改最后一个结点的指针域的值由值由NULL变为指向头结点，形成一个环。变为指向头结点，形成一个环。n 特点：特点：p循环链表中，从任一结点出发都可访问到表中所循环链表中，从任一结点出发都可访问到表中所有结点。有结点。循环条件：循环条件：p-next != Hp-next != H26双向链表双向链表n 线性表的链式表示和实现线性表的链式表示和实现双向链表双向链表27双向链表双向链表n 双向链表：双向链表：p顾名思义，在双向链表的结点中有两个

15、指针域，一个指向直接后继，另一个指向直接前趋。p将头结点和尾结点链接起来也能构成循环链表，称之为双向循环链表。nC语言描述如下：语言描述如下： typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList;28双向链表双向链表n 结点结构：结点结构：n 双向循环链表：双向循环链表：datanextprior29双向链表双向链表n 对于带头结点的空双向循环链表对于带头结点的空双向循环链表n 双向循环链表结构的对称性可用下式描述：双向循环链表结构的对称性

16、可用下式描述：p即结点即结点*p的存储位置既存放在其前趋结点的存储位置既存放在其前趋结点 *(pprior)的直接后继指针域中p也存放在它的后继结点也存放在它的后继结点 *(pnext)的直接前趋指针域中。的直接前趋指针域中。L-next=L-piror=L(p-prior)-next=p=(p-next)-prior30双向链表双向链表n 对于不需要改变表结构的操作类似于单链表，仅对于不需要改变表结构的操作类似于单链表，仅需要对一个方向上的指针作操作，算法描述也相需要对一个方向上的指针作操作，算法描述也相同。同。n对于插入、删除操作呢？对于插入、删除操作呢？ 需要两个方向上的指针修改！需要两

17、个方向上的指针修改！31双向链表双向链表n 插入操作插入操作n 实现步骤实现步骤p先修改指针先修改指针p所指结点的前驱结点的指针信息，再所指结点的前驱结点的指针信息，再修改修改p所指结点的指针信息；所指结点的指针信息；p按照两个方向上的单链表修改。按照两个方向上的单链表修改。espba32双向链表双向链表n 算法算法2.18Status ListInsert_DuL(DuLinkList &L,int I,Elemtype e) if(!(p=GetElemP_Dul(L,i) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DuLNode

18、) return ERROR; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK; 33双向链表双向链表n 删除操作删除操作p只需修改指针只需修改指针p所指结点的前驱结点和后继结点的所指结点的前驱结点和后继结点的指针信息释放指针指针信息释放指针p所指结点所指结点Pabc34双向链表双向链表n 算法算法2.19Status ListDelete_DuL(DuLinkList &L,int i，Elemtype e) if(!(p=GetElemP_Dul(L,i) return ERROR; e=p-data; ppriornext=pnext; pnextprior=pprior; free(