【数据结结构ppt课件】线性表.ppt

《【数据结结构ppt课件】线性表.ppt》由会员分享，可在线阅读，更多相关《【数据结结构ppt课件】线性表.ppt（69页珍藏版）》请在三一办公上搜索。

1、Thursday, November 17, 2022,1,数据结构课件,西北大学计算机系,本演示文稿可能包含观众讨论和即席反应。使用 PowerPoint 可以跟踪演示时的即席反应，在幻灯片放映中，右键单击鼠标请选择“会议记录”选择“即席反应”选项卡必要时输入即席反应单击“确定”撤消此框此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。,Thursday, November 17, 2022,2,第2章 线性表,2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加,Thursday, November 17, 2022,

2、3,2.1 线性表的概念及运算,2.1.1 线性表的逻辑结构 2.1.2 线性表的抽象数据类型定义,Thursday, November 17, 2022,4,线性表的定义,线性表(Linear List)是由n (n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1， ，an）。 数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。 线性表的逻辑结构图为：,Thursday, November 17, 2022,5,线性表的特点,同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个

3、数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。,Thursday, November 17, 2022,6,2.1.2 线性表的抽象数据类型定义,抽象数据类型定义 ：ADT LinearList数据元素：D=ai| aiD0, i=1,2,，n n0 ，D0为某一数据对象 关系： | ai, ai+1D0，i=1,2, ,n-1 基本操作： （1）InitList（L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 （2）DestroyList(L) 操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L)

4、操作前提：线性表L已存在 。 操作结果：将表L置为空表。 ADT LinearList,Thursday, November 17, 2022,7,2.2 线性表的顺序存储,2.2.1 线性表的顺序存储结构 2.2.2 线性表顺序存储结构上的基本运算,Thursday, November 17, 2022,8,顺序存储结构的定义,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。 假设线性表中每个元素

5、占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为： loc(ai) =loc(a1)+(i-1)k,Thursday, November 17, 2022,9,顺序存储结构示意图,Thursday, November 17, 2022,10,顺序存储结构的C语言定义,#definemaxsize=线性表可能达到的最大长度；typedef struct ElemType elemmaxsize； /* 线性表占用的数组空间*/ int last； /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/ SeqList；注意区分元素的序号和数组的下标，如

6、a1的序号为1，而其对应的数组下标为0。,Thursday, November 17, 2022,11,2.2.2 线性表顺序存储结构的基本运算,线性表的基本运算：查找操作 插入操作 删除操作顺序表合并算法线性表顺序存储结构的优缺点分析,Thursday, November 17, 2022,12,查找操作,线性表的两种基本查找运算按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。按内容查找Locate（L,e）: 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若

7、找不到，则返回一个“空序号”，如-1。 线性表的查找运算算法描述为：,Thursday, November 17, 2022,13,线性表的查找运算,int Locate(SeqList L，ElemType e)i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while (i=L.last) /*若没找到，则返回空序号*/,Thursday, November 17, 2022,14,插入操作,线性表的插入运算是指在表的第i (1in+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，ei-1，ei，en) 变成长度为n+1的线性表（e1，,ei-1，e，ei，

8、en）。 线性表的插入运算算法。,Thursday, November 17, 2022,15,插入算法示意图,已知：线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，,Thursday, November 17, 2022,16,插入运算,int InsList(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) ) /*首先判断插入位置是否合法*/ printf(“插入位置i值不合法”)；return(

9、ERROR); if(L-last=maxsize-1) printf(“表已满无法插入”)； return(ERROR); for(k=L-last;k=i-1;k-) /*为插入元素而移动位置*/ L-elemk+1=L-elemk; L-elemi-1=e; /*在C语言中数组第i个元素的下标为i-1*/ L-last+; return(OK);算法演示（此处连接算法演示程序）。,Thursday, November 17, 2022,17,删除操作,线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表 (e1，,ei-1，ei，ei+1，en)，变成长度为n-1的线性

