数据结构 第2章 线性表(2).ppt

《数据结构 第2章 线性表(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法第三讲：线性表（二）内容提要线性表的顺序存储结构回顾单链表循环链表双向链表静态链表09/08/20212线性表的顺序存储结构回顾（1）09/08/20213a10a21……ai-1i-2aii-1……ani-1空闲空间下标：数组的长度MAXSIZE线性表的当前长度length(=n)data即LOC(a1)//线性表顺序存储的结构代码#defineMAXSIZE20typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];intlength;}SqList;三个属性：存储空间的起始地址：data线性表的最大存储

2、容量：MAXSIZE线性表的当前长度：lengthc(i-1)*cLOC(ai)存储位置地址计算公式：LOC(ai)=LOC(a1)+(i-1)*c其中c为每个数据元素占用的字节长度线性表的顺序存储结构回顾（2）09/08/20214//插入算法的思路（参数：线性表L，插入位置i，插入元素e）如果插入位置i不合理，提示异常；如果线性表长度大于等于数组长度MAXSIZE，提示异常或动态增加容量；从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；将要插入元素e填入位置i处；表长加1。ABCDEFGH空闲空间ABCDEFGH空闲空间插入前：插入后：线性表的顺序存

3、储结构回顾（3）09/08/20215//删除算法的思路（参数：线性表L，删除位置i，用来存放被删除元素的变量e）如果删除位置i不合理，提示异常；取出删除元素，存放在e中；从删除位置i开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；表长减1。删除前：删除后：ABCDEFGH空闲空间ABCDEFGH空闲空间实验1：顺序存储结构线性表09/08/20216FTP地址：218.193.53.74用户：zheng_stu密码：123456目录：/student/数据结构/实验1文件：sqlist_todo.cpp任务：在程序中标有/*ADDYOURCODEHERE*/的地方

4、加入自己的代码使程序功能完整，且能够正确运行。线性表顺序存储结构的优缺点09/08/20217优点无须为表示表中元素之间的逻辑关系而增加额外的存储空间（存储位置足以决定逻辑关系）可以快速地存取变种任一位置的元素（地址计算公式）缺点插入和删除操作需要移动大量元素（为了保持存储位置的相邻关系）当线性表长度变化较大时，难以确定存储空间的容量（必须动态修改存储容量）造成存储空间的“碎片”（因为只能使用整块的连续的存储空间）。顺序存储结构不足的解决办法思路(链式存储）：元素可以散落在任何位置，不必相邻让每个元素知道它的下一个元素在哪里我们只需要知道第一个元素的位置插入删除不再需要移动元

5、素而是需要修改元素间的关系09/08/20218123456234561线性表链式结构的存储示意假设我们有一个线性表(a1,a2,…,an)09/08/20219ai0500ai+1………………0800地址0500数据信息结点指针数据域指针域a10700an………………NULL第一个结点地址0900……0900头指针指针指向空最后一个结点图a：链表中的相邻元素图b：一个完整的链表【注意】有没有不大协调的地方？头结点与头指针09/08/202110a10700an………………NULL第一个结点地址0900……0900头指针指针指向空最后一个结点……0500可存线性表长度等公共数

6、据，地址0500头结点图c：一个带头结点的完整链表头结点头结点是为了操作的统一和方便而设立的，放在第一个元素之前，其数据域一般无意义（或可以存放链表的长度）有了头结点，对在第一个元素前插入节点和删除第一个节点的操作与其他节点的操作就同意了头结点不一定是链表的必要元素头指针头指针是指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针由于头指针的标识作用，常把头指针冠以链表的名字（即把头指针看做链表）头指针是链表的必要元素【注意】接下去的讨论都基于带头结点的链表另一种图示与单链表的C语言定义09/08/202111//单链表的结构代码typedefintElemType

7、;typedefstructNode{ElemTypedata;structNode*next;}Node;typedefNode*LinkList;a1a2an^头指针数据域指针域数据元素头结点后继指针地址结点头指针^空链表aiai+1p->datap->next->data*p假设我们定义：Node*p;*p->nextpp->next单链表的读取单链表的第i个元素的地址在哪？算法思路：声明一个结点指针p指向链表的第一个结点，初始化整型变量j从1开始；当j