《计算机应用基础》1.2线性表ppt课件

1、第第 1 1 章章 数据构造数据构造 1.1 根本数据构造与算法根本数据构造与算法 1.2 线性表线性表 1.3 栈和队列栈和队列 1.4 树和二叉树树和二叉树 1.5 查找查找 1.6 内部排序内部排序ABCDEFG姓名姓名 学号学号 成果成果 班级班级 李红李红 9761059 95 机机97.6 10658651.2 线性表1. 线性表的定义线性表的定义1) 定义：具有一样数据类型的定义：具有一样数据类型的n(n0)个数据元素组成的有限序个数据元素组成的有限序列。是最简单、最常用的数据构造。列。是最简单、最常用的数据构造。 2) 表示表示: L=( a0，a2，a3，ai-1，ai ，a

2、i+1，,.,an-1 ) 其中其中: n: n为线性表长度为线性表长度(n=0(n=0称为空表称为空表) )，表中相邻元素之间，表中相邻元素之间存在着顺序关系。存在着顺序关系。a0 a0 ：表头元素；：表头元素；an-1 an-1 ：表尾元素；：表尾元素；ai-1ai-1称为称为aiai的直接前驱；的直接前驱；ai+1 ai+1 称为称为aiai的直接后继。的直接后继。 表头表尾1.2 线性表1. 线性表的定义线性表的定义1) 定义：具有一样数据类型的定义：具有一样数据类型的n(n0)个数据元素组成的有限序个数据元素组成的有限序列。是最简单、最常用的数据构造。列。是最简单、最常用的数据构造。

3、 2) 表示表示: L=( a0，a2，a3，ai-1，ai ，ai+1，.,an-1 ) 3) 线性构造特点线性构造特点:(1)(1)有且只需一个根结点有且只需一个根结点a0 a0 ，无前驱，无前驱 。(2)(2)有且只需一个终端结点有且只需一个终端结点an-1 an-1 ，无后继，无后继 。(3)(3)其他结点有且只需一个直接前驱和一个直接后继。其他结点有且只需一个直接前驱和一个直接后继。1.2 线性表1. 线性表的定义线性表的定义1) 定义：具有一样数据类型的定义：具有一样数据类型的n(n0)个数据元素组成的有限序个数据元素组成的有限序列。是最简单、最常用的数据构造。列。是最简单、最常用

4、的数据构造。 2) 表示表示: 3) 线性构造特点线性构造特点:4) 线性表的分类线性表的分类 (1)简单线性表：简单线性表： 数据元素是简单项数据元素是简单项(数字、字母、季节名等数字、字母、季节名等)。 如如:(12,34,4,67,8) (2)复杂线性表：复杂线性表： 数据元素由假设干个数据项组成，此时数据元素称为记数据元素由假设干个数据项组成，此时数据元素称为记录或结点录或结点, 如学生成果表如学生成果表.L=( a0，a2，a3，ai-1，ai ，ai+1，.,an-1 ) 学生安康情况登记表如下：姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631 男男

5、 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经衰弱神经衰弱 . . .1.1.顺序表根本概念顺序表根本概念1.2.2 线性表的顺序存储构造1) 顺序存储构造：顺序存储构造： 用一组地址延续的存储空间依次存放线性表的各元素用一组地址延续的存储空间依次存放线性表的各元素 。顺序表：顺序表：采用顺序存储构造的线性表称为顺序表采用顺序存储构造的线性表称为顺序表(一维数组一维数组) 表中的一切元素所占存储空间延续表中的一切元素所占存储空间延续表中各元素在存储空间中按逻辑顺序存放表中各元素在存储空间中按逻

