线性表完整版课件

1、1.2 线性表 线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。1.2 线性表1. 线性表（Linear List)的定义 具有相同数据类型的n(n0)个数据元素组成的有限 序列。 数据元素之间具有的逻辑关系为线性关系的数据元素集合称为线性表。 n为线性表的长度, 长度为0的线性表称为空表。1.2 线性表2. 线性表的表示L=( a1，a2，a3，ai-1，ai ，ai+1，,.,an ) 表头表尾这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。3. 线性结构特点:(1)有且只有一个根结点a

2、1 ，无前驱 。(2)有且只有一个终端结点an ，无后继 。(3)其他结点有且只有一个直接前驱和一个直接后继。1.2 线性表几个线性表的例子： 数列： ( 25， 12， 78， 34， 100， 88)1a1 a2 a3 a4 a5 a6一个数据元素为一个整数2字母表： ( A， B， C， , Z)a1 a2 a3 a26一个数据元素为一个字母1.2 线性表简单线性表几个线性表的例子：数据文件：399001张 华 女17 99002李 军 男18 99003王 明 男17 99050刘 东 女19 学号 姓 名性别年龄其 他 一个数据元素为一个记录a1a2a3 a50.1.2 线性表复杂线

3、性表 用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映。 ( a1，a2，a3， . . , an ) 所谓一个元素的 是指该元素占用的若干(连续的)存储单元的第一个单元的地址。地址LOC(ai)a1a2a3an d1 d2 d3 dn 1.2.2 线性表的顺序存储结构 若假设每个数据元素占用k个存储单元，并且已知第一个元素的存储位置LOC(a1)，则有 LOC(ai) = LOC(a1)+(i1)ka1a2a3an 结论：LOC(a1)=100 k=4 求LOC(a5)=?a1a2a3an a4a5100 104 108 112 116

4、 LOC(a5) = 100+(5 1)4=116事先分配给线性表的空间当前已经占用的空间尚未使用的空间#define M 100datatype AM;int n;C 语言1) 顺序存储结构： 2) 第i个元素地址顺序表的基本运算 插入和删除1)顺序表的插入运算: 在线性表的第i个元素之前插入一个新的元素，先移动，后插入。ABCDEFGH空闲空间插队前大哥，求求你？ABCDEFGH空闲空间插队后大哥，谢谢你！1) 顺序存储结构： 2) 第i个元素地址顺序表的基本运算 插入和删除1)顺序表的插入运算: 在线性表的第i个元素之前插入一个新的元素，先移动，后插入。ai-1.a2a1anai+1ai

5、 x ai-1. a2 a1 ai an an ai+1 ai ai x插入程序举例(在8个数中任意位置插入一个数)：#define N 8main() int aN+1=12,34,45,6,78,9,10,91, i,j,x; printf(“input the location to be inserted:”); scanf(“%d,%d”,&i,&x); ai-1=x; for(j=0;j=N;j+) printf(“%d,”,aj);for(j=i-1;j=i-1;j-) aj+1=aj;插入运算时间性能分析：在第i个位置上作插入x,则需将第i个至第n个元素移动，即共需移动(n-i

6、+1)个元素。插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数(期望值)：pi：在第i个位置上作插入的概率。等差数列求和公式: (首项+末项)项数)/2(n-i+1)MOVEi线性表(a0,a1,a2)平局移动元素个数:()*(3+2+1+0)=1.5在一线性表(a0,a1,a2)中插入任意一数i，求平局移动元素次数: i 移动次数(n-i+1) 1(插入到第个数a0前) 3 2 (插入到第2个数a1前) 23 (插入到第3个数a2前) 1 (插入到第3个数a2后) 0 1) 顺序存储结构： 2) 第i个元素地址顺序表的基本运算插入和删除2)顺序表删除运

