《软件技术基础概论 教学课件 ppt 作者 吕林涛第2章 线性表》由会员分享，可在线阅读，更多相关《软件技术基础概论 教学课件 ppt 作者 吕林涛第2章 线性表（52页珍藏版）》请在金锄头文库上搜索。
1、22:30:42,第2章 线性表,线性表是最简单、最基本、最常用的一种线性结构。它在很多领域，尤其是在程序设计语言和程序设计过程中被大量使用。 本章介绍线性表的基本概念及其逻辑结构和存储结构，并针对不同存储结构给出实现线性表的建立以及在线性表中插入、删除和查找的算法 。,本章内容提要: 线性表及其逻辑结构 线性表的顺序存储结构及运算实现 线性表的链式存储结构及运算实现,2.1 线性表及其逻辑结构,线性表的定义,线性表的基本操作,一个线性表是n个元素的有限序列，其特点是在数据元素的非空集合中： （1）存在唯一一个称为“第一个”的元素。 （2）存在唯一一个称为“最后一个”的元素。 （3）除第一个元
2、素之外，序列中的每一个元素只有一个直接前驱。 （4）除最后一个元素之外，序列中的每一个元素只有一个直接后继。,线性表的定义,线性表的定义为：具有相同数据类型的n（n0）个数据元素的有限序列，通常记为（a1, a2, , ai-1, ai, ai+1, , an），其中，n为表长，n=0时称为空表。 线性表中相邻元素之间存在着顺序关系：ai-1称为ai的直接前驱，ai+1称为ai的直接后继； 对于ai，当i=2，n时，有且仅有一个直接前驱ai-1；当i=1，2，n-1时，有且仅有一个直接后继ai+1； a1是表中的第一个元素，它没有前驱； an是表中的最后一个元素，它没有后继。 对非空线性表，数
3、据元素ai在表中的位置仅取决于元素ai本身的序号i。,线性表的定义,线性表的特征如下： （1）均匀性：线性表中每个数据元素的长度、大小和类型都相同。 （2）有序性：线性表中各数据元素是有序的，且各数据元素之间的次序是不能改变的。,线性表的定义,2.1 线性表及其逻辑结构,线性表的定义,线性表的基本操作,数据结构的运算是定义在逻辑结构层面上，而运算的具体实现则建立在存储结构上。因此，线性表基本运算是作为逻辑结构的一部分，并且每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。对线性表实施的基本操作有如下几种 。,线性表的基本操作,2.2 线性表的顺序存储结构及运算实现,线性表的顺序存储
4、,顺序表基本运算的实现,线性表的顺序存储是用一组地址连续的存储单元按顺序依次存放线性表中的每一个元素（数据元素），这种存储方式存储的线性表称为顺序表。在这种顺序存储结构中，逻辑上相邻的两个元素在物理位置上也相邻；也即无需增加额外存储空间来表示线性表中元素之间的逻辑关系。 由于顺序表中每个元素具有相同的类型，即其长度相同，则顺序表中第i个元素ai的存储地址为 Loc(ai)=Loc(a1)+(i-1)L （1in） 其中，Loc(a1)为顺序表的起始地址（即第一个元素的地址）；L为每个元素所占存储空间的大小。 因此，只要知道顺序表的起始地址和每个元素所占存储空间的大小，就可以求出任意一个元素的存
5、储地址，即顺序表中的任意一个元素都可以随机存取（随机存取的特点是存取每一个元素所花费的时间相同）。,线性表的顺序存储顺序表,一维数组在内存中占用的存储空间就是一组连续的存储区域，并且每个数组元素的类型相同，故用一维数组来存储顺序表。为了避免元素的序号及其下标的不一致性，我们约定顺序表中的元素存放于一维数组时是从下标为1的位置开始的。 此外，考虑到顺序表的运算有插入、删除等操作，即表长是可变的，因此，数组的容量需要设计得足够大。我们dataMAXSIZE来存储顺序表，而MAXSIZE是根据实际问题所定义的一个足够大的整数。此时顺序表中的数据由data1开始依次存放。由于当前顺序表中的实际元素个数
6、可能还未达到MAXSIZE-1值，因此需要用一个len变量来记录当前顺序表中最后一个元素在数组中的位置（即下标）。这里的len起着一个指针的作用，它始终指向顺序表中的最后一个元素且表空时len=0。,线性表的顺序存储顺序表,从结构上考虑，我们将data和len组合在一个结构体里来作为顺序表的类型： typedef struct datatype dataMAXSIZE; /存储顺序表中的元素 int len; /顺序表的表长 SeqList; /顺序表类型 其中，datatype为顺序表中元素的类型，在具体实现中可为int、float、char类型或其他结构类型；顺序表中的元素可存放在data
7、数组中下标为1MAXSIZE-1的任何一个位置；第i个元素的实际存放位置就是i；len为顺序表的表长。有了顺序表类型，则可以定义如下顺序表和指向顺序表的指针变量： SeqList List, *L；其中，List是一个结构体变量，它内部含有一个可存储顺序表的data数组；,线性表的顺序存储顺序表,L是指向List这类结构体变量的指针变量，如“L=”。在这种定义下，List.datai或L-datai均表示顺序表中第i个元素的值，而List.len或L-len均表示顺序表的表长，两种表示如图所示。,线性表的顺序存储顺序表,2.2 线性表的顺序存储结构及运算实现,线性表的顺序存储,顺序表基本运算的
8、实现,1. 顺序表的初始化 顺序表的初始化就是构造一个空表。将L设为指针变量，然后动态分配顺序表的存储空间，并设表长len=0。 算法如下： SeqList *Init_SeqList() SeqList *L; L=(SeqList*)malloc(sizeof(SeqList); L-len=0; return L; ,顺序表算法实现,2. 建立顺序表 依次输入顺序表的长度n和n个顺序表元素即可建立顺序表。算法如下： void CreatList(SeqList *L) int i, n; printf(“Input length of List: “); scanf(“%d“, ,顺序表
9、算法实现,3.插入运算： 在表的第i个位置插入一个值为x的新元素，使得原表长为n的表变为表长为n+1的表。插入x的过程如下： （1）按an到ai的顺序依次将anai后移一个元素位置，为插入的x让出存储位置。 （2）将x放入空出的第i个位置。 （3）修改表长len的值（len同时是指向最后一个元素的指针），使其指向新的表尾元素。 插入时可能出现下列非法情况： （1）当L-len=MAXSIZE-1，顺序表已放满元素。 （2）当i1或iMAXSIZE时，i已超出数组范围。 （3）当L-len+1iMAXSIZE时，i虽没有超出数组范围，但i指示的位置使得顺序表元素不再连续存放。 （2）、（3）可以
10、用i1或iL-len+1表示。,顺序表算法实现,插入算法如下： void Insert_SeqList(SeqList *L, int i, datatype x) int j; if(L-len=MAXSIZE-1) /表满 printf(“The List is full!n“); else if(iL-len+1) /插入位置非法 printf(“The position is invalid !n“); else for(j=L-len;j=i;j-) /将anai顺序后移一个元素位置 L-dataj+1=L-dataj; L-datai=x; /插入x到第i个位置 L-len+; /
11、表长增1 ,顺序表算法实现,4.删除运算： 将顺序表中第i个元素从表中除去，删除后使原表长为n的顺序表成为表长为n-1的顺序表。删除ai的过程如下： （1）按ai+1到an的顺序依次将ai+1an前移一个元素位置，移动的同时即完成了对ai的删除。 （2）修改len值，使其仍指向表的最后一个元素。 删除时可能会出现下列非法情况： （1）当L-len=0时，顺序表为空而无法删除。 （2）当i1或iL-Len时，i位置上没有元素，即删除位置非法。,顺序表算法实现,删除算法如下： void Delete_SeqList(SeqList *L, datatype i) int j; if(L-len=0
12、) /表为空 printf(“The List is empt !n“); else if(iL-len) /删除位置非法 printf(“The position is invalid !n“); else for(j=i+1;jlen;j+) /将ai+1an顺序前移一个位置实现对ai的删除 L-dataj-1=L-dataj; L-len-; /表长减1 ,顺序表算法实现,5. 查找运算： 在顺序表中查找与给定值x相等的元素。完成该运算最简单的方法是：从第一个元素a1起依次和x比较，直至找到一个与x相等的元素时则返回该元素的存储位置（即下标）；如果查遍整个表都没找到与x相等的元素则返回0
13、值。 算法如下： int Location_SeqList(SeqList *L, datatype x) int i=1; /从第一个元素开始查找 while(ilen /未找到则返回0值 ,顺序表算法实现,查找算法的主要运算是比较。显然，比较的次数与x在表中的位置有关，当ai=x时，对算法需要比较i次，在等概率的情况下，查找成功的平均比较次数为 因此，查找算法的时间复杂度为O(n)。,顺序表算法实现,2.3 线性表的链式存储结构及运算实现,顺序表表示的线性表特点是用物理位置上的邻接关系来表示元素之间的逻辑关系，使我们可以随机存取表中的任意一个元素，但也产生了在插入和删除操作中移动大量元素的
14、问题。 链式存储可用连续或不连续的存储单元来存储线性表中的元素，元素之间的逻辑关系无法用物理位置上的邻接关系来表示，因此，需要用“指针”来指示元素之间的逻辑关系，即通过“指针”链接起元素之间的邻接关系，而“指针”要占用额外存储空间。链式存储方式失去了顺序表可以随机存取元素的功能,但却换来了存储空间操作的方便性：进行插入和删除操作时无需移动大量的元素。 本节将从四个方面介绍线性表的链式存储结构及运算实现。,2.3 线性表的链式存储结构及运算实现,单链表,单链表运算实现,循环链表,单链表应用示例,单链表,在每个元素中除了含有数据信息外，还要有一个指针用来指向它的直接后继元素，即通过指针建立起元素之
15、间的线性关系，我们称这种元素为结点。结点中存放数据信息的部分称为数据域，存放指向后继结点指针的部分称为指针域线性表中的n个元素通过各自结点的指针域“链”在一起又被称为链表。每个结点中只有一个指向后继结点的指针，故称其为单链表。链表是由一个个结点构成的，单链表结点的定义如下： typedef struct node datatype data; /data为结点的数据信息 struct node *next; /next为指向后继结点的指针 LNode; /单链表结点类型 结点结构如图,单链表,线性表（a1, a2, a3, a4, a5, a6）对应的链式存储结构示意如下图所示。将第一个结点的地址200放入到一个指针变量如H中，最后一个结点由于没有后继，其指针域必须置空（NULL）以表明链表到此结束。通过指针H就可以由第一个结点的地址开始“顺藤摸瓜”地找到每一个结点 。,单链表,线性表的链式存储结
