第二章线性表 1.教学内容:2.1线性表逻辑结构 2.2线性表的顺序存储及运算实现 2.3线性表的链式存储和实现。 2教学目的:(①)理解线性表的定义及其运算: (2)理解顺序表和链表的定义、组织形式、结构特征和类型说明 3)掌握在这两种表上实现的插入、删除和按值查找的算法 (4)了解循环链表、双(循环)链表的结构特点和在其上施加的插入 3教学重点:()线性表的定义及逻辑上的特点: (2)顺序表上插入、删除和定位运算的实现 (3)单链表的结构特点及类型说明 (4)头指针和头结点的作用及区别: (5)定位、删除、插入运算在单链表上的实现 (6)循环链表、双链表的结构特点,循环链表、双链表上删除与人國的实」 4.教学难点:(①)线性表与线性结构的联系与区别 (2)头结点在链表中的作用;指针操作: (3)删除、插入运算中的指针操作顺序 (4)双链表上指针的操作顺序 5教学时数:9学时(含习题课2学时) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第二章 线性表 ⒈教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。 ⒉教学目的：⑴理解线性表的定义及其运算； ⑵理解顺序表和链表的定义、组织形式、结构特征和类型说明； ⑶掌握在这两种表上实现的插入、删除和按值查找的算法； ⑷了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。 ⒊教学重点：⑴线性表的定义及逻辑上的特点； ⑵顺序表上插入、删除和定位运算的实现； ⑶单链表的结构特点及类型说明； ⑷头指针和头结点的作用及区别； ⑸定位、删除、插入运算在单链表上的实现； ⑹循环链表、双链表的结构特点，循环链表、双链表上删除与插入运算的实现。 ⒋教学难点：⑴线性表与线性结构的联系与区别； ⑵头结点在链表中的作用；指针操作； ⑶删除、插入运算中的指针操作顺序； ⑷双链表上指针的操作顺序。 ⒌教学时数： 9学时（含习题课2学时）
21线性表的逻辑结构 ◆线性表的定义 ◆线性表的基本操作 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 2.1 线性表的逻辑结构 线性表的定义 线性表的基本操作
21.1线性表的定义 ◆线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系,数据 元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的,或者说线性 表是由同一类型的数据元素构成的线性结构。 ◆线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为 ai1, aj, aH+1,.an) 其中n为表长,n=0时称为空表。 ◆表中相邻元素之间存在着顺序关系。将a1称为a1的直接前趋,an1称为a1的直 接后继。就是说:对于a1,当=2,…,n时,有且仅有一个直接前趋a1,当i=1, 2,…,n-1时,有且仅有一个直接后继a+1,而a1是表中第一个元素,它没有前趋 an是最后一个元素无后继。 ◆需要说明的是:a为序号为i的数据元素(i=1,2…,n),通常我们将它的数据类 型抽象为 datatype, datatype根据具体问题而定,如在学生情况信息表中,它是用户 自定义的学生类型;在字符串中,它是字符型;等等。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 3 2.1.1 线性表的定义 线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据 元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性 表是由同一类型的数据元素构成的线性结构。 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直 接后继。就是说：对于ai，当 i=2，...，n 时，有且仅有一个直接前趋 ai-1.，当i=1， 2，...，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋， an 是最后一个元素无后继。 需要说明的是：ai为序号为 i 的数据元素（i=1,2,…,n），通常我们将它的数据类 型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户 自定义的学生类型； 在字符串中，它是字符型； 等等
2.1.2线性表的基本操作 ①线性表初始化: Init List(L) 需要说明的是 初始条件:表L不存在 操作结果:构造一个空的线性表 某数据结构上的基本 (2)求线性表的长度: Length List((L) 运算,不是它的全部运 初始条件:表L存在 操作结果:返回线性表中的所含元素的个数 算,而是一些常用的基 (3)取表元: Get list(Li) 本的运算,而每一个基 初始条件:表L存在且1<=<= Length_List((L) 本运算在实现时也可能 操作结果:返回线性表L中的第i个元素的值或地址 (4按值查找: Locate list(L,x),x是给定的一个数据元素。 根据不同的存储结构派 初始条件:线性表L存在 生出一系列相关的运算 操作结果:返回在L中首次出现的值为x的那个元素的序号或地址,称为查 找成功;否则,在L中未找到值为x的数据元素,返回一特殊值表示查找失败。 来 (5)插入操作: Insert List((u1x) 初始条件:线性表L存在,插入位置正确(1<=<=n+1,n为插入前的表长) 在上面各操作中定义 操作结果:在线性表L的第i个位置上插入一个值为ⅹ的新元素,这样使原 的线性表L仅仅是一个 序号为i,i+1,…,n的数据元素的序号变为i+1+2,…,n+1,插入后表长= 原表长+1。 抽象在逻辑结构层次的 (6)删除操作: Delete List(L) 线性表,尚未涉及到它 初始条件:线性表L存在,1<=<=n 操作结果:在线性表中删除序号为的数据元素,删除后使序号为i+1, 的存储结构。 i+2,n的元素变为序号为i,i+1,…n-1,新表长=原表长-1。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 4 2.1.2 线性表的基本操作 ⑴线性表初始化：Init_List(L) 初始条件：表L不存在 操作结果：构造一个空的线性表 ⑵求线性表的长度：Length_List(L) 初始条件：表L存在 操作结果：返回线性表中的所含元素的个数 ⑶取表元：Get_List(L,i) 初始条件：表L存在且1<=i<=Length_List(L) 操作结果：返回线性表L中的第ｉ个元素的值或地址 ⑷按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。 初始条件：线性表L存在 操作结果：返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查 找成功; 否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。 ⑸插入操作：Insert_List(L,i,x) 初始条件：线性表L存在，插入位置正确 (1<=i<=n+1,ｎ为插入前的表长)。 操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原 序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1，插入后表长= 原表长+1。 ⑹删除操作：Delete_List(L,i) 初始条件：线性表L存在，1<=i<=n。 操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，新表长＝原表长－１。 需要说明的是： 某数据结构上的基本 运算，不是它的全部运 算，而是一些常用的基 本的运算，而每一个基 本运算在实现时也可能 根据不同的存储结构派 生出一系列相关的运算 来。 在上面各操作中定义 的线性表Ｌ仅仅是一个 抽象在逻辑结构层次的 线性表，尚未涉及到它 的存储结构
22线性表的顺序存储及运算 实现 ◆线性表的顺序存储 ◆顺序表上基本运算 的实现 ◆顺序表应用举例 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 2.2 线性表的顺序存储及运算 实现 线性表的顺序存储 顺序表上基本运算 的实现 顺序表应用举例
22.1线性表的顺序顺序存储 ◆线性表的顺序存储是指在内存中用地址连续的一块存 储空间顺序存放线性表的各元素,用这种存储形式存储 的线性表称其为顺序表。 ◆设a1的存储地址为LoC(a1),每个数据元素占d个存储 地址,则第i个数据元素的地址为: Loc(ai=Loca)+(i-1*d lsIs ◆从结构性上考虑,通常将data和|as封装成一个结构 作为顺序表的类型: typedef struct i datatype data[MAXSIZE t last Seqlist; 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 2.2.1 线性表的顺序顺序存储 线性表的顺序存储是指在内存中用地址连续的一块存 储空间顺序存放线性表的各元素，用这种存储形式存储 的线性表称其为顺序表。 设 a１的存储地址为Loc(a１)，每个数据元素占d个存储 地址，则第i个数据元素的地址为： Loc(ai )=Loc(a１)+(i-1)*d 1≤I≤n 从结构性上考虑，通常将 data 和 last 封装成一个结构 作为顺序表的类型： typedef struct { datatype data[MAXSIZE]; int last; } SeqList;
222顺序表上基本运算的实现 1.顺序表的初始化 顶序表的初始化即构造一个空表,对表是一个加工型 的运算,因此,将L设为指针参数,首先动态分配存储空 间,然后,将表中ast指针置为-1,表示表中没有数据 元素。算法如下: SeqList * init seqlisto { Seqlist料; L=malloc( sizeof(seqList)) L->|ast=-1 return l; 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 2.2.2 顺序表上基本运算的实现 ⒈ 顺序表的初始化 顺序表的初始化即构造一个空表，对表是一个加工型 的运算，因此，将 L设为指针参数，首先动态分配存储空 间，然后，将表中 last 指针置为－1，表示表中没有数据 元素。算法如下： SeqList *init_SeqList( ) { SeqList *L; L=malloc(sizeof(SeqList)); L->last=-1; return L; }
2插入运算 4线性表的插入是指在表的第个位置上插入一个值为x的新 素,算法如下 int Insert_ SeqList(SeqList *L, int i, datatype x) i int j if (L->last== MAXSIZE-1) printi("表满") return(-1);}*表空间已满,不能插 f(iL->last2)/*检查插入位置的正确性* { printf(("位置错"; return(0);} forG=L->last; j>=i-1; j-) L->datalj+1=L->datall;/ *结点移动* L->data i-1]=X; /*新元素插入* L->ast+;/*s仍指向最后元素* return(1);/*插入成功,返回* 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 ⒉插入运算 线性表的插入是指在表的第i个位置上插入一个值为 x 的新 元素，算法如下： int Insert_SeqList(SeqList *L，int i，datatype x) { int j; if (L->last == MAXSIZE－1) { printf(＂表满＂); return(-1); } /*表空间已满，不能插 入*/ if (iL->last+2) /*检查插入位置的正确性*/ { printf(＂位置错＂); return(0); } for(j=L->last; j>=i-1; j--) L->data[j+1]=L->data[j]; /* 结点移动 */ L->data[i-1]=x; /*新元素插入*/ L->last++; /*last仍指向最后元素*/ return (1); /*插入成功，返回*/ }
插入算法的时间性能分析 ◆顺序表上的插入运算,时间主要消耗在了数据的移动上, 在第价个位置上插入x,从a1到an都要向下移动一个位置, 共需要移动n-1+1个元素,而1的取值范围为:1sks n+1,即有n+1个位置可以插入。设在第个位置上作插入 的概率为P,则平均移动数据元素的次数: 设:P=1/(n+1),即为等概率情况,则: n+1 n+1 pic (n-i+1) n ◆这说明:在顺序表上做插入操作需移动表中一半的数据 元素。显然时间复杂度为O(n) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在了数据的移动上， 在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置， 共需要移动 n－i＋1个元素，而 i 的取值范围为 ：1≤ i≤ n+1，即有 n＋1个位置可以插入。设在第i个位置上作插入 的概率为Pi，则平均移动数据元素的次数： 设：Pi=1/ (n+1) ，即为等概率情况，则： 这说明：在顺序表上做插入操作需移动表中一半的数据 元素。显然时间复杂度为Ｏ(n)。 + = = − + 1 1 E ( 1 ) n i i n i p n i
3删除运算 线性表的删除运算是指将表中第i个元素从线性表中去掉, 算法如下: int Delete Seqlist(seqlist *L; t i cint i int ji f(L->ast1)/检查空表及删除位置的合法性考 prnt("不存在第个元素" return(O); forG=i; jlast;j++) L->data-1]=L-> data;/*向上移动* L->last return (1: /*删除成功* 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 ⒊删除运算 线性表的删除运算是指将表中第 i 个元素从线性表中去掉， 算法如下： int Delete_SeqList(SeqList *L;int i) { int j; if(iL->last+1) /*检查空表及删除位置的合法性*/ { printf (＂不存在第i个元素＂); return(0); } for(j=i; jlast; j++) L->data[j-1]=L->data[j]; /*向上移动*/ L->last--; return(1); /*删除成功*/ }