6、辑顺序存放 顺序存储构造特点顺序存储构造特点1.2 线性表1.1.顺序表根本概念顺序表根本概念4.2.2 线性表的顺序存储构造1) 顺序存储构造：顺序存储构造： 2) 第第i个元素地址个元素地址4.2 线性表其中其中:m：每个元素占：每个元素占m个存储单元个存储单元Loc(a0)第一个元素地址第一个元素地址(基址基址) mi)Loc(a)Loc(a0ian1.ai.a1a0bb+mb+i*mb+n*m存储地址存储地址存储形状存储形状空闲空闲数据元素在线性表中的位序数据元素在线性表中的位序12n i 从存取方式看,线性表的顺序存储构造是可以随机存储的存储构造. 1. 1.顺序表根本概念顺序表根本

7、概念1.2.2 线性表的顺序存储构造1) 顺序存储构造：顺序存储构造： 2) 第第i个元素地址个元素地址1.2 线性表2.顺序表的根本运算顺序表的根本运算 存取存取: 访问线性表的第访问线性表的第i个元素，运用或改动数个元素，运用或改动数据元素的值。据元素的值。 查找查找: 在线性表中查找满足某种条件的数据元在线性表中查找满足某种条件的数据元素。素。 插入插入: 在线性表的第在线性表的第i个元素之前，插入一个同个元素之前，插入一个同类型的元素。类型的元素。 (*) 删除删除: 删除线性表中第删除线性表中第i个元素。个元素。 (*) 求表长求表长: 求出线性表中元素的个数。求出线性表中元素的个数

8、。 置空表置空表: 建立一个空表。建立一个空表。 去除表去除表: 将已有线性表变为空表，即删除表中一将已有线性表变为空表，即删除表中一切元素。切元素。 1. 1.顺序表根本概念顺序表根本概念1.2.2 线性表的顺序存储构造1) 顺序存储构造：顺序存储构造： 2) 第第i个元素地址个元素地址1.2 线性表2.顺序表的根本运算顺序表的根本运算 ai-1.a1a0an-1ai+1ai x ai-1. a1 a0 ai an an-1 ai+1 ai ai先挪动先挪动后插入后插入 x步骤：步骤：(1)将将ai an顺序向后挪动顺序向后挪动,为新元素让出位置为新元素让出位置(2)将将x置入空出的第置入空

9、出的第i个位置个位置举例：举例：( (在第在第4 4个和第个和第5 5个元素之间插入元素个元素之间插入元素91) 91) 6741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 8212191插入程序举例插入程序举例( (在在8 8个数中恣意位置插入一个数个数中恣意位置插入一个数) )：#define N 8#define N 8main()main() int aN+1=12,34,45,6,78,9,10,91, i,j,x; int aN+1=12,34,45,

10、6,78,9,10,91, i,j,x; printf(“input the location to be inserted: printf(“input the location to be inserted:);); scanf(“%d,%d scanf(“%d,%d,&i,&x);,&i,&x); ai-1=x; ai-1=x; for(j=0;j=N;j+) for(j=0;j=N;j+) printf(“%d, printf(“%d,aj);,aj); for(j=i-1;j=N-1;j+)for(j=i-1;j=i-1;j-)for(j=N-1;j=i-1;j-) aj+1=aj;

