《c2-线性表(一).ppt》由会员分享，可在线阅读，更多相关《c2-线性表(一).ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1线性表线性表(一一)执行校长李 伟数据结构数据结构(第二讲第二讲 )2知识回顾知识回顾n数据逻辑结构有那些？数据逻辑结构有那些？n数据的物理结构有那些？数据的物理结构有那些？n算法的特性和要求？算法的特性和要求？3教学内容教学内容n线性表的类型定义线性表的类型定义n线性表的顺序表示和实现线性表的顺序表示和实现4重点、难点重点、难点n重点重点pp线性表的定义线性表的定义线性表的定义线性表的定义 pp线性表的顺序表示和实现方法线性表的顺序表示和实现方法线性表的顺序表示和实现方法线性表的顺序表示和实现方法 n难点难点p线性表的顺序存储的实现方法线性表的顺序存储的实现方法 5线性表的类型定义线性表的
2、类型定义n线性表的类型定义线性表的类型定义n线性表的顺序表示和实现线性表的顺序表示和实现6线性表的类型定义线性表的类型定义n线性结构定义线性结构定义p若结构是非空有限集，则有且仅有一个开始结点和若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。前驱和一个直接后继。p可表示为：（可表示为：（a1,a2,an）7线性表的类型定义线性表的类型定义n特点特点p存在唯一的被称为“第一个”的数据元素。即首元素或者头元素。p存在唯一的被称为“最后一个”的数据元素。即尾元素。p除首尾元素外，其他数据元素只有一
3、个直接前驱和一个直接后继。p简言之，线性结构反映结点间的逻辑关系是一对一的。8线性表的类型定义线性表的类型定义n线性结构包括：线性结构包括：p线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等。p其中最典型、最常用的是线性表线性表。n线性表线性表p由由n(n0)个数据元素个数据元素a1,a2,an组成的有限序组成的有限序列。列。p其中数据元素的个数其中数据元素的个数n定义为表的长度。定义为表的长度。p当当n=0时称为空表。时称为空表。9线性表的类型定义线性表的类型定义n常常将非空的线性表常常将非空的线性表(n0)记作：记作：(a1，a2，an)p这里的数据元素ai(1in)只是
4、一个抽象的符号，其具体含义在不同的情况下可以不同。10线性表的类型定义线性表的类型定义n例例1：分析26 个英文字母组成的英文表是什么结构。n分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关元素间关系是线性的。系是线性的。（A,B,C,D,Z）11线性表的类型定义线性表的类型定义n例例2 分析学生情况登记表是什么结构。p在复杂的线性表中，一个数据元素可以由若干个在复杂的线性表中，一个数据元素可以由若干个数数据项据项组成。在这种情况下，常把数据元素称为组成。在这种情况下，常把数据元素称为记录记录，含有大量记录的线性表又称含有大量记录的线性表又称文件文件。p分析：分析：
5、数据元素都是同类型数据元素都是同类型(记录记录)，元素间关系是，元素间关系是线性的。线性的。学号姓名性别年龄班级012003010622陈建武男 192003级电信0303班012003010623赵玉凤女 182003级电信0303班012003010624王 泽男 192003级电信0303班：数据项数据项记录记录文件文件 注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！12线性表的类型定义线性表的类型定义n线性表的逻辑结构：线性表的逻辑结构：（a1,a2,ai-1，ai,ai1，,an）线性起点线性起点线性终点线性终点数据元素数据元素ai的直接前驱的直接
6、前驱ai的直接后继的直接后继下标，是元素的下标，是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n=0时称为时称为空表空表13线性表的类型定义线性表的类型定义n抽象数据类型定义抽象数据类型定义ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=|ai-1,ai D,i=1,2,n 基本操作：InitList(&L)操作结果：构造一个空的线性表L DestroyList(&L)初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(&L)初始条件：线性表L已存在 操作结果：将L
7、重置为空表 ListEmpty(L)初始条件：线性表L已存在 操作结果：若L为空表，则返回TRUE，否则返回FALSE 14线性表的类型定义线性表的类型定义n抽象数据类型定义抽象数据类型定义 ListLength(L)初始条件：线性表L已存在 操作结果：返回L中数据元素的个数 GetElem(L,I,&e)初始条件：线性表L已存在，1i ListLength(L)操作结果：用e返回L中第i个数据元素的 LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是数据元素判定函数 操作结果：返回L中第1个与e满足关系的数据元素的位序。若这样 的数据元素不存在，则
8、返回值为0 PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在 操作结果：若cur_e是L的数据元素，且不是第一个，则用 pre_e返 回它的前驱，否则操作失败，pre_e无定义 15线性表的类型定义线性表的类型定义n抽象数据类型定义抽象数据类型定义 NextElem(L,cur_e,&next_e)初始条件：线性表L已存在 操作结果：若cur_e是L的数据元素，且不是最后一个，则用 next_e返回它的后继，否则操作失败，next_e无定义 ListInsert(&L,i,e)初始条件：线性表L已存在，1i ListLength(L)+1 操作结果：在L中第i个位置之
9、前插入新的数据元素e，L的长度加1 ListDelete(&L,i,&e)初始条件：线性表L已存在，1i ListLength(L)操作结果：删除L中第i个数据元素，并用e返回其值，L的长度减1 ListTraverse(L,visit()初始条件：线性表L已存在 操作结果：依次对L中的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 ADT List16线性表的类型定义线性表的类型定义n算法算法2-1 void union(List&La，List Lb)La_len=ListLength(La);/求线性表长 Lb_len=ListLength(Lb);for(i=1
10、;i=Lb_len;i+)GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal)ListInsert(La,+La_en,e);/La中不存在和e相同的数据元素，则插入 /union利用两个线性表利用两个线性表LA和和LB分别表示两个集合分别表示两个集合A和和B，现要求一个新的集合，现要求一个新的集合A=A B。17线性表的类型定义线性表的类型定义n算法算法2-2已知线性表已知线性表LA和线性表和线性表LB中的数据元素按值非中的数据元素按值非递减有序排列，现要求将递减有序排列，现要求将LA和和LB归并为一个新归并为一个新的线性表的线
11、性表LC，且，且LC中的元素仍按值非递减有序中的元素仍按值非递减有序排列。排列。18线性表的类型定义线性表的类型定义 void mergelist(List La，List Lb，List&Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_Len=ListLength(Lb);while(i=La_Len)&(j=Lb_Len)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while(i=La_le
12、n)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/mergelist19线性表的类型定义线性表的类型定义n算法分析算法分析p上述两个算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间。p假如GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比p算法2-1的时间复杂度为O(ListLength(LA)*ListLength(LB),p算法2-2的时间复杂度为O(ListLength(
13、LA)+ListLength(LB),20线性表的类型定义线性表的类型定义n线性表的类型定义线性表的类型定义n线性表的顺序表示和实现线性表的顺序表示和实现21线性表的顺序表示和实现线性表的顺序表示和实现n顺序存储结构顺序存储结构p把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。n顺序存储结构特点顺序存储结构特点p逻辑上相邻的数据元素，其物理上也相邻；物理顺序与逻辑顺序相同，可随机存取。p若已知表中首元素在存储器中的位置，则其 他元素存放位置亦可求出（利用下标i）。22线性表的顺序表示和实现线性表的顺序表示和实现n例：例：已知：每个元素需占用L个存储
14、单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+L 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L23线性表的顺序表示和实现线性表的顺序表示和实现a1a2aiai+1an 地址地址 内容内容 元素在表中的位序元素在表中的位序b=LOC(a1)b+L Lb+(i-1)+(i-1)L Lb+(n-1)+(n-1)L Lb+(MaxSize-1)+(MaxSize-1)L L空闲区空闲区L1 1i i
15、2 2n ni+1i+1 LOC(ai )=LOC(a1)+L*（i-1）24线性表的顺序表示和实现线性表的顺序表示和实现n高级程序设计语言中，数组类型也有随机存取的高级程序设计语言中，数组类型也有随机存取的特性。所以通常用数组来描述数据结构中的顺序特性。所以通常用数组来描述数据结构中的顺序存储结构。存储结构。n在此，由于线性表的长度可变，且所需最大存储在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在空间随问题不同而不同，则在C语言中可用动态分语言中可用动态分配的一维数组。配的一维数组。25线性表的顺序表示和实现线性表的顺序表示和实现n线性表的动态分配顺序存储结构线性表的动
16、态分配顺序存储结构#define LIST_INIT_SIZE 100/初始分配量#define LISTINCREMENT 10 /分配增量typedef struct ElemType *elem;/基址 int length;/当前长度 int listsize;/当前存储容量 SqList;/SqList为结构体名字数组指针elem指示线性表的基地址。length指示线性表的当前长度。listsize指示顺序表当前分配的存储空间大小。当空间不足时，可进行再分配，为顺序表增加一个大小为LISTINCREMENT个数据元素的空间。26线性表的顺序表示和实现线性表的顺序表示和实现n算法算法2
17、-3：初始化初始化p在这种结构中，容易实现线性表的某些操作。在这种结构中，容易实现线性表的某些操作。p只是要特别注意只是要特别注意C语言中数组下标从语言中数组下标从”0”开始，则表中开始，则表中第第i个数据元素的下标是个数据元素的下标是(i-1)。Status InitList_Sq(SqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/分配失败 L.length=0;/空表长度为0 L.listsize=LIST_INIT_SIZE;/初始存储容量 return
18、 OK;/InitList_Sq 27线性表的顺序表示和实现线性表的顺序表示和实现n线性表的插入操作线性表的插入操作p线性表的插入操作是指在线性表的第i-1个元素和第i个数据元素之间插入一个新的元素。p插入新元素后线性表的数据元素ai-1和ai之间的逻辑关系发生了变化。p在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动元素才能反映这个逻辑关系的变化。28在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242528304277123456781
19、23456789插入插入25252525线性表的顺序表示和实现线性表的顺序表示和实现29线性表的顺序表示和实现线性表的顺序表示和实现n实现步骤：实现步骤：p 将第将第n至第至第i位的元素向后移动一个位置；位的元素向后移动一个位置；p 将要插入的元素写到第将要插入的元素写到第i个位置；个位置；p 表长加表长加1。n注意事先应判断注意事先应判断:p插入位置i是否合法?p表是否已满?30线性表的顺序表示和实现线性表的顺序表示和实现n算法算法2-4Status ListInsert_Sq(SqList*L，int i，ElemType e)if(iL.length+1)return ERROR;if(
20、L.length=L.listSize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);If(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;/ListInsert_Sq31线性表的顺序表示和实现线性表的顺序表示和实现n插入操作插入操作算法时间
21、复杂度算法时间复杂度p 这里的问题规模是表的长度这里的问题规模是表的长度n。p 插入算法的时间主要花费在结点后移的语句上，插入算法的时间主要花费在结点后移的语句上，该语句的执行次数为该语句的执行次数为n-i次，与插入节点所在位次，与插入节点所在位置置i 有关。有关。p由此可看出，所需移动结点的次数不仅依赖于表的由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。长度，而且还与插入位置有关。p长度为长度为n的表中插入元素需移动元素的平均次数的表中插入元素需移动元素的平均次数 Eis=n/2 pListInsert_Sq的时间复杂度为的时间复杂度为O(n)32123456789
22、121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：线性表的顺序表示和实现线性表的顺序表示和实现33线性表的顺序表示和实现线性表的顺序表示和实现n线性表的删除操作线性表的删除操作Status ListDelete_Sq(SqList*L，int i，ElemType&e)if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;/ListDelete_Sq长度为n的表中删除元素需移动元素的平均次数 Edl=(n-1)/2 ListDelete_Sq的时间复杂度为O(n)34本讲总结本讲总结n线性结构的特点有哪些？线性结构的特点有哪些？n顺序存储的优点有哪些？顺序存储的优点有哪些？n顺序表中下标与相对地址的关系？顺序表中下标与相对地址的关系？n在对顺序表进行插入操作中应注意什么？在对顺序表进行插入操作中应注意什么？35实验实验n用用C C语言实现本讲的算法语言实现本讲的算法36