Ch21-22线性表-顺序存储.ppt

1 第二章 线性表 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： 2 线性表(Linear List) ：由n(n)个数据元素(结点)a1,a2， an 组成的有限序列。其中数据元素的个数n定义为表的长度。 当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义 在不同的情况下可以不同。 例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化 情况。 （6，17，28，50，92，188） 2.1 线性表的逻辑结构 3 例3、学生健康情况登记表如下： 姓 名学 号性 别年龄 健康情况 王小林790631 男 18 健康 陈 红790632 女 20 一般 刘建平790633 男 21 健康 张立立790634 男 17 神经衰弱 . . 4 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它 没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而 仅有一个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个直 接前趋a i-1和一个直接后继a i+1。 线性表的逻辑特征 5 ADT 线性表的定义 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具 体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19 6 例2-1 利用两个线性表LA和LB分别表示两个集合A 和B，现要求一个新的集合A=AB。 void union(List Lb-len=listlength(Lb); for(I=1;IL.length+1) printf(“Position error”); return ERROR 15 if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1;j=I-1;j-) L.dataj+1=L.dataj; L.dataI-1=x; L.length+; 16 这里的问题规模是表的长度，设它的值为n。该算法的时 间主要化费在循环的结点后移语句上，该语句的执行次数 （即移动结点的次数）是n-i+1。由此可看出，所需移动结 点的次数不仅依赖于表的长度，而且还与插入位置有关。 当”插入”操作在表尾进行时，由于循环变量的终值大于初 值，结点后移语句将不进行；这是最好情况，其时间复杂 度O（1）； 当”插入”操作在表头进行时，结点后移语句将循环执行n次 ，需移动表中所有结点，这是最坏情况，其时间复杂度为 O（n）。 算法的复杂度分析 17 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度 。 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动 结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点 的移动次数为n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均 等的，则 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2 18 也就是说，在顺序表上做插入运算，平均要移动 表上一半结点。当表长 n较大时，算法的效率相 当低。虽然Eis(n)中n的的系数较小，但就数量级 而言，它仍然是线性阶的。因此算法的平均时间 复杂度为O(n)。 19 2、删除 线性表的删除运算是指将表的第 i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an) 20 算法2. Void deleteList(Sqlist if(IL.length) printf(“Position error”); return ERROR； for(j=i;j Void main() int a; int *pointer_1; a=100; pointer_1= printf(“%dn”,a); printf(“%dn”,*pointer_1); 运行结果： 100 100 *pointer_1=200 思考加入下列语句， 得到什么结果？ 32 结构体类型 定义一个结构体类型stu，这个结构体类型包括学 号、姓名、成绩、家庭地址等四个数据项。 struct stu int num; char name20; float score; char addr30； ； 可以用这个结构体类型来定义变量，例如 struct stu student1,student2; 结构体类型名结构体变量名 33 也可以在声明类型的同时定义变量 struct stu int num; char name20; float score; char addr30； student1,student2； 结构体变量的引用 例1. student1.num=2011003; 例2. printf(“%s”,) 例3. scanf(“%d”, char name20; float score; ; struct student s1; struct student *p; p= s1.num=1001; strcpy(,“John“); s1.score=98.5; printf(“%ld,%s,%fn“,s1.num,,s1.score); printf(“%ld,%s,%fn“,(*p).num,(*p).name,(*p).score) ; printf(“%ld,%s,%fn“,p-num,p-name,p-score); 执行结果： 1001，John，98.500000 1001，John，98.500000 1001，John，98.500000 36 以下三种形式等价： 结构体变量名.成员名 (*p).成员名 p-成员名 例如，上面程序中 s1.score, (*p).score, p-score是一样的 。 37 用指针处理链表 举例：定义如下一个结构体类型： Struct student int num; float score; Struct student *next; ; 101 85.596.0 103 80.0 102num s