《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊 数据结构-第三章》由会员分享，可在线阅读，更多相关《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊 数据结构-第三章（94页珍藏版）》请在金锄头文库上搜索。
1、数据结构 C+实现 第三章 缪淮扣 顾训穰 沈 俊 编著 科 学 出 版 社,新世纪计算机专业系列教材,第三章 线性表,3.1 线性表的定义 线性表(linear-list)是最常用最简单的一种数据结构。一个线性表是n (n0)个相同类型数据元素的有限序列。记为： L= (a1, a2 , , an ) 其中，L是表名，a1是第一个数据元素（也简称为元素），无前驱，有一个后继；an是最后一个数据元素(即第n个数据元素)，有一个前驱，无后继。其余的每个数据元素ai (i=2,3, ,n-1)都只有一个前驱，且只有一个后继。i (i=1,2, ,n)称为表的序号。n是数据元素的个数，也称为表的长度
2、，若n=0，L称作空表。,两个例子都是线性表： 某班级学生的数据库课程的成绩： (72，65，83， 94，87，98，57) 某车间职工的编号：(“0108”， “0110”， “0122”， “0132“， “0718“) 在稍复杂的线性表中，一个数据元素可能是由若干个数据项组成的。 例如在例1-1给出的“人事登记表”中，每一个职工的信息就是一个数据元素，它是由“编号”、“姓名”、“性别”、“出生日期”、“婚否”和“基本工资”六个数据项组成的。,线性表的基本操作主要有： (1) 初始化：设定一个空的线性表L。 (2) 求长度：线性表L中数据元素的个数len。 (3) 取元素：取线性表L中序
3、号为i的数据元素， 若1ilen，则函数值为线性表L中第i个数据元素，否则为NULL。 (4) 定位：给定值item，若线性表L中有数据元素等于item，则返回该数据元素的序号，若有多个数据元素等于item，则返回最小的序号，若无数据元素等于item，则返回0。,(5) 插入：在线性表L的第i个数据元素之前插入一个新元素item，这里1ilen+1，当i = len+1时，即在线性表L的表尾插入(即追加)新元素，插入成功返回1，不成功返回0。 (6) 删除：删除线性表L的第i个元素。当 1ilen时，删除成功，返回被删元素的值，否则返回NULL。 (7) 是否是空表：线性表L为空，则返回值1，
4、否则返回值0。 (8) 表清空：将线性表L设置为空表，即len = 0。 对线性表的操作还有很多，像取前驱、取后继、排序等等。,3.2 线性表的顺序表示,用顺序存储方式存储的线性表称为顺序表。 顺序表的特点是： 顺序表是计算机中一种最基本和最主要的存储结构。 一块地址连续的有限空间存放表中的数据元素。 任意两个逻辑上相邻的数据元素在物理上也必然相邻。 顺序表中的每个表项都是单个数据元素，所有表项的 数据类型相同。 顺序表可以随机访问。 顺序表通常用数组存储，在C+中，数组有静态数组和动态数组两种，对于顺序表，我们将采用静态数组方式存储。,3.2.1 顺序表的类定义,顺序表的抽象数据类型的描述：
5、 ADT seqlist is Data 线性表的长度；若干个相同类型的数据元素组成的表 Operation seqlist 初始化值：无 动作： 置顺序表的长度为0 length 输入： 无 前置条件：无 动作： 读线性表的长度 输出： 线性表的长度 后置条件：无,get 输入： 表的序号i 前置条件：序号i大于或等于1，并且小于或等于表的长度 动作： 取序号为i的数据元素 输出： 如果是合法序号，则返回表的第i个数据元素；否则，返回NULL。 后置条件：无 locate 输入：要定位的项item 前置条件：无 动作：在表中查找item 输出：如果找到，则返回item在表中的位置，否则返回0
6、 后置条件：无,insert 输入： 要插入的项item和序号i 前置条件：表未满，并且i未越界 动作： 在序号i处插入项item 输出： 若插入成功返回1；否则输出0 后置条件：表中增加了一个新元素，长度加1 delete 输入： 序号i 前置条件：表非空，并且i未越界 动作： 删除序号为i的数据元素 输出：若删除成功，则返回被删元素的值；否则返 回 NULL 后置条件：表中减少了一个元素，长度减1,empty 输入： 无 前置条件：无 动作： 检查表的长度 输出： 表为空时返回1，否则返回0 后置条件：无 clear 输入： 无 前置条件：无 动作： 清空顺序表 输出： 无 后置条件：表的
7、长度是0 end ADT seqlist,顺序表的类定义及顺序表的8个基本操作的实现 一个顺序表涉及的数据成员包括数组、数组所允许的最多元素的个数和当前数组元素的个数，它们被封装在类的私有域中。 # include /定义在头文件seqlist.h中 # include const int maxlen = 100 ; /maxlen是顺序表中最大项数 class seqlist private : datatype datamaxlen ; /抽象类型datatype定义的数组 int len; /数据元素个数,public: seqlist(void); /构造函数，初始化表 seqlis
8、t(void); /析构函数 int length (void) const; /返回线性表的长度 datatype get (int i ) const; /返回第i个数据元素 int locate(datatype / 构造函数。初始化表，置顺序表的长度为0 seqlist:seqlist(viod):len(0),/析构函数 seqlist:seqlist(void) /返回顺序表的长度 int seqlist:length(void) const return len; /取线性表的第i个数据元素，即C+中数组的第i-1个数据元素 datatype seqlist:get(int i
9、) const if ( i =1 ,/返回数据元素item在表中的位置 int seqlist:locate(datatype ,/*删除线性表第i个元素(即数组的第i-1个元素)，并返回*/ datatype seqlist:dele(const int i ) if ( len = 0 ) return NULL; /空表不能删除 if ( ilen ) return NULL; /删除的元素越界 datatype t = datai-1; for ( int j = i ; j len ; j+ )dataj-1 = dataj ; /从第i+1个元素开始依次左移 len-; retu
10、rn t; ,/判断表是否为空表 int seqlist:empty(void) const if ( len = 0 ) return 1; return 0; /清空顺序表 void seqlist:clear(void) len=0; ,3.2.2 顺序表插入、删除算法的 复杂度分析,通常顺序表的插入和删除操作都会保持各元素原来的顺序不变。 举例来看顺序表上的插入和删除，如图3-1和图3-2。 图3-1是在原来已有7个元素的表的第4个元素前插入数据元素x=24的过程。 图3-2是在原来已有8个元素的顺序表中删除第4个元素的过程。,在顺序表中插入一个数据元素时，算法中时间复杂度最高的部分是
11、循环移动数据元素的操作。插入时，是从后向前循环右移数据元素，而循环移动数据元素的次数和插入数据元素的序号有关，最好的情形是在序号n+1处插入新元素(即追加)，移动元素个数为0，最坏情形是在序号1处插入新元素，移动元素个数为n；一般情形逐个移动n-i+1个元素。若在顺序表的任何位置上插入数据元素的概率相等，即为1/(n+1)，数据元素移动的平均次数为：,在顺序表中删除一个数据元素时，是从删除位置向后循环左移数据元素，一般情形逐个移动ni个数据元素。若在顺序表的任何位置上删除数据元素的概率相等(1/n)，数据移动的次数平均为：,因此，顺序表中插入和删除一个数据元素的时间复杂度为O(n)。 定位一个
12、数据元素的时间复杂度为O(n)。其余操作的时间复杂度均为O(1)。,在顺序表的插入和删除操作中，若不需保持数据元素原来的顺序，此时可采用下图3-3 、图3-4所示的方式移动数据元素。 在插入时，把新元素插入到表尾，如图3-3所示。,在删除时，把表中的最后一个数据元素移来覆盖被删元素，如图3-4所示。在这种情形下，插入时移动0个数据元素，删除时移动1个数据元素。,3.2.3 顺序表的应用,例3-1 利用上面介绍的顺序表seqlist，编写一个程序，在屏幕输出“China“。 程序： typedef char datatype; / defined in seqlist.h # include “
13、seqlist.h“ void main(void) seqlist list1; list1.insert(C, 1); list1.insert(h, 2); list1.insert(i, 3); list1.insert(n, 4); list1.insert(a, 5); for (int i=1;i6;i+) cout list1.get(i); cout“n“; ,3.3 线性表的链表表示,线性表的顺序存储方式的缺陷: 顺序表是用数组方式来存储的，因数组元素个数固定。当顺序表的长度等于数组的元素个数时，顺序表就不能再插入新数据元素了。 对于有n个数据元素的顺序表，若要保持各数据元
14、素原来的顺序不变，则插入和删除一个数据元素的时间复杂度为O(n)。 顺序表要求存储空间是物理上连续的，这样即使存储空间中的存储单位数超过所需的数目，却因其不连续，也无法使用。 克服这些缺陷的办法是：对线性表采用链表存储方式。,在链表存储方式中，用户通过new函数向系统动态申请所需的存储空间，把数据元素插入链表中合适的位置，而这些在不同时刻向系统动态申请的存储空间在内存中很可能不连续。 因而，任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链表中的指针链接实现的。 链表的表长是动态的、可扩充的，在链表中插入和删除时不需移动元素。 用链表存储方式存储线性表数据元素的方法是
15、用结点(node)构造链。结点通常有一个数据域，另外还有一个或一个以上的指针域。 链表存储主要有单链、单循环链和双向链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。,3.3.1 单链表,1. 单链表的结构 采用链接存储方式存储的线性表称为线性链表，又称单链表(linked list)，或简称为链表。在单链表中，每一个数据元素占用一个结点。如图3-5所示。一个结点由两个域组成，一个域存放数据元素data，一个域存放指向该链表中下一个结点的指针next，它给出下一个结点的开始存储地址。,在单链表的表尾结点中，指针域为空以“”表示之。 设线性表存有某系99级学生的学号如下： (99101，99104，99110，99201，99208) 可用如图3-6所示的单链表表示。,单链表结构中又有带头结点和不带头结点两种结构。像图3-6这样的第一个结点就是数据结点的单链表结构，我们称其为不带头结点的单链表。,3-7是带头结点的单链表结构，头结点是由头指针所指向的不存放数据元素的结点。我们把头结点的数据域部分涂上阴影，以明显表示该结点为头结点。,单链表使得插入和删除变得很方便。 对于不带头结点的单链表的插入：希望在单链表(a1, a2 , , an )的第i 个结点前插入一个新元素x，那么可能会出现三种情况。 (1) 若i =1即ai 是链表