10、表(e1，,ei-1， ei+1，en)。 算法思路示意 算法实现,Thursday, November 17, 2022,18,删除算法示意,将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。,Thursday, November 17, 2022,19,删除算法,int DelList(SeqList *L,int i,ElemType *e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/ int k; if(iL-last+1) printf(“删除位置不合法！”)； return(ERROR)； *e= L-elemi-1; /* 将

11、删除的元素存放到e所指向的变量中*/ for(k=i;ilast;k+) L-elemk-1= L-elemk; /*将后面的元素依次前移*/ L-last-; return(OK);,Thursday, November 17, 2022,20,合并算法,已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。 算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.el

12、emj ，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。算法实现此处连接算法演示,Thursday, November 17, 2022,21,顺序表合并算法实现,void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0;j=0;k=0; while(ilast ,Thursday, November 17, 2022,22,顺序存储结构的优点和缺点,优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间； 2.可方便地随机存取表中的任一元素。 缺点：1.插入

13、或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低； 2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。,Thursday, November 17, 2022,23,2.3 线性表的链式存储,链表定义： 采用链式存储结构的线性表称为链表 。现在我们从两个角度来讨论链表：1.从实现角度看，链表可分为动态链表和静态链表；2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。,Thursday, November 17, 2022,24,2.3.1 单链表 2.3.2 单链表上的

14、基本运算 2.3.3 循环链表 2.3.4 双向链表 *2.3.5 静态链表 2.3.6 顺序表和链表的比较,链表,Thursday, November 17, 2022,25,2.3.1 单链表,结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。 单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。 单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。头指针 ：指向链表头结点的指针。,Thursday, Novem

15、ber 17, 2022,26,单链表的示例图,Thursday, November 17, 2022,27,带头结点的单链表示意图,有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点。带头结点的空单链表 带头结点的单链表,Thursday, November 17, 2022,28,单链表的存储结构描述,typedef struct Node / * 结点类型定义 * / ElemType data； struct Node * next；Node, *LinkList；/* LinkList为结构指针类型*/,Thursday, November 17, 2022,29,2.

16、3.2 单链表上的基本运算,线性表的基本运算：建立单链表 单链表查找 单链表插入操作 单链表删除 算法应用示例：求单链表的长度 求两个集合的差,Thursday, November 17, 2022,30,建立单链表,头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。,Thursday, November 17, 2022,31,头插法建表算法,Linklist CreateFromHead() LinkList L; Node *s; int flag=1; /* 设置一个标志，初值

17、为1，当输入“$”时，flag为0，建表结束*/ L=(Linklist)malloc(sizeof(Node)；/*为头结点分配存储空间*/ L-next=NULL; while(flag) c=getchar(); if(c!=$) /*为读入的字符分配存储空间*/ s=(Node*)malloc(sizeof(Node); s-data=c; s-next=L-next; L-next=s; elseflag=0; ,Thursday, November 17, 2022,32,尾插法建表,C1 ,s,r,L,Thursday, November 17, 2022,33,尾插法建表算法,

18、Linklist CreateFromTail() /*将新增的字符追加到链表的末尾*/ LinkList L; Node *r, *s; int flag =1; L=(Node * )malloc(sizeof(Node);/*为头结点分配存储空间*/ L-next=NULL; r=L; /*r指针始终动态指向链表的当前表尾*/ while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/ c=getchar(); if(c!=$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s else flag=0; r-

19、next=NULL; ,Thursday, November 17, 2022,34,单链表查找,按序号查找 算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL-next），用j做记数器，累计当前扫描过的结点数（初值为0），当j = i 时，指针p所指的结点就是要找的第i个结点 。算法实现，算法演示。,Thursday, November 17, 2022,35,按序号查找算法实现,/ * 在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存

20、储位置; 否则返回NULL * /Node * Get(LinkList L, int i) Node *p； p=L；j=0； / * 从头结点开始扫描 * / while (p-next!=NULL)&(jnext； j+； / * 扫描下一结点 * / / * 已扫描结点计数器 * / if（i= =j）return p； / * 找到了第i个结点 * / else return NULL； / * 找不到，i0或in * /,Thursday, November 17, 2022,36,按值查找算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值

21、为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。,单链表查找,Thursday, November 17, 2022,37,按值查找算法实现,/ * 在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL * /Node *Locate( LinkList L,ElemType key) Node *p; p=L-next; / * 从表中第一个结点比较 * / while (p!=NULL) if (p-data!=key) p=p-next; else br

22、eak; / * 找到结点key，退出循环 * / return p;,Thursday, November 17, 2022,38,单链表插入操作,算法描述： 要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。,s,a1,ai-1,ai,s,pre,L,Thursday, November 17, 2022,39,单链表插入操作算法实现,void InsList(LinkList L,int i,E

23、lemType e) /*在带头结点的单链表L中第i个结点之前插入值为e的新结点。 */ Node *pre,*s; pre=L; int k=0; while(pre!=NULL,Thursday, November 17, 2022,40,单链表删除,算法描述： 欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。,Thursday, November 17, 2022,41,单链表删除算法实现,void DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中

24、删除第i个元素，并保存其值到变量*e中*/ Node *p,*r; p=L; int k =0;while(p-next!=NULL /*释放被删除的结点所占的内存空间*/,Thursday, November 17, 2022,42,求单链表的长度,算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p-next=NULL）。intListLength(LinkList L) /*L为带头结点的单链表*/ Node *p; p=L-next; j=0; /*用来存放单链表的长度*/ while(p!=NULL) p

25、=p-next; j +; return j;算法演示链接。,Thursday, November 17, 2022,43,求两个集合的差,已知：以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。算法实现算法演示链接,Thursday, November 17, 2022,44,求两个集合的差算法实现,void Difference (LinkL

26、ist LA,LinkList LB) /*此算法求两个集合的差集*/ Node *pre;*p, *r; pre=LA;p=LA-next; /*p向表中的某一结点，pre始终指向p的前驱*/ while(p!=NULL) q=LB-next; /*扫描LB中的结点，寻找与LA中*P结点相同的结点*/ while (q!=NULL ,Thursday, November 17, 2022,45,2.3.3 循环链表,循环链表(Circular Linked List) 是一个首尾相接的链表。 特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的

27、循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。 带头结点循环单链表示意图。,Thursday, November 17, 2022,46,带头结点的循环单链表示意图,空链表,带头结点的一般形式,带尾结点的一般形式,Thursday, November 17, 2022,47,循环单链表合并为一个循环单链表,已知：有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表

28、的头结点。,Thursday, November 17, 2022,48,循环单链表合并算法实现,LinkList merge_1(LinkList LA,LinkList LB)/*此算法将两个链表的首尾连接起来*/ Node *p, *q; p=LA; q=LB; while (p-next!=LA) p=p-next;/*找到表LA的表尾*/ while (q-next!=LB) q=q-next;/*找到表LB的表尾*/ q-next=LA;/*修改表LB 的尾指针，使之指向表LA 的头结点*/ p-next=LB-next;/*修改表LA的尾指针，使之指向表LB 中的第一个结点*/f

29、ree(LB); return(LA);,Thursday, November 17, 2022,49,2.3.4 双向链表,双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双 ( 向) 链表 (Double Linked List)。双向链表的结构定义：typedef struct Dnode ElemType data； struct DNode *prior，*next； DNode,* DoubleList；,Thursday, November 17, 2022,50,双链表的结构定义,双链表的结点结构,Thurs

30、day, November 17, 2022,51,双向循环链表示意图,空的双向循环链表,非空的双向循环链表,Thursday, November 17, 2022,52,双向链表的前插操作,算法描述：欲在双向链表第i个结点之前插入一个的新的结点，则指针的变化情况如图所示。,Thursday, November 17, 2022,53,双向链表的前插操作算法实现,void DlinkIns(DoubleList L,int i,ElemType e) DNode *s,*p; /*首先检查待插入的位置i是否合法*/ /*若位置i合法，则让指针p指向它*/ s=(DNode*)malloc(si

31、zeof(DNode); if (s) s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return TRUE; else return FALSE; 算法演示连接。,Thursday, November 17, 2022,54,双向链表的删除操作,算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示。,Thursday, November 17, 2022,55,双向链表的删除操作算法实现,intDlinkDel(DoubleList L,int i,ElemType *e)DNode *p; /*首

32、先检查待插入的位置i是否合法*/ /*若位置i合法，则让指针p指向它*/ *e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return TRUE; ,Thursday, November 17, 2022,56,双向链表应用举例,已知：设一个循环双链表L=（a,b,c,d）编写一个算法将链表转换为L=（b,a,c,d）。算法思想：实际上是交换表中前两个元素的次序。算法实现：voidswap(DLinkList L) DNode * p,*q,*h; h=L-next; /* h指向表中的第一个结点，即a */ p=h

33、-next; /* p指向b结点 */ q=h-prior; /* 保存a 结点的前驱 */ h-next=p-next; p-next-prior=h; /*变换指针指向*/ p-prior=q; p-next=h; L-next=p;,Thursday, November 17, 2022,57,*2.3.5 静态链表,基本概念：游标实现链表的方法：定义一个较大的结构数组作为备用结点空间（即存储池）。当申请结点时，每个结点应含有两个域：data域和next域。data域存放结点的数据信息，next域为游标指示器，指示后继结点在结构数组中的相对位置（即数组下标）。数组的第0个分量可以设计成表

34、的头结点，头结点的next域指示了表中第一个结点的位置，为0表示静态单链表的结束。我们把这种用游标指示器实现的单链表叫做静态单链表(Static Linked List)。静态链表的结构定义，静态链表的插入和删除操作示例。 基本操作：初始化、分配结点与结点回收、前插操作、删除。,Thursday, November 17, 2022,58,静态链表的结构定义,#define Maxsize= 链表可能达到的最大长度typedef struct ElemType data; int cursor; Component, StaticListMaxsize;,Thursday, November

35、17, 2022,59,静态链表的插入和删除操作示例,已知：线性表 a，b，c，d，f，g，h，i），Maxsize=11,Thursday, November 17, 2022,60,静态链表初始化,算法描述：初始化操作是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：void initial(StaticList space,int *av) int k; space0-cursor=0;/*设置静态单链表的头指针指向位置0*/ for(k=0;kcursor=k+1; /*连链*/ spaceMaxsize-1=0; /

36、*标记链尾*/ *av=1; /*设置备用链表头指针初值*/ ,Thursday, November 17, 2022,61,静态链表分配结点与结点回收,分配结点int getnode(int *av)/*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/ int i=*av; *av=space*av.cur; return i; 结点回收void freenode(int *av,int k) /*将下标为 k的空闲结点插入到备用链表*/ spacek.cursor=*av; *av=k; ,Thursday, November 17, 2022,62,静态链表前插操作,算法描述

37、：1、先从备用单链表上取一个可用的结点；2、将其插入到已用静态单链表第i个元素之前。void insbefore(StaticList space,int i,int *av) j=*av ;/*j为从备用表中取到的可用结点空间的下标*/ av=spaceav-cursor;/*修改备用表的头指针*/ spacej-data=x; k=space0-cursor;/*k为已用静态单链表的第一个元素的下标值*/ for(m=1;mcursor; spacej-cursor=spacek-cursor; /*修改游标域*/ spacek-cursor=j;,Thursday, November 1

38、7, 2022,63,静态链表删除,算法描述：首先寻找第i -1个元素的位置，之后通过修改相应的游标域进行删除；在将被删除的结点空间链到可用静态单链表中，实现回收。void delete(StaticList space;int i;int *av ) k=space0-cursor; for(m=1,mcursor ; j=spacek-cursor ; spacek-cursor=spacej-cursor;/*从删除第i个元素*/ spacej-cursor=*av;/*将第i 个元素占据的空间回收*/ av=j ; /*置备用表头指针以新值*/,Thursday, November 1

39、7, 2022,64,2.3.6 顺序表和链表的比较,1基于空间的考虑 2基于时间的考虑 3基于语言的考虑,Thursday, November 17, 2022,65,2.4 一元多项式的表示及相加,一个一元多项式Pn(x)可按升幂的形式写成：Pn(x)=p0+p1x+p2x2+p3x3+ +pnxn 在计算机内，可以用一个线性表P来表示： P=（p0，p1，p2， ，pn） 用单链表存储多项式的结点结构如下： typedef struct Polynode int coef; int exp; Polynode *next; Polynode , * Polylist;,Thursday,

40、 November 17, 2022,66,建立多项式链表,算法描述：输入多项式的系数和指数，用尾插法建立一元多项式的链表。Polylist polycreate() Polynode *head, *rear, *s; int c,e; rear=head =(Polynode *)malloc(sizeof(Polynode); /*建立多项式的头结点， rear 始终指向单链表的尾*/ scanf(“%d,%d”,Thursday, November 17, 2022,67,多项式的单链表表示示意图,说明：图示分别为多项式A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x

41、8,Thursday, November 17, 2022,68,两个多项式相加,运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。算法实现，算法演示若p-expexp，则结点p所指的结点应 是“和多项式”中的一项，令指针p后移；若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结

42、点。,Thursday, November 17, 2022,69,两个多项式相加算法实现,void polyadd(Polylist polya;Polylist polyb) /* p和q分别指向polya和polyb链表中的当前计算结点*/ /* pre指向和多项式链表中的尾结点*/ while p!=NULL & q!=NULL） if （p-expexp） /*将p结点加入到和多项式中*/ else if ( p-exp= =q-exp） /*若指数相等，则相应的系数相加。若系数为0则删除p，q节点*/ else /*将q结点加入到和多项式中*/ ./*将多项式polya或polyb中剩余的结点加入到和多项式中*/,