第2周线性表（上）第6讲-本周小结数据结构.pdf

《第2周线性表（上）第6讲-本周小结数据结构.pdf》由会员分享，可在线阅读，更多相关《第2周线性表（上）第6讲-本周小结数据结构.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、知识点： 线性表概念线性表概念 顺序表及算法设计顺序表及算法设计 单链表及算法设计单链表及算法设计 1/19 1线性表两类存储结构的比较 I.顺序表 II.链表 2/19 插入和删除操作需要移动大量元素。插入和删除操作需要移动大量元素。 初始空间大小分配难以掌握初始空间大小分配难以掌握。 缺点缺点 存储密度大：无须为表示线性表中元素之间的逻辑关存储密度大：无须为表示线性表中元素之间的逻辑关 系而增加额外的存储空间。系而增加额外的存储空间。 具有随机存取特性。具有随机存取特性。 优点优点 3/19 存储密度小：为表示线性表中元素之间的逻辑关系而需存储密度小：为表示线性表中元素之间的逻辑关系而需

2、要增加额外的存储空间（指针域）要增加额外的存储空间（指针域）。 不具有随机存取特性不具有随机存取特性。 缺点缺点 由于采用节点的动态分配方式，具有良好的适应性。由于采用节点的动态分配方式，具有良好的适应性。 插入和删除操作只需修改相关指针域，不需要移动元素插入和删除操作只需修改相关指针域，不需要移动元素。 优点优点 4/19 2线性表的算法设计 数据的存储结构顺序表：链表？ 算法的处理过程用C/C+语言描述。 5/19 顺序表用数组表示 借鉴数组处理方法（存、取元素） 顺序表不同于数组 顺序表是线性表的一种存储结构 注意：注意： 线性表线性表L：（：（1，2，3） 数组：数组：int a=1，

3、2，3； 而数组：而数组：int b=空，空，1，2，空，空，3；不对应；不对应L 6/19 基于顺序表基本操作的算法设计基于顺序表基本操作的算法设计 查找元素查找元素 插入元素插入元素 删除元素删除元素 7/19 基于特殊方法的顺序表算法设计基于特殊方法的顺序表算法设计 将整数顺序表将整数顺序表L以第一个元素为分界线（基准）进行划分以第一个元素为分界线（基准）进行划分 在顺序表在顺序表L中删除所有值为中删除所有值为x的元素的元素 8/19 荷兰国旗问题荷兰国旗问题：设有一个条块序列，每个条块为红设有一个条块序列，每个条块为红 （0）、白（）、白（1）、兰（）、兰（2）三种颜色中的一种。假设该

4、序列）三种颜色中的一种。假设该序列 采用采用顺序表顺序表存储，设计一个时间复杂度为存储，设计一个时间复杂度为O(n)的算法，使得的算法，使得 这些条块按红、白、兰的顺序排好，即排成荷兰国旗图案。这些条块按红、白、兰的顺序排好，即排成荷兰国旗图案。 例如：例如：1 0 2 1 0 0 1 2 2 1 0 2 012010122012 000011112222 本算法本算法 9/19 解：解： 012010122012 ik j初始状态（i=-1，k=n，j=1） 用用0i表示表示0元素区间。元素区间。 kn- -1表示表示2元素区间。元素区间。 中间部分为中间部分为1元素区间。元素区间。 用用j

5、从头开始从头开始扫描顺序表扫描顺序表L中部的所有元素。中部的所有元素。 10/19 j指向指向元素元素1：说明它属于中部，保持不动，：说明它属于中部，保持不动，j+。 j指向指向元素元素0：说明它属于前部，：说明它属于前部，i增增1（扩大（扩大0元素区间），将元素区间），将i、j位置的元素交位置的元素交 换，换，j+。 j指向指向元素元素2：说明它属于后部，：说明它属于后部，k减减1（扩大（扩大2元素区间），将元素区间），将j、k位置的元素位置的元素 交换，此时交换，此时j位置的元素可能还要交换到前部，所以位置的元素可能还要交换到前部，所以j不前进。不前进。 012010122012 ik j

6、 j指向0，交换到前面 每一次循环：每一次循环： 11/19 void move1(SqList * while (jdataj=0) i+; swap(L-datai，L-dataj); j+; else if (L-dataj=2) k-; swap(L-datak，L-dataj); else j+;/L-dataj=1的情况的情况 算法如下：算法如下： 12/19 基于单链表基本操作的算法设计基于单链表基本操作的算法设计 查找节点查找节点 插入节点插入节点 删除节点删除节点 需要查找前驱节点 13/19 基于两个建表方法的单链表算法设计基于两个建表方法的单链表算法设计 头插法：相对次序

7、相反头插法：相对次序相反 尾插法：相对次序相同尾插法：相对次序相同 14/19 荷兰国旗问题荷兰国旗问题：设有一个仅由红（：设有一个仅由红（0）、白）、白 （1）、兰（）、兰（2）这三种颜色的条块组成的条块序列。）这三种颜色的条块组成的条块序列。 假设该序列采用假设该序列采用单链表单链表存储，设计一个时间复杂度存储，设计一个时间复杂度 为为O(n)的算法，使得这些条块按红、白、兰的顺序的算法，使得这些条块按红、白、兰的顺序 排好，即排成荷兰国旗图案。排好，即排成荷兰国旗图案。 15/19 解：解：用用p指针扫描节点，根据指针扫描节点，根据p- -data值将该节点插值将该节点插 入到入到3个单

8、链表个单链表L、L1和和L2（L1和和L2不带头节点的）中。不带头节点的）中。 最后将它们链接起来。最后将它们链接起来。 012012 L p 012012 L p L1 L2 最后将L、L1和L2链接起来 16/19 算法如下：算法如下： void move2(LinkList * L1=NULL; L2=NULL; p=L-next; r=L; 做 准 备 工 作 17/19 while (p!=NULL) if (p-data=0) r-next=p; r=p; else if (p-data=1) if (L1=NULL) L1=p; r1=p; else r1-next=p; r1=p; else /p-data=2 if (L2=NULL) L2=p; r2=p; else r2-next=p; r2=p; p=p-next; 建立L带头节点的单链表 建立L1不带头节点的单链表 建立L2不带头节点的单链表 18/19 r-next=r1-next=r2-next=NULL; r-next=L1; /L的尾节点和的尾节点和L1的首节点链接起来的首节点链接起来 r1-next=L2; /L1的尾节点和的尾节点和L2的首节点链接起来的首节点链接起来 结 尾 工 作 所以，两个建表算法是许多算法设计的基础！ 19/19