数据结构(第2章)资料.ppt

01/06/2002 数据结构讲义 第二章 线性表 ⒈教学内容： 2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。 ⒉教学目的： ⑴理解线性表的定义及其运算； ⑵理解顺序表和链表的定义、组织形式、结构特征和类型说明； ⑶掌握在这两种表上实现的插入、删除和按值查找的算法； ⑷了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。 2.1 线性表的逻辑结构 线性表的定义 线性表的基本操作 2.1.1 线性表的定义 线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 2.1.2 线性表的基本操作 ⑴线性表初始化：Init_List(L) 初始条件：表L不存在 操作结果：构造一个空的线性表 ⑵求线性表的长度：Length_List(L) 初始条件：表L存在 操作结果：返回线性表中的所含元素的个数 ⑶取表元：Get_List(L,i) 初始条件：表L存在且1=i=Length_List(L) 操作结果：返回线性表L中的第ｉ个元素的值或地址 2.2 线性表的顺序存储及运算实现 线性表的顺序存储 顺序表上基本运算的实现 顺序表应用举例 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; 2.2.2 顺序表上基本运算的实现⒈ 顺序表的初始化 顺序表的初始化即构造一个空表，对表是一个加工型的运算，因此，将 L设为指针参数，首先动态分配存储空间，然后，将表中 last 指针置为－1，表示表中没有数据元素。算法如下： SeqList *init_SeqList( ) { SeqList *L; L=malloc(sizeof(SeqList)); L-last=-1; return L; } ⒉插入运算 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，算法如下： int Insert_SeqList(SeqList *L，int i，datatype x) {　int j; if (L-last == MAXSIZE－1) { printf(＂表满＂); return(-1); } /*表空间已满，不能插入*/ if (i1 || 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);　　　/*插入成功，返回*/ } 插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 n－i＋1个元素，而 i 的取值范围为 ：1≤ i≤ n+1，即有 n＋1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数： 设