《数据结构 第2章 线性表单向链式存储》由会员分享，可在线阅读，更多相关《数据结构 第2章 线性表单向链式存储（39页珍藏版）》请在金锄头文库上搜索。
1、单链表：线性表的链接存储结构。 存储思想：用一组任意的存储单元存放线性表的元素。,2.3 线性表的链接存储结构及实现,单链表,存储特点： 逻辑次序和物理次序不一定相同。 2.元素之间的逻辑关系用指针表示。,2.3 线性表的链接存储结构及实现,例：(a1, a2 ,a3, a4)的存储示意图,单链表,a1 0200,a2 0325,a3 0300,a4,2.3 线性表的链接存储结构及实现,单链表,数据域,指针域,单链表是由若干结点构成的； 单链表的结点必须有一个指针域。,data：存储数据元素 next：存储指向后继结点的地址,struct node ElemType data;struct n
2、ode *next; ;,2.3 线性表的链接存储结构及实现,如何申请一个结点？,s=new struct node ;,s,s=new struct node ;,2.3 线性表的链接存储结构及实现,s-data,如何引用数据元素？,如何引用指针域？,s-next,2.3 线性表的链接存储结构及实现,单链表,为了清楚起见，在讨论单链表的存储示意图时，通常将右图用下图表示。,2.3 线性表的链接存储结构及实现,单链表,头指针：指向第一个结点的地址。 尾标志：终端结点的指针域为空。,2.3 线性表的链接存储结构及实现,单链表,空表和非空表不统一？ 如何将空表与非空表统一？,L中的地址值不相同,使
3、L中的地址值相同,头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一，操作方便,2.3 线性表的链接存储结构及实现,带头结点的单链表,非空表,头结点,第一个结点,终端结点（尾结点）,由于单链表的存储空间是动态分配的，只要记住头指针，就能对单链表操作，所以单链表的类型描述只要考虑结点类型和指向结点的指针类型。,单链表类型的描述,2.3 线性表的链接存储结构及实现,typedef struct node ElemType data;struct node *next; Node,*LinkList; 其中：Node等价于struct nodeLinkList等价于
4、struct node *,单链表的实现按位查找,操作接口： int GetLinkList (LinkList L,int i, ElemType & x),核心操作（关键操作）：工作指针后移。从第1个结点出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。,2.3 线性表的链接存储结构及实现,L,a1,a2,an,ai,1. 工作指针p初始化; 累加器j置1;,2.1 工作指针p后移; 2.2 累加器j加1;,2. 循环直到p为空或p指向第i个结点,3. 若p为空，则第i个元素不存在，抛出查找位置异常；否则查找成功，返回结点p的数据元素；,2.3 线性表的链接存
5、储结构及实现,单链表的实现按位查找,算法描述伪代码,int GetLinkList(LinkList L,int i,ElemType ,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述C描述,不能,错,对,int GetLinkList(LinkList L, ElemType x, LinkList ,2.3 线性表的链接存储结构及实现,单链表的实现按值查找,算法描述C描述,L,a1,an,x,p,p,p,如果找到了，p指向某个存在的结点，反之p为空,单链表的实现插入,操作接口： int InsertLinkList (LinkList L,int i,ElemType
6、x);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1、x和ai之间逻辑关系的变化？,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,插入位置的合理范围：1,n+1 i=1 p指向头结点 i=n+1 p指向尾结点,让p指向ai的直接前驱,注意分析边界情况表头、表尾。,单链表的实现插入,2.3 线性表的链接存储结构及实现,L,a1,an,ai,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。,控制指针p移动的循环
7、： while(p ,j=0,j=n,当插入位置i合法，将指针变量移到第i-1个结点，j记住位置i-1。 移动p的条件是：p!=NULL & ji-1)printf(“位置异常“);return 0;else/(p ,，,基本语句？时间复杂度？,单链表的实现删除,操作接口： int DeleteLinkList (LinkList L,int i,ElemType ,2.3 线性表的链接存储结构及实现,如何实现结点ai-1和ai之间逻辑关系的变化？,算法描述： q=p-next; x=q-data; p-next=q-next; delete q;,删除位置的合理范围：1,n i=1 p指向头
8、结点 i=n p指向尾结点的直接前驱,单链表的实现删除,2.3 线性表的链接存储结构及实现,算法描述： q=p-next; x=q-data; p-next=q-next; delete q;,注意分析边界情况表头、表尾。,控制指针p移动的条件： while(p-next ,删除的结点必须存在，因此p-next不能为空。,j=0,j=n,算法描述伪代码,1. 工作指针p初始化；累加器j清零；2. 查找第i-1个结点并使工作指针p指向该结点；3. 若p不存在后继结点，则抛出位置异常；否则，3.1 暂存被删结点和被删元素值；3.2 摘链，将结点p的后继结点从链表上摘下；3.3 释放被删结点；3.4
9、 返回被删元素值；,2.3 线性表的链接存储结构及实现,单链表的实现删除,int DeleteLinkList(LinkList L,int i,ElemType ,2.3 线性表的链接存储结构及实现,算法描述C描述,单链表的实现删除,if ( !p-next| ji-1) printf(“位置异常”);return 0; else /(p-next,单链表的实现创建函数,操作接口：int creatLinkListf(LinkList &L, int n),头插法：将待插入结点插在头结点的后面 。,算法描述： L=new Node; L-next=NULL;,2.3 线性表的链接存储结构及实
10、现,35,12,24,33,42,例如,单链表的实现创建函数,操作接口：int creatLinkListf(LinkList ,头插法：将待插入结点插在头结点的后面 。,2.3 线性表的链接存储结构及实现,35,12,24,33,42,算法描述： s=new Node; scanf(,插入第一个元素结点,L,单链表的实现创建函数,操作接口：int creatLinkListf(LinkList ,头插法：将待插入结点插在头结点的后面 。,2.3 线性表的链接存储结构及实现,35,12,24,33,42,算法描述： s=new Node; scanf(,依次插入每一个结点,int creatL
11、inkListf(LinkList ,2.3 线性表的链接存储结构及实现,单链表的实现创建函数（头插）,算法描述：,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现创建函数,操作接口：int creatLinkListr(LinkList ,算法描述： L=new Node; L-next=NULL; R=L;,35,12,24,33,42,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现创建函数,操作接口： int creatLinkListr(LinkList ,算法描述： s=new Node; scan
12、f(,35,12,24,33,42,插入第一个元素结点,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现创建函数,操作接口：int creatLinkListr(LinkList ,算法描述： s=new Node; scanf(,35,12,24,33,42,依次插入每一个结点,35,int creatLinkListr(LinkList ,2.3 线性表的链接存储结构及实现,单链表的实现创建函数(尾插),算法描述：,int creatLinkList(LinkList /调用插入函数 ,2.3 线性表的链接存储结构及实现,单链表的实现创建函数(用插
13、入函数实现),算法描述：,单链表的实现销毁函数,销毁函数将单链表中所有结点的存储空间释放。,2.3 线性表的链接存储结构及实现,操作接口：int destroyLinkList(LinkList ,L,a1,a2,an,ai,算法描述： q=p; p=p-next; delete q;,注意：保证链表未处理的部分不断开,单链表的实现销毁函数,int destroyLinkList(LinkList ,2.3 线性表的链接存储结构及实现,算法描述：,启示：算法设计的一般过程,算法设计的一般步骤： 第一步：确定入口（已知条件）、出口（结果）； 第二步：根据一个小实例画出示意图； 第三步： 正向思维
14、：选定一个思考问题的起点，逐步提出问题、解决问题； 逆向思维：从结论出发分析为达到这个结论应该先有什么； 正逆结合； 第四步：写出具体算法，分析边界情况； 第五步：进一步验证，手工运行。,存储分配方式比较,顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。 单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。,2.4 顺序表和单链表的比较,2.4 顺序表和单链表的比较,时间性能比较,按位查找： 顺序表的时间复杂度为(1)，是随机存取； 单链表的时间复杂度为(n)，是顺序存取。 插入和删除： 顺序表需移动表长一半的元素，时间复杂度为(n) 单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间复杂度仅为(1),2.4 顺序表和单链表的比较,空间性能比较,空间性能是指某种存储结构所占用的存储空间的大小。,定义结点的存储密度：,2.4 顺序表和单链表的比较,