7、算：定义：指将表中第i个元素从线性表中去掉。原表长为n：( a1，a2，ai-1，ai ，ai+1， an ) 新表长为n-1：( a1，a2，ai-1，ai+1， ， an ) 步骤：(1)将ai+1 an， 顺序向前移动(2)表长减一ABCDEFGH空闲空间逃离后ABCDEFGH空闲空间逃离前骗子，还我钱(删除第五个元素21) 6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 867顺序表的基本运算2)顺序表删除运算：时间性能分析：时间消耗与插入运算相同，平均移动元素次数：qi:在第i个位置上作插入的概率。设qi=1/n

8、共需移动(n-i)个元素。 i 移动次数(n-i) 1(删除第1个数a0) 22 (删除第2个数a1) 13 (删除第3个数a2) 0线性表(a0,a1,a2)平局移动元素个数:(1/3)*(2+1+0)=1在一线性表(a0,a1,a2)中删除任意一数i，求平局移动元素次数:作业：有一数组，存储十个数，编程序删除其中任意一个数。重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素 因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表顺序表优点和缺点优点：逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。缺点：插入和删

9、除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；容易造成存储空间的“碎片”思路(链式存储）：元素可以散落在任何位置，不必相邻让每个元素知道它的下一个元素在哪里我们只需要知道第一个元素的位置插入删除不再需要移动元素而是需要修改元素间的关系123456234561顺序存储结构不足的解决办法 假定上图为当前内存的使用情况，阴影部分为已用内存，现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为8的连续的存储空间。但实际上，系统的可用内

10、存远大于该线性表所要求的内存空间，应采用其它的存储结构链式存储。当前内存的状态建立一个含有8个元素的线性表 L=(a1,a2,a3, a4, a5, a6, a7, a8) 可以采用链式存储结构，每一个数据元素占用两个存储单元，其中一个用来存放数据元素的值，另外一个存放下一个数据元素存储单元的地址，这种结构称为链式存储结构。在这种结构中，数据元素存放是不连续的。 a1Heada2a3 a4a5a6a7a8地址数据指针6462149594327901137991a24212743495990a1a3a7 a6a4a5a86499027594321Head链式存储结构特点:1.2.3 线性表的链式

11、存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存储：线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。 1.2.3 线性表的链式存储结构2.线性链表:定义：线性表的链式存

12、储结构称为线性链表数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的 前一个结点或后一个结点 线性链表中结点组成：1.2.3 线性表的链式存储结构结合C语言：链表就是一组组的数据用链将它连起来，如下图所示。 数据1数据2数据5数据3数据4数据链问题是用什么来存放数据，用什么来作为链。解决办法?数据1指针数据2指针数据3指针数据域指针域从上图知，可以定义一个结构，其中一部分存放数据，另一部分存放指向下一数据的指针。这就构成了单链表。节点每组数据和指针称为链表的一个节点。351.分配内存函数： malloc() 原型在stdlib.h中 1)调用方式 void *malloc(u

13、nsigned size) 2)功能 在内存中分配size个字节的存储空间，并返回指向分配存储区起始地址的指针；如果不能获得需要的存储空间，将返回空指针。 注：在把返回值赋给具有一定数据类型的指针变量时，应对返回值作强制类型转换。结合C语言：跟链表相关的函数36例：为1000个字符动态分配内存 char *p; p=(char *)malloc(1000); 结合C语言：37 struct data int no; char name10; int score; ; struct data *p; p=(struct data *)malloc(sizeof(struct data); if

14、(p=NULL) puts(“out of memoryn”); exit(1); 结合C语言：exit()函数:被定义在stdlib.h中 0: 程序正常终止 非0：程序非正常终止382. calloc()函数 原型在stdlib.h中 1)调用方式 void *calloc(unsigned n, unsigned size) 2)功能 分配n个具有size个字节的存储空间，并返回一个指向被分配内存起始地址的指针；如果没有足够的内存满足要求，则返回一个空指针结合C语言：393. free()函数 原型在stdlib.h中 1)调用方式 void free(void *ptr) 2)功能 释

