数据结构第2章线性表单向链式存储.ppt

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