数据结构——用C语言描述（第二版第2章线性表.ppt

1、,第2章 线性表,2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储结构 2.4 线性表存储结构的选择 2.5 线性表的应用举例,从本章开始到第四章讨论的线性表、栈、队列和串的逻辑结构都属于线性结构。在线性结构中，元素之间存在一个对一个的相互关系，其逻辑特征为： （1）存在唯一的一个被称为“起始”的数据元素。 （2）存在唯一的一个被称为“终端”的元素。 （3）除起始元素外，其它每个元素有且仅有一个直接前趋。 （4）除终端元素之外，其它每个元素有且仅有一个直接后继。 本章的基本内容：线性表的逻辑结构定义和各种存储结构、描述方法及其建立在这两种存储结构上的运算实现。,第2

2、章 线性表,在实际应用中，线性表是最常用而且最简单的一种数据结构。 线性表定义：线性表是由n个数据元素组成的有限序列，其中，n即数据元素的个数，定义为线性表的长度，当n为零时称为空表，一般将n0时的线性表记为：（a1，a2，ai，an） 其中，a1是第一个数据元素，又称为起始结点，an是最后一个数据元素，又称为终端结点。当i=1，2，n-1时，ai有且仅有一个直接后继a i+1；当i =2，3，n 时，ai有且仅有一个直接前趋a i-1。注意这里的ai（1 i n）仅仅是一个抽象的符号，其具体含义，在不同的情况下各不相同，它可以是一个数，一条记录或一个符号，甚至是更复杂的信息。例如，英文字母表

3、(A，B，Z)是一个线性表，职工工资表等。 线性表的结点之间的逻辑关系符合线性结构的逻辑特征，是一种线性结构。,2.1.1 线性表的逻辑结构,2.1 线性表的基本概念,常见的线性表的基本运算： （1）置空表SETNULL(L)：将线性表L置成空表。 （2）求长度LENGTH(L)：求给定线性表L中数据元素的个数。 （3）取元素GET(L,i)：结果是线性表L中的第i个数据元素。 （4）定位函数LOCATE(L,x)：当线性表中存在一个值为x的数据元素，则结果是该数据元素在表中的位序，否则，表示值为x的数据元素不存在。 （5）前趋函数PRIOR(L,x)：若x为线性表中的一个数据元素，且其位序大

4、于1，则结果为x 的直接前趋，否则，给出一个特殊值示出该元素没有直接前趋。 （6）后继函数NEXT（L，x）：若x的位序小于LENGTH（L），则结果为该元素的直接后继，否则，给出一个特殊值，示出x无直接后继。,2.1.2 线性表的运算,（7）插入INSERT(L,x,i)：函数功能为在线性表L中的第i 个位置上插入一个值为x 的新元素，使运算前长度为n 的线性表变为长度为n+1的线性表。 （8）删除DELETE(L,i)：函数功能为删除线性表L中的第i 个数据元素，使在此之前长度为n 的线性表L变成长度为n1的线性表。 利用基本运算可以实现线性表的其它复杂运算。 需要指出的是，这里给出的只是

5、定义在逻辑结构上的抽象运算，即只关心这些运算是“做什么”的，至于“怎样实现”则依赖于所选定的存储结构。,顺序表是线性表的顺序存储结构，即按顺序存储方式构成的线性表的存储结构。其存储方式是：线性表的第一个元素存放在个一片连续的存储空间开始位置处，第二个元素紧跟着存放在第一元素之后，以此类推。 利用顺序表来存储线性表，可借助数据元素在计算机内的物理位置相邻特性来表示线性表中数据元素之间的线性逻辑关系。 设线性表每个元素占c个存储单元，若以第一个数据元素在存储单元中的存储地址作为起始地址，则可得出线性表中第i个数据元素的地址为： LOC(ai)=LOC(a1)+(i-1)* c （1iLENGTH(

6、L)） 这样，一旦起始地址LOC（a1） （图2.1中设为b）和一个数据元素占用的存储单元的大小（c值）确定下来，就可求出任一个数据元素的存储地址，显然，这种表便于进行随机访问，因此，顺序表是一种随机存取的结构。,2. 2.1 顺序表,2.2 线性表的顺序存储,在具体实现时，可利用高级程序设计语言中的一维数组即向量来为线性表的顺序存储开辟存储空间，存储空间大小应大于等于线性表长度，用一个整型变量来表示线性表的长度，从而可将顺序表描述为： # define MAXSIZE 999 typedef int elemtype ； /* elemtype表示元素类型，此处设为 int */ typed

