第二章 线性表.ppt

1、第2章 线性表,本章主要介绍下列内容 线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例,退出,2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 线性表的应用举例,2.1 线性表的逻辑结构,2.1.1 线性表的定义 线性表是由n（n0）个类型相同的数据元素组成的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线

2、性表。,举例 La=（34，89，765，12，90，-34，22） 数据元素类型为int。 Ls=(Hello,World, China, Welcome) 数据元素类型为string。 Lb=(book1,book2,.,book100) 数据元素类型为下列所示的结构类型： struct bookinfo int No; /图书编号 char *name; /图书名称 char *auther; /作者名称 .; ,2.1.2 线性表的基本操作 线性表初始化：Init_List(L) 求线性表的长度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_

3、List(L,x) 插入操作：Insert_List(L,i,x) 删除操作：Delete_List(L,i),2.2 线性表的顺序存储结构,2.2.1 线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：,图2-1 线性表顺序存储结构示意图,其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai+1)=LOC(a1)+(i-1)*L 顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻数据

4、元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；,（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。 在C语言中，实现线性表的顺序存储结构的类型定义 #define MAXSIZE 100 /线性表的最大长度 typedef struct datatype dataMAXSIZE; int last; SeqList;,2.2.2 典型操作的算法实现 初始化线性表L SeqList *init_S

5、eqList( ) SeqList *L; L=malloc(sizeof(SeqList); L-last=-1; return L; ,2.在线性表L中第i个数据元素之前插入数据元素X 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-dat

6、aj; /* 结点移动 */ L-datai-1=x;/*新元素插入*/ L-last+; /*last仍指向最后元素*/ return (1);/*插入成功，返回*/ ,3. 删除操作 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); /*删除成功*/ ,在线性表L中检索值为X的数据元素 int Loc

7、ation_SeqList(SeqList *L, datatype x) int i=0; while(idatai!= x) i+; if (iL-last) return -1; else return i; /*返回的是存储位置*/ ,插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： 分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其

8、做插入或删除操作时，这一点需要值得考虑。,2.3 线性表的链式存储结构,线性表顺序存储结构的特点 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 l在做插入或删除元素的操作时，会产生大量的数据元素移动； l对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； l线性表的容量难以扩充。,线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每

9、个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2-2所示的形式存储：,图2-2 线性表链式存储结构示意图,术语 表示每个数据元素的两部分信息组合在一起被称为结点； 其中表示数据元素内容的部分被称为数据域（data）； 表示直接后继元素存储地址的部分被称为指针或指针域（next）。 单链表简化的图2-3描述形式,图 2-3 单联表结构示意图,其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）

10、符号表示。 带头结点的单链表 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图2-4所示：,图 2-4 带头结点的单链表结构示意图,链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,在C语言中，实现线性表的链式存储结构的类型定义 typedef struct node datatype

11、data; struct node *next; LNode，*LinkList； 定义头指针变量： LinkList H；,2.3.2 典型操作的算法实现 (1)在链表的头部插入结点建立单链表 LinkList Creat_LinkList1( ) LinkList L=NULL；/*空表L为表头*/ Lnode *s; int x; /*设数据元素的类型为int*/ scanf(%d, ,2. 求表长(带头结点的) int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向头结点*/ int j=0; while (p-next) p=p-n

12、ext; j+ /* p所指的是第 j 个结点*/ return j; ,3. 查找操作 (1) 按序号查找 Get_Linklist(L,i) Lnode * Get_LinkList(LinkList L, Int i); /*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/ Lnode * p=L; int j=0; while (p-next !=NULL ,(2)按值查找即定位 Locate_LinkList(L,x) Lnode * Locate_LinkList( LinkList L, datatype x) /*在单链表L中查找值为x的结点，找到后返回其指针，否

13、则返回空*/ Lnode * p=L-next; while ( p!=NULL ,4.插入操作 int Insert_LinkList( LinkList L, int i, datatype x) /*在单链表L的第i个位置上插入值为x的元素*/ Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(参数i错);return 0; /*第i-1个不存在不能插入*/ else s=malloc(sizeof(LNode); /*申请、填装结点*/ s-data=x; s-next=p-next; /*新结点

14、插入在第i-1个结点的后面*/ p-next=s return 1; ,5. 删除操作 int Del_LinkList(LinkList L，int i) /*删除单链表L上的第i个数据结点*/ LinkList p,s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(第i-1个结点不存在);return -1; else if (p-next=NULL) printf(第i个结点不存在);return 0; else s=p-next; /*s指向第i个结点*/ p-next=s-next; /*从链表中删除*/ free(

15、s); /*释放*s */ return 1; ,2.3.3 循环链表 若将链表中最后一个结点的next域指向 实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。,图2-7 带头结点的循环链表示意图,2.3.4 双向循环链表 在循环链表中，访问结点的特点 访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。 结论：循环链表并不适用于经常访问前驱结点的情况。 解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。 双向链表就是每个结点有两个指针域。一个指向后继结点，另

16、一个指向前驱结点。,图 2-8,(a),(b),用C语言实现双向循环链表的类型定义 typedef struct dlnode datatype data; struct dlnode *prior,*next; DLNode,*DLinkList;,（1）在双向循环链表DL中，第i个数据元素之前插入数据元素e 在一个结点之前插入一个新结点的过程。 在双向循环链表中的p结点之前插入s结点应使用下列语句序列： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;,图 2-9,双向链表中结点的删除 p-prior-next=p-next; p-

17、next-prior=p-prior; free(p);,x,x,P,2.4 线性表的应用举例,例22 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。,算法如下： void merge(SeqList A, SeqList B, SeqList *C) int i,j,k; i=0;j=0;k=0; while ( idatak+=A.datai+; else C-datak+=B.dataj+; while (idatak+= A.datai+; while (jdatak+=B.dataj+; C-last=k-1; 算法的时间复杂度是O(m+n)，其中m是A的表长，n是B的表长。,2.4 应用举例 例2.4 已知单链表H，写一算法将其倒置。即实现如图2.22的操作。(a)为