数据结构 方风波 王巧莲 主编 黄鹤鸣 副主编 第二章线性表新.pptVIP

数据结构 第二章 线性表 线性表 知 识 点 线性数据结构的基本特征和基本运算 顺序表的插入与删除运算 链表的插入与删除运算 难 点 顺序表的溢出的判断 利用本章的基本知识设计有效的算法解决与线性相关的应用问题 要 求 熟练掌握以下内容： 线性表的基本运算 了解以下内容： 线性表运算时间复杂性分析 目录 2.1 线性表及其运算 2.2 顺序存储结构 2.3 链表存储结构 2.4 应用实例及分析 小 结 习题与练习 2.1.1 线性表（Linear List） 线性表是由有限数目的相同类型元素组成的序列。 表中的数据元素，除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素； 第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的长度，当n=0时，这个表叫做空表。 线性表在计算机内存中采用各元素顺序存储的方式，这种存储结构叫做向量。 每个线性表元素叫做这个向量的一个分量。 如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单，用的也最普遍。 2.1.2 线性表的运算 对于给定的线性表，可进行如下的基本运算： 1. 求线性表的长度n； 2. 在第i个数据元素前面插入一个新的数据元素； 3. 删除第i个数据元素； 4. 存取或更新线性表第i个元素； 5. 将两个或两个以上的线性表合并成一个线性表； 6. 将一个线性表拆成多个线性表； 7. 将线性表中各数据元素按某个域值（如关键字）递增或递减的顺序重新排列； 8. 在线性表中查找满足某种条件的数据元素； 1. 数据元素的插入(insert) 设用一个一维数组A[n]表示此线性表，原来有m个元素（mn），元素值已给定。 规定数组的下标从1开始，即这里数据元素对应的数组下标从1到n。 要求在第i个元素前插入一个新数据元素，值为G，因原线性表的数据元素是连续排列的，中间没有空单元，所以第i个元素及其后面的各元素均需向后移动一个单元位置，这样才能将G插入到i位置，且元素总数由m增加为（m+1）。 插入函数 void insert(A, int n, m, i, G) { int j; if (i1||in+1) printf(“i值错！\n”); else { for (j=m;j=i;j--) A[j+1]=A[j]; /*将第i个元素及其后面的元素后移*/ A[i]=G; m++; /*线性表长度加1*/ } } 插入函数分析 在循环语句中，当i=1时，须循环m次，表示元素插入线性表头的前面，则原线性表中m个元素均须向后移动一个单元，这是最不利的情况。 当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾的后面，所以线性表的所有m个元素均不移动，这是最好的情况。 2. 数据元素的删除(Delete) 设用一个一维数组A[n]表示此线性表，原来有n个元素，元素值已给定。 要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面的所有元素都需要向前移动一个单元，且数据元素总数由原来的n减少到n-1. 删除函数 void delete(A,int n,i) { int j; if (i1||in) printf(“i值错！\n”); else { for (j=i;j=n;j++) A[j]=A[j+1]; n--; } } 删除函数分析 在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利的情况； 当i=n时，则循环一次也不执行，只是将元素数目n比原来减少一个，而第n个数据元素不必再考虑，其余的各单元的元素均维持不变，这是最好的情况。 2.3.1 链表及其运算 知 识 点 单链表的结点形式、组织方法和特点 单链表的基本运算和相应的算法 循环链表的组织方法和基本运算算法 双链表的结点形式、组织方法和特点 双链表的基本运算和相应的算法 顺序表与链表比较，各自的优、缺点 链表的应用 难 点 双链表插入、删除运算的算法 利用链接结构的特点设计有效算法，解决与链表结构相关的应用问题 要