7、ef struct elemtype vecMAXSIZE； int len； sequenlist ； 在上面描述中，顺序表是一个结构体类型。其中，vec成员（又称为数据域）指线性表数据元素所占用的存储空间，而len成员（又称为长度域）则用于存储线性表长度，它表示线性表最后一个元素在向量中的位置，elemtype 则为线性表中数据元素类型。,本节讨论在定义线性表顺序存储结构之后，如何在这种结构上实 现有关数据运算。下面重点讨论线性表的数据元素的插入和删除运算。 1插入运算 线性表的插入运算是指在表的第i个元素之前插入一个新的数据元素，插入的结果使得线性表的长度由n变为n+1，线性表的数据元素

8、间的逻辑关系发生了变化，使得物理存储顺序也发生相应的变化。插入过程如图2.2所示。,2.2.2 顺序表上的基本运算,具体算法描述如下： int insert(sequenlist *L， int i，elemtype x) int j； if (*L).len)=MAXSIZE-1) printf(“the list is overflow!n”)； /*溢出判断*/ return（0）； else if ( i(*L).len+1) printf(“position is not correct!n”)； return（0）；/*插入位置不正确*/ ,else for (j = (*L).l

9、en；j =i-1；j-) /*后移元素*/ (*L).vec j+1 = (*L).vec j ； (*L).veci-1 = x； /*插入新元素x*/ (*L).len =(*L).len+1； /*修改表长*/ return(1); /*insert*/ 在本算法中是从最后一个元素开始后移，直到第i个元素为止。该算法时间主要花费在for循环语句上，执行的次数为n-i+1。当i=1时，全部元素均参加移动，共需要移动n次；当i = n+1时，不需移动元素。 算法在最坏情况下，时间复杂度为O(n)，最好情况下时间复杂度为O(1)。显然，元素移动的次数直接影响了算法执行时间。,平均移动次数。

10、假设pi为在第i个元素之前插入一个元素的概率，且为等概率，则平均移动次数的期望值为： 其中，当1in+1时，p1=p 2= =pn+1 = 可见，在顺序存储的线性表中插入一个元素，约平均移动线性表中一半的元素，显然，当n较大时，算法效率较低，算法的平均时间复杂度为O(n)。2删除运算 删除运算是指将线性表中的第i个元素删除，使线性表的长度由n变成n-1，由： (a1，a2，a i-1，ai，a i+1，an)变成为： (a1，a2，a i-1，a i+1，an) 其中， 1in。 线性表进行删除元素后，仍是一个线性表。删除过程如图2.3所示。,具体算法如下： void delete(L，i)

11、sequenlist *L； int i； int j； if (i(*L).len+1) printf(“delete fail！n”)； /*删除位置不正确*/ else *y =(*L).veci-1；/*y为一外部变量，用于接收被删除的元素*/ for(j= i；j=(*L).len；j +) (*L).vecj-1=(*L).vecj； /*元素前移*/ (*L).Len-； /*修改表长*/ /*delete*/,与插入算法相似，要删除一个元素需向前移动元素，删除第i个元素时，将第i+1，i+2，n个元素依次前移，其移动次数为n-i，假设删除线性表中的任一位置上元素的概率相等（等于

12、1/n），则删除运算所需的移动元素的平均移动次数如下所示。 由此可见，对线性表删除一个元素时，约需有一半的元素参加移动。显然，该算法的时间复杂度为(n)。 通过以上讨论可以发现，当表长较大时，对顺序存储结构进行插入和删除运算，由于要移动元素，运算效率低，但这种存储结构对于随机存取元素却十分方便。,例如，一个线性表中可能含有重复的元素（值相同），现要求删除重复元素中的多余元素，只保留其中位序最小的一个。如线性表（5，2，2，3，5，2），经过清除重复元素后变为( 5，2，3 )。 假定线性表以顺序存储方式存储，则其算法可描述如下： void purge(sequenlist *L ) int i

13、=0，j ，k； while ( i=(*L).Len-1) j = i+1； while ( j=(*L).Len-1) if (*L).veci= =(*L).vecj) for ( k =j；k=(*L). Len-1；k +) (*L) .vec k 1 = (*L) .vec k ；/ *元素前移*/ (*L ) .Len- -；/*修改表长度*/ else j + +； i + +； /* purge */,线性表顺序存储结构的特点： （1） 无需为表示数据元素之间的关系而增加额外存储空间； （2）可以方便地随机存取表中任一元素。 （3）必须预先为线性表分配空间，表容量难以扩充，必

