数据结构（线性表）

第二章 线性表,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。2.熟练掌握这两类存储结构:顺序存储结构和链式存储结构的描述方法。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。3.熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4.熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。5. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,第二章 线性表,学习提要,线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个外，集合中的每个数据元素均 只有一个前驱；除最后一个外，集合中的每个数据元素均 只有一个后继。,线性表（Linear List）：具有相同特征的数据元素的一个有限序列。表示为：（a1，a2， ai，ai+1 an）序列中所含元素的个数n叫线性表的长度，n0；当n=0时表示一个空表。a1叫表头元素，an叫表尾元素。除第一个和最后一个元素外，每个元素都只有一个之间前驱和一个直接后驱。线性表用二元组表示为：linear_list=(A，R)其中 A= ai|1in, n0, aiElemType R=r r= |1in-1,线性表的抽象数据类型ADT List 数据对象：Dai|aiElemSet, i=1,2,.,n, n0 数据关系：R|ai-1 ,aiD,i=2,.,n 基本操作：（1）结构初始化： InitList( &L ) 操作结果：构造一个空的线性表L。（2）销毁结构： DestroyList( &L ) 初始条件：线性表L已存在。 操作结果：销毁线性表L。,（3）引用型操作：ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则FALSEListLength( L ) 初始条件：线性表L已存在。 操作结果：返回L中元素个数。PriorElem( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e无定义。NextElem( L, cur_e, &next_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是最后一个，则用 next_e返回它的后继，否则操作失败，next_e无定义。,（3）引用型操作： （续）GetElem( L, cur_e, &next_e )初始条件：线性表L已存在， 1iLengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem( L, e, compare( ) )初始条件：线性表L已存在，compare( )是元素判定函数。操作结果：返回L中第1个与e满足关系compare( )的元素 的位序。若这样的元素不存在，则返回值为0。ListTraverse(L, visit( ) /线性表遍历初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。,（4） 加工型操作ClearList( &L )初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem( L, i, &e )初始条件：线性表L已存在，1iLengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert( &L, i, e )初始条件：线性表L已存在，1iLengthList(L)+1操作结果:在L的第i个元素前插入新元素e，L长度增1。ListDelete(&L, i, &e)初始条件：线性表L已存在且非空，1iLengthList(L)操作结果:删除L第i个元素，用e返回其值，L的长度减1。 ADT List,需要说明的是： 1. 某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。读者掌握了某一数据结构上的基本运算后，其它的运算可以通过基本运算来实现，也可以直接去实现。2. 在上面各操作中定义的线性表仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法，而算法的实现只有在存储结构确立之后。,线性表的逻辑结构:例 英文字母表（A,B,C,.Z)是一个线性表例 一张学生信息表也是一个线性表,线性表的物理（存储）结构1、顺序存储结构顺序表：将线性表中的所有元素按其逻辑顺序相继存放在一个连续的存储空间中。元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L其中： L: 一个元素占用的存储单元个数 LOC(ai): 线性表第i个元素的地址特点: 实现逻辑上相邻物理地址相邻 实现随机存取实现：可用C语言的一维数组实现,在C语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等运算，即表长是可变的，因此，数组的容量需设计的足够大，设用：dataMAXSIZE来表示，其中MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据从 data0 开始依次顺序存放。当前线性表中的实际元素个数可能未达到MAXSIZE多个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last= -1。,typedef int DataType; #define M 1000DataType dataM;,例 typedef struct card int num; char name20; char author10; char publisher30; float price;DataType;DataType libraryM;,数据元素不是简单类型时,可定义结构体数组,或动态申请和释放内存DataType *p= (DataType *)malloc(M*sizeof(DataType);free(p);,从结构性上考虑，通常将 data 和 last 封装成一个结构作为顺序表的类型： typedef struct DataType dataMAXSIZE; int last; SeqList; 定义一个顺序表：SeqList L ;这样表示的线性表如右图所示。表长L.last+1，线性表中的数据元素a1至an分别存放在L.data0至L.dataL.last中。,顺序存储结构下基本操作的实现：1、插入在第i个元素之前插入一个新的数据元素x。 在顺序表上完成这一运算则通过以下步骤进行： (1) 将anai顺序向下移动，为新元素让出位置； (2) 将 x 置入空出的第i个位置； (3) 修改 last 指针(相当于修改表长)，使之仍指向最后一个元素。,算法如下： int Insert_SeqList(SeqList *L，int i，DataType x) int j; if (L-last= =MAXSIZE1) printf(“表满,不能插入元素); return(-1); if (iL-last+2) printf(位置错);return(0); for(j=L-last;j=i-1;j-) L-dataj+1=L-dataj; /* 结点向后移动 */ L-datai-1=x;/*新元素插入*/ L-last+; /*last仍指向最后元素*/ return (1);/*插入成功，返回*/ ,算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,顺序存储结构下基本操作的实现：2、删除将表中第 i 个元素从线性表中去掉。 在顺序表上完成这一运算则通过以下步骤进行： (1) 将ai+1an 顺序向上移动。 (2) 修改last指针(相当于修改表长)使之仍指向最后一个元素。,算法如下：int Delete_SeqList(SeqList *L;int i) int j; if ( iL-last+1 ) printf (“不存在第i个元素”); return(0); for(j=i;jlast;j+) L-dataj-1=L-dataj; /*向前移动*/ L-last - - ; return(1); /*删除成功*/ ,算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。,顺序存储结构下基本操作的实现：3、按值查找在线性表中查找与给定值x相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素 a1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 x 相等的元素，返回-1。,13,13,13,13,13,算法如下：int Location_SeqList(SeqList *L, datatype x) int i=0; while(idatai!= x) i+; if (iL-last) return -1; else return i; /*返回的是存储位置*/,算法评价本算法的主要运算是比较。显然比较的次数与x在表中的位置有关，也与表长有关。当 a1=x 时，比较1次成功。当 an=x 时比较 n 次成功。设x出现在1n的概率相等，都为1/n，所以平均比较次 数为: (1+2+n)/n =（n+1)/2时间性能为O(n)。,顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充,线性表的链式存储结构特点：(1)用一组任意的存储单元存储线性表的数据元素;(2)利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素;(3)每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。结点数据域：元素本身信息指针域：指示直接后继的存储位置,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,线性链表定义：结点中只含一个指针域的链表，也叫单链表。typedef struct node DataType data; struct node *next; LNode，*LinkList；若声明 LNode *p;则：p=malloc(sizeof(LNode)；表示生成一个新结点。 free(p)；表示系统回收p结点。,头结点：在单链表第一个结点前附设的一个结点。头结点指针域为空表示线性表为空。,单链表上基本运算的实现1、建立单链表(1)在链表的头部插入结点建立单链表链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部。,下图展现了线性表：（25,45,18,76,29）之链表的建立过程，因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。,算法如下：LinkList Creat_LinkList1( ) LinkList L=NULL；/*空表*/Lnode *s; int x; /*设数据元素的类型为int*/scanf(%d,25,45,18,76,29,(2) 在单链表的尾部插入结点建立单链表以上算法读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针 r 用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部，如下图所示。,H=NULL r=NULL /*初始状态*/,29,r,H,76,29,r,H,18,76,29,r,H,25,45,18,76,29,r,H,45,18,76,29,r,H,算法如下：LinkList Creat_LinkList2( ) LinkList L=NULL; Lnode *s,*r=NULL; int x; scanf(%d,25,45,18,76,29,单链表上基本运算的实现2、查找操作(1) 按序号查找 Get_Linklist(L,i)算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第个结点时返回空。Lnode * Get_LinkList(LinkList L, Int i); Lnode * p=L; int j=0; while (p-next !=NULL ,(2) 按值查找即定位 Locate_LinkList(L,x) 算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空。算法如下：Lnode * Locate_LinkList( LinkList L, datatype x) Lnode * p=L-next; while ( p!=NULL ,单链表上基本运算的实现3、插入(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。操作如下： s-next=p-next;p-next=s;,单链表上基本运算的实现3、插入(2)前插结点：设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面。q=L;while (q-next!=p) q=q-next; s-next=q-next; q-next=s;,单链表上基本运算的实现4、删除 设p指向单链表中某结点，删除*p。首先要找到*p的前驱结点*q，然后完成指针的操作即可。操作由下列语句实现：q-next=p-next;free(p);,循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状；特点：从表中任一结点出发均可找到表中其他结点，提高查找效率；操作与单链表基本一致,循环条件不同：单链表：p或p-next=NULL循环链表：p或p-next=H,双向链表（double linked list）结点定义 typedef struct dlnode datatype data; struct dlnode *prior,*next; DLNode,*DLinkList;,空双向循环链表：,非空双向循环链表：,双向链表中结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面。操作如下： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;,双向链表中结点的删除：设p指向双向链表中某结点，删除*p。操作如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);,例:已知单链表L，写一算法，删除其重复结点，即实现如下图2.23的操作。算法思路：用指针p指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之；p指向下一个；依此类推，p指向最后结点时算法结束。,算法如下：void pur_LinkList(LinkList H) LNode *p,*q,*r; p=H-next; /*p指向第一个结点*/ if(p=NULL) return; while (p-next) q=p; while (q-next) if (q-next-data=p-data) r=q-next; q-next=r-next; free(r); else q=q-next; p=p-next; 该算法的时间性能为O(n2)。,顺序表和链表的比较:顺序存储有三个优点： (1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外存储开销。 (3) 顺序表具有按元素序号随机访问的特点。两个缺点： (1)在顺序表中做插入删除操作时，平均移动大约表中 一半的元素，因此对n较大的顺序表效率低。 (2)需要预先分配足够大的存储空间，估计过大，可能 会导致顺序表后部大量闲置；预先分配过小，又会 造成溢出。,链表的优缺点恰好与顺序表相反。在实际中怎样选取存储结构呢？通常有以下几点考虑：基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于的。,基于运算的考虑 在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。,基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。,思考1： 试分别用顺序表作为存储结构，实现将线性表(a0,a1,.an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下： void ReverseList( Seqlist *L) DataType temp ; /设置临时空间用于存放data int i; for (i=0;ilength/2;i+) /L-length/2为整除运算 temp = L-datai; /交换数据 L - data i = L - data L - length-1-i; L - data L - length - 1 - i = temp;,思考2： 为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。,思考3：在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?答：下面分别讨论三种链表的情况。1. 单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。,思考4：下述算法的功能是什么?LinkList De