《数据结构》(C语言版)第二章课件.ppt

第二章 线性表,,教学要求： 理解线性表的概念 掌握线性表的抽象数据类型和应具有的基本操作 掌握线性表的顺序存储结构的实现方法 掌握线性表的链表存储结构的实现方法 掌握线性表的简单应用,教学重点： 线性表的抽象数据类型 线性表的顺序存储结构 线性表的链式存储结构 线性表的简单应用,教学难点： 线性表算法的设计与实现,线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱线性结构 是 一个数据元素的有序（次序）集,线性表是一种最简单的线性结构,2.1 线性表的类型定义,线性表：线性表是n个元素的有序序列，是最常用且最简单的一种数据结构a0, a1, ai-1，ai, ai1 ，, an-1）,线性表的逻辑结构：,n=0时称为,,数据元素,,线性起点,,ai的直接前趋,ai的直接后继,,,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长n0,空表,线性终点,,,,（ A, B, C, D, , Z）,例2 分析学生情况登记表是什么结构分析：数据元素都是同类型（记录），元素间关系是线性的。

分析： 数据元素都是同类型（字母）， 元素间关系是线性的注意：同一线性表中的元素必定具有相同特性 ！,例1 分析26 个英文字母组成的英文表是什么结构综上例： 线性表中的数据元素可以是各种各样的 但同一个表中的元素必须具有相同的特性 相邻数据元素之间存在序偶关系 线性表中每一个元素都有确定的位置，如a1是第一个数据元素，ai是第i个数据元素,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,...,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表数据关系：,R1 |ai-1 ,aiD, i=2,...,n ,设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 性表中的位序基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,, ADT List,InitList( ,2依值性表LA中进行查访;,3若不存在，则插入之GetElem(LB, i)e,LocateElem(LA, e, equal( )),ListInsert(LA, n+1, e),操作步骤：,4重复上述过程，直到访问到LB中所有元素。

GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之,void union(List ,for (i = 1; i <= Lb_len; i++) ,, // union,,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素仍选用线性表表示集合例 2-2,集合 B,集合 A,,从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上,,因此，算法的策略应该和例2-1相同,void union(List // union,GetElem(Lb, i, e); // 取Lb中第 i 个数据元素赋给 e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之,for (i = 1; i <= Lb_len; i++) ,InitList(La); // 构造(空的)线性表LA,2.2 线性表类型 的实现----顺序映象,最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。

顺序映象, 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,,,,,,,,,,,,,以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址,在C语言中，一维数组的机内表示就是顺序结构因此，可用C语言的一维数组实现线性表的顺序存储顺序映像的 C 语言描述,typedef struct SqList; // 俗称 顺序表,ElemType *elem; // 存储空间基址,int length; // 当前长度,int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位),typedef struct ElemType listMaxSize; int size; SqList; /* MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size MaxSize，SqList是该结构体的名字。

/,线性表的基本操作在顺序表中的实现,InitList( if (!L.elem) exit(OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE return OK;,,,,线性表操作 LocateElem(L, e, compare()) 的实现,先看一下查找的过程:,例如：顺序表,e =,38,i,1,2,3,4,1,8,50,,,,,,可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) // 在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回 0 // LocateElem_Sq,O( ListLength(L) ),算法的时间复杂度为：,i = 1; // i 的初值为第 1 元素的位序 p = L.elem; // p 的初值为第 1 元素的存储位置,while (i <= L.length ,if (i <= L.length) return i; else return 0;,(*compare)(*p++, e),,线性表操作 ListInsert( p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; // 表长减1 return OK;,算法时间复杂度为:,O( ListLength(L)),p = // 表尾元素的位置,if ((i L.length)) return ERROR; // 删除位置不合法,元素左移,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,若假定性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,,问题： 、在顺序表中，第个元素前面插入一个元素，要移动多少个元素？ 、在顺序表中，要删除第个元素，要移动多少个元素？,作业: 用C语言编写代码,实现顺序表里面所有的操作。

2.3 线性表类型 的实现---链式映象,一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、静态链表,五、其它形式的链表,,,主要内容:,一、单链表,二、线性表的操作在单链表中的实现,,,重点:,线性表的操作在单链表中的实现: 包括在单链表中查找、插入、删除 一个元素以及生成一个单链表的算法,,,难点:,用一组地址任意的存储单元存放线性表中的数据元素一、单链表,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针头结点,,头指针,头指针,,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针空指针,线性表为空表时， 头结点的指针域为空,,,,Typedef struct LNode ElemType data; // 数据域 struct LNode *next; // 指针域 LNode, *LinkList;,二、结点和单链表的 C 语言描述,LinkList L； // L 为单链表的头指针,,三、单链表操作的实现,GetElem(L, i, e) // 取第i个数据元素,ListInsert( j = 1; // p指向第一个结点，j为计数器,while (jnext; ++j; // 顺指针向后查找，直到 p 指向第 i 个元素 // 或 p 为空,e = p-data; // 取得第 i 个元素 return OK;,,p // 第 i 个元素不存,线性表的操作 ListInsert( j = 0; while (p // i 大于表长或者小于1,,Status GetElem_L(LinkList L, int i, ElemType j = 1; // p指向第一个结点，j为计数器,while (jnext; ++j; // 顺指针向后查找，直到 p 指向第 i 个元素 // 或 p 为空,e = p-data; // 取得第 i 个元素 return OK;,,p // 第 i 个元素不存,Status ListInsert_L(LinkList L, int i, ElemType e) // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e // LinstInsert_L,算法的时间复杂度为:,O(ListLength(L)),,p = L; j = 0; while (p // i 大于表长或者小于1,,s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s-data = e; s-next = p-next; p-next = s; // 插入 return OK;,,,,s,p,,,,线性表的操作ListDelete ( p-next = q-next; e = q-data; free(q);,,p,,q,,,,Status ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next // 删除位置不合理,q = p-next; p-next = q-next; // 删除并释放结点 e = q-data; free(q); return OK;,,,操作 ClearList(,算法时间复杂度：,O(ListLength(L)),,如何从线性表得到单链表？,链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。

例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表操作步骤：,一、建立一个“空表”；,二、输入数据元素an， 建立结点并插入；,三、输入数据元素an-1， 建立结点并插入；,,,,,,,,,,,,,,,,an,,,,,,,,,,an,,an-1,,,,,,四、依次类推，。