14、须按线性表最大可能的长度分配空间，有可能造成存储空间浪费。 （4）插入和删除运算时必须移动大量元素，效率较低； 为避免大量元素的移动，本节讨论线性表的另一种存储结构，即链式存储结构，是最常用的存储方法之一，它不仅可以表示线性表，而且可以表示各种复杂的非线性数据结构。这种结构按不同的分类方法可分为单链表、循环链表和双向链表等。,2.3 线性表的链式存储结构,2.3.1 单链表,链式存储结构是利用任意的存储单元来存储线性表中的数据元素，这些单元可以是连续的，也可以是不连续的。 由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继，为了表示出每个元素与其直接后继之间的关系，在链

15、式存储结构中，除了存储元素本身的信息外，还需要存储指示其直接后继的信息，所以用链式存储结构表示线性表中的一个元素时其结点形式至少需要两部分，其中，用一个域存储数据元素本身的信息（称作数据域），用另一个域存储直接后继的信息（称作指针域或链域），结点结构如下图。,这样，利用每个结点的指针域就可以将n个结点按其逻辑次序连成一个链表，这种链表中每个结点只含一个指针域，故称为线性链表或单链表。例如，线性表（red，orange，white，yellow，green，blue），其单链表的存储方式如图2.4所示。 由于单链表中第一个结点无直接前趋，可另设一个头指针head存储第一个结点的地址。同样，最后一

16、个结点无直接后继，其指针域为空值即为NULL，有时用 表示。整个单链表可由头指针唯一地确定。单链表是一种非随机存取的存储结构。 也可以将图2.4中的单链表直观地画成如图2.5所示，其中箭头用来表示链域中的指针。,单链表可以用C语言中的指针数据类型实现，描述如下： typedef int elemtype ； typedef struct node /*结点类型定义*/ elemtype data ； /* 数据域 */ struct node *next ； /* 定义指针域 */ linklist ； linklist * head ，*p； /* head，p为单链表指针类型 */ 另外，

17、利用C语言中的指针数据类型要注意指针变量和结点变量，其关系如图2.6所示。,为了便于实现各种运算，常在单链表的第一个结点之前增设一个附加的结点，称为头结点，其它的结点称为表结点。本章若无特殊说明，均采用带头结点的单链表，如图2.7的(a)，(b)所示。,2.3.2 单链表上的基本运算,1建立单链表 （1）建立带头结点的单链表 linklist * creatlist ( ) /* 函数返回一个指向单链表表头的指针 */ char ch；int x ； linklist *head ， *r ， *p ； p =（linklist *）malloc（sizeof（linklist）； head

