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

《《计算机应用基础课件》1.2线性表.ppt》由会员分享，可在线阅读，更多相关《《计算机应用基础课件》1.2线性表.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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，ai+1，,.,an-1

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

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

4、性表的分类线性表的分类 (1)简单线性表：简单线性表：数据元素是简单项数据元素是简单项(数字、字母、季节名等数字、字母、季节名等)。如如:(12,34,4,67,8):(12,34,4,67,8)(2)复杂线性表：复杂线性表：数据元素由数据元素由若干个数据项若干个数据项组成，此时数据元素称为组成，此时数据元素称为记录记录或结点或结点,如学生成绩表如学生成绩表.L=(a0，a2，a3，ai-1，ai，ai+1，.,an-1)学生健康情况登记表如下：姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建

5、平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经衰弱神经衰弱.1.1.顺序表基本概念顺序表基本概念1.2.2 线性表的顺序存储结构1)顺序存储结构：顺序存储结构：用一用一组地址连续的存储空间组地址连续的存储空间依次存放线性表的各元素依次存放线性表的各元素 。顺序表：顺序表：采用顺序存储结构的线性表称为顺序表采用顺序存储结构的线性表称为顺序表(一维数组一维数组)表中的所有元素所占表中的所有元素所占存储空间连续存储空间连续表中各元素在存储空间中按表中各元素在存储空间中按逻辑顺序存放逻辑顺序存放 顺序存储结构特点顺序存储结构特点1.2 线性表1.1.顺序表基本概念

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

7、2)第第i个元素地址个元素地址1.2 线性表2.顺序表的基本运算顺序表的基本运算 存取存取:访问线性表的第访问线性表的第i个元素，使用或改变数据元素个元素，使用或改变数据元素的值。的值。查找查找:在线性表中查找满足某种条件的数据元素。在线性表中查找满足某种条件的数据元素。插入插入:在线性表的第在线性表的第i个元素之前，插入一个同类型的个元素之前，插入一个同类型的元素。元素。(*)删除删除:删除线性表中第删除线性表中第i个元素。个元素。(*)求表长求表长:求出线性表中元素的个数。求出线性表中元素的个数。置空表置空表:建立一个空表。建立一个空表。清除表清除表:将已有线性表变为空表，即删除表中所有元

8、素。将已有线性表变为空表，即删除表中所有元素。1.1.顺序表基本概念顺序表基本概念1.2.2 线性表的顺序存储结构1)顺序存储结构：顺序存储结构：2)第第i个元素地址个元素地址1.2 线性表2.顺序表的基本运算顺序表的基本运算 插入和删除插入和删除插入和删除插入和删除1)1)顺顺序序表表的的插插入入运运算算:在在线线性性表表的的第第i i个个元元素素之之前前插插入入一一个新的元素，先移动，后插入。个新的元素，先移动，后插入。ai-1.a1a0an-1ai+1ai x ai-1.a1 a0 ai an an-1 ai+1 ai ai x步骤：步骤：(1)将将ai an顺序向后移动顺序向后移动,为

9、新元素让出位置为新元素让出位置(2)将将x置入置入”空出空出”的第的第i个位置个位置举例：举例：(在第在第4个和第个和第5个元素之间插入元素个元素之间插入元素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

10、aN+1=12,34,45,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”,&i,&x);scanf(“%d,%d”,&i,&x);ai-1=x;ai-1=x;for(j=0;j=N;j+)for(j=0;j=N;j+)printf(“%d,”,aj);printf(“%d,”,aj);for(j=i-1;j=for(j=i-1;j=i-1;j-);j=i-1;j-)aj+1=aj;aj+1=aj;

