第2章线性表.

第二章线性表本章主要内容：•线性表的定义•线性表的顺序存储结构及其基本操作•线性表的链式存储结构及其基本操作学习目的及要求：•掌握线性表的定义•掌握线性表的两种存储结构第二章线性表2.1线性表的定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示和相加2.1线性表的定义线性结构线性表栈队列串数组广义表一个数据元素的有序(次序)集。基本特征：1.集合中必存在唯一的“第一元素”2.集合中必存在唯一的“最后元素”3.除最后元素，均有唯一后继4.除第一元素，均有唯一前驱一、定义二、特点三、抽象数据类型线性表的定义2.1线性表的定义一、定义线性表——是由n个具有相同特性的数据元素a1,a2,…,an组成的有限序列，记为(a1,a2,…,an)。1．数据元素的类型可以是高级语言提供的简单数据类型也可以是用户定义的任何类型。2．线性表中元素个数n为线性表的长度。n=0时，称为空表；n0时，线性表中第i个数据元素记为ai，i为数据元素的位序。2.1线性表的定义二、特点1.线性表是个有限序列。2.线性表中的每一个数据元素的位置由该元素所在表中的序号(下标)确定的。3.除第一个元素a1外，每个数据元素有且仅有一个前驱元素；除最后一个元素an外，每个数据元素有且仅有一个后继元素。数据元素之间存在着序偶关系。a1a2a3a4……an2.1线性表的定义a3的前驱a3的后继三、抽象数据类型线性表的定义ADTList{数据对象：D={ai|ai∈ElemSet,1≤i≤n,n≥0}数据关系：R={ai,ai+1}|ai,ai+1∈D，1≤i≤n-1}2.1线性表的定义基本操作：三、抽象数据类型线性表的定义Destroylist(&L)//销毁初始条件：线性表L已存在。操作结果：销毁线性表L。InitList(&L)//初始化操作结果：构造一个空线性表L。2.1线性表的定义三、抽象数据类型线性表的定义//{引用型操作}线性表L已存在，对表结构无改变Listempty(L)操作结果：判断L是否为空。ListLength(L)操作结果：返回L中数据元素个数。GetElem(L,i,&e)操作结果：用e返回第i个数据元素的值。LocateElem(L,e,compare())操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，或locate(L,x)返回L中第一个与x值相同的元素位置。2.1线性表的定义//{加工型操作}线性表已存在，表元素或结构改变ClearList(&L)操作结果：将线性表L置为空表。Putelem(&L,i,&e)操作结果：为L中第i个位置赋e值。元素之间的关系改变：ListInsert(&L,i,e)操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。三、抽象数据类型线性表的定义2.1线性表的定义三、抽象数据类型线性表的定义利用上述定义的线性表可以完成其他更复杂操作。例2-1设两个线性表LA和LB分别表示两个集合A和B，现要得到一个新的集合A=A∪B(并)。此问题可演绎为对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到LA中。2.1线性表的定义三、抽象数据类型线性表的定义voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中。La.len=ListLength(La);//求线性表的长度Lb.len=ListLength(Lb);for(i=1;i=Lb.len;i++){GetElem(Lb,i,e);//取Lb中的第i个数据元素给eif(!LocateElem(La,e,equal))ListInsert(La,++La.len,e);}}该算法的时间复杂度为：O(ListLength(La)ListLength(Lb))2.1线性表的定义2.2线性表的顺序表示和实现一、线性表的顺序存储结构二、线性表顺序存储结构的实现一、线性表的顺序存储结构1.顺序存储结构方式用一组地址连续的存储单元存储线性表的数据元素，又称为顺序表。a1a2aian…12…i…n…bb+Lb+2Lb+(i-1)Lb+(n-1)L两方面的内容：(1)顺序表常用数组来描述(2)设每个数据元素占用L个存储单元，则第i个数据元素的存储位置记为LOC(ai)，与其相邻元素ai-1的存储位置LOC(ai-1)的关系满足：LOC(ai)=LOC(ai-1)+L第i数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L2.2线性表的顺序表示和实现b:线性表的起始位置与b相差一个与位序成正比的常量一、线性表的顺序存储结构2．顺序存储结构的特点逻辑相邻等价于物理相邻(1)优点a.容易查找一个结点的前驱和后继。b.随机存取。(2)缺点a.插入和删除操作比较困难。b.建立空表时，较难确定所需的存储空间。2.2线性表的顺序表示和实现一、线性表的顺序存储结构3．用一维静态数组表示线性表（1）描述如下：typedefintElemType;#defineMax_length100;ElemTypes[Max_length];2.2线性表的顺序表示和实现（2）插入操作的算法实现用一维静态数组表示线性表2.2线性表的顺序表示和实现必须弄清和需要规范的问题用一维静态数组表示线性表1．如何理解插入元素？(1)本书所讲的插入均是在第i个元素之前(而不是之后)插入。(2)第i个元素之前插入就是：先把原来第i个元素及后面的元素都往后挪一步，然后在第i个位置上插入。(3)1≤i≤n+12.2线性表的顺序表示和实现a1ea2a3a4a5a6插入ea1a2a3a4a5a6用一维静态数组表示线性表2．如何表示第i个元素？2.2线性表的顺序表示和实现a1a2a3a4a5a6elem[0]elem[4]自然语言表示和画图表示时，均以1为下标；程序中涉及内存空间表示时，均以0为下标。3．如何表示相邻两个元素移动？elem[j]=elem[j+1]elem[j]=elem[j-1]elem[j-1]=elem[j]elem[j+1]=elem[j]用一维静态数组表示线性表4．移动时j的范围如何表示？2.2线性表的顺序表示和实现a1a2a3a4a5a6a1ea2a3a4a5a6elem[j]=elem[j-1]被赋值的位置：a3~a72≤j≤6（2）插入操作的算法实现问题：线性表的逻辑结构发生了什么变化？两个变化：ai-1和ai的位置关系发生变化线性表的长度增1a1a2ai-1aiana1a2ai-1aiane用一维静态数组表示线性表2.2线性表的顺序表示和实现voidinsert(elemtypes[],int*n,inti,elemtypee){intj;if(i1||i*n+1)return;for(j=*n;j=i;j--)s[j]=s[j-1];s[j]=e;*n++;}a1ea2a3a4a5a6用一维静态数组表示线性表插入ea1a2a3a4a5a6时间复杂度：O(ListLength(L))2.2线性表的顺序表示和实现（3）删除操作的算法实现问题：线性表的逻辑结构发生了什么变化？两个变化：ai-1和ai的位置关系发生变化线性表的长度减1a1a2ai-1aiai+1ana1a2ai-1ai+1an用一维静态数组表示线性表2.2线性表的顺序表示和实现作业2：用C语言的一维静态数组描述线性表这种数据结构，并给出删除一个该种结构存储的数据元素的算法（函数），并计算算法时间复杂度。用一维静态数组表示线性表2.2线性表的顺序表示和实现voiddelete(elemtypes[],inti,int*n,elemtype*e;){intj;*e=s[i-1];for(j=i-1;j=*n-2;j++)s[j]=s[j+1];*n--;}删除用一维静态数组表示线性表时间复杂度：O(ListLength(L))a1a2a3a4a5a6a1a3a4a5a62.2线性表的顺序表示和实现i-1jj*n-24.动态分配顺序存储结构(1)C语言描述#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineINCREMENT10//线性表存储空间的分配增量typedefintElemType;typedefstruct{ElemType*elem;//存储空间的基址intlength;//线性表当前长度intlistsize;//当前分配的存储容量}SqList;一、线性表的顺序存储结构2.2线性表的顺序表示和实现用一维动态数组表示线性表1.动态存储结构的含义？typedefintElemType;typedefstruct{ElemType*elem;//存储空间的基址intlength;//线性表当前长度intlistsize;//当前分配的存储容量}SqList;SqListL;2.2线性表的顺序表示和实现必须弄清的问题定义类型定义表变量用一维动态数组表示线性表2.结构体变量如何调出内部成员？（1）结构体变量是值类型，调用成员用“.”（2）结构体变量是指针类型，调用成员用“-”L-elem=…2.2线性表的顺序表示和实现必须弄清的问题voidf(SqListL){L.elem[0]=3;L.length=6;}voidg(SqList*L){L-elem[0]=3;L-length=6;}用一维动态数组表示线性表3.如何动态申请内存空间？int*elem;elem=(int*)malloc(100*sizeof(int));2.2线性表的顺序表示和实现必须弄清的问题malloc函数的作用：申请一定字节数的空间，将首地址返回malloc申请的空间不能直接使用，需要先格式化（类似硬盘）字节数格式化用一维动态数组表示线性表4.如何动态追加内存空间？elem=(int*)realloc(elem,(100+50)*sizeof(int));2.2线性表的顺序表示和实现必须弄清的问题realloc函数说明参数一：n个字节连续空间的首地址elem参数二：新空间的字节数，设为n+k个，函数功能：在elem末尾追加分配k个字节的空间，或者在内存其它地方重新分配n+k个字节的空间并将elem开始的前n个字节的数据复制到新空间的前n个字节上，并返回新首地址。格式化后K个字节未格式化，因此仍然需要格式化用一维动态数组表示线性表5.结构体类型的定义与使用？2.2线性表的顺序表示和实现必须统一的问题1.类型定义位置：在函数之外2.变量定义：带struct与不带structtypedefstruct{…}SqList1;voidf(){SqList1L;…}structSqList2{…};voidf(){structSqList2L;…}用一维动态数组表示线性表statusinitlist(sqlist*L){L-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L-elem)return(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;returnOK;}2.2线性表的顺序表示和实现#defineLIST_INIT_SIZE100//初始分配元素个数#defineOVERFLOW-1//表示状态#defineOK1//表示状态typedefintStatus;//表示状态类型typedefintElemType;//表示实体元素的类型（2）初始化的算法实现结构体变量初始化，就是对结构体变量的内部成员赋初值。Statusinsertlist(sqlist*L,inti,elemtypee){elemtype*newbase,*q,*p;//参数检查if(i1||iL-length+1