数据结构讲义第2章-线性表

1、第二章第二章 线性表线性表线性结构的特点：在数据元素的非空有限集中1. 存在唯一的一个被称做“第一个”的数据元素；2. 存在唯一的一个被称做“最后一个”的数据元素；3. 除第一个之外，每个元素都只有一个前驱；4. 除最后一个之外，每个元素都只有一个后继。2.1 线性表的逻辑结构线性表的逻辑结构o 线性表是一种最简单的数据结构，它是一种线性结构。o 线性表是n(n0)个数据元素的有限序列，通常记为：(a1，a2， ai-1，ai，ai+1，an)其中:o 同一线性表中的数据元素必须具有相同数据类型，o ai是线性表的第i个元素，称i为数据元素ai的序号o 相邻数据元素间存在序偶关系：将 ai-1

2、 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。a1 是表中第一个元素，它没有前趋；an 是最后一个元素无后继；其余有且仅有一个直接前趋 ，有且仅有一个直接后继 o n为表长， n0 时称为空表（）。o 线性表的数据元素，或者叫结点，或者叫记录，是独线性表的数据元素，或者叫结点，或者叫记录，是独立的信息。立的信息。它可以是一个数：它可以是一个数：例某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用线性表表示为：（6，17，28，50，92，188）或一个符号，如英文字母表（或一个符号，如英文字母表（A A，B B，Z Z）；）；也可以由若干个数据项组成：如：也可以由

3、若干个数据项组成：如：学生健康情况登记表如下： 姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱线性表的其他表示方式线性表的其他表示方式: 二元组表示二元组表示 L= ， 其中其中D= a1,a2, a3, . an S= R R=, , 图示表示图示表示 a1a3a2a4an-1an.线性表的基本操作：n表的初始化n存取操作：存、取线性表中第i个数据元素n查找操作：在线性表中查找满足条件元素n插入操作：在线性表的第i个元素之前插入n删除操作：删除线性表的第i个元素n遍历n求表长o说明：说明：(1)上面列

4、出的操作，只是线性表的一些常用的基本操作；(2)线性表的复杂操作可通过基本操作实现。 2.22.2 线性表的线性表的顺序存储顺序存储和实现和实现 一 线性表的顺序存储结构顺序表 二 顺序表的基本操作算法 三 顺序表应用举例 线性表的顺序存储结构，指的是用一组地址连续的存储单元依次存储线性表的数据元素，用物理上的相邻表示逻辑上的相邻。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n 线性表（a1,a2, a3, . an ） 的顺序存储结构用顺序存储结构存储的线性表称为顺序表 2.2 线性表的顺序存储和实现一一 线性表的顺序存储结构线性表的顺序存储结构顺序表顺

5、序表 线性表的顺序存储结构2.2 线性表的顺序存储和实现说明：说明：l在顺序存储结构下，线性表元素之在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序间的逻辑关系，通过元素的存储顺序反映（表示）出来；反映（表示）出来；l假设线性表中每个数据元素占用假设线性表中每个数据元素占用 t 个个存储单元，那么，在顺序存储结构中存储单元，那么，在顺序存储结构中，线性表的第，线性表的第i个元素的存储位置与第个元素的存储位置与第1个元素的存储位置的关系是：个元素的存储位置的关系是： Loc(ai+1 ) = Loc( ai )+ tLoc(ai ) = Loc( a1 )+ ( i 1) t顺序表

6、特点：可随机存取顺序表特点：可随机存取a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nt t个单元个单元Loc( a1 )Loc(ai )一一 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表顺序表的定义：2.2 线性表的顺序存储和实现一维数组表长 # define ListSize 100 typedef int ElemType; ElemType ListListSize; int length;一一 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表例1： 写出线性表（6，17，28，50，92，188）的顺序存储结构表示。例2：写出右表的顺序

7、表定义。姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱方法1：2.2 线性表的顺序存储和实现 # define ListSize 100 typedef int ElemType; ElemType ListListSize; int length;一一 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表例2：几种表示方法：# define ListSize 100 typedef int ElemType; typedef struct ElemType dataListSize; int leng

8、th;SqList;#define LIST_INIT_SIZE 100#define LISTINCREAMENT 10typedef structElemType *elem;int length;int listsize;SqList方法2：方法3：二二 顺序表上的基本操作顺序表上的基本操作1.插入功能：在顺序表v 中的第 i ( 1=i=ListSize)return -1; /*溢出*/ if (iL.length+1) return (0); /* i 值不合法*/for ( j=L.length-1 ; j= i-1; j-)L.dataj+1= L.data j;/* 结点移动