15、放由ptr指向的内存空间，并将它返回给堆 注：free()只能由前面动态内存分配函数中所分配地址的那个指针来调用结合C语言：头结点是在链表的起始结点之前附加的一个结点.带头结点的单链表123head123head头结点单链表带头结点的单链表head空表head 空表head-next=NULL头结点有两个优点：由于起始结点的位置被存放在头结点的指针域中，故在链表的第一个位置上的操作与表中其他位置上操作一致，无须进行特殊处理。无论链表是否为空，其头指针都是指向头结点的非空指针，故此空表和非空表的处理也统一了。起始结点 struct Node int data; struct Node *next

16、; ;struct Node * head;head-next(head-next) -data起始结点的地址6链表的访问struct Node * p ; p=head-next;head63120pp=p-next;pp=p-next;pp-next=NULL 表明p到达表尾结点p=p-next;p=0 空指针 对于线性链表，可以从头指针(head)开始，沿各结点的指针扫描到链表中的所有结点。 typedef struct Node int data; struct Node *next; LinkList;LinkList * head;新的类型名代换旧的类型名，即：LinkList等价

17、与struct node struct Node int data; struct Node *next; ;struct Node * head;将当前结点的元素值赋给xx=p-data;LinkList * p ; int x ; x6pLinkList * p ; int x ; p将x赋给当前结点，修改当前结点的元素值 x=10;p-data=x;10 尾插法建立单链表（n个节点）特点：头指针固定不变，新产生的结点总是链接到链表的尾部。操作步骤：（1）进行定义：head为头指针，tail为尾指针，p为结点。 （2）建立头节点 head=(struct node *) malloc( s

18、izeof(struct node); head-next=NULL; tail=head; （3）生成新结点（p），输入数据 p=(struct node *) malloc( sizeof(struct node); scanf(“%d”,&p-data); p-next=NULL;（4）链接到表尾 tail-next=p; tail=p;（5）重复（3）（4），继续建立新结点，直到n个节点为止。当表空时，头指针和尾指针同时指向头节点47struct node char name10; int wage; struct node *next; ;48定义头指针、尾指针、新节点指针初始化（带

19、头节点）开辟新节点节点个数next=NULL; tail=head; for( i=0; idata); p-next=NULL; tail-next=p; tail=p; return head; / 建立头结点/ 用tail标记链表尾部/生成新结点/输入结点的数据域/链接到表尾/ 更新尾指针/ 返回链表的头指针3 .单链表: 定义：由n个结点链接，且每个结点中只包含一个指针域的链表。 例：线性单链表( A, B, C, D, E, F )ABCDEhead F1.2.3 线性表的链式存储结构逻辑结构存储结构3 .单链表: (1)单链表插入：增加新结点,修改链接指针后插结点在指针p所指结点之

20、后插入一个指针s所指的结点修改p和s所指结点的指针域的指针即可 1.2.3 线性表的链式存储结构插入步骤修改s指针域,使其指向p结点的后继结点:snext=pnextp B C Xs A修改p指针域, 使其指向新结点s: pnexts考虑上述两步骤若颠倒会怎样？插入步骤修改s指针域,使其指向p结点的后继结点:snext=pnextp B C Xs A修改p指针域, 使其指向新结点s: pnexts后面的结点都将从链表中脱离它们占用着内存空间，程序却找不到它们了3 .单链表: (2)单链表删除：不需要移动元素,仅修改指针链接删除结点删除p指向的结点只修改p(被删除结点)的前驱结点的指针域即可 1

21、.2.3 线性表的链式存储结构删除步骤修改q结点指针域 qnextpnextCpBA删除前删除后qpCBAfree(p);先找到p的前驱结点qqnextqnextnext1)存储空间动态分配，可以按需要使用；2)插入/删除结点操作时，只需要修改指针，不必移动数据元素优点缺点1)每个结点需加一指针域，存储密度降低；2)非随机存储结构，查找定位操作需要从头指针出发顺着链表扫描。线性表的链式存储结构优缺点存储分配方式顺序存储结构用一段连续的存储单元依次存储线性表的数据元素单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素时间性能查找顺序存储结构O(1)单链表O(n)插入和删除顺序存储结构需

