大学数据结构课件线性表.ppt

1、第2章 线性表,2.1 线性表抽象数据类型,1.线性表的定义,线性表是n(n0)个数据元素的有限序列。由相同类型数据元素（a1, a2, an）组成的线性结构。数据元素之间存在着线性的逻辑关系： （1）表中有且仅有一个开始结点； （2）表中有且仅有一个终端结点； （3）除开始结点外，表中每个结点均只有一个前趋结点（Predecessor）; （4）除终端结点外，表中每个结点只均只有一个后继结点（Successor）,2.线性表抽象数据类型,2.2 线性表的顺序存储结构及实现,1.顺序表的存储结构,实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线

2、性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。 向量是内存中一批地址连续的存储单元。所以，线性表的顺序存储也称为向量存储。,顺序表的存储结构如图所示,顺序存储结构的线性表称作顺序表,a0,a1,a2,a3,a4,a5,elem,length=6,MaxSize-1,第i个元素的地址： LOC(ai)=LOC(a1)+L*(i-1),typedef struct ElemType elem MAXSIZE; int length; Sqlist;,静态一维数组,事先定义的常量,结构体类型名，之后可用于说明结构体

3、变量,在结构体中还可以使用动态一维数组。如下定义：,typedef struct ElemType *elem ; int length ; Sqlist1 ;,使用指针表示数组域,表长域,Sqlist a ;a.Elem=(Sqlist1*)malloc(MAXSIZE*sizeof(ElemType);free (a.elem),#define MAXSIZE 100,2.顺序表操作的实现（线性表在向量中基本运算的实现）,#define MAXSIZE 100 Typedef int ElemType ; typedef struct ElemType elem MAXSIZE; /*数组

4、域*/ int length; /*表长域*/ Sqlist; /*结构体类型名*/,（1）插入数据元素Insert(L, i, x),（1）插入数据元素Insert(L, i, x),（1）插入数据元素Insert(L, i, x),（1）插入数据元素Insert(L, i, x),int Insert (Sqlist *L, int i, ElemType x) int j; for(j = L-length; j i; j-) L-elemj = L-elemj-1; /*依次后移*/ L-elemi = x; /*插入x*/ L-length +; /*元素个数加1*/ return

5、1; ,typedef struct ElemType elem MAXSIZE; int length; Sqlist;,插入算法的实现,（2）删除数据元素ListDelete(L, i, x),（2）删除数据元素操作的算法实现,int Delete ( Sqlist *L, int i) int j; for(j = i +1; j lengh-1; j+) L-elemj-1 = L - elemj; /*依次前移*/ L - lengh-;/*数据元素个数减1*/ return 1; ,3.顺序表操作的效率分析,时间效率分析:,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基

6、本操作(最深层语句频度) T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置i,若i =lengh，则根本无需移动（特别快）； 若i =0，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,设 Pi 是在第 i 个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n, 当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1/(n+1),则 插入时的平均移动次数为: n(n+1)/2(n+1)n/2O(n),同理可证:顺序表删除一元素的时间效率为: T（n)=(n-1)/2 O(n),顺序表中的其余操作都和数据元

7、素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n), 其余操作的时间复杂度都为O(1),插入效率：,删除效率：,4. 顺序表应用举例,例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过100个。 实现方法：1、采用直接编写一个主函数实现。2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SqList.h中，通过 #include “SqList.h” ）,程序设计如下：,void main(void) Sqlist m

