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

《Ch21-22线性表-顺序存储.ppt》由会员分享，可在线阅读，更多相关《Ch21-22线性表-顺序存储.ppt（38页珍藏版）》请在三一文库上搜索。

1、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

2、，92，188）,2.1 线性表的逻辑结构,3,例3、学生健康情况登记表如下：,4,从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。,线性表的逻辑特征,5,ADT 线性表的定义,线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19,6,例2-1 利用两个线性表LA和LB分别表示两个

3、集合A和B，现要求一个新的集合A=AB。 void union(List if(!locateelem(La，e，equal)listinsert(La，+la-en，e) ,7,例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法如下：,8,void mergelist(list la，list lb，list ,9,while(I=la-len) getelem(la，I+，ai);listinsert(lc，+k，ai); while(j=lb-len) getelem(lb，j

4、+，bj);listinsert(lc，+k，bi); ,10,2.2.1 线性表的顺序表示 线性表的顺序表示：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 如何计算数据元素的存储位置？ 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*l,2.2 线

5、性表的顺序存储结构,11,由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。 # define ListSize 100 typedef ElemType DataType; typedef struct DataType dataListSize; int length; Sqlist;,12,在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序

6、表，则表中第i个元素是L.dataI-1。 以下主要讨论线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的第I(1in+1个位置上，插入一个新结点x，,2.2.2 顺序表上实现的基本操作,13,使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，an),14,算法2. Void InsertList(Sqlist return ERROR,15,if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1;j=I-1;j-) L.da

7、taj+1=L.dataj; L.dataI-1=x; L.length+; ,16,这里的问题规模是表的长度，设它的值为n。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。 当”插入”操作在表尾进行时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）； 当”插入”操作在表头进行时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。,算法的复杂度分析,17,由于插入可能在表中任何位置上进行，因此需分析算法的

8、平均复杂度。 在长度为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的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度

9、为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 ,21,该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 若I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点； 若I=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。 删除算法的平均性能分析与插入算法相似。

10、在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n)= pi(n-I) 式中，pi表示删除表中第i个结点的概率。,算法的复杂度分析,22,在等概率的假设下， p1=p2=p3=pn=1/n 由此可得： Ede(n)= (n-I)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。,23,小结：顺序存储方式的优缺点,优点： .在节点等长时可以随机存取。 存储密度高，节省存储空间。 用结点的物理次序反映结点之间的逻辑关系。 缺点： 插入和删除结点时需要移动大量的结点。 必

11、须静态分配连续的空间。,24,课堂练习,顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。 【解答】108 在一个长度为n的顺序表的第i（1in+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1in）个元素时，需向前移动（ ）个元素。 【解答】n-i+1，n-i,25,当线性表采用顺序存储结构时，其主要特点是（ ）。 【解答】逻辑结构中相邻的结点在存储结构中仍相邻,26,作业,试写一个删除算法 Void elete_seq(Sqlist &plist， ElemType x), 在plist所指顺序表中，删除一个值为的元素，返回删除成功与

12、否的标志。 （请首先给出顺序表的定义，再写出算法）,27,附:,“指针”,程序经过编译后,系统为变量分配内存单元。 不同类型的变量分配到的字节数是不同的。 例如：整型变量分配2个字节，单精度分配4个字节。 内存区中的每一个字节有一个编号，称为“地址”。 概念辨析：内存单元的地址和内存单元的内容 例：假设程序中定义了2个整型变量i和j, 编译时系统将 3000和3001这两个字节给变量I,将3002和3003这两个 字节给j. 那么地址为3000的内存单元中存放着变量i的值。,28,“直接访问”方式和“间接访问”方式 按变量地址存取变量值的方式称为“直接访问” 例如 ：printf(“%d”,i

13、) 是如何执行的？ scanf(“%d”,&i) 是如何执行的？,将变量i的地址存放在另外一个变量中，通过这个变量的 值（也就是i的地址），找到i的内存起始地址，读取i的值。 i_pointer= /将i的地址（3000）存放到i_pointer中。,29,地址是指向变量的，知道地址就知道了地址所指向的变量。所以，一个变量的地址称为该变量的“指针”。 变量的指针就是变量的地址。 存放变量地址的变量是指针变量。 定义一个指针变量 int *pointer_1; /pointer_1这个变量可以存放一个整型变量的地址。 float *pointer_2; /pointer_2这个指针变量可以存放一

14、个浮点型变量的地址。,30,指针变量的引用,两个运算符 “&” 与 “*” &: 取地址符。 *: 指针运算符，取指针所指向的对象的内容。 例如： &a 是变量a的地址； *p是指针变量p所指向的存储单元的内容， 也就是p所指向的变量的值。,31,例子： 通过指针变量访问整型变量。,#include Void main() int a; int *pointer_1; a=100; pointer_1= 运行结果： 100 100,*pointer_1=200,思考加入下列语句， 得到什么结果？,32,结构体类型,定义一个结构体类型stu，这个结构体类型包括学号、姓名、成绩、家庭地址等四个数据

15、项。,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”,student1.name) 例3. scanf(

16、“%d”, &student1.num),34,指向结构体类型数据的指针,一个结构体变量的指针就是该变量所占据的内存段的起始地址。可以设一个指针变量，用来指向一个结构体变量，此时该指针变量的值是结构体变量的起始地址。 举例：指向结构体变量的指针的应用 （见下一页中的程序）,35,#include #include void main() struct student long num; char name20; float score; ; struct student s1; struct student *p; p= ,执行结果： 1001，John，98.500000 1001，John

17、，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; ;,38,typedef 的功能,typedef可以声明新的类型名来代替已有的类型名。 例如 int i,j; 等价于 typedef int INTEGER; INTEGER i,j; 而 int n100; 等价于 typedef int NUM100; NUM n;,