22、要平均移动表长一半的元素，时间为O(n)单链表在找出某位置的指针后，插入和删除的时间仅为O(1)空间性能顺序存储结构需要预分配存储空间，分大了，浪费，分小了，易发生溢出单链表不需要预分配一整块存储空间，只要有就可以分配，元素个数也不受限制链式存储结构和顺序存储结构的比对：假设我们的校园只有单行道保安沿这条路线巡逻，需要查遍所有地点。有一天，保安先从主教出发，想把以上地点走一遍，此时主管告诉他，不行，你必须从主校门开始走。主校门办公楼图书馆体育馆机电楼主教逸夫楼北门事实上，把主校门和北门连接起来，形成一个环路，就解决了这个问题。单链表的尴尬4.循环链表特点：表中最后一个结点的指针域指向头结点，

23、整个链表首尾相连形成一个环。 带头结点的循环链表1.2.3 线性表的链式存储结构优点：从表中任一结点出发均可找到表中其它结点。对带头结点的单循环链表head为空的判定条件是 head-next=head带头结点的空循环链表例：假设长度大于1的循环单链表中，既无头结点也无头指针，p指向该链表中某一结点，编写一个算法删除该结点的前驱结点。单链表只能从头结点开始遍历整个链表，而循环单链表则可以从表中任意结点开始遍历整个链表。.a1a2an-1a0ps=p;while(s-next-next!=p) s=s-next;如何寻找前驱结点？s指向该结点的前驱结点的前驱结点ss-next=p;删除该结点的前

24、驱结点思考：对于单链表而言，连接两个单链表应该如何实现？.a0head1a1an-1.b0head2b1bn-1currentcurrent-next=head2-next对于循环单链表呢？.a0head1a1an-1.b0head2b1bn-1pp=head1-next;head1-next=head2-next-next;Head2-next=p;.a0head1a1an-1.b0head2b1bn-1p主校门办公楼图书馆体育馆机电楼主教逸夫楼北门终于有一天，保安在感叹：如果我们有双行道该多好啊！双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结

25、点的指针域。07/08/2022645.双向链表定义：在双向链表中，每个结点有两个指针域，next 指向后继结点，prior指向前趋结点。 datapriornext结点构成：1.2.3 线性表的链式存储结构作用：可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找的不足。head.ana2a1nextprior对指向双向链表任一结点的指针p，有下面的关系：p-next-prious=p-prious-next=ppnextpriouspriousnext设对象引用p表示双向链表中的第i个结点，则p.next表