8、yList; int i , x; Initiate( ,程序运行结果：1 2 3 4 6 7 8 9 10,elem 100 length=0,#include #include Sqlist.h #define MAXSIZE 100 typedef int ElemType;,elem 0=1 Elem1=2 Elem4=5 Elem9=10 length=10,typedef struct ElemType elem MAXSIZE; int length; Sqlist;,elem 0=1 Elem1=2 Elem4=6 Elem8=10 length=9,主要优点: 算法简单，空间

9、单元利用率高；,主要缺点: 1. 插入和删除时需要移动较多的数据元素，所以在频繁时行插入、删除操作时效率较低。 2.需要预先确定数据元素的最大个数。并预先占用一片地址连续的存储空间。 3. 如果插入数据元素量超过预先分配的存储空间时，要临时扩大有很大困难。,线性表顺序存储结构的主要优缺点,2.3 线性表的链式表示和实现,线性表的链表存储结构的特点：是构成链表的结点（即分配给每一个数据元素的存储单元）可分为两个域（数据域和指针域）。数据域保存数据元素本身的数据信息，指针域保存其直接后继结点的地址（称为指针）。数据元素间的逻辑关系由每个结点的指针体现。所以，逻辑上相邻的数据元素在物理上不要求相邻。

10、因此它不需要一片地址连续的存储空间，可以避免了顺序表所具有的缺点。,2.3.1 结点结构与指针变量,结点的存储结构定义为： typedef int ElemType ; Typedef struct node ElemType data; /* 数据域 */ struct node *next; /* 指针域 */ Lnode,1. 结点结构,假设h, p, q为指针变量，可说明如下： Lnode *h, *p, *q; /* 4 bytes 未赋值 */ h=NULL; /* set NULL to h */ h=(Lnode*)malloc(sizeof(Lnode); /* point

11、to a new node */ p=h; /* p 和 h 中存放的是同一结点的首地址 */ p-data = 12; p-next =NULL; free(h) /* or free(p) ,release the nodes space to the system*/,2. 指针变量及其基本操作,指针变量的主要操作： 语句 执行前 执行后,2.3.2 单链表及其结构 n个结点链接在一起可以构成一个链表。由于其每个结点中只包含一个指针域，故称为单链表。,非空线性单链表,包括一个头结点和n个数据元素的结点。头指针h指向链表的头结点或首元结点。头指针h 可以作为链表的唯一已知条件。对链表的各种

12、操作一般须从头指针开始。,首元结点 存储线性表第一个数据元素,2.3.3 线性链表基本运算的实现,1) 在带头结点单链表第一个数据元素前插入结点,* 分别在带头结点单链表的首元结点和其它结点前插入结点的操作比较,2) 删除带头结点单链表第一个数据元素结点,* 删除带头结点单链表首元结点和其它结点操作的比较,3) 在不带头结点单链表第一个数据元素前插入结点,4).在不带头结点单链表其他数据元素前插入结点,* 在不带头结点单链表首元结点和其他结点前插入结点之比较,5) 删除不带头结点单链表第一个数据元素结点,6) 删除不带头结点单链表其他数据元素结点,p,ai-1,a1,ai,an,h,data

13、next,ai+1,p-next = p-next -next ( ai-1 .next = ai.next ),结 论 （1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样 （2）删除操作和插入操作类似 （3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数 （4）因此，带头结点单链表的算法设计简单,2.3.4 单链表的操作实现举例, q=h; while(q-next!=p) q=q-next; s=(Ln

14、ode*)malloc(sizeof(Lnode) s-data = x; s-next =p; q-next = s; ,Typedef struct node ElemType data; struct node *next; Lnode,1、在p 指向的结点前插入数据元素x,2、在线性表中值为x的元素前插入值为y的数据元素,void Insert(Lnode *h, ElemType x, ElemType y) s=(Lnode*)malloc(sizeof(Lnode) s-data = y; q=h; p=q-next; while(p!=NULL) ,Typedef struct

15、 node ElemType data; struct node *next; Lnode,3、删除p所指向的结点, q=h; while( q-next !=p ) q=q-next; q-next = p-next; free( p ); ,4、删除线性表中值为x的数据元素,void Delete( Lnode *h, ElemType x ) q=h; p=q-next; while(p!=NULL) ,Typedef struct node ElemType data; struct node *next; Lnode,5、删除线性链表中第i个元素结点，并返回该数据元素的值。,Elem

16、Type Deletei ( Lnode *h, int i ) int k=0; p=h; while( p -next !=NULL) ,2.3.5 单链表操作的效率分析,单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：,删除一个数据元素时比较数据元素的平均次数为：,所以，单链表进行数据元素插入删除操作的时间复杂度为O(n)。,2.4 循环链表与双向链表,循环单链表是单链表的另一种形式的存储结构，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成

17、一个环。它的优点是从表中任一结点出发均可找到表中其它结点。,程序设计： p!=NULL改为 p!=head P-!=NULL改为 p-!=head,2.4.1 循环链表, rb-next = ra-next; ra-next = hb-next； free(hb); ra = rb ,让b链表尾结点的指针域保存a链表的头结点地址,让a链表尾结点的指针域保存b链表的首元结点地址,消毁b链表的头结点,让a链表的尾指针指向b链表的尾结点,将两个循环链表首尾相接,双向链表是每个结点除后继指针域外还有一个前驱指针域，它是解决查找前驱结点问题的有效途径。,2.4.2 双向链表,1、在双向链表中插入一个结点：, s-next=p; s-prior=p-prior; p-prior-next = s; p-prior = s; ,2、从双向链表中删除一个结点：, p-prior-next = p-next; p