VC编程教程 第2章 线性表.ppt

1、第2章 线性表,本章主要介绍下列内容 线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例,本章学习要求 了解：线性表的基本概念和基本运算。 掌握：顺序表的存储结构和查找、插入、删除等基本运算。 掌握：单链表的存储结构以及单链表的建立、查找、插入、删除等操作。 掌握：双向链表的存储结构以及插入、删除操作。 了解：静态链表的存储结构和基本运算。 掌握：利用线性表的基本运算解决复杂问题。,2.1 线性表的逻辑结构 2.2 线性表的顺序存储及运算实现 2.3 线性表的链式存储和运算实现 2.4 顺序表和链表的比较,2.1 线性表的逻辑结构,2.1.1 线性表的定义 2

2、.1.2 线性表的基本运算,定义：一个线性表是具有相同类型的n（n0）个数据元素的有限序列，通常记为： L=,特征： L为线性表名称，习惯用大写书写； ai为数据元素，习惯用小写书写； i为元素的序号 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项,2.1.1 线性表的定义,线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继

3、,举例 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; /作者名称 .; ,初始化：Init_List(L) 构造一个空的线性表 求长度:Length_List(L)返回表中所含元素的个数 取表元:Get_List(L,i)返回第i个元素的值或地址 按值查找

4、:Locate_List(L,x)返回首次出现x的序号或地址，查找失败时返回一个特殊值 插入:Insert_List(L,i,x)在第i个位置上插入一个值为x的元素 删除:Delete_List(L,i)删除序号为i的数据元素,2.1.2 线性表的基本运算,2.2 线性表的顺序存储及运算实现,2.2.1 顺序表的定义 2.2.2 顺序表上存储结构的实现 2.2.3 顺序表上基本运算的实现 2.2.4 顺序表应用举例,元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*d 1in 其中，d为每个数据元素所占据的存储单元数目。 特点： 逻辑上相邻物理地址相邻 随机存取 实现：可用C语言

5、的一维数组实现,LOC(a1)+(n-1)*d,LOC(a1),LOC(a1)+(i-1)*d,存储地址,LOC(a1)+d,2.2.1 顺序表的定义,顺序表：用一组地址连续的存储单元顺序存放线性表的各元素叫,#define MAXSIZE 1000 datatype dataMAXSIZE; int last;,例 typedef int datatype; 例 typedef struct card int num; char name20; char author10; char publisher30; float price; datatype;,2.2.2存储结构的实现,空表时：

6、last=-1,SeqList L;,#define MAXSIZE 100 /线性表的最大长度 /通常将data和length封装成一个结构作为顺序表的类型： typedef struct datatype dataMAXSIZE; int last; /线性表的当前长度 SeqList;,SeqList *L;,线性表存储空间的获取通过L=(SeqList *)malloc(sizeof(SeqList);,根据C语言中函数参数的传递采用值传送的规则，有时定义一个指向SeqList 类型的指针更为方便，能够实现信息的回送，因此我们定义一个指针类型： typedef SeqList *PSe

7、qList ； PSeqList是一个能够指向SeqList 类型变量的指针类型；如 SeqListPoint是一个指针变量，线性表的存储空间可通过 SeqListPoint=( PSeqList )malloc(sizeof(SeqList) 操作来获得，也可以通过SeqListPoint=j=i-1;j-) L-dataj+1=L-dataj;,（2）将x置入空出的第i个位置 L-datai-1=x;,算法,（3）修改last指针 L-last+;,算法实现,基本操作：数据的移动 第i个元素上插入一个元素所需移动的元素次数：,性能分析,平均移动次数：设Pi是在第i个元素上插入一个元素的概率

8、，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,n-i+1,由于 1 i n+1，共有 n1个位置可以插入，即：,（1）检查表是否存在，若不存在退出； （2）检查删除位置的合法性（ i 是否为1ilength）若不满足，退出； （3）将a i+1an往前移动,删除 定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表,变成长度为n-1的线性表,Ch2_2.c,步骤：,（4）修改last指针,算法,（1）将a i+1an往前移动 for(j= i;jlast;j+) L-dataj-1=L-dataj;,（2）修改last指针 L-last-;,算法实

9、现,性能分析,平均移动次数：设pi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,基本操作：数据的移动 第i个元素上删除一个元素所需移动的元素次数：,n-i,分析结论 故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,按值查找 定义：在线性表存在的情况下，查找值与给定值x相等的数据元素，若成功，返回在表中首次出现的值为x的那个元素的序号(不是下标)；,算法,算法评价 基本操作：数据比较 时间复杂度：,2.2.4 顺序表应用举例,例2-1将顺序