9、 */ L.datai-1=e ; /* 插入e */ L.length+; /* 表长增1 */ return 1;/*插入成功，返回*/ int insert_listSq (ElemType Vector, int length, int i, ElemType e)if(length=ListSize)return -1; /*溢出*/ if (ilength+1) return (0); /* i 值不合法*/for ( j=length-1 ; j= i-1; j-)Vectorj+1= Vector j;/* 结点移动 */ Vectori-1=e ; /* 插入e */ len

10、gth+; /* 表长增1 */ return 1;/*插入成功，返回*/ typedef int ElemType; 2.2 线性表的顺序存储和实现顺序表插入算法示例2：o 顺序表插入算法分析顺序表插入算法分析o 平均移动数据元素的次数：o 这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度T(n)(n)。 1111s2)1(11)1(Eniniiininninp2.2 线性表的顺序存储和实现功能：在顺序表 删除第 i ( 1=i=n+1)个数据元素，将被删除元素值存入e, 删除前线性表为 (a1, a2, a3, ai-1 ,ai, an ) 删除后,线性表长度为n1,

11、线性表为 (a1, a2, a3, ai-1 , ai+1, an )2.2 线性表的顺序存储和实现2. 删除删除2.2 线性表的顺序存储和实现注意两点：1 第i+1至第n个元素（共ni个）依次前移2 表长减1删除操作示意图删除操作示意图int delete_listSq (SqList &L , int i,ElemType &e)if (iL.length) return (0); /* 检查空表及删除位置的合法性 */ e =L.datai-1 ; /* 取出第i个元素存入e */ for ( j=i-1; j=L.length-2; j+)L.dataj= L.data

12、 j+1;/* 结点移动 */ L.length-; /* 表长减1 */ return 1;/*删除成功，返回*/ # define ListSize 100 typedef int ElemType; typedef struct ElemType dataListSize; int length;SqList;2.2 线性表的顺序存储和实现算法：删除算法：采用定义：调用示例： main() SeqList L;ElemType e; delete_ListSq(L,2,e); o 顺序表删除算法分析顺序表删除算法分析o设删除第i个元素的概率为Pi，当Pi=1/ n，即为等概率情况，则平均

13、移动数据元素的次数：o这说明：在顺序表上做删除操作需移动表中一半的数据元素。显然时间复杂度T(n)(n)。 2.2 线性表的顺序存储和实现11121)(1)(Eniniideninninp3. 初始化空表初始化空表2.2 线性表的顺序存储和实现# define ListSize 100 typedef int ElemType; typedef struct ElemType dataListSize; int length;SqList;void init_listSq (SqList &L)L.length 0; return; 采用定义：算法：思考：采用其它的定义如何初始化空表？

14、三三 顺序表应用举例顺序表应用举例 1.设有两个按元素值递增有序排列的顺序表A和B，请编写算法将A和B归并成一个按元素值递增有序排列的线性表C。 void merge(SeqList A,SeqList B,SeqList &C)void merge(SeqList A,SeqList B,SeqList &C)i=0;j=0;k=0;i=0;j=0;k=0; while ( iA.length & jB.length ) while ( iA.length & jB.length ) if (A.dataiB.dataj) C.datak+=A.datai+;

15、 if (A.dataiB.dataj) C.datak+=A.datai+; else else C.datak+=B.dataj+; C.datak+=B.dataj+; while (iA.length ) while (iA.length ) C.datak+= A.datai+; C.datak+= A.datai+; while (jB.length ) while (jdata p nextp p 线性链表的类型定义线性链表的类型定义例：例：定义头指针变量：定义头指针变量：LinkList H；相当于定义了一个单链表相当于定义了一个单链表H 两个两个C 函数函数1) malloc

16、(int size) 功能：在系统内存中分配功能：在系统内存中分配size个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。使用方法：使用方法： p = (LinkList) malloc(sizeof(LNode ); 为为p申请一个结点申请一个结点2. 3. 1 线性链表指针变量图示 数据数据域域指针指针域域 pdata pnextp p2) free ( p ) 功能：将指针变量功能：将指针变量p所指示的存储空间，所指示的存储空间，回收到系统内存空间中去。回收到系统内存空间中去。使用方法：使用方法：free(p)2. 3. 1 线性链表二二 线性链表基本操作的算法线性链

17、表基本操作的算法初始化带头结点的线性链表1）初始化空表 算法：LinkList init_List ( ) head = (LinkList)malloc(sizeof(LNode); head-next = null; return head; headhead1.建立单链表建立链表LinkList Creat_LinkList( ) LinkList L=NULL；/*空表*/ scanf(%d,&x); while (x!=flag) s=malloc(sizeof(LNode); s-data=x; s-next=L; L=s; scanf (%d,&x); retur

18、n L;2）头插法建表 不带头节点二二 线性链表基本操作的算法线性链表基本操作的算法o例：线性表（25,45,18,76,29）之链表的建立过程。 25 45187629761825 451825 4525 4525 在头部插入建立单链表建立链表LinkList Creat_LinkList( )LinkList L=NULL; r=NULL; scanf(%d,&x); while (x!=flag) s=malloc(sizeof(LNode); s-data=x; if (L=NULL) L=s; /*第一个结点的处理*/ else r-next=s; /*其它结点的处理*/ r

19、=s; /*r 指向新的尾结点*/ scanf(%d,&x); if ( r!=NULL) r-next=NULL; /*对于非空表，最后结点的指针域放空指针*/ return L;2）尾插法建表 H=NULL r=NULL /*初始状态*/29rH7629rH187629rH2545187629rH45187629rH2. 查找(1)按序号查找按序号查找Linklist Get_LinkList(LinkList L, int i)/*在带头结点带头结点的的单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/ p=L;j=0;while (p-next !=NULL &

20、; jnext; j+; if (j=i) return p; else return NULL; (2)按值查找 Locate_LinkList(L,x)Linklist Locate_LinkList( LinkList L, elemtype x)/*在带头结点带头结点的的单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/ p=L-next; while ( p!=NULL & p-data != x) p=p-next; return p; 3.插入(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面，插入示意图如右图。操作如下

21、： s-next=p-next;p-next=s;注意：两个指针的操作顺序不能交换。在*p之后插入*s p so (2)前插结点：设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图。n 首先要找到*p的前驱*qn 然后再完成在*q之后插入*s：o s-next=q-next; o q-next=s;图 在*p之前插入*s spq Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(参数i错);return 0; /*第i-1个不存在不能插入*/ else s=malloc

22、(sizeof(LNode); /*申请、填装结点*/ s-data=x; s-next=p-next; /*新结点插入在第i-1个结点的后面*/ p-next=s return 1; (3)插入运算 Insert_LinkList(L,i,x)int Insert_LinkList( LinkList L, int i, datatype x) /*在单链表L的第i个位置上插入值为x的元素*/ 4. 删除 o (1)删除结点：设p指向单链表中某结点，删除*p。n首先要找到*p的前驱结点*q，n然后完成指针的操作即可：o q-next=p-next;o free(p);图2.15 删除*p p

23、qo(2)删除运算：Del_LinkList(L,i)oint Del_LinkList(LinkList L，int i)o /*删除单链表L上的第i个数据结点*/o LinkList p,s;o p=Get_LinkList(L,i-1); /*查找第i-1个结点*/o if (p=NULL) o printf(第i-1个结点不存在);return -1; o else if (p-next=NULL)o printf(第i个结点不存在);return 0; o else s=p-next; /*s指向第i个结点*/o p-next=s-next; /*从链表中删除*/o free(s);

24、 /*释放*s */o return 1;o o2.3.3 循环链表循环链表带头结点的单循环链表(a)非空表a1Han(b)空表Ho 单循环链表的连接操作示例：np= R1 next; /*保存R1 的头结点指针*/nR1-next=R2-next-next; /*头尾连接*/nfree(R2-next); /*释放第二个表的头结点*/nR2-next=p; /*组成循环链表*/。两个用尾指针标识的单循环链表的连接R2b1bna1anR1p2.3.4 双向链表双向链表双向链表结点的定义：typedef struct dlnode ElemType data; struct dlnode *pr

25、ior,*next;DLNode,*DLinkList;priornextdatao 结构特点：o 设p指向双向循环链表中的某一结点，即 p中是该结点的指针，则o p-prior-next = p = p-next-prior带头结点的双循环链表(b)空表H(a)非空表Ha2a1an2.3.4 双向链表双向链表o结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图所示。o s-prior=p-prior;o p-prior-next=s;o s-next=p;o p-prior=s;o操作 必须要放到操作的前面完成.双向链表中的结点插入p

26、2.3.4 双向链表双向链表sop-prior-next=p-next;op-next-prior=p-prior;ofree(p); p2.3.4 双向链表双向链表o结点的删除：设p指向双向链表中某结点，删除P结点。线性链表小结线性链表小结线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入删除操作通过修改结点的指针实现； 3 不能随机存取元素.2.3.5 静态链表静态链表o下面先请看图2.22 ，在图2.22中，规模较大的结构数组 sdMAXSIZE 中有两个链表：其中链表SL是一个带头结点的单链表，表示了线性表(a1, a2, a3, a4, a5)，而另一个单链表AV是将当前 sd 中的空结点组成的链表。 DatanextSL=004 1a45 2a23 3a31 4a12 5a5-1 AV=667 78 89 910 1011 11-1o 数组sd的定义如下： o #define MAXSIZE /*足够大的数*/ o typedef stru