11、 aj+1=aj;在第在第i i个位置上作插入个位置上作插入x,x,那么需将第那么需将第i i个至第个至第n n个元素挪动，个元素挪动，即共需挪动即共需挪动(n-i+1)(n-i+1)个元素。个元素。插入运算时间性能分析：插入运算时间性能分析：插入运算，时间主要耗费在数据挪动上。在长度为插入运算，时间主要耗费在数据挪动上。在长度为n n的线性的线性表中插入一个元素，那么平均挪动元素次数表中插入一个元素，那么平均挪动元素次数( (期望值期望值) )：?) 1(11niiisinpEpipi：在第：在第i i个位置上作插入的概率。个位置上作插入的概率。等差数列求和公式等差数列求和公式: (首项首项

12、+末项末项)项数项数)/211) 1(11niinn11npi(n-i+1)2n线性表线性表(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. 1.顺序表根本概念顺序表根本概念1.2.2 线性表的顺序存储构造1) 顺序存储构造：

13、顺序存储构造： 2) 第第i个元素地址个元素地址1.2 线性表2.顺序表的根本运算顺序表的根本运算 2)2)顺序表删除运算：顺序表删除运算：定义：指将表中第定义：指将表中第i i个元素从线性表中去掉。个元素从线性表中去掉。原表长为原表长为n n：( a0( a0，a1a1，ai-1ai-1，ai ai ，ai+1ai+1， an-1 ) an-1 ) 新表长为新表长为n-1n-1：( a0( a0，a1a1，ai-1ai-1，ai+1ai+1， ， an-1 ) an-1 ) 步骤：步骤：(1)将将ai+1 an-1， 顺序向前挪顺序向前挪动动(2)表长减一表长减一举例：举例：( (删除第五个

14、元素删除第五个元素21) 21) 6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 8时间性能分析：时间性能分析：时间耗费与插入运算一样，平均挪动元素次数：时间耗费与插入运算一样，平均挪动元素次数：niniidlninninqE1121)(1)(qi:qi:在第在第i i个位置上作插入的概率。设个位置上作插入的概率。设qi=1/n qi=1/n 共需挪动共需挪动(n-i)(n-i)个元素。个元素。67 i 挪动次数挪动次数(n-i) 1(删除第删除第1个数个数a0) 22 (删除第删除第2个数个数a1) 13 (删除第删除第3

15、个数个数a2) 0线性表线性表(a0,a1,a2)平平局挪动元素个数局挪动元素个数:(1/3)*(2+1+0)=1在一线性表在一线性表(a0,a1,a2)中删除恣意一数中删除恣意一数i，求平局挪动元，求平局挪动元素次数素次数:niniidlninninqE1121)(1)(作业：有一数组，存储十个数，作业：有一数组，存储十个数，编程序删除其中恣意一个数。编程序删除其中恣意一个数。 1. 1.顺序表根本概念顺序表根本概念3.3.顺序表优点和缺陷顺序表优点和缺陷优点：优点：逻辑上相邻元素存储位置也相邻逻辑上相邻元素存储位置也相邻, ,无需添加额外存无需添加额外存储空间可方便随机存取表中任一元素。储

16、空间可方便随机存取表中任一元素。缺陷：缺陷：插入和删除运算不方便插入和删除运算不方便, ,必需挪动大量结点必需挪动大量结点, ,效率效率较低不适宜元素经常变动的大的线性表。较低不适宜元素经常变动的大的线性表。1.2.2 线性表的顺序存储构造1.2 线性表2.顺序表的根本运算顺序表的根本运算链式存储构造特点链式存储构造特点: :1.2.3 线性表的链式存储构造存储空间可以不延续。存储空间可以不延续。不要求逻辑上相邻的元素在物理位置上也相邻。不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由指针域确定。数据元素间逻辑关系由指针域确定。1.2 线性表即即 链表存储构造是一种动态数据构造，

17、其特点是它包含链表存储构造是一种动态数据构造，其特点是它包含的据对象的个数及其相互关系可以按需求改动，存的据对象的个数及其相互关系可以按需求改动，存储空间是程序根据需求在程序运转过程中向系统恳储空间是程序根据需求在程序运转过程中向系统恳求获得，链表也不要求逻辑上相邻的元素在物理位求获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储构造所具有的弱点。置上也相邻，它没有顺序存储构造所具有的弱点。 zhang33531082548#namesumnext构造体构造体元素元素构造体元素构造体元素的地址的地址构造体元素的构造体元素的成员是地址型成员是地址型数据数据struct stud

18、ent char name10; int sum; struct student *next; ;pstruct student *p; strcpy(p-name,zhang)；p-sum=335;p-next=? zhang33531082548#bai32831483108#zhao35231883148#wu34703188#headp1p2p3有四个构造体元素：有四个构造体元素：zhang33531082548#bai32831483108#zhao35231883148#wu34703188#head有四个构造体元素：有四个构造体元素：head3尾结点的指针域置为尾结点的指针域置为

19、“NULL空，作空，作为链表终了的标志为链表终了的标志1头指针变量头指针变量head指向链表的首结点。指向链表的首结点。2每个结点由每个结点由2个域组成：个域组成： 1数据域数据域存储结点本身的信息。存储结点本身的信息。 2指针域指针域指向后继结点的指针。指向后继结点的指针。zhang33531082548#bai32831483108#zhao35231883148#wu347NULL3188#struct student char name10; int sum; struct student *next; ;链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :定义：线性表

20、的链式存储构造称为线性链表定义：线性表的链式存储构造称为线性链表1.2.3 线性表的链式存储构造数据域数据域: 一部分存放数据元素值一部分存放数据元素值 指针域指针域: 存放指针存放指针,用于指向该结点的用于指向该结点的 前一个结点或后一个结点前一个结点或后一个结点 线性链表中线性链表中结点组成：结点组成：分类：单链表、循环单链表、双向链表分类：单链表、循环单链表、双向链表 Data next next 1.2 线性表其单链表表示图如下：其单链表表示图如下： 有一线性表有一线性表: : (bat (bat，catcat，eateat，fatfat，hathat，jatjat，latlat，ma

21、t)mat)hathat200200.catcat135135eateat170170.matmatNullNullbatbat130130fatfat110110jatjat205205latlat160160 110 130 160头指针头指针 head 165 170 200 205 165简化为：简化为：链尾链尾略略bat cat eat mat 单链表是由表头独一确定，因此单链表可以用头指针的名字来命名。例如：假设头指针名是head，那么把链表称为表head。head用C言语描画的单链表如下： struct node char name20; struct node *next;st

22、ruct node *head; typedef struct node char name20; struct node *next;LinkList;LinkList *head;新的类型名代换旧的类新的类型名代换旧的类型名，型名，也就是说：也就是说：LinkList等等价与价与struct node链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :1.2.3 线性表的链式存储构造1.2 线性表3 .单链表单链表: 定义：由定义：由n个结点链接，且每个结点中只包含一个个结点链接，且每个结点中只包含一个指针域的链表。指针域的链表。 例：线性单链表例：线性单链表( A, B,

23、 C, D, E, F )( A, B, C, D, E, F )逻辑形状逻辑形状 ABCDEhead F其中其中: head称为单链表的头指针称为单链表的头指针,指向表中的第一个结点指向表中的第一个结点物理形状物理形状 E7FNULLB25A13C31D1头指针头指针 存储地址存储地址 数据域数据域 指针域指针域 19 1713192531单链表存取单链表存取: :必需从头必需从头指针开场进展，依次顺指针开场进展，依次顺着指针向链尾方向扫描。着指针向链尾方向扫描。找到各个元素找到各个元素, ,因此说因此说线性表的链式存储构造线性表的链式存储构造是一种顺序存储的存储是一种顺序存储的存储构造。构

24、造。ABCDEhead FABCDEhead FABCDEhead F带头节点的单链表带头节点的单链表编程：创建带头节点的单链表。编程：创建带头节点的单链表。程序算法：1定义三个构造体类型的指针变量head, p, s2利用malloc函数开辟头结点，由head, p共同来指向3再利用malloc函数开辟相应的内存空间，由s来指向4由键盘输入数据，赋给s所指向的内存空间5p-next=s;6p=s;7回到第3步;程序算法：1定义三个构造体类型的指针变量head, p, s2利用malloc函数开辟头结点，由head, p共同来指向3再利用malloc函数开辟相应的内存空间，由s来指向4由键盘输

25、入数据，赋给s所指向的内存空间5p-next=s;6p=s;7回到第3步;head=p=(strutc node*) malloc(sizeof(struct node);headpv对带头结点的复杂链表的根本操作对带头结点的复杂链表的根本操作创建创建程序算法：1定义三个构造体类型的指针变量head, p, s2利用malloc函数开辟头结点，由head, p共同来指向3再利用malloc函数开辟相应的内存空间，由s来指向4由键盘输入数据，赋给s所指向的内存空间5p-next=s;6p=s;7回到第3步;As-data=getchar();spv对带头结点的复杂链表的根本操作对带头结点的复杂链

26、表的根本操作创建创建headp程序算法：1定义三个构造体类型的指针变量head, p, s2利用malloc函数开辟头结点，由head, p共同来指向3再利用malloc函数开辟相应的内存空间，由s来指向4由键盘输入数据，赋给s所指向的内存空间5p-next=s;6p=s;7回到第3步;spv对带头结点的复杂链表的根本操作对带头结点的复杂链表的根本操作创建创建AsheadpBABCDEhead FABCDEhead F带头节点的单链表带头节点的单链表 typedef struct nodechar data;struct node *next; Linklist; Linklist *head

27、,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(input letters to create a list:n); while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; 编程：创建带头节点的单链表。编程：创建带头节点的单链表。带头节点的单链表带头节点的单链表 typedef struct nodechar data; struct node *next; Link

28、list; Linklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(input letters to create a list:n); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; 2000Bdata next struct nodechar data; struct node *next; Linklist; Link

29、list *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(input letters to create a list:n); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; Aheadp用户输入为：ABCsptypedef struct nodechar data; struct node *next; Linklist; Link

30、list *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(input letters to create a list:n); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; Ahead用户输入为：ABCspsBptypedef struct nodechar data; struct node *next; Linklist; Li

31、nklist *head,*p,*s; char ch; head=(Linklist *)malloc(sizeof(Linklist); printf(input letters to create a list:n); p=head; while(ch=getchar()!=n) s=(Linklist *)malloc(sizeof(Linklist); s-data=ch; p-next=s; p=s; p-next=NULL; Ahead用户输入为：ABCsBpsCpNULLtypedef链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :1.2.3 线性表的链式存

32、储构造1.2 线性表3 .单链表单链表: (1)(1)单链表插入：添加新结点单链表插入：添加新结点, ,修正链接指针修正链接指针后插结点后插结点在指针在指针p p所指结点之后插入一个指针所指结点之后插入一个指针s s所指的结点所指的结点修正修正p p和和s s所指结点的指针域的指针即可所指结点的指针域的指针即可 插入步骤插入步骤修正修正s s指针域指针域, ,使其指向使其指向p p结点的后继结点结点的后继结点:s:snext=pnext=pnextnextp B C Xs A修正修正p指针域指针域, 使其指向新结点使其指向新结点s: pnexts思索上述两步骤假设颠倒会怎样？思索上述两步骤假设

33、颠倒会怎样？插入步骤插入步骤修正修正s s指针域指针域, ,使其指向使其指向p p结点的后继结点结点的后继结点:s:snext=pnext=pnextnextp B C Xs A修正修正p指针域指针域, 使其指向新结点使其指向新结点s: pnexts思索上述两步骤假设颠倒会怎样？思索上述两步骤假设颠倒会怎样？后面的结点都将从后面的结点都将从链表中脱离链表中脱离它们占用着内存空间，程它们占用着内存空间，程序却找不到它们了序却找不到它们了链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :1.2.3 线性表的链式存储构造1.2 线性表3 .单链表单链表: (2)(2)单链表删除：不

34、需求挪动元素单链表删除：不需求挪动元素, ,仅修正指针链接仅修正指针链接删除结点删除结点删除删除p p指向的结点指向的结点只修正只修正p(p(被删除结点被删除结点) )的前驱结点的指针域即可的前驱结点的指针域即可 删除步骤删除步骤修正修正q q结点指针域结点指针域 q qnextnextp pnextnextCpBA删除前删除前删除后删除后qpCBAfree(p);先找到先找到p的前驱结点的前驱结点qq qnextnextq qnextnextnextnext链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :1.2.3 线性表的链式存储构造1.2 线性表3 .单链表单链表:

35、4.4.循环链表循环链表特点：表中最后一个结点的指针域指向头结点，整特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连构成一个环。个链表首尾相连构成一个环。 带头节点的循环链表带头节点的循环链表优点：从表中任一结点出发均可找到表中其它结点。优点：从表中任一结点出发均可找到表中其它结点。对带头结点的单循环链表对带头结点的单循环链表head为空的断定条件是为空的断定条件是 head-next=head带头结点的空循环链表带头结点的空循环链表链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :1.2.3 线性表的链式存储构造1.2 线性表3 .单链表单链表: 4.4.循环链表

36、循环链表5.5.双向链表双向链表定义：在双向链表中，每个结点有两个指针域，定义：在双向链表中，每个结点有两个指针域，nextnext 指向后继结点，指向后继结点，priorprior指向前趋结点。指向前趋结点。 datapriornext结点构成：结点构成：作用：可以方便地沿向前或向后两个方向查找。抑制作用：可以方便地沿向前或向后两个方向查找。抑制单链表中每个结点只能找到它的后继结点，不能找到单链表中每个结点只能找到它的后继结点，不能找到前驱结点。假设要找前驱结点，必需从头指针开场重前驱结点。假设要找前驱结点，必需从头指针开场重新查找的缺乏。新查找的缺乏。head.ana2a1nextprio

37、r对指向双向链表任一结点的指针对指向双向链表任一结点的指针p，有下面的关系：，有下面的关系：p-next-priou=p-priou-next=ppnextpriouspriousnext链式存储构造特点链式存储构造特点: :2.2.线性链表线性链表: :1.2.3 线性表的链式存储构造1.2 线性表3 .单链表单链表: 4.4.循环链表循环链表5.5.双向链表双向链表(1)插入结点：在插入结点：在p指针所指的结点后插入一个结点指针所指的结点后插入一个结点q，只需，只需求修正求修正p,q结点的结点的prior和和next域即可。域即可。p插入前插入前cbax待插入的结点待插入的结点:qcbax

38、qpp p结点作为结点作为q q结点的前驱结点的前驱:q-prior=p:q-prior=p；p p结点的后继作为结点的后继作为q q结点的后继结点的后继:q -next=p-next:q -next=p-next；q q结点作为结点作为p p 结点的后继结点的前驱结点结点的后继结点的前驱结点:p-next-prior=q:p-next-prior=qq q结点作为结点作为p p结点的后继结点的后继:p-next=q:p-next=q； (p (p的后继指向新结点的后继指向新结点q)q)确定新结确定新结点点q q的前的前驱和后继驱和后继链式存储构造特点链式存储构造特点: :2.2.线性链表线性

39、链表: :1.2.3 线性表的链式存储构造1.2 线性表3 .单链表单链表: 4.4.循环链表循环链表5.5.双向链表双向链表p删除前删除前cba(2)删除结点：删除删除结点：删除P指针所指结点，只需修正指针所指结点，只需修正P指针的前驱和后指针的前驱和后继结点的继结点的next，prior域即可。域即可。p p的后继结点作为的后继结点作为p结点前驱结点的后继结点前驱结点的后继 (a c) p p的前驱结点作为的前驱结点作为p p结点后继结点的前驱结点后继结点的前驱 ( a ( a c) c) p-prior-next = p-next；p-next-prior= p-prior；free(p

40、)；cba习题讲解习题讲解1. 1. 线性表的顺序存储构造和线性表的链式存储构造线性表的顺序存储构造和线性表的链式存储构造分别是分别是_。 A. A. 顺序存取的存储构造、顺序存取的存储构造顺序存取的存储构造、顺序存取的存储构造 B. B. 随机存取的存储构造、顺序存取的存储构造随机存取的存储构造、顺序存取的存储构造 C. C. 随机存取的存储构造、随机存取的存储构造随机存取的存储构造、随机存取的存储构造 D. D. 恣意存取的存储构造、恣意存取的存储构造恣意存取的存储构造、恣意存取的存储构造2. 2. 在单链表中，添加头结点的目的是在单链表中，添加头结点的目的是_。 A. A. 方便运算的实

41、现方便运算的实现 B. B. 使单链表至少有一个结点使单链表至少有一个结点 C. C. 标识表结点中首结点的位置标识表结点中首结点的位置 D. D. 阐明单链表是线性表的链式存储实现阐明单链表是线性表的链式存储实现3 用链表表示线性表的优点是用链表表示线性表的优点是_。 A. 便于插入和删除操作便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序一样数据元素的物理顺序与逻辑顺序一样 C. 破费的存储空间较顺序存储少破费的存储空间较顺序存储少 D. 便于随机存取便于随机存取4.某线性表采用顺序存储构造某线性表采用顺序存储构造,每个元素占每个元素占4个存个存储单元储单元,首地址为首地址为200,

42、那么第那么第12个元素的存储地个元素的存储地址是址是_. A. 248 B. 247 C. 246 D. 2445. 以下对于线性链表的描画中正确的选项是以下对于线性链表的描画中正确的选项是_。(05.4月月 A存储空间不一定是延续，且各元素的存储存储空间不一定是延续，且各元素的存储顺序是恣意的顺序是恣意的B存储空间不一定是延续，且前件元素一定存储空间不一定是延续，且前件元素一定存储在后件元素的前面存储在后件元素的前面C存储空间必需延续，且前件元素一定存储存储空间必需延续，且前件元素一定存储在后件元素的前面在后件元素的前面D存储空间必需延续，且各元素的存储顺序存储空间必需延续，且各元素的存储顺

43、序是恣意的是恣意的6. 线性表是线性表是 A. 一个有限序列，可以为空一个有限序列，可以为空 B. 一个有限序列，不能为空一个有限序列，不能为空 C. 一个无限序列，可以为空一个无限序列，可以为空 D. 一个无限序列，不能为空一个无限序列，不能为空7在一个长度为在一个长度为n的线性表中，删除值为的线性表中，删除值为x的元素时需求比较元的元素时需求比较元 素和挪动元素的总次数为素和挪动元素的总次数为 A. n+1/2 B.n/2 C. n D.n+18. 一个长度为n的顺序存储的线性表中，向第i个元素(1in+1) 位置插入一个新元素时，需求从后面向前依次后移 个元 素。 A. n-i B. n

44、-i+1 C. n-i-1 D. i9.设单链表中指针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-next C. p-next=q-next D. q-next=null 11.在一个单链表中，假设要在p所指向

45、的结点之后插入一个新结 点，那么需求相继修正个指针域的值。 A. 1 B. 2 C. 3 D.412.不带头结点的单链表不带头结点的单链表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所指向的所指向的结

46、点之前插入一个新结点，那么需求相继修正个指针域结点之前插入一个新结点，那么需求相继修正个指针域的值。的值。A. 2 B. 3 C. 4 D.615.在一个带有头结点的双向循环链表中，假设要在在一个带有头结点的双向循环链表中，假设要在p所指向的所指向的结点之后插入一个结点之后插入一个q指针所指向的结点，那么需求对指针所指向的结点，那么需求对q-next赋值为赋值为A. p-prior B. p-next C. p-next-next D. p-prior -prior16.线性表采用链式存储时，其地址线性表采用链式存储时，其地址A. 必需是延续的必需是延续的B. 一定是不延续的一定是不延续的C.

47、 部分地址必需是延续的部分地址必需是延续的D. 延续与否均可以延续与否均可以2.在一个单链表中删除指针在一个单链表中删除指针p所指向结点时，应执行所指向结点时，应执行一下操作：一下操作： q=p-next; p-data= p-next-data; p-next=_； free(q);填空题填空题 1.数据构造分为逻辑构造和存储构造，循环队列属数据构造分为逻辑构造和存储构造，循环队列属 于于 构造。构造。05.9月月 pqABBC3. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把_ _的值赋给q-next，然后把_的值赋给p-next。4.假定指向单链表中第一个结点

48、的表头指针为head，那么向该单链 表的表头插入指针p所指向的新结点时，首先执行_赋值操 作，然后执行_赋值操作。 headp5. 在一个单链表中删除指针p所指向结点的后继结点时，需求把_的值赋给p-next指针域。6. 在_链表中，既可以经过设定一个头指针也可 以经过设定一个尾指针来确定它，即经过头指针或 尾指针可以访问到该链表中的每个结点。 7. 在一个带有头结点的双向循环链表中的p所指向的结 点之前插入一个指针s所指向结点时,可执行如下操作：(1) s -prior=_；(2) p-prior-next=s;(3) s-next=_;(4) p-prior=_;ps8. 线性表的长度是指_。 线性表中包含数据元素的个数线性表中包含数据元素的个数 9.根据线性表的链式存储构造中每个