10、表（a1，a2，an）重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大。,基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： if(aia1) 继续比较下一个; if(aia1) 将它上面的元素依次下移一个位置; ai放入最上面; ,内存,5,6,7,4,an,0,1,4,数组下标,n-1,5,n,8,3,2,3,例2-2有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也按从小到大的升序排列。,基本思路： 依次扫描A和B的元素，比较当前元素ai和bj： if(aibj) ai赋给Ck; i+;k+； else

11、bj赋给Ck; j+;k+； 将未完的那个顺序表中余下部分赋给C;,课本例题2.1 P31,例2.1有一线性表的顺序表示 (a1，a2， ，an) ，设计一算法将该线性表逆置成逆线性表(an，an-1， ，a1)，要求用最少的辅助空间。 解题思路：可考虑将a1与an交换，a2与an-1交换，ai与an - i+1交换，其中1in/2 逆线性表仍占用原顺序表空间，只用一个辅助空间。,优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充,顺序存储结构的优缺点,2.3 线性表的链式存储结构,特

12、点： 用一组任意的存储单元存储线性表的数据元素 利用指针存储其前驱或后继的存储单元地址 每个结点，除存储本身信息外，还需额外空间存储其逻辑关系,例,2.3.1 单链表 2.3.2 单链表上基本运算的实现 2.3.3 循环链表 2.3.4 双向链表 2.3.5 静态链表 2.3.6 单链表应用举例,单链表,1、结点结构 线性表的链接表示的目的是用一组可以是不连续的存储单元，存储线性表的各个元素，为了表示每个元素与其后继元素之间的逻辑关系，每个元素除了需要存储自身信息外，还要存储一个指示其后继元素的信息，即后继元素的地址。这样每个结点包括两个域：值域（data）-存放元素本身的信息；指针域（lin

13、k）-存放其后继结点的存储位置。,例,线性表h=(A,B,C,D,E,F)的链式存储结构如图1所示。 由于这种链表中，每个结点只有一个指针域，故又称为单链表。指向链表中第一个结点的指针，称为这个链表的头指针(h)。,图1 线性表h的链式 存储结构,h,图2 单链表h的逻辑结构示意图,h,在讨论链表时，主要关心的只是线性表中元素之间的逻辑顺序，而不是每个元素在存储器中的位置，所以通常可把图1的单链表，更加直观地表示成图2所示的用箭头相链接的结点序列，其中h代表头指针。,注：图中用“”表示空指针，在算法中用NULL表示。,2、单链表的类型定义,typedef struct Node *PNode;

14、 /* 结点指针类型 */ struct Node /* 单链表结点结构 */ DataType data; /* 值域 */ struct Node *next; /* 指针域 */ ; 为提高可读性,可定义单链表类型如下: typedef struct Node *LinkList; LinkList list; /* 定义一单链表list */ PNode p; /* 定义一单链表结点指针*/,则指针p所指结点的两个域表示为： 值域： p-data 指针域： p-next,p,指针域,值域,为使运算简单,可以在单链表的第一个结点之前另加一个结点，称之为头结点。头结点的data字段可以存放

15、与整个链表相关的信息（例如元素个数等），也可以不存任何信息，头结点的next字段指向第一个结点，如图3所示。,图3 带头结点的单链表,注：设置表头结点的目的是统一空链表与非空链表的操作，简化链表操作的实现。带头结点的空链表表示为：list-next=NULL;而不带头结点的空链表只能表示为list=NULL;,3、头结点的概念与作用,头结点,第一个结点,2.3 .2 单链表上基本运算的实现,1、建立单链表 2、求表长 3、查找 4、插入 5、删除,1、建立单链表,（1）在链表的头部插入结点建立单链表,例：线性表（25，45，18，76）,建立一个空表； 读入一个数据元素值； while（未结束

16、） 申请一个新结点空间；,算法描述,x,s-next=H-next;,H-next=s;,将数据元素值填入新申请的结点空间中；,读入下一个数据元素值； ,将该结点插入到链表的头部；,算法思想：,（2）在链表的尾部插入结点建立单链表,例：线性表（25，45，18，76）,建立一个空表,头指针为L，L指向头结点； 设置尾指针r，r指向头结点; 读入一个数据元素值； while（未结束） 申请一个新结点空间,将数据元素值填入；,算法描述,修改尾指针; 读入下一个数据元素值； ,将该结点插入到尾指针r的后面；,算法思想：,2、求表长,算法思想： 设置一个计数器j，初值为0； 设置一个指针p，从第一个结

17、点开始扫描； while（未结束） j+; 扫描下一个结点； ,算法描述,（1）按序号查找：,算法思想： 设置一个计数器j，初值为0； 设置一个指针p，从第一个结点开始扫描； while（未结束 扫描下一个结点； ,算法描述,3、查找,（2）按值查找：,算法思想： 设置一个指针p，从第一个结点开始扫描； while（未结束,p-next=s;,4、插入,前插结点：设p指向单链表某一结点,s指向待插入的值为x的结点,将s插入到p的前面,s-next=p;,q-next=s;,q=L; while(q-next!=p) q=q-next;,找到第i-1个结点； 申请新结点空间,将x填入; 将新结点