26、示第 个结点，p.next.prior表示第 个结点，即p.next.prior = p；同样地，p.prior表示第 个结点，p.prior.next仍表示第 个结点，即p.prior.next = p。双向链表的关系i+1ii-1i5.双向链表(1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。p插入前cbax待插入的结点:q1.2.3 线性表的链式存储结构cbaxqpp结点作为q结点的前驱:q-prior=p；p结点的后继作为q结点的后继:q -next=p-next；q结点作为p 结点的后继结点的前驱结点:p-next-prior=qq

27、结点作为p结点的后继:p-next=q； (p的后继指向新结点q)确定新结点q的前驱和后继5.双向链表p删除前cba(2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。1.2.3 线性表的链式存储结构p p的后继结点作为p结点前驱结点的后继 (a c) p的前驱结点作为p结点后继结点的前驱 ( a c) p-prior-next = p-next；p-next-prior= p-prior；free(p)；cba习题讲解1. 线性表的顺序存储结构和线性表的链式存储结构分别是_。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、

28、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构2. 在单链表中，增加头结点的目的是_。 A. 方便运算的实现 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现BA3 用链表表示线性表的优点是_。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取4.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为200,则第12个元素的存储地址是_. A. 248 B. 247 C. 246 D. 244AD5. 下列

29、对于线性链表的描述中正确的是_。(05.4月 ）A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的A6. 线性表是（） A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空7在一个长度为n的线性表中，删除值为x的元素时需要比较元 素和移动元素的总次数为（） A. （n+1）/2 B.n/2 C. n D.n+18. 一个长度为n的顺序存储的线性表中，向第i个元素(1

30、in+1) 位置插入一个新元素时，需要从后面向前依次后移（ ）个元 素。 A. n-i B. n-i+1 C. n-i-1 D. iACB9.设单链表中指针p指向结点ai,若要删除ai之后的结点（若存 在），则需修改指针的操作为（）。A. p-next= p-next-next B. p=p-next C. p=p-next-next D. next=p10.设单链表中指针p指向结点ai,指针q指向将要插入的新结点 x，则当x插在链表中两个数据元素ai和ai+1之间时，只要先 修改 q-next=p-next，后修改（）即可。A. p-next= q B. p-next= p-next-nex

31、t C. p-next=q-next D. q-next=null 11.在一个单链表中，若要在p所指向的结点之后插入一个新结 点，则需要相继修改（）个指针域的值。 A. 1 B. 2 C. 3 D.4AAB12.不带头结点的单链表L为空的判定条件是（）。A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL13带头结点的单链表L为空的判定条件是（）。A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL14.在一个带有头结点的双向循环链表中，若要在p所指向的结点

32、之前插入一个新结点，则需要相继修改（）个指针域的值。A. 2 B. 3 C. 4 D.6ABC15.在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q-next赋值为（）A. p-prior B. p-next C. p-next-next D. p-prior -prior16.线性表采用链式存储时，其地址（）A. 必须是连续的B. 一定是不连续的C. 部分地址必须是连续的D. 连续与否均可以BD17. 下列叙述中正确的是：(2010年9月国二） A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空

33、间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对 B1.在一个单链表中删除指针p所指向结点时，应执行一下操作： q=p-next; p-data= p-next-data; p-next=_； free(q);p-next-nextpqABBC2. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把_ _ 的值赋给q-next，然后把_的值赋给p-next。p-nextq3.假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针p所指向的新结点时，首先执行_ _赋值操作，然后执行_ _ 赋值操

34、作。 p-next=headhead=pheadp4. 在一个单链表中删除指针p所指向结点的后继结点时，需要把_的值赋给p-next指针域。p-next-next5. 在_链表中，既可以通过设定一个头指针也可 以通过设定一个尾指针来确定它，即通过头指针或 尾指针可以访问到该链表中的每个结点。 循环6. 在一个带有头结点的双向循环链表中的p所指向的结 点之前插入一个指针s所指向结点时,可执行如下操作：(1) s -prior=_；(2) p-prior-next=s;(3) s-next=_;(4) p-prior=_;p-priorpsps7. 线性表的长度是指_。 线性表中包含数据元素的个数

35、 8.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_。 单链表、双链表 9. 循环单链表与非循环单链表的主要不同是循环单链表的尾结 点指针_，而非循环单链表的尾结点指针_。 指向链表头节点 指向空 10.访问单链表中的结点，必须沿着_依次进行。 指针域 11. 在双向链表中，每个结点有两个指针域，一个指向_， 另一个指向_。前驱节点 后续节点 12. 在一个双向链表中删除指针p所指向的结点时，需要对 p-next-prior指针域赋值为_。 p-prior 13.设head为单循环链表L的头结点，则L为空表的条件是_。 head-next=head 14. 在一个长度为n的顺序表