SUN数据结构第2节线性表(第3-4讲).ppt

2.1 线性表的逻辑结构 2.1 线性表的逻辑结构 线性表举例 线性表举例 线性表的基本运算 2.2线性表的顺序存储及运算实现 线性表的顺序存储结构 线性表的顺序存储结构 线性表的顺序存储结构 顺序表上基本运算的实现 顺序表上基本运算的实现 顺序表上基本运算的实现 顺序表上基本运算的实现 顺序表上基本运算的实现 线性表在顺序存储结构下的运算实现——顺序表的插入算法InsertList(L,i,x)的实现 线性表在顺序存储结构下的运算实现——顺序表的插入算法InsertList(L,i,x)的实现 void InsertList(SeqList *L,int i,Datatype x) { if (i1 || iL-length+1) { printf(“Error!”) ; //插入位置出错 exit(1); } if(L-length==MaxLen) { printf(“overflow!”) ; 　 //表已满 exit(1); } for(j=L-length-1;j=i-1;j--) L-data[j+1]=L-data[j]; //数据元素后移 L-data[i-1]=x; //插入x L-length++; //表长度加1 } 线性表在顺序存储结构下的运算实现——顺序表的删除运算DeleteList(L,i)的实现 线性表在顺序存储结构下的运算实现——顺序表的删除运算DeleteList(L,i)的实现 链表的分类 单链表：只设置一个指向后继结点地址的指针域； 循环链表：链表首尾相接构成一个环状结构； 双向链表：单链表中增加一个指向前驱的指针。 本章小结 【例2-2】将顺序表(a1，a2，a3，…，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大（这里假设数据元素的类型具有可比性，可设为整型）。 typedef int DataType; void part(SeqList *L) { int i,j; DataType x,y; x=L-data[0]; //将基准元素a1置入x中 for(i=1;iL-length;i++) if(L-data[i]x)　//当前元素小于a1 { y=L-data[i]; for(j=i-1;j=0;j--)　//向后移动 L-data[j+1]=L-data[j]; L-data[0]=y; } } 【例2-3】 利用线性表的基本运算，编写将线性表A和B中公共元素生成线性表C的算法。 void commelem(SeqList *A, SeqList *B, SeqList *C) { int i,k,j=1; DataType x; Initlist(C); for(i=1;i=Getlen(A);i++) { x=Getelem(A,i); //依次获取线性表A中的元素，存放在x中 k=Locate(B,x); //在线性表B中查找x if(kO){ InsetrList(C,j,x);j++; } //若在线性表B中找到了，将其插入到C中 } ｝ 线性表的顺序存储结构的特点 优点：顺序表中的任意数据元素的存储地址可由公式直接导出，因此顺序表可以“随机存取”其中的任意元素。 不足： （1）需预先分配相应的存储空间 ——预分配空间过小，存储空间不便于扩充；预分配空间过大，容易造成空间浪费。 （2）插入与删除运算的效率很低，插入、删除操作时需移动大量数据。 课后作业： 创建顺序表，在顺序表的第i个位置插入一个元素。 例：创建线性表20 56 89 45 67 在该线性表的第3个位置插入一个元素97 程序运行结果能够输出20 56 97 89 45 67 2.3 线性表的链式存储及运算实现 线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。 采用链式存储结构的表示的线性表简称链表。 链式存储方式可用于表示线性结构，也可用于表示非线性结构。 由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。 用链式存储结构表示线性表中的一个元素时至少需要两部分信息，一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，