《《数据结构实用教程（C语言版）》-董凤服-电子教案及算法 电子教案 第2章 线性表》由会员分享，可在线阅读，更多相关《《数据结构实用教程（C语言版）》-董凤服-电子教案及算法 电子教案 第2章 线性表（69页珍藏版）》请在金锄头文库上搜索。
1、,数据结构实用教程（C语言版） 中国水利水电出版社,第2章 线性表,本章主要介绍下列内容 线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例,本章目录,结束,2.1 线性表的基本概念,2.1.1 线性表的定义 2.1.2 线性表的基本操作,返回到总目录,2.1.1 线性表的定义,1. 线性表的定义 线性表是具有相同数据类型的n（n=0）个数据元素的有限序列，通常记为： （a1，a2， ai-1，ai，ai+1，an） 其中n为表长，当n=0时称为空表。 在线性表中相邻元素之间存在着顺序关系。如对于元素ai 而言，ai-1 称为 ai 的直接前驱，ai+1 称为
2、 ai 的直接后继。,返回到本节目录,2. 线性表的特点 （1）有且仅有一个开始结点（a1），它没有直接前驱； （2）有且仅有一个终端结点（an），它没有直接后继； （3）除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。,2.1.1 线性表的定义,返回到本节目录,2.1.2 线性表的基本操作,数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。下面定义的线性表的基本操作仅是定义在逻辑结构上的，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。 线性表的基本操作有： （1）初始化线性表InitList(L)。 其作用是建立一个空表
3、L（即建立线性表的构架，但不包含任何数据元素）。,返回到本节目录,（2）求线性表的长度GetLength(L)。其作用是返回线性表L的长度（即所含数据元素的个数）。 （3）求线性表中第i个元素GetElem(L,i,x)。其作用是在1iGetLength(L)返回成功，并用x存储线性表L的第i个元素的值。 （4）按值查找操作Locate(L,x)。在线性表L查找一个与给定值x相等的数据元素，其作用是若存在一个或多个与x相等的数据元素，则返回的元素所在位置的最小值或地址值；否则返回0或NULL值。,2.1.2 线性表的基本操作,返回到本节目录,（5）插入操作InsElem(L,i,x)。其作用是
4、在线性表L的第i个位置上插入一个值为 x 的新元素，使线性表L由（a1，a2， ai-1，ai，ai+1，an）变为（a1，a2， ai-1，x，ai，ai+1，an）。其中1iGetLength(L)+1。 （6）删除操作DelElem(L,i,x)。其作用是删除线性表L的第i个位置的数据元素并用x将其存储，使线性表L由（a1，a2， ai-1，ai，ai+1，an）变为（a1，a2， ai-1，ai+1，an）。其中1iGetLength(L)。 （7）输出元素值DispList(L)。其作用是依次扫描线性表L，并输出各元素的值。,2.1.2 线性表的基本操作,返回到本节目录,2.2 顺序
5、表,2.2.1 顺序表 2.2.2 顺序表的基本操作实现,返回到总目录,1. 顺序表的定义 数据结构在内存中的表示通常有两种形式，即顺序存储表示和链式存储表示。线性表的顺序存储表示又称为顺序表。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。 假设顺序表(a1，a2， ai-1，ai，ai+1，an)，每个数据元素占用d个存储单元，则元素ai的存储位置为： Loc(ai)= Loc(a1)+(i-1)d 1in,2.2.1 顺序表,返回到本节目录,其中，Loc(a1)是顺序表第一个元素a1的存储位置，通称为顺序表的起始地址。顺序
6、存储结构示意图如图2-1所示。 顺序表的存储特点： （1）顺序表的逻辑顺序和物理顺序是一致的。 （2）顺序表中任意一个数据元素都可以随机存取，所以顺序表是一种随机存取的存储结构。,2.2.1 顺序表,返回到本节目录,2. 顺序表的类型定义 #define MAXLEN 100 /*定义常量MAXLEN为100表示存储空间总量*/ #define OK /*定义常量OK为1表示成功*/ #define ERROR 0 /*定义常量ERROR为0表示失败*/ #define OVER -1 /*定义常量OVER为-1表示结束*/ typedef int ElemType; /*定义ElemType
7、为int类型*/ typedef struct /*顺序表存储类型*/ ElemType dataMAXLEN; /*存放线性表的数组*/ int Length; /*Length是顺序表的长度*/ SeqList;,2.2.1 顺序表,返回到本节目录,2.2.2 顺序表的基本操作实现,1顺序表的初始化 顺序表的初始化即构造一个空顺序表L，将表L的实际长度置0，算法描述见算法2.1。 算法2.1 void InitList( SeqList *L ) L-Length=0; /*初始的化顺序表为空*/ ,返回到本节目录,2顺序表的建立 初始化顺序表后向表中输入n个元素建立表L，算法描述见算法2
8、.2。 算法2.2 void CreateList(SeqList *L,int n) int i; printf(“请输入各个元素值：n“); for(i=0;idatai); L-Length=i; ,2.2.2 顺序表的基本操作实现,返回到本节目录,3求顺序表的长度操作 返回顺序表L的Length值，算法描述见算法2.3。 算法2.3 int GetLength(SeqList *L ) return L-Length ; 4查找操作 顺序表的查找分为按值与按序号查找，下面将分别介绍这两种方法的实现，读者可根据具体的问题相应选择所需的查找方法。,2.2.2 顺序表的基本操作实现,返回到本
9、节目录,（1）按号查找 查找顺序表中第i个元素的值，在i无效时返回出错，有效时返回成功，并用x存储第i个元素的值，算法描述见算法2.4。 算法2.4 int GetElem(SeqList *L, int i, ElemType *x) if (iL-Length) return ERROR; else *x = L-datai-1; return OK; ,2.2.2 顺序表的基本操作实现,返回到本节目录,2）按值查找操作 顺序表中的按值查找是指在顺序表中查找与给定值x相等的数据元素的所在位置，算法描述见算法2.5。 算法2.5 int Locate(SeqList *L, ElemType
10、 x) int i=0; while(i Length /*返回的是元素位置*/ ,2.2.2 顺序表的基本操作实现,返回到本节目录,2.2.2 顺序表的基本操作实现,5插入操作 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长增1，原顺序表如图2-2所示。,返回到本节目录,5插入操作,步骤如下： (1) 将anai 之间的所有结点依次后移，为新元素让出第i个位置，如图2-3所示。,返回到本节目录,5插入操作,步骤如下： (2) 将新结点x插入到第i个位置，如图2-4所示。 (3) 顺序表的长度增1，插入成功，并返回，算法描述见算法2.6。,返回到本节目录,5插入操
11、作,算法2.6 int InsElem(SeqList *L, int i, ElemType x) int j; if (L-Length=MAXLEN) printf (“顺序表已满！“); return OVER; /*表满，不能插入*/ if (iL-Length+1) /*检查给定的插入位置的正确性*/ printf(“插入位置出错！“); return ERROR; if (i = L-Length+1) L-datai-1=x; L-Length+; return OK; /*插入的位置为表尾，则不需移动直接插入即可*/ for (j=L-Length-1; j=i-1; j-)
12、 /*结点移动*/ L-dataj+1=L-dataj; L-datai-1=x; /*新元素插入*/ L-Length+; /*顺序表长度增1 */ return OK; /*插入成功，返回*/ ,返回到本节目录,5插入操作,插入算法的时间性能分析： 顺序表插入操作大约需移动表中一半数据元素，其时间复杂度为(n)。,返回到本节目录,2.2.2 顺序表的基本操作实现,6. 删除操作 线性表的删除操作是指将第 i 个元素从顺序表中去掉，删除后顺序表表长减1，原顺序表如图2-5所示。,返回到本节目录,6. 删除操作,步骤如下： (1) 将要删除的元素值赋给指针变量*x，如图2-6所示,返回到本节目
13、录,6. 删除操作,步骤如下： (2) 将ai+1an 之间的结点依次顺序向前移动，如图2-7所示。 (3) 顺序表的长度减1，删除成功，并返回，算法描述见算法2.7。,返回到本节目录,6. 删除操作,算法2.7 int DelElem (SeqList *L, int i, ElemType *x) int j; if (L-Length=0) printf (“顺序表为空！“); return ERROR; /*表空，不能删除*/ if (iL-Length) /*检查是否空表及删除位置的合法性*/ printf (“不存在第i个元素“); return ERROR; *x= L-data
14、i-1; /*用指针变量*x返回删除的元素值*/ for(j=i;jLength-1;j+) /*结点移动*/ L-dataj-1=L-dataj; L-Length-; /*顺序表长度减1*/ return OK; /*删除成功，返回*/ ,返回到本节目录,6. 删除操作,删除算法的时间性能分析： 与插入操作相同，其时间主要消耗在了移动表中元素上，（大约需要移动表中一半的元素），显然该算法的时间复杂度为(n)。,返回到本节目录,2.2.2 顺序表的基本操作实现,7 顺序表的输出操作 扫描顺序表L，输出各元素的值，算法描述见算法2.8。 算法2.8 void DispList(SeqList
15、*L) int i; for(i=0;iLength;i+) printf(“%5d “, L-datai); ,返回到本节目录,2.3 链表,2.3.1 单链表 2.3.2 单链表的基本操作实现 2.3.3 链表的变形,返回到总目录,2.3.1 单链表,1. 单链表的定义 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息，这样构成的链表称为线性单向链接表，简称单链表，其结点结构如图2-8所示。,图2-8 单链表的结点示意图,其中，data部分称为数据域，用于存储一个数据元素（结点Node）的信息。next部分称为指针域，用于存储其直接后继的存储地址的信息。,返回到本节目录,2.3.1 单链表,单链表分为带头结点（其next域指向链表第一个结点的存储地址）和不带头结点两种类型。在许多情况
