《数据结构(第二版)课件 包振宇 第二章 线性表》由会员分享，可在线阅读，更多相关《数据结构(第二版)课件 包振宇 第二章 线性表（65页珍藏版）》请在金锄头文库上搜索。
1、,2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3线性表的链式存储结构 2.4 典型例题,第二章 线性表,线性表的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称为“第一个”的数据元素；（2）存在唯一的一个被称为“最后一个”的数据元素；（3）除第一个以外，集合中的每一个数据元素均有且只有一个前驱；（4）除最后一个以外，集合中每一个数据元素均有且只有一个后继。,2.1 线性表的逻辑结构,线性表是最简单的一种数据结构。简单地说，一个线性表是n(n)个具有相同属性的数据元素的有限序列，其中各个数据元素有着依次相邻（串接）的逻辑关系。 线性表中数据元素的个数n称为线性表的长度。
2、n=0 时，该线性表为空表。n0时该线性表可记为：（A0,A1,Ai,An-1）其中，A0称为起点，An-1称为终点，每个元素的序号代表它在该线性表中的逻辑位置减1（与数组下标对应），除了起点（A0）和终点(An-1)外，每个数据元素都有且只有一个直接前趋和一个直接后继。Ai+1是Ai的直接前驱，Ai+1是Ai的直接后继。 线性表中的数据元素可以是各式各样的，但同一线性表中的元素必定有相同的特性，即属同数据对象，相邻数据元素辶间存在着有序关系。 线性表是一个相当灵活的数据结构，其表长可根据不同的操作增长或缩短。对线性表进行的基本操作有：存取、插入、删除、合并、分解、查找、排序、求线性表的长度等
3、。,2.2 线性表的顺序存储结构,2.2.1 顺序分配 线性表的顺序存储结构是用一组地址连续的存储单元依次存储该线性表中的各个元素。假设线性表的每个数据元素占用L个存储单元，并以所占的第一个单元的存储地址为数据元素的存储位置，则第i+1个数据元素的存储位置为： loc(Ai)=Loc(A0)+i*L. 因此，在内存中可以通过地址计算直接存取线性表中的任一元素，所以，线性表的顺序存储结构可以随机存取。这种结构的特点是逻辑上相邻的元素物理上也相邻（如图2-1所示）。顺序表可用语言的一维数组实现，数组的类型随数据元素的属性而定。,2.2.2 线性表的操作,线性表结构简单、易于实现，但插入或删除一个元
4、素时需对其后继的全部元素逐个进行移动（平均需移动表中的一半元素）操作不方便，需花费较多时间，特别是当插入元素而需动态扩大连续存储时，线性表后面的存储区可能已被占用从而无法扩大。所以，这种结构仅适用于数据元素个数不经常变动或只需在顺序存取设备上做成批处理的场合。下面我们分情况讨论线性表的插入和删除操作。,(一)线性表插入操作(1),1、在数组中下标为i的元素前插入一个新元素。 例2.1 某语言程序中，整型数组的个元数组成一个线性表。为了在i位置前插入一个新元素b，可用如下函数inst1来实现，当插入成功时返回1，否则返回0，所以该函数的返回值类型是整型。插入前后的线性表的示意图如右：,举例（续）
5、,分析： 初始条件V,i,b 执行条件：0i98 执行结果：1 成功 0 不成功 N-S流程图如右： 图,举例（续）,用函数实现算法如下： int ins1( int V , int i, int b) int j； if(i98) printf(“The value of i is out of rangen”)； return 0; /*插入失败*/ for (j=99；ji；j-) vj=vj-1;/*后移*/ vi=b； /*插入*/ return 1； /*插入成功 */ ,线性表的插入操作（2）,2、在有序表中插入一个新元素 例2.2 设有一个有序线性表，用数组结构实现，最大元素个
6、数为n。设当前元素个数是m。要求在该有序表中插入一个值为x的元素。当x=63时，插入前后的有序表的示意图如右：,举例（续）,分析：初始条件：a,n,m,x 插入条件：mn 执行结果：1 成功 0 不成功 N-S流程图如右：,举例（续）,根据分析用函数实现算法如下： int ins2(int a ,int n,int m,int x) int i; if(m=n) printf(“插入失败”); return 0; /*插入失败*/ for(i=m-1; i=0 /*插入成功 */ ,（二）线性表的删除(1),1删除下标为i的 数据元素 例2.3 为在V0到V99中删除一个元素Vi,引用del1
7、函数。删除前后的线性表的示意图如右,举例（续）,分析： 初始条件： 数组V，删除下标i 删除条件：0i99 执行结果：1成功,0不成功 N-S流程图如右:,举例（续）,Del1函数定义如下： int del1 (int v ,int i ) int j; if (i99) printf(“the value of I is out of rangen”); return 0; /*删除失败*/ for (j=i; j99; j+) Vj=Vj+1; /*从vI+1到v99逐个前移*/ V99=0; /*数组最后一个元素清0或某种结束标记*/ return 1; /*删除成功 */ ,线性表的删
8、除操作(2),2在有序顺序表中删除一个数据元素 例2.4 在有序表中删除一个值为x的数据元素。当x的值为78时删去前后的线性表的 示意图如右：,举例（续）,分析： 初始条件：数组a, 数组元素个数n,删除元素值 x 查找a中是否有x值的元素：有x,则删除成功，返回1；无x,则删除不成功，返回0。 NS流程图如右：,举例（续）,对应算法实现函数如下： int del2(int a,int n,int x) int i,j; for(j=0;jn;j+) if(aj= =x)i=j;break; if (j= =n) printf(“找不到x，删除不成功”); return 0; /*找不到x，删
9、除不成功*/ for(;in;i+) ai=ai+1;/* 把所找到元素x后面的所有元素前移*/ an-1=0; n-;/*数组最后一个元素清0或某种结束标记*/ return 1;/*删除成功*/ ,2.3 线性表的链式存储结构,线性表顺序存储虽可随机存取表中的任一元素，但从另一方面来看，这一特点也铸成这种存储结构的三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，使存储空间不能得到充分利用；其三，表的容量难以根据实际需要扩充。为克服上述缺点，本节讨论线性表的另一种存储结构线性表的链式存储结构，简称线性链表。,2.3.1
10、线性链表的实现,线性表进行链式存储时，线性表中的各个元素在主存中可独立地（并不需要依次相邻）存储。如图2-14所示，每个数据元素（或称为结点）的存储包括两个部分：数据区和指针区。数据区存放元素本身的数据，指针区存放的是其后继元素的地址（没有后继元素时设置地址为空指针NULL）。指针区中存储的信息称作指针或链。用指针相连接的结点序列称为链表。若链表中的每一结点只含有一个指针域，则称此链表为线性单链表。为方便起见，我们有时将第一个数据元素之前附加设一个“头结点”，其中的数据区可存放链表的附加信息（如元素个数），也可不存放任何信息，指针区存放第一个结点的地址。,线性表的单链表存储结构,结点在C语言程
11、序中可用结构体数据类型来描述： struct node int data; /本书中如无特别说明，则链表中的数据元素的类型为int型 struct node * link; ; typedef struct node NODE； 在线性链表中，每个数据元素的存储位置都包含在其直接前驱结点的信息之中。假设P是指向线性表中第i个数据元素的指针，该结点称为P结点或结点ai。则P-data=ai； -link-data=ai+1。,2.3.2 线性链表的运算,设p链表中某一结点的指针，可以说明如下： NODE *p； 申请一个结点可用C语言的标准存储分配库函数malloc。调用如下： p = (NOD
12、E * ) malloc ( sizeof (NODE); 当用完后释放结点占用空间时调用函数free free(p);,（一）线性链表的建立,例.5 建立一个如图所示的链表。,例2.5 函数定义如下,NODE * create_linklist(NODE * head,int x,int y,int z) NODE * p, *q; p=(NODE *)malloc(sizeof(NODE); head=p; p-data=x; q=(NODE *)malloc(sizeof(NODE); p-link=q; p=q; p-data=y; q=(NODE *)malloc(sizeof(NO
13、DE); p-link=q; p=q; p-data=z; p-link=NULL; return (head); ,（二）线性链表的插入操作,设链表结点类型的定义为： typedef struct node int data; struct node *link; NODE; 在链接存储的线性表中插入一个键值为x的新结点，分以下四种不同情况： 1、在某指针P所指结点之后插入； 2、插入首结点之前，使新结点为新的首结点； 3、接在线性表的末尾； 4、在有序链表中插入，使新的线性表依旧有序。,分情况讨论（1）,1、在线性链表中某指针p所指结点之后插入值为x的结点,算法的NS流程图,插入结点的函数
14、,函数定义如下： void lq_insl(p,x) NODE *p; /*新结点在P所指结点之后*/ int x; /*新结点的键值*/ NODE *u; u=(NODE *)malloc(sizeof(NODE); u-data=x; u-link=p-link; p-link=u; ,分情况讨论（2）,2、首结点之前插入键值为x的新结点,算法的NS流程图,算法的NS流程图,首结点之前插新结点函数定义,void lq_ins2(hpt,x) NODE *hpt; /*链表头指针*/ int x; /*新结点的键盘值*/ NODE *u; u=(NODE *)malloc(sizeof(NO
15、DE); u-data=x; u-link=hpt; hpt=u; ,分情况讨论（3）,3、在链式存储的线性表的末尾接上一个键值为x的新结点,算法的NS流程图,线性表末尾接上新结点函数定义,void lq_ins3(hpt,x) NODE *hpt; /*链表头指针*/ int x; /*新结点的键盘值*/ NODE*u,*p; u=(NODE)*malloc(sizeof(NODE); u-data=x; u-link=null; if (hpt=null) /*如链表为空链表*/ hpt=u;return; /*x以链表首结点开始顺序走向末尾结点*/ for( p=hpt; p-link!
16、=null;p= p-link); p-link=u; ,分情况讨论（4）,4、在有序链式存储线性表中插入一键值为X的新结点(假设x=8),算法的NS流程图,有序链式线性表中插入新结点函数,voikd lq_ins4 (hpt,x) /*设链表从小到大有序*/ NODE *hpt; /*链表头指针*/ int x; /*新结点的键值*/ NODE *u,*q,*p; u=(NODE *)malloc(sizeof(NODE); u-data=x; /*从链表首结点开始顺序寻找*/ for(p=htp;p u-link=p ,（三）线性链表的删除操作,完成删除算法可有以下几个步骤组成： 1、如链表为空链表
