数据结构讲解剖析.ppt

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示和相加 2.1 线性表的类型定义 一、线性表的定义 线性表是一个由n(n≧0)个同类型的数据元素a1，a2， …an组成的有限序列。通常记为： (a1，a2，…ai-1, ai, ai+1,…an) 其中：数据元素的个数n为表的长度。 当n=0时称为空表。 这里的数据元素ai(1≦i≦n) 表示线性表中第i个数据元素，它可以是任意类型。 2.1 线性表的类型定义 例1：26个英文字母组成的字母表 （A，B，C、…、Z） 是一个长度为26的线性表。 例2：某公司2000年每月产值表(单位：万元) （400，420，500，…，600，650） 是一个长度为12的线性表。 上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成。 2.1 线性表的类型定义 例3：下图为10个学生的成绩表,它也是一个 线性表,该线性表的数据元素类型为结构体。 2.1 线性表的类型定义 二、线性表的逻辑特征 在非空的线性表中，有且仅有一个被称作“第一个”的数据元素a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个被称作“最后一个”的数据元素an，它没有直接后继，而仅有一个直接前趋 an-1； 其余的数据元素ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。 2.1 线性表的类型定义 三、线性表的形式定义 L_List=(D,R) D={ ai| ai∈ElemSet,i=1,2, …，n n≥0} R={ai-1，ai| ai-1，ai∈D, i=2, …，n} ElemSet为某一数据对象集，即数据元素的集合；n为线性表的长度。 2.1 线性表的类型定义 四、线性表的主要操作(库函数中没有，需要用户自己实现) 1．Initiate(L) 初始化：构造一个空的线性表L。 2．Insert(L,i,x) 插入：在给定的线性表L中，在第i 个元素之前插入数据元素x。线性表L长度加1。 3．Delete(L,i) 删除：在给定的线性表L中，删除第i个元素。线性表L的长度减1。 4．Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回－1。 2.1 线性表的类型定义 5．Length(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。 6．Get(L,i,e) 存取：对给定的线性表L，返回第i (1≤i≤Length(L))个数据元素e。 7．Traverse(L) 遍历：对给定的线性表L，依次输出L的每一个数据元素。 …… 2.2 线性表的顺序表示和实现 一、线性表的顺序存储表示 在计算机中，用一段地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。用这种方法存储的线性表简称顺序表。 线性表的顺序存储结构中的特点是：其逻辑关系上前后相邻的两个数据元素，在计算机中的存储位置也必定是相邻的。即ai+1一定存在ai的下一个存储单元中。 线性表的顺序存储结构示意图如下： 2.2 线性表的顺序表示和实现 线性表的顺序存储结构示意图 2.2 线性表的顺序表示和实现 由于线性表中每个数据元素的类型相同，占用的内存空间也相同。因此，假设线性表中的第一个数据元素的存储地址为Loc(a1)，设每一个数据元素占用d字节的内存空间，则线性表中第i个元素 ai 在这段连续的存储空间中的存储地址为： Loc(ai)= Loc(a1)+(i-1)*d 2.2 线性表的顺序表示和实现 1、线性表的静态分配顺序存储结构 #define MAXNUM 100 /*定义顺序表最大元素个数*/ ElemType List[MAXNUM] ; /*定义顺序表List。注意 ：ElemType代表线性表元素的类型，具体编