18、= p ； p-next =NULL； /* 生成头结点*/ r = p ； /*建立单链表表尾指针 */ ch = getchar ( ) ； /*ch为建立与否标志 */ while ( ch ! = ? ) /*? 为输入结束标志符 */ scanf ( “ % d ” , p -next = NULL；/*生成新结点*/ r-next = p ； /*连接新结点 */ r = r-next ； /*修改尾指针 */ ch = getchar ( ) ；/*读入建立与否的标志*/ return ( head ) ； /*返回表头指针head */ /* creatlist */,（2）建

19、立不带头结点的单链表 linklist * creatlist ( ) /*函数返回一个指向链表表头的指针*/ char ch；int x ；linklist *head ， *p， *r head =NULL ；r =NULL ； /*设立尾指针r，其初值为空 */ ch = getchar ( )； /*读入建立与否标志 */ while ( ch != ? ) /* ? 为输入结束标志符 */ p=(linklist *)malloc(sizeof(linklist)； /*申请新结点空间 */ scanf ( “ % d ”， if (head = = NULL) head = p；

20、else r-next = p； /*非空表，则新结点*p插入到*r之后 */ r = p ； /*尾指针移动，指向新的表尾 */ ch = getchar ( )； /* 读入建立与否的标志 */ if ( r! = NULL ) r-next = NULL； return head ；/*返回表头指针head */ /* creatlist */ 在算法中引入头结点可以不必区分空表与非空表，可以统一空链表与非空链表的处理。 上述两个算法的时间复杂度都为O(n)。,2.单链表上元素的检索 一般情况下，可以按某个元素的序号或按某给定值两种方法检索。 （1）按值检索 按值检索，即是检索单链表中是

21、否存在值为给定值k的结点，整个过程可以通过结点的值和给定值的比较而实现。 linklist *locate（ linklist *head ， elemtype k ） linklist *s； s= head-next ； /*从第一个结点起开始比较*/ while ( s!= NULL ) /*扫描整个链表*/ if ( s-data != k) s = s-next ； else break ； return s； /*返回结点的位置或NULL*/ /*Locate*/ 算法时间复杂度为O(n)。,（2） 按序号检索 即利用被访问结点的序号而检索或查找结点的过程。 linklist *g

22、et(linklist *head，int i) int j； linklist *p ； p = head ；j = 0； while ( (p-next != NULL ) q = head； p= head-next； while ( p ! = head ) s = q ； q = p ； p = p-next ； q-next = s； p-next = q； return head； /* invert */,2.3.4 双向链表 在单循环链表中，从任一个已知结点出发可以找到其前趋结点，但时间耗费需O(n )，若希望能快速确定一个结点的直接前趋，可以再加上一个指针域存储其直接前趋的

23、信息，这样就可以构成双向链表，它有两个方向不同的链 ，如果将每个方向的链表构成一个环，则可以构成双向循环链表。 双向链表的C语言描述： typedef struct dupnode elemtype data ； struct dupnode *next，*prior ； dulinklist ； dulinklist *head ; 双向循环链表也可由头指针head唯一确定，同样可增加头结点，使得双链表的某些运算简便一些，如图2.11所示。,由于双向链表在其结构中，每个结点既有指向其直接前趋的指针域，又有指向其直接后继的指针域，因此比起单链表来，要在一个双向链表中检索某一个已知结点的直接前趋

24、和后继结点要方便得多。 结点*p可通过多种方式访问，设指针p指向双向链表中某个结点，则有：p-next-prior = p = p-prior-next 双向链表中结点的插入情况如图2.12所示。,在*p结点之前插入结点*s的正确步骤应为： p-prior-next = s； s-prior = p-prior； s-next = p ； p-prior = s ； 由于双向链表中每个结点涉及两个指针的运算，对于某些运算要注意运算顺序。 在上面的步骤中指针p-prior的修改必须在 *p结点的前趋结点 *(p-prior)的后继指针修改之后方可改动，否则会不能正确地插入结点。 在双向链表中删除

25、一个结点*p的指针变化如图2.13所示。指针修改的运算步骤为： p-prior-next= p-next； p-next-prior =p-prior；,1插入算法 void indulist (dulinklist *head ,int i, elemtype x)/*在双向循环链表head中的第i个结点之前插入值为x的新结点 */ dulinklist *p，*s ;int j ; p = head ; j = 0 ; while ( p-next! = head) else printf ( “error！n” ) /* indulist */,2删除算法 void deledulist

26、 (dulinklist *head,int i) /* 删除双向链表head中的第i个结点 */ dulinklist *p ; int j ; p = head ; j = 0 ; while (p-next! = head) /*deledulist*/ 以上两个算法的时间复杂度都为O(n)。,一般而言，对存储结构的选择应主要从存储空间、运算时间、程序设计语言三方面考虑。 （1）存储空间。 （2） 运算时间。 （3）程序设计语言。 线性表的顺序实现和链接实现各有优缺点，只能根据实际问题的具体实现需要，对各个方面的优缺点加以综合平衡后来确定适宜的存储结构。,2.4 线性表存储结构的选择,2

27、.5 线性表的应用举例,在数学上，一个一元多项式Pn(x)可写成： Pn(x)=p0+p1x+p2x2+pnxn 显然，该多项式可以由每项的系数p0，p1，pn唯一地确定，所以，可以将它用一个线性表P来表示成： P=(p0，p1，pi，pn) 若Qm(x)也是一元多项式，则其也可用线性表Q表示为： Q=(q0，q1，qm) 则Pn(x)+ Qm(x)同样也可用线性表R表示。设mn ，则 R=(p0+q0，p1+q1，p2+q2，pm+qm，pm+1，pn) 如果对P、Q都采用顺序存储结构，可以很方便地实现多项式的相加。例如，一个多项式 T(x)=1 + 2 x1 0 0 0 0+ 4 x4 0

28、 0 0 0,若对该多项式选择顺序存储结构，只存储每项的系数构成一个线性表而让每项的指数隐含在系数的序号中，会造成存储空间的极大浪费。若在存储系数的同时也存储相应的指数，这样，对于含有n项的多项式在最坏情形下（即n+1项的系数均不为0时）也只需2(n+1)个存储单元的空间，这种表示将大大的节省存储空间。 其数据类型可定义如下： #define MAXSIZE 9999 typedef struct node /* 定义结点类型 */ float coef ; /* 系数域 */ int exp ; /* 指数域 */ elemtype ; typedef struct elemtype vecMAXSIZE ；/* 定义线性表的向量结构*/ int len ； /* 线性表长度 */ sequenlist ; /*类型定义*/,由于顺序存储结构具有随机存取的特点，对于元素的插入和删除运算需要移动大量元素，所以，当只需求解一个多项式的值而无需修改多项式的系数和指数值时，宜采用顺序存储结构。 由于多项式相加时会产生新的项和系数可能为零的项，需要进行相应的结点空间的增加和释放，所以一般采用链式存储结构。这里采用单链表来实现