数据结构3学习.pptx
静态链表的特点：静态链表的存储结构仍需要预先分配一个较大的空间。这点类似于顺序表。静态链表的插入删除操作时不需要移动元素，只需修改指针，类似于单链表。仍具有链式存储结构的主要优点。datacursor01234maxsize-12410a2a1a3datacursor01234maxsize-12310a2a1a3如操作：在结点a3之前插入元素结点a4，变化为右图a44第1页/共24页静态链表的C语言描述/线性表的静态链表存储结构#define MAXSIZE 100 /链表的最大长度typedef struct ElemType data;int cur;component,SLinkList MAXSIZE;SLinkList S;/S0.cur指示第一个结点在数组中的位置借用一维数组来描述借用一维数组来描述第2页/共24页 1.双向链表双向链表五、其它形式的链表五、其它形式的链表 单链表中只有一个指针域，指向直接后继结点。因此，从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前驱，则需要从表头指针出发寻查。为了克服单链表的单向性缺点，可利用双向链表双向链表。双向链表的结点中有两个指针域，其一指向直接后继，其一指向直接后继，另一指向直接前驱。另一指向直接前驱。priorelemnext结点结构第3页/共24页双向链表的C C语言表示typedef struct DuLNode ElemType data;/数据域 struct DuLNode *prior;/指向前驱的指针域 struct DuLNode *next;/指向后继的指针域 DuLNode,*DuLinkList;第4页/共24页 最后一个结点的指针域的指针指向头结点。从表中任一结点出发均可找到表中其他结点。a1 a2 .an 2.循环链表循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。第5页/共24页双向循环链表双向循环链表空表空表非空表非空表 a1 a2 .anLL（只有一个头结点）第6页/共24页双向链表的操作特点：“查询查询”和单链表相同。和单链表相同。“插入插入”和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。第7页/共24页ai-1aies-next=p-next;p-next=s;s-next-prior=s;s-prior=p;psai-1ai插入第8页/共24页ai-1删除aiai+1p-next=p-next-next;p-next-prior=p;pai-1第9页/共24页本章小结本章小结1.1.了了解解线线性性表表的的逻逻辑辑结结构构特特性性是是数数据据元元素素之之间间存存在在着着线线性性关关系系，在在计计算算机机中中表表示示这这种种关关系系的的两两类类不不同同的的存存储储结结构构是是顺顺序序存存储储结结构构和和链链式式存存储储结结构构。用用前前者者表表示示的的线线性性表表简简称称为为顺顺序序表表，用后者表示的线性表简称为链表。用后者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描述方法，以及熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。线性表的各种基本操作的实现。3.3.能够从时间和空间复杂度的角度综合比较线性能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。表两种存储结构的不同特点及其适用场合。第10页/共24页1.以下说法正确的是（）A.顺序存储方式的优点是存储密度大且插入、删除运算效率高。B.链表的每个结点中都恰好包含一个指针。C.线性表的顺序存储结构优于链式存储结构。D.顺序存储结构属于静态结构而链式结构属于动态结构。课堂练习答案：D第11页/共24页2.说法错误的是（）A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低。B.顺序存储的线性表可以随机存取。C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。D.线性表的链式存储结构优于顺序存储结构。答案：D第12页/共24页3.在双向链表存储结构中，删除p所指的结点时须修改指针（）。p-next-prior=p-prior;p-prior-next=p-next;第13页/共24页4.以下说法错误的是（）A.对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表。B.对单链表来说，只有从头结点开始才能扫描表中全部结点。C.双链表的特点是找结点的前趋和后继都很容易。D.对双链表来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针中。答案：答案：A A第14页/共24页5.从表中任一结点出发都能扫描整个表的是（），便于插入删除的是（）A.单链表B.顺序表C.双向链表D.循环链表答案：C,D A,C,D第15页/共24页写出带头结点的双向循环链表L为空表的条件：答案：(L=L-next)&(L=L-prior)空表空表L第16页/共24页判断题1.在具有头结点的链式存储结构中，头指针指向链表中的数据结点。（）2.顺序存储的线性表可以随机存取。（）3.在单链表中，要访问某个结点，只要知道该结点的指针即可，因此，单链表是一种随机存取结构。（）4.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（）1.F 2.T 3.F 4.T第17页/共24页问答题线性表有两种存储结构，一是顺序表，二是链表，试问：1.如果有n个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？答：由于链式结构可以用任意的存储空间来存储各数据元素，且存储空间可以是连续的，也可以不连续。此外，这种结构对于元素进行插入和删除操作时都无需移动元素，仅修改指针即可。很适用于线性表容量变化的情况。第18页/共24页2.若线性表的总是基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应采用哪种存取结构？为什么?答：由于顺序存储结构一旦确定了起始位置，线性表中的任何一个元素都可以进行随机存取，即存取速度较高；并且，由于线性表的总数基本稳定，且很少进行插入和删除，故这一特点恰好避开了顺序存储结构的缺点。因此，应选用顺序存储结构。第19页/共24页3.在单链表和双向链表中，能否从当前结点出发访问到任一结点？答：在单链表中只能由当前结点访问其后继的任一结点，但因其没有指向前驱的指针而无法访问其前驱结点。在双向链表中，由于当前结点既有指向后继的指针，又有指向前驱的指针，所以在双向链表中可以由当前结点出发访问表中的任何一个结点。第20页/共24页4.链表所表示的元素是否有序？如果有序，则有序性体现在何处？链表所表示的元素是否一定要在物理上相邻？顺序表的有序性又如何理解？答：链表所表示的元素是有序的，其有序性体现在逻辑上有序，即按指针指向的顺序有序。链表所表示的元素在物理上不一定相邻，但也可以相邻。顺序表的有序性不仅体现在逻辑结构上有序，而且在物理结构上也有序。第21页/共24页课后作业1.对以下单链表分别执行下列各程序段，并画出结果示意图。(1)Q=P-next;(2)L=P-next;(3)R-data=P-data;(4)R-data=P-next-data;(5)P-next-next-next-data=P-data;(6)T=P;while(T!=NULL)T-data=T-data*2;T=T-next;(7)T=P;while(T-next!=NULL)T-data=T-data*2;T=T-next;L5738642.第22页/共24页2.简述以下算法的功能。1）Status A(LinkList L)/L是无表头结点的单链表 if(L&L-next)Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;return OK;/A2)void BB(LNode*s,LNode*q)p=s;while(p-next!=q)p=p-next;p-next=s;/BB void AA(LNode*pa,LNode*pb)/pa和pb分别指向单循环链表中的两个结点 BB(pa,pb);BB(pb,pa);/AA第23页/共24页感谢您的观看。第24页/共24页
