线性表及其存储结构课件

《线性表及其存储结构课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章线性表及其存储结构3.1线性表的基本概念3.2线性表的顺序存储及运算3.3线性表的链式存储及运算3.1线性表的基本概念线性表是由n(n≥0)个数据元素a1,a2,…,an组成的一个有限序列。表中的每一个数据元素，除了第一个外，有且只有一个前件；除了最后一个外，有且只有一个后件。即线性表或是一个空表或可以表示为：（a1,a2,…,ai,…,an）其中ai（i=1,2,…,n)是属于数据对象的元素，通常也称其为线性表中的一个结点。数据元素在线性表中的位置，只取决于它们自己的序号。非空线性表的结构特征为：①有且只有一个根结点a1,它无前件；

2、②有且只有一个终端结点an,它无后件；③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性别、入学成绩4个数据项。3.2线性表的顺序存储及其运算3.2.1线性表的顺序存储线性表的顺序存储结构称为顺序表。线性表的顺序存储结构具有两个基本特点：①线性表中所有元素所占的存储空间是连

3、续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。假设线性表中的第一个数据元素的存储地址（即首地址）为ADR(a1)，每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：ADR(ai)=ADR(a1)+(i-1)k长度为n的线性表在计算机中的顺序存储结构如图3-1所示。在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。应注意数组的基本类型要与线性表中数据元素的类型相同。数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中的位

4、置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对C语言，顺序表可定义如下：对C语言，顺序表可定义如下：#defineMaxLength50typedefintElemType;typedefstruct{ElemTypelist[MaxLength];intlength;}SeqList;今后使用此定义时，MaxLength及ElemType要根据实际问题的需要可重新选定。3.2.2顺序表的基本运算1.顺序表的插入设长度为n的顺序表为（a1,a2,…,ai,…,an），要在顺序表的第i(1≤i≤n)个元素ai之前插入一个新元素

5、x，插入后得到长度为n+1的线性表(a1,a2,…,ai-1,x,ai,…,an)，即(a1,a2,…,ai-1,a’i,a’i+1,…,a’n+1)，其中a’i为新插入的元素x，a’i+1为原表中的ai，其余类推，a’n+1为原表中an。一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置。移动结束时，第i个位置就被空出，然后将新元素插入，插入结束线性表的长度增1。在平均情况下，插入一个新元素，需要移动表中一半的元素。注意：若最后一个元素之后没有多

6、余的自由空间（即表的大小n=MaxLength）时，那么插入一个元素，将会发生上溢。在顺序表L中的第i个元素之前插入一个新元素x的算法InsertList描述如下：voidInsertList(SeqList*L,inti,ElemTypex){intj,n=L->length;if(i<1

7、

8、i>n+1){printf("i值不合法");exit(1);}if(n>=MaxLength){printf("表空间上溢");exit(1);}for(j=n-1;j>=i-1;j--)L->list[j+1]=L->list[j];/*

9、数据元素依次向后移动一个位置*/L->list[i-1]=x;/*插入x*/L->length++;/*表长增加1*/}2.顺序表的删除通常，在长度为n的顺序表中，要删除线性表的第i(1≤i≤n)个元素ai。得到长度为n-1的线性表(a1,a2,…,ai-1,ai+1,…,an)。即(a1,a2,…,ai-1,a’i,a’i+1,…,a’n-1)，其中a’i为原表中的ai+1，其余类推，a’n-1为原表中an。一般情况下，要删除第i(1≤i≤n)个元素，需要从第i+1个元素开始，直到第n个元素之间，共有n-i个元素依次向前移动了一个位置。删

10、除结束后，顺序表的长度就缩小了１。在平均情况下，要在顺序表中删除一个元素，需要移动表中一半的元素。在顺序表L中删除第i个元素并用x返回其值的算法DeleteList描述如下：vo