第2课--线性表及其顺序存储结构.

2019/12/201教学目的：掌握线性表的概念和类型定义教学重点：线性表的顺序存储结构和链式存储结构教学难点：链表的操作第2章线性表2019/12/202线性表（Linearlist）是最简单且最常用的一种数据结构。这种结构逻辑上具有下列特点：存在一个唯一的没有前驱的数据元素——称为表头；存在一个唯一的没有后继的数据元素——称为表尾；其它数据元素均有且仅有一个直接前驱和一个直接后继.本章学习导读2019/12/2031.线性表的概念和类型定义2.线性表的顺序存储结构及算法实现3.补充:C语言中结构体与指针操作教学重点：线性表的插入、删除操作本课内容2019/12/204线性表由一组具有相同属性的数据元素构成。数据元素的含义很广泛，在不同的具体情况下，可以有不同的含义。1.线性表的定义线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。当n=0时称为空表，即不含有任何元素。2.1线性表的基本概念2019/12/205例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生统计表2019/12/206从以上例子可看出,线性表的特点：（1）有序性：线性表长度是有限的；（2）有序性：元素之间是有顺序限制的，并且用直接前驱和后继来描述；（3）同型性：所有元素是同一数据类型；（4）抽象性：数据元素的类型没有具体定义，只是给出一个抽象说明（Elemtype)。即可以是简单类型，也可以是复杂的构造类型；（5）原子性：数据元素整体上作为一个独立的存储对象，不再分解为更小的数据单位进行存储。2019/12/207线性表的ADT定义•ADTLiner_list{•数据对象定义：D={ei|ei∈ElemType&&0≤i≤n&&n≥0}•数据关系定义：R={ei-1,ei|ei-1,ei∈D&&2≤i≤n}•数据运算定义：（一组操作说明）•初始化线性表Initlist(L）•求线性表的长度Getlen(L)•取第i个元素Getelem(L,i):•插入元素InsElem(L,i,x)•删除元素Delelem(L,i)•清空表ClearList(L)•释放表Destroy(L)2019/12/2082.2线性表的顺序结构及实现线性表的顺序存储结构可以有静态结构和动态结构两种不同的方式。顺序存储结构的特点：在内存中用地址连续的存储单元按照数据元素的逻辑顺序、依次“一个接一个”地存放线性表的所有数据元素，通过物理位置的相邻来表示元素之间的逻辑关系。所谓静态结构指：线性表所占的存储空间是在编译时就确定的，一经分配不再改变。动态结构指：线性表所需的存储空间可以在运行时分配，并且能够根据需要动态增加或释放。2019/12/209线性表的顺序存储结构需要两个分量描述：用于存储数据元素的数组data，以及表长length。通常将它们定义在一个结构类型中。可用结构类型sqList定义来描述顺序表(静态)：#defineMaxLen100//线性表的容量typedefstruct{ElemTypedata[MaxLen];//定义存储表中元素的数组intlength;//线性表的实际长度}sqList;typedefintElemType//元素类型ElemType简化为int型时2.2.1线性表的顺序静态结构及实现2019/12/20101．初始化顺序表Initlist(L)的实现顺序表的初始化即构造一个空表，只要将表L中的表长度置为0，就可以实现建空表的功能（数据元素的存储空间data已由编译程序实现）。voidinitlist(sqList*L){L-length=0;}2．求线性表长度GetLen(L)的实现intGetlen(sqList*L){returnL-length;}该算法的时间复杂度为O(1)2.2.1线性表的顺序静态结构及实现2019/12/20113．按序号取元素GetElem(L,i)的实现根据约定，序号为i的元素存储在数组下标为i-1的数组元素中，所以可直接从该数组元素中取得值。i的有效值应大于等于1和小于等于线性表的实际长度。ElemTypeGetElem(sqLlist*L,inti){if(i1||iL-length)/*判断参数是否合法*/{printf(“error”);exit(1);}returnL-data[i-1];}2.2.1线性表的顺序静态结构及实现2019/12/20125．顺序表的插入算法(重点)顺序表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表(a1,a2,…，ai-1,ai,ai+1,…,an)成为表长为n+1的线性表需要注意的是:插入后形成的新表必须保持原来的特点:逻辑上相邻的元素物理上也相邻.2.2.1线性表的顺序静态结构及实现2019/12/2013例：在线性表(a1，a2，…，ai-1，ai，ai+1，…，an)第i个位置插入x(i的取值范围为1≤i≤n+1):序号元素0a01a12a2┇┇i-1ai-1iaii+1ai+1i+2ai+2┇┇numanum序号元素0a01a12a2┇┇i-1ai-1ixi+1aii+2ai+1┇┇numanum插入x插入前插入后2019/12/2014•插入算法步骤描述：•1.判断参数i是否合法,合法则继续•2.判断表是否已满，未满则继续•3.由最后一个元素开始依次将第i个位置后的元素后移(索引length-1至i-1)•4.将新元素保存到第i个位置(i-1处）•5.修改线性表长度(length+1)2019/12/2015插入算法描述：voidInsertElem(sqList*L,inti,Elemtypex){if(i1||iL-length+1){printf(“Error!”);//插入位置出错exit(1);}if(L-length==MaxLen){printf(“overflow!”);//表已满exit(1);}for(j=L-length;j=i;j--)L-data[j+1]=L-data[j];//数据元素后移L-data[i]=x;//插入xL-length++;//表长度加1}2.2.1线性表的顺序静态结构及实现2019/12/2016)1(11inpEniiin11112)1(11)1(Eniniiinninninp假设表中任何位置插入概率是均等的,即Pi=1/(n+1),则：插入算法的效率分析：该算法的时间主要花费在移动数据元素上，移动次数取决于插入位置i和表的长度n。所以用数据元素的移动操作来估计算法的时间复杂度。在第i个位置上插入x，共需要移动n-i+1个元素，i的取值范围为：1≤i≤n+1，即有n+1个位置可以插入。由于插入的位置是随机的，因此需要分析执行该算法移动数据元素的平均值。设在第i个位置上插入的概率为Pi，则平均移动数据元素的次数为：结论：线性表的插入操作平均要移动一半的元素，时间复杂度为Ｏ(n)。2019/12/20176．顺序表的删除运算DeleElem(L,i)的实现顺序表的删除运算是指将表中第i个元素从线性表中去掉.对表长为n的线性表:(a1，a2，…，ai-1，ai，ai+1，…，an)进行删除操作后变为表长n-1的表(a1，a2，…，ai-1，ai+1，…，an)，i的合理取值范围为：1≤i≤n。2.2.1线性表的顺序静态结构及实现2019/12/2018图2-5线性表中的删除运算示意图a1a2ai-1ana1a2...ai-1aiai+1...an...MaxLen-1012in-1n删除aiMaxLen-1012...i-1i+1i+2n-1下标数据元素下标数据元素删除前删除后ai+1i-1i+1an-1......2019/12/2019算法实现：(1)将第i个(索引i-1）后的元素（共n-i+1个）依次向前移动一个位置,从而删除元素ai，保证逻辑上相邻的元素物理位置也相邻。(2)修改线性表长度，使其减1。线性表的删除算法如下：voidDelelem(sqList*L,inti)//删除线性表中第i个元素{if(i1||iL-length)//检查空表及删除位置的合法性{printf(“不存在第i个元素”);exit(0);}for(j=i;j=L-length-1;j++)L-data[j-1]=L-data[j];//向前移动元素L-length--;}2.2.1顺序结构线性表-删除算法2019/12/2020niideinp1)(E11121)(1)(Eniniideninninp删除算法的时间性能分析：与插入运算相同，删除运算的时间也主要消耗在移动表中数据元素上，删除第i个元素时，其后面的元素ai+1～an都要向前移动一个位置，共移动了n-i个元素，所以在等概率的情况下，在线性表中删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数为：由此可以看出，在线性表上删除数据元素时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。通常情况下，我们认为在线性表中任何位置删除元素是等概率的，即pi=1/n，则：2019/12/2021线性表的动态分配顺序结构类型SqList定义如下，注意与静态结构sqList的区别#defineList_Init_Len100//线性表的初始容量#defineIncrement10//分配增量typedefstruct{ElemType*Elem;//数据元素的存放地址（基址）intlength;//线性表中的元素个数(实际长度)intListSize;//线性表容量}SqList;typedefintElemType//元素类型ElemType简化为int型2.2.2线性表的顺序动态结构及实现(重点）2019/12/2022静态结构，数据表存储空间静态分配，不能改变#defineMaxLen100//线性表的最大容量typedefstruct{ElemTypedata[MaxLen];//存储表元素的数组，空间在编译时分配intlength;//线性表的实际长度}sqList;#defineList_Init_Len100//线性表的初始容量#defineIncrement10//分配增量typedefstruct{ElemType*Elem;//数据元素的存放地址（基址）intlength;//线性表中的元素个数(实际长度)intListSize;//线性表容量}SqList;描述数据元素地址的是指针，可以根据需要在运行时增加存储或减少。2019/12/2023/*构造一个空的线性表L,成功返回1，否则返回0*/statusInitList(SqList*L)data为指针，其指向有InitList操作进行且在运行时刻动态更改2.2.2线性表的动态结构及实现内存空间Data?lengthsize2019/12/2024•/*构造一个空的线性表L,成功返回ok*/•StatusInitListsq2(SqList*L)•{•//申请线性表数据元素的存储空间•L-elem=(ElemType*)malloc(List_Init_Len*sizeof(ElemType));•if(L-elem==0)return0;/*分配失败*/•/*存储空间分配成功，为变量L指向的成员赋值*/•L-length=0;•L-ListSize=List_Init_Len;•return(ok);•}•注意调用方法：•Sqlistlist2;/*声明结构体*/InitListsq2(&list2);/*传递结构体的地址*/教材算法2.3的C程序实现22019/12/20252.2.2线性表的顺序动态结构_插入算