《华师本科生数据结构课件 第2章 线性表》由会员分享，可在线阅读，更多相关《华师本科生数据结构课件 第2章 线性表（89页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,线性表是最简单、也是最基本的一种线性数据结构。其存储表示法主要有两种：顺序存储结构和链式存储结构。这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学习理解和掌握。,学习的意义：,2.1 线性表的类型定义 2.4 有序表 2.1.1 线性表的定义 2.5 顺序表和链表的综合比较 2.1.2 线性表的基本操作 2.2 线性表的顺序表示和实现
2、2.2.1 顺序表线性表的顺序存储表示 2.2.2 顺序表中基本操作的实现 2.2.3 顺序表其他算法举例 2.3 线性表的链式表示和实现 2.3.1 单链表和指针 2.3.2 单链表的基本操作 2.3.3 单链表的其他基本操作 2.3.4 循环链表 2.3.5 双向链表,主要内容：,线性表是n 个类型相同数据元素的有限序列，表中相邻的数据元素之间存在“序偶”关系。通常记作（a1, a2, a3, , an ）。,姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .,2. 1 线性表的类型定义,例1、数学
3、中的数列（11，13，15，17，19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某单位的电话号码簿。,2.1.1 线性表的定义,2.1.1 线性表的定义,特性：设 A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一线性表 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一 类型的； 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前驱，ai+1 是ai 的直 接后继； 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有 一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据
4、结构 称为线性结构。线性表是一种线性数据结构； 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表 中的位置，仅取决于它的序号；,2.1.1 线性表的定义,1、 二元组表示 L = ，其中：D = a1，a2，a3，, .， an S = R R = , , ,线性表的其他表示方式:,2.1.2 线性表的基本操作,1. 初始化线性表L InitList( GetElem(L,i,e) PriorElem(L,x, InitList (,for (k = 1; k = Lb_len, found; k+) G
5、etElem (Lb, k, e); i = LocateElem (Lc, e); if (i = 0) found = FALSE; else ListDelete ( ,算法中构造的线性表Lc是一辅助结构，它的引入是为了在程序执行过程中不破坏原始数据La，因此算法的最后应销毁Lc！,如果不使用辅助结构Lc，那算法又如何设计呢？,2.1.2 线性表的基本操作,【例2-4 】判别两个集合A和B是否相等。,【方法二 】_不使用辅助结构Lc （1）若线性表La和线性表Lb的长度不等，则返回两集合不等； （2）对Lb中的每个数据元素，在La中进行查询； （3）若La中不存在与该数据元素相同的数据元
6、素，则返回两集合不等； （4）重复（2）和（3）步，直到Lb中的数据元素都遍历完为止； （5）返回两集合相等。,2.1.2 线性表的基本操作,【例2-4 】判别两个集合A和B是否相等。,【具体算法 】_方法二 bool isequal (List La, List Lb) if ( ListLength(La) != ListLength(Lb) ) return (FALSE); Lb_len = ListLength (Lb); for (k = 1; k= Lb_len; k+) GetElem (Lb, k, e); i = LocateElem (La, e); if (i = 0)
7、 return (FALSE); return (TRUE); ,该算法的正确性是因为集合中不存在两个相同的元素！,为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,通常线性表有两种存储表示方法：顺序存储表示和链式存储表示。,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,线性表（a1,a2, a3, . an ） 的顺序存储结构,用顺序存储结构存储的线性表称为顺序表,2.2 线性表的顺序表示和实现,2.2.1 顺序表线性表的顺序存储表示,2.2.1 顺序表线性表的顺序存储表示,说明： 在顺序存储结构下，线性表元素之间的逻辑
8、关系，通过元素的存储顺序反映（表示）出来； 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i 1) t,2.2.1 顺序表线性表的顺序存储表示,可用C语言中的一维数组来表示,但数组不是线性表,因为线性表的长度可变。数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定.如: #define MAX 100 int vMAX;,2.2.1 顺序表线性表的顺序存储表示,顺序表的类型定义#define LIST_INIT_SIZE 100 / 线性表存储空间的初
9、始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef struct ElemType * elem; /线性表存储空间基址(一维数组) int length; /当前线性表长度 int listsize; /当前分配的线性表存储空间大小 int incrementsize; /约定增补空间量(以ElemType为单位) SqList;,SqList ：类型名， SqList类型的变量是结构变量，它的四个域分别是： *elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配； length：存放线性表的表长； listsi
10、ze：用于存放当前分配（存放线性表元素）的存储空间的大小。 incrementsize：约定增补空间量（当线性表空间不够时）,2.2.1 顺序表线性表的顺序存储表示,存放线性表元素 的一维数组,设 A = （a1,a2 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,顺序表通过 元素的存储顺序 反映线性表元素间的逻辑关系,L.elem L.lenght L.Listsize L.incrementsize,n 99,10,功能：构造一个空的顺序表。 方法：首先要按需为其动态分配一个存储区域，然后设其当前长度为。,2.2.2
11、 顺序表中基本操作的实现,、初始化操作,算法: void InitList_Sq (SqList /需要扩容时每次可增加的元素个数 ,等价于：L.elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof(ElemType),功能：在顺序表L中查找其值与给定值e相等的数据元素的位序，如果未找到，则返回0。 方法：从第一个元素起，依次和e相比较，直到找到一个其值与e相等的数据元素，则返回它在线性表中的“位序”；或者查遍整个顺序表都没有找到其值和e相等的元素后返回0。,2.2.2 顺序表中基本操作的实现,2、查找元素操作,算法: （书本上的写法） int
12、 LocateElem_Sq (SqList L, ElemType e) i = 1; /i初始值为第一个元素的位序 p = L.elem; /p的初值为第一个元素的存储位置 while (i = L.length /该线性表中不存在满足判定的数据元素 ,算法: （另一种写法） int LocateElem_Sq (SqList L, ElemType e) for (i = 0; i L.length; i+) if (L.elemi = e) return (i+1); return (0); ,注意：位序是从1到L.length!,功能：在顺序表L 中的第 i ( 1iL.length
13、+1)个数据元素之前插入一个新元素x。 插入前线性表为： (a1, a2, a3, ai-1 ,ai, an ) 插入后，线性表长度为L.length+1, 线性表为： (a1, a2, a3, ai-1 , x, ai, an ),2.2.2 顺序表中基本操作的实现,、插入元素操作,2.2.2 顺序表中基本操作的实现,插入前,插入后,_插入操作示意图,、插入元素操作,一般情况下，在顺序表中第i个元素之前插入一个新的元素时，首先需将L.elemL.length-1至L.elemi-1依次往后移动一个位置。显然，此时顺序表的长度应该小于数组的最大容量；否则，在移动元素之前，必须先为顺序表“扩大数
14、组容量”。,2.2.2 顺序表中基本操作的实现,、插入元素操作,算法: void ListInsert_Sq (SqList /表长增1 ,void increment (SqList ,可用realloc (L.elem, (L.listsize+L.incrementsize)*sizeof(ElemType);来代替,void ErrorMessage (char *s) cout s endl; /printf (“%sn”, s); exit (1); ,一般情况下，当插入位置i=L.length+1时，for循环的执行次数为0，即不需要移动元素；反之，若i=1，则需将顺序表中全部（
15、n个）元素依次向后移动。然而，当顺序表中数据元素已占满空间时，不论插入位置在何处，为了扩大当前的数组容量，都必须移动全部数据元素，因此，从最坏的情况考虑，顺序表插入算法的时间复杂度为O(n)，其中n为线性表的长度。,删除算法的主要步骤: 1）若i 不合法或表L空，算法结束，并返回 0；否则转2） 2）将第i个元素之后的元素（不包括第i个元素）依次向前移动一个位置; 3）表长 - 1,2.2.2 顺序表中基本操作的实现,功能：在顺序表L 中删除第 i ( 1iL.length)个数据元素。 删除前线性表为： (a1, a2, a3, ai-1 ,ai, ai+1, an ) 删除后，线性表长度为L.length-1, 线性表为： (a1, a2, a3, ai-1 , ai+1, an ),4、删除元素操作,一般情况下，从顺序表中删除第i个元素时，需将L.elemi至L.elemL.length-1的元素依次往前移动一个位置。,2.2.2 顺序表中基本操作的实现,、删除元素操作,算法: void ListDelete_Sq (SqList /表长减1 ,等价于： e = L.elemi-1; mem
