《《数据结构(C／C++描述)》-第2章 线性表》由会员分享，可在线阅读，更多相关《《数据结构(C／C++描述)》-第2章 线性表（69页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Data Structure）,第2章 线性表,线性结构的基本特征:,1集合中必存在惟一的一个“第1元素”;,2集合中必存在惟一的一个 “最后元素”,3除最后元素在外，均有 惟一的后继；,4除第1元素之外，均有 惟一的前驱。,线性结构是一个数据元素的有序集。,2.1 线性表的类型定义,2.3 线性表链式存储及实现,2.4 线性表应用举例,2.2 线性表顺序存储及实现,2.1 线性表的 类型定义,抽象数据类型线性表的定义如下：,ADT List, 数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 / 称 n 为线性表的表长; / 称 n=0 时的线性表为空表
2、。,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,/ 设线性表为 (a1，a2, . . . ，ai，. . . ，an), / 称 i 为 ai 在线性表中的位序。,基本操作：,初始化线性表,销毁线性表, ADT List,常用操作：,GetElem( L, i, &e ),LocateElem( L, e, compare( ) ),ListInsert( &L, i, e ),ListDelete(&L, i, &e),利用上述定义的线性表类型 可以实现其它更复杂的操作,2. 求 lc = lalb，其中，la、lb、lc 有序,3. 静态链表算法,例 ：1. 求 A=AB
3、,2.2 线性表的顺序存储及实现,最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。,顺序表示（映象）, 以 x 的存储位置和 y 的存储位置之间某种关系，表示逻辑关系。,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址，称作线性表的基地址。,线性表的顺序表示：,如何计算 元素地址 ？,以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + d 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第1个数据元素的存储位置： LOC(ai) = LOC(a1) + (i-1)d 基地址（若b）
4、,顺序表动态分配的顺序存储结构描述：,typedef struct SqList; / 俗称 顺序表,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),线性表的基本操作在顺序表中的实现,InitList(&L) / 结构初始化,LocateElem(L, e, compare( ) / 查找,ListInsert(&L, i, e) / 插入元素,ListDelete(&L, i) / 删除元素,int InitList_Sq( SqList& L, in
5、t maxsize )/ 构造一个最大容量为 maxsize 的顺序表 ,算法时间复杂度：,O(1),L.elem = new ElemTypemaxsize; / 为顺序表动态分配大小为 maxsize 的数组空间if (!L.elem) exit(OVERFLOW);,L.length = 0;L.listsize = maxsize;return OK;,ListInsert( &L, i, e ),初始条件：操作结果：,线性表 L 已存在，,在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。,/插入数据元素,且 1iLengthList(L)+1,线性表插入操作算法2.4L
6、istInsert(&L, i, e) 的实现：,首先分析:,插入元素时，线性表的逻辑结构发生什么变化？,(a1, , ai-1, ai, , an) 改变为, ,(a1, , ai-1, e, ai, , an),int ListInsert_Sq(SqList &L, int i, ElemType e) /在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 /算法的健壮性,算法时间复杂度为:,O( ListLength(L) ),q = &(L.elemi-1); / q 指示插入位置，指向第i个元素for (p = &(L.elemL.len
7、gth-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增 1return OK;,元素右移,if (L.length = L.listsize) / 当前存储空间已满 return OVERFLOW;或申请再分配（P.24）。,if (i L.length+1) return ERROR; / 插入位置不合法, / 健壮性讨论,考虑移动元素的平均情况:,假设在第 i 个元素之前插入的概率 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值（平均次数）为：,若假定在线性表中任何一个位置上进
8、行插入的概率都是相等的，则移动元素的期望值为：,ListDelete(&L, i, &e),初始条件：操作结果：,线性表 L 已存在且非空，,删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。,/删除数据元素,1iLengthList(L),线性表删除操作算法2.5 ListDelete(&L, i, &e)的实现：,首先分析：,删除元素时，线性表的逻辑结构发生什么变化？,(a1, , ai-1, ai, ai+1, , an) 改变为：,ai+1,an, ,表的长度减少1,(a1, , ai-1, ai+1, , an),int ListDelete_Sq (SqList &L
9、, int i, ElemType &e) ,for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减 1return OK;,算法时间复杂度为:,O( ListLength(L),p = &(L.elemi-1); / p 指向被删除元素的位置e = *p; / 被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,元素左移,考虑删除时移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线
10、性表中删除一个元素所需移动元素次数的期望值（平均次数）为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,LocateElem( L, e),初始条件：操作结果：,线性表 L 已存在，e 为给定值,返回 L 中第 1 个等于 e 的元素的 位序(1)。若这样的元素不存在，则返回值为 0。,/ 定位函数,顺序表的查找与表中元素定位：,e =,38,i,1,2,3,4,1,8,50,可见，基本操作是，将顺序表中的元素逐个和给定值 e 相比较。,int LocateElem_Sq(SqList L, ElemType e) / 在顺序表中查询第一个满足判定条件的数据
11、元素， / 若存在，则返回它的位序，否则返回 0。 ,O( ListLength(L) ),if (i = L.length) return i; else return 0;,算法的时间复杂度为：,i = 1; / i 的初值为第 1 元素的位序p = L.elem; / p 的初值为第 1 元素的存储位置,while (i = L.length & L.elemi!=e +i);,/找到满足条件的元素,/ 没有找到满足条件的元素,2.3 线性表的链式存及实现,一. 概念 用一组地址任意的存储单元存放线性表中的数据元素。,2.3.1 单链表的定义及存储,以 元素 （数据元素的映象数据域） +
12、 指针 （指示后继元素的存储位置指针域） = 结点 （表示数据元素ai的存储映象）,以“结点的序列”表示的线性表 称作链表,以线性表中第 1 个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第 1 个结点之前虚加一个“头结点”，以指向头结点的指针作为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,Typedef struct LNode ElemType data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList;,二.结点和单链表的结构描述,2.3.2 单链表基本操作的实现
13、,GetElem(L, i, e) / 取第i个数据元素,ListInsert(&L, i, e) / 插入数据元素,ListDelete(&L, i, e) / 删除数据元素,ClearList(&L) / 将线性表置空,CreateList(&L, n) / 生成含 n 个数据元素的链表,线性表的取元素操作 GetElem(L, i, &e) 在单链表中的实现:,j,1,2,3, 算法2.10,i=3,i=7,j=7,因此，查找第 i 个数据元素的基本操作为移动指针，比较 j 和 i.,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须从第1 个数据元素起，依次顺链查找。,令 j 为记数器，指针 p 同步指向线性表中的第 j 个数据元素。,