11、在第在第i i个位置上作插入个位置上作插入x,x,则需将第则需将第i i个至第个至第n n个元素移动，即共个元素移动，即共需移动需移动(n-i+1)(n-i+1)个元素。个元素。插入运算时间性能分析：插入运算时间性能分析：插入运算，时间主要消耗在数据移动上。在长度为插入运算，时间主要消耗在数据移动上。在长度为n n的线性表的线性表中插入一个元素，则中插入一个元素，则平均移动元素次数平均移动元素次数(期望值期望值)：p pi i：在第：在第i i个位置上作插入的概率。个位置上作插入的概率。等差数列求和公式等差数列求和公式:(首项首项+末项末项)项数项数)/2(n-i+1)线性表线性表(a0,a1

12、,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)顺序存储结构：顺序存储结构：2)第第i个元素地址个元素地址1.2 线性表2.顺序表的基本运算顺序表的基本运算 插入和删除插入和删除插入和删除

13、插入和删除2)2)顺序表删除运算：顺序表删除运算：定义：定义：指将表中第指将表中第i个元素从线性表中去掉。个元素从线性表中去掉。原表长为原表长为n n：(a0，a1，ai-1，ai，ai+1，an-1)新表长为新表长为n-1n-1：(a0，a1，ai-1，ai+1，an-1)步骤：步骤：(1)将将ai+1 an-1，顺序向前移动顺序向前移动(2)表长表长减一减一举例：举例：(删除第五个元素删除第五个元素21)6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 8时间性能分析：时间性能分析：时间消耗与插入运算相同，时间消耗与插入运

14、算相同，平均移动元素次数：平均移动元素次数：q qi i:在第在第i i个位置上作插入的概率。设个位置上作插入的概率。设q qi i=1/n=1/n 共需移动共需移动(n-i)(n-i)个元素。个元素。67 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，求平局移动，求平局移动元素次数元素次数:作业作业：有一数组，存储十个数，：有一数组，存储十个

15、数，编程序删除其中任意一个数。编程序删除其中任意一个数。1.1.顺序表基本概念顺序表基本概念3.3.顺序表优点和缺点顺序表优点和缺点优点：优点：逻辑上相邻元素逻辑上相邻元素存储位置也相邻存储位置也相邻,无需增加额外存无需增加额外存储空间可方便储空间可方便随机存取随机存取表中任一元素。表中任一元素。缺点：缺点：插入和删除运算不方便插入和删除运算不方便,必须移动大量结点必须移动大量结点,效率效率较低不适合元素经常变动的大的线性表。较低不适合元素经常变动的大的线性表。1.2.2 线性表的顺序存储结构1.2 线性表2.顺序表的基本运算顺序表的基本运算1.1.链式存储结构特点链式存储结构特点:1.2.3

16、 线性表的链式存储结构存储空间可以存储空间可以不连续不连续。不要求逻辑上相邻的元素在物理位置上也相邻。不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由数据元素间逻辑关系由指针域指针域确定。确定。1.2 线性表即即 链表存储结构是一种链表存储结构是一种动态动态数据结构，其特点是它数据结构，其特点是它包含的据对象的个数及其相互关系可以包含的据对象的个数及其相互关系可以按需要改按需要改变变，存储空间是程序，存储空间是程序根据需要根据需要在程序运行过程中在程序运行过程中向系统申请向系统申请获得，链表也不要求逻辑上相邻的元获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储

17、结构所素在物理位置上也相邻，它没有顺序存储结构所具有的弱点。具有的弱点。zhang33531082548#namesumnext结构体结构体元素元素结构体元素结构体元素的地址的地址结构体元素的结构体元素的成员是地址型成员是地址型数据数据struct student char name10;int sum;struct student*next;pstruct student *p;strcpy(p-name,”zhang”)；p-sum=335;p-next=?zhang33531082548#bai32831483108#zhao35231883148#wu34703188#headp1p2

18、p3有四个结构体元素：有四个结构体元素：zhang33531082548#bai32831483108#zhao35231883148#wu34703188#head有四个结构体元素：有四个结构体元素：head（3）尾尾结结点点的的指指针针域域置置为为“NULL（空空）”，作作为链表结束的标志为链表结束的标志（1）头指针头指针变量变量head指向链表的首结点。指向链表的首结点。（2）每个）每个结点结点由由2个域组成：个域组成：1）数据域）数据域存储结点本身的信息。存储结点本身的信息。2）指针域）指针域指向后继结点的指针。指向后继结点的指针。zhang33531082548#bai3283148

