《第2章-线性表》由会员分享，可在线阅读，更多相关《第2章-线性表（44页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表 性表的抽象数据类型 性表的顺序存储结构 性表的链式存储结构 性表的抽象数据类型 一个 线性表 (是由 n(n 0)个数据元素 (结点 ) 组成的有限序列。 数据元素可以是一个字符、一个数或一个记录，也可以是更复杂的信息。 线性表一： 26个英文字母组成的字母表（ A， B， C， ， Z）。表中的数据元素是单个字母字符。 线性表二：某学生五门课的成绩列表（ 76， 87，88， 80， 92）。表中的数据元素是整数。 线性表三：某班级学生信息表（如下表所示）。表中的数据元素是一个记录，包括姓名、学号、性别和年龄 4个数据项。 线性表中的元素可以是各种各样的，但同一线性表中的元素
2、必定具有相同特性，即属同一数据对象。 一个线性表可记为： （ a1,a ai, ,a n）， n 0 其中， n=0时，称为空表。 称 i为 表中 是 线性表的抽象数据类型定义 （参见教材） 返回本章目录 性表的顺序存储结构 线性表的顺序存储是指在内存中用地址连续的一块存储空间依次存放线性表的数据元素，用这种存储形式存储的线性表称其为 顺序表 。 假设每个数据元素占 将 则有如下关系： (d 线性表的第一个数据元素 常称作线性表的基地址。 顺序表的存储结构如下图所示，其中 序表的类型定义 #100 / 顺序表的容量 / 存放顺序表的元素 / 顺序表的实际长度 示线性表实际可能达到的最大长度。
3、性表基本运算在顺序表上的实现 0”开始，因此，若 表中第 1. 初始化线性表运算 ; sq,i) ( / i 值不合法 ; ; e) i=0; i=; i+1; 5. 插入元素运算 i, e) j; () ; / i 值不合法 j=j=i; / 插入位置及之后的元素右移 j= e; / 插入 e ; / 表长增 1 ; 6. 删除元素运算 i) j; ( ; / i 值不合法 j=i; j=i+j j) k= j;j+;k+; k= i;i+;k+; k= j;j+;k+; （ 2）求线性表长度 h) i=1; p=h-p-，循环停止 p=p-i+; /指针 i; （ 3）求线性表中第 h,i
4、) j=1; p=h-(i h) /j+; p; / 返回第 本算法的时间复杂度为 O(n)。 （ 4）按值查找 h,e) p=h-p!=& p-e) /从第 1个结点开始，查找 p=p-p; （ 5）插入结点 h,e,i) j=0; p=h,*s; (i h)+1) ; /j+; /从头结点开始，查找第 s=( ); /创建新结点 s-e; s-p-p-s; /插入链表中 ; （ 6）删除结点 h,i) j=0; p=h,*q; (i h) ; /j+; /从头结点开始，查找第 q=p- /删除并释放结点 p-q-q); ; （ 7）输出元素值 h) *p=h- (p!= %5d ”, p-
5、 /输出结点的 p=p- 2. 建立单链表 （ 1） 头插法建表 算法思路： 从一个空表开始，读取数据，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，如此重复，直到读入结束标志为止。 算法如下： h,a,n) s; i; h=( ); / 创建头结点 h-i=0;ai; s-h-s; / 2) 尾插法建表 算法思路：将新结点插入到当前链表的表尾上，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点。 算法如下： h,a,n) *s,*r; i; h=( ); / 创建头结点 r=h; / 始时指向头结点 i=0;ai; r-s; r=s; / 将新结
6、点插入到尾结点之后 r- / 将尾结点的 / 头插法建表和尾插法建表算法的时间复杂度都是 O(n)。 3. 单链表的应用举例 【 例 1】 设 设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的空间。表中允许有重复的数据。 算法思路： 设立 3个指针 中 比较 较小者插入 链到 将两个结点均链到 如此反复，直到有一个表的元素已归并完（ 止，再将另一个表的剩余段链接到 具体算法： pa=pb=hc=pc= / 用 if( pc=pa;pa= if( pc=pb;pb= pa;pc=pa;pa=pb;pc=pb;pb= pa?pa: / 插入剩余段 / 释放 / 本算法的基本操作是结点数据的比较和结点的链入，在最坏情况下，对每个结点均需进行上述操作，因此，若表 m和 n，则本算法的时间复杂度为 O(m+n)。 【 例 2】 设计算法，根据输入的学生人数和成绩建立一个单链表，并累计其中成绩不及格的人数。要求给出完整的程序。 解题思路：先定义单链表结点的类型，并根据