18、插入到第i-1个结点后面；,算法描述,算法评价,将数据元素插入到第i个位置的算法思想：,算法描述,算法评价,删除结点：单链表中删除b，设p指向a,s=p-next; p-next=s-next; free(s);,5、删除,单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢,循环链表是表中最后一个结点的指针指向头结点，使链表构成环状,2.3 .3循环链表(circular linked list),特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-next=NUL

19、L 循环链表p或p-next=H,设置尾指针的循环链表,设置尾指针的循环链表，在对两个单循环链表进行连接使可以提高效率。,r1-next=r2-next-next;,r2-next=p;,p=r1-next;,单链表具有单向性的缺点，找前驱不方便！ 结点定义,typedef struct dlnode datatype data; struct node *prior,*next; DuNode,*DLinkList;,p-prior-next= p= p-next-proir;,2.3 .4双向链表（double linked list）,void del_dlinklist(DuNode

20、*p) p-prior-next=p-next; p-next-prior=p-prior; free(p); ,删除,算法描述,算法评价：T(n)=O(1),p-prior-next=p-next;,p-next-prior=p-prior;,void ins_dlinklist(DuNode* p,int x) DuNode *s; s=(DuNode*)malloc(sizeof(DuNode); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; ,算法描述,算法评价：T(n)=O(1),插入,p-prior-

21、next=s;,s-prior=p-prior;,s-next=p;,p-prior=s;,2.3 .5静态链表,SL=0,静态链表： #define MAXSIZE typedef struct datatype data; int next; /静态指针 SNode; SNode sdMAXSIZE; int SL,AV;,AV=6,SL： （a1,a2,a3,a4,a5）,头结点,头指针,空闲链表头指针,1、静态链表的结构,静态链表中存储空间的申请,/分配一个结点空间 int malloc_SList() int t; if(AV=-1)return 1; t=AV; AV=sdAV.n

22、ext; return t; ,2、静态链表的运算,静态链表中存储空间的释放,/释放t所指 的结点空间 void free_SList(int t) sdt.next=AV; AV=t; ,7,静态链表中查找第i个结点,算法思想： 设置一个计数器j，初值为0； 设置一个指针p指向头结点； while（未结束 扫描下一个结点； ,/查找静态表中第i个结点 int get_SList(int SL,int i) int p,j; j=0; p=SL; while(sdp.next!=-1 ,例2-4在带头结点的静态链表中SL的第i个结点之前插入值为x的新结点。,申请一个新结点空间t；,例:在SL：

23、 （a1,a2,a3,a4,a5）中将x插入第2个位置.,插入之后变成 SL： （a1,x,a2,a3,a4,a5）,算法思想： 查找将第i-1个结点，将p指向它；,将x填入新结点t；,将新结点t插入p的后面；,x,sdt.next=sdp.next,2,sdp.next=t,6,2.3 .6单链表应用举例,例2-5已知单链表H,写一算法将其倒置。P44例2.4,基本思路： 设置新链表; 依次取原链表的每个结点; while(原链表还有结点) 将该结点插入到新链表的头部;,例2-6删除单链表H中重复的结点。,基本思路： 将p指向第一个结点; while(p非空) 删除p之后与p值相同的结点;,

24、例2-7两个单链表A、B递增有序，归并A、B成递减有序的链表C。,基本思路： 将p、q分别指向A、B第一个结点; while(p非空且q非空) if（p值q值)p插在C的头部;p指向下一个结点; else q插在C的头部;q指向下一个结点; 将A、B剩余部分插在C的头部；,例2-8 求解约瑟夫问题。,设由n个人围坐在一个圆桌周围，现从第s个人开始从1报数，数到m的人出列，然后从出列的下一个人重新开始从1报数，数到m的人再出列如此反复，直到所有的人都出列，求出出列的次序,约瑟夫问题的两种实现方法,1.用顺序表：从第 s 个元素开始计数到第s+m-1 个元素，输出该元素，从删除的元素的下一个元素重复该过程，如果计数到表尾则转第一个元素重新计数，一直到顺序表空。 2.用单链表： （1）在不带头结点的循环链表中查找第s个结点，用p作为第s个结点的指针，pre指向p 的前驱； （2）从p所指的结点开始计数查找第m个结点； （3）输出该结点元素值； （4） 删除该结点，同时将该结点下一结点指针作为当前指针即p指针，重复到步骤（2），直到链表中所有结点都被删除完为止。,顺序存储的C语言算法,int josephus_ SeqList (PSeqList josephus_seq, i