19、3108#zhao35231883148#wu347NULL3188#struct student char name10;int sum;struct student*next;1.1.链式存储结构特点链式存储结构特点:2.2.线性链表线性链表:定义：定义：线性表的链式存储结构称为线性链表线性表的链式存储结构称为线性链表1.2.3 线性表的链式存储结构数据域数据域:一部分存放数据元素值一部分存放数据元素值 指针域指针域:存放指针存放指针,用于指向该结点的用于指向该结点的 前一个结点或后一个结点前一个结点或后一个结点 线性链表中线性链表中结点组成：结点组成：分类：分类：单链表、循环单链表、双向

20、链表单链表、循环单链表、双向链表 1.2 线性表其单链表示意图如下：其单链表示意图如下：有一线性表有一线性表:(bat (bat，catcat，eateat，fatfat，hathat，jatjat，latlat，mat)mat)hathat200200.catcat135135eateat170170.matmatNullNullbatbat130130fatfat110110jatjat205205latlat160160 110 130 135 160头指针头指针 head 165 170 200 205 165简化为简化为：链尾链尾略略bat cat eat mat 单链表是由表头唯一

21、确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。head用C语言描述的单链表如下：struct node char name20;struct node *next;struct node*head;typedef struct node char name20;struct node *next;LinkList;LinkList*head;新新的类型名代换的类型名代换旧旧的类的类型名，型名，也就是说：也就是说：LinkList等等价与价与struct node1.1.链式存储结构特点链式存储结构特点:2.2.线性链表线性链表:1.2.3 线性表

22、的链式存储结构1.2 线性表3.单链表单链表:定义：定义：由由n个结点链接，且每个结点中只个结点链接，且每个结点中只包含一个指针域包含一个指针域的的链表。链表。例：例：线性单链表线性单链表(A,B,C,D,E,F)(A,B,C,D,E,F)逻辑状态逻辑状态 ABCDEhead F其中其中:head称为单链表的头指针称为单链表的头指针,指向表中的第一个结点指向表中的第一个结点物理状态物理状态 E7FNULLB25A13C31D1头指针头指针 存储地址存储地址 数据域数据域 指针域指针域 19 1713192531单链表存取单链表存取:必须从头指必须从头指针开始进行，依次顺着针开始进行，依次顺着指

23、针向链尾方向扫描。指针向链尾方向扫描。找到各个元素找到各个元素,因此说线因此说线性表的链式存储结构是性表的链式存储结构是一种一种顺序存储顺序存储的存储结的存储结构构。ABCDEhead FABCDEhead FABCDEhead F带带头节点头节点的单链表的单链表编程：创建带头节点的单链表。编程：创建带头节点的单链表。程序算法：（1）定义三个结构体类型结构体类型的指针变量head,p,s（2）利用malloc函数开辟头结点头结点，由head,p共同来指向（3）再利用malloc函数开辟相应的内存空间，由s来指向（4）由键盘输入数据，赋给s所指向的内存空间（5）p-next=s;（6）p=s;（

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

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

26、回到第（3）步;spv对带头结点的复杂链表的基本操作对带头结点的复杂链表的基本操作创建创建AsheadpBABCDEhead FABCDEhead F带带头节点头节点的单链表的单链表 typedef struct nodechar data;struct node*next;Linklist;Linklist*head,*p,*s;char ch;head=(Linklist*)malloc(sizeof(Linklist);printf(input letters to create a list:n);while(ch=getchar()!=n)s=(Linklist*)malloc(si

27、zeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;编程：创建带头节点的单链表。编程：创建带头节点的单链表。带带头节点头节点的单链表的单链表 typedef struct nodechar data;struct node*next;Linklist;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*

28、)malloc(sizeof(Linklist);s-data=ch;p-next=s;p=s;p-next=NULL;2000Bdata next struct nodechar data;struct node*next;Linklist;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-d

29、ata=ch;p-next=s;p=s;p-next=NULL;Aheadp用户输入为：ABCsptypedef struct nodechar data;struct node*next;Linklist;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=

30、s;p-next=NULL;Ahead用户输入为：ABCspsBptypedef struct nodechar data;struct node*next;Linklist;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;Ah

31、ead用户输入为：ABCsBpsCpNULLtypedef1.1.链式存储结构特点链式存储结构特点:2.2.线性链表线性链表:1.2.3 线性表的链式存储结构1.2 线性表3.单链表单链表:(1)(1)单链表插入：单链表插入：增加新结点增加新结点,修改链接指针修改链接指针后插结点后插结点在指针在指针p p所指结点之后插入一个指针所指结点之后插入一个指针s s所指的结点所指的结点修改修改p p和和s s所指结点的指针域的指针即可所指结点的指针域的指针即可 插入步骤插入步骤修改修改s s指针域指针域,使其指向使其指向p p结点的后继结点结点的后继结点:s snext=pnext=pnextnext

32、p B C Xs A修改修改p指针域指针域,使其指向新结点使其指向新结点s:pnexts考虑上述两步骤若颠倒会怎样？考虑上述两步骤若颠倒会怎样？插入步骤插入步骤修改修改s s指针域指针域,使其指向使其指向p p结点的后继结点结点的后继结点:s snext=pnext=pnextnextp B C Xs A修改修改p指针域指针域,使其指向新结点使其指向新结点s:pnexts考虑上述两步骤若颠倒会怎样？考虑上述两步骤若颠倒会怎样？后面的结点都将从后面的结点都将从链表中脱离链表中脱离它们占用着内存空间，程它们占用着内存空间，程序却找不到它们了序却找不到它们了1.1.链式存储结构特点链式存储结构特点:

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

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

35、线性链表:1.2.3 线性表的链式存储结构1.2 线性表3.单链表单链表:4.4.循环链表循环链表5.5.双向链表双向链表定义：定义：在双向链表中，每个结点有在双向链表中，每个结点有两个指针域两个指针域，next 指向后继结点，指向后继结点，prior指向前趋结点。指向前趋结点。datapriornext结点构成：结点构成：作用：作用：可以方便地沿向前或向后两个方向查找。克服可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新前驱结点。若要找前驱结点，必须从头指针开始重

36、新查找的不足。查找的不足。head.ana2a1nextprior对指向双向链表任一结点的指针对指向双向链表任一结点的指针p，有下面的关系：，有下面的关系：p-next-priou=p-priou-next=ppnextpriouspriousnext1.1.链式存储结构特点链式存储结构特点:2.2.线性链表线性链表:1.2.3 线性表的链式存储结构1.2 线性表3.单链表单链表:4.4.循环链表循环链表5.5.双向链表双向链表(1)插入结点：插入结点：在在p指针所指的结点后插入一个结点指针所指的结点后插入一个结点q，只需，只需要修改要修改p,q结点的结点的prior和和next域即可。域即可

37、。p插入前插入前cbax待插入的结点待插入的结点:qcbaxqpp 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的前的前驱和后继驱和后继1.

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

39、r；free(p)；cba习题讲解习题讲解1.1.线性表的顺序存储结构和线性表的链式存储结构线性表的顺序存储结构和线性表的链式存储结构分别是分别是_。A.A.顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B.B.随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C.C.随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D.D.任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构2.2.在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是_。A.A.方便运算的实现方便运算的实现

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

41、储地址是是_.A.248 B.247 C.246 D.2445.下列对于线性链表的描述中正确的是下列对于线性链表的描述中正确的是_。(05.4月月）A）存储空间不一定是连续，且各元素的存储）存储空间不一定是连续，且各元素的存储顺序是任意的顺序是任意的B）存储空间不一定是连续，且前件元素一定）存储空间不一定是连续，且前件元素一定存储在后件元素的前面存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储）存储空间必须连续，且前件元素一定存储在后件元素的前面在后件元素的前面D）存储空间必须连续，且各元素的存储顺序）存储空间必须连续，且各元素的存储顺序是任意的是任意的6.线性表是（）线性表是（）

42、A.一个有限序列，可以为空一个有限序列，可以为空 B.一个有限序列，不能为空一个有限序列，不能为空 C.一个无限序列，可以为空一个无限序列，可以为空 D.一个无限序列，不能为空一个无限序列，不能为空7在一个长度为在一个长度为n的线性表中，删除值为的线性表中，删除值为x的元素时需要比较元的元素时需要比较元 素和移动元素的总次数为（）素和移动元素的总次数为（）A.（n+1）/2 B.n/2 C.n D.n+1详见计算机基础综合实训教程详见计算机基础综合实训教程详见计算机基础综合实训教程详见计算机基础综合实训教程P175P1758.一个长度为n的顺序存储的线性表中，向第i个元素(1in+1)位置插入

43、一个新元素时，需要从后面向前向前依次后移（）个元 素。A.n-i B.n-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

44、=null 11.在一个单链表中，若要在p所指向的结点之后插入一个新结 点，则需要相继修改（）个指针域的值。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所指向的结所指向的结点之前插入一

45、个新结点，则需要相继修改（）个指针域的值。点之前插入一个新结点，则需要相继修改（）个指针域的值。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.部分地址必须是连续的部

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

47、p-next。p-nextp-nextq q4.假定指向单链表中第一个结点的表头指针为head，则向该单链 表的表头插入指针p所指向的新结点时，首先执行_赋值操 作，然后执行_赋值操作。p-next=headp-next=headhead=phead=pheadp5.在一个单链表中删除指针p所指向结点的后继结点时，需要把_的值赋给p-next指针域。p-next-nextp-next-next6.在_链表中，既可以通过设定一个头指针也可 以通过设定一个尾指针来确定它，即通过头指针或 尾指针可以访问到该链表中的每个结点。循环循环循环循环7.在一个带有头结点的双向循环链表中的p所指向的结 点之前之

48、前插入一个指针s所指向结点时,可执行如下操作：(1)s-prior=_；(2)p-prior-next=s;(3)s-next=_;(4)p-prior=_;p-priorp-priorp ps sps8.线性表的长度是指_。线性表中包含数据元素的个数线性表中包含数据元素的个数 9.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_。单链表、双链表单链表、双链表 10.循环单链表与非循环单链表的主要不同是循环单链表的尾结 点指针_，而非循环单链表的尾结点指针_。指向链表头节点指向链表头节点 指向空指向空 11.访问单链表中的结点，必须沿着_依次进行。指针域指针域 12.在双向链

49、表中，每个结点有两个指针域，一个指向_，另一个指向_。前驱节点前驱节点 后续节点后续节点 13.在一个双向链表中删除指针p所指向的结点时，需要对 p-next-prior指针域赋值为_。p-prior 14.设head为单循环链表L的头结点，则L为空表的条件是_。head-next=head 15.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是 _。bceda 16.在一个长度为n的顺序表中的删除第i个元素（0in-1），需 要向前移动_个元素。n-i17.线性表L=(a1,a2,an)用数组表示，假定删除表中任一元

50、素的 概率相同，则删除一个元素平均需要移动元素的个数是 。(n-1)/218.一含N个元素的顺序表，若在第i个元素之前插入一个元素，需移动 个元素。n-i+119.从链表种删除q结点之后的p结点，语句为：q-next=。p-next 20.链表中每个结点包含两部分内容，一部分为数据域，另一部 分为 域。指针指针 21.在单链表中，要删除某一指定的结点，必须找到该结点的 _。前驱前驱 假假定定建建立立了了以以下下链链表表结结构构，指指针针p p、q q分分别别指指向向如如图图所所示示的的结结点点，则则以以下下可可以以将将q q所所指指结结点点从从链链表表中中删删除除并并释释放放该结点的语句组是该