第 1 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65

Presentation on theme: "第 1 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65"— Presentation transcript:

1 第 1 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65
第 1 章　 数据结构 65 10 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 865 A B C D E F G 姓名 学号 成绩 班级 李红 机97.6

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

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

4 1.2 线性表 L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 1. 线性表的定义
1) 定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。是最简单、最常用的数据结构。 2) 表示: L=( a1，a2，a3，…ai-1，ai ，ai+1，an ) 3) 线性结构特点: 4) 线性表的分类 (1)简单线性表： 数据元素是简单项(数字、字母、季节名等)。 如:(12,34,4,67,8) (2)复杂线性表： 数据元素由若干个数据项组成，此时数据元素称为记录或结点, 如学生成绩表. 简单线性表：一副扑克的点数 （2，3，4，…，J，Q，K，A）

5 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633
学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 21 张立立 790634 17 神经衰弱 …….. …….

6 1.2 线性表 顺序存储结构特点 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 1.顺序表基本概念 顺序表：
1.2.2 线性表的顺序存储结构 1.顺序表基本概念 1) 顺序存储结构： 用一组地址连续的存储空间依次存放线性表的各元素 。 顺序存储结构特点 表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放 顺序表： 采用顺序存储结构的线性表称为顺序表(一维数组)

7 4.2 线性表 1.顺序表基本概念 4.2.2 线性表的顺序存储结构 1) 顺序存储结构： 2) 第i个元素地址 其中:
m：每个元素占m个存储单元 Loc(a1)第一个元素地址(基址) 对数组而言

8 存储地址 存储状态 数据元素在线性表中的位序 b an－1 …….. ai a1 a0 1 2 从存取方式看,线性表的顺序存储结构是可以随机存储的存储结构. b+m b+i*m i b+n*m n 空闲

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

10 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 ….. … 先移动 后插入 ….. … … … 1.2.2 线性表的顺序存储结构
1) 顺序存储结构： 2.顺序表的基本运算 ——插入和删除 2) 第i个元素地址 1)顺序表的插入运算: 在线性表的第i个元素之前插入一个新的元素，先移动，后插入。 x ai-1 ….. a2 a1 an … ai+1 ai 先移动 后插入 ai-1 ….. a2 a1 ai … an x ai ai … ai+1 an …

11 (1)将ai ~ an顺序向后移动,为新元素让出位置 (2)将x置入”空出”的第i个位置
步骤： (1)将ai ~ an顺序向后移动,为新元素让出位置 (2)将x置入”空出”的第i个位置 举例：(在第4个和第5个元素之间插入元素91) 67 41 26 21 4 8 9 16 67 41 26 21 4 8 9 16 21 67 41 26 21 4 8 9 16 91

12 插入程序举例(在8个数中任意位置插入一个数)：
#define N 8 main() { int a[N+1]={12,34,45,6,78,9,10,91}, i,j,x; printf(“input the location to be inserted:”); scanf(“%d,%d”,&i,&x); a[i-1]=x; for(j=0;j<=N;j++) printf(“%d,”,a[j]); } for(j=i-1;j<=N-1;j++) a[j+1]=a[j]; for(j=N-1;j>=i-1;j--) a[j+1]=a[j];

13 插入运算时间性能分析： 插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数(期望值)：
<例>在一线性表(a1,a2,a3)中插入任意一数i，求平局移动元素次数: pi：在第i个位置上作插入的概率。 在第i个位置上作插入x,则需将第i个至第n个元素移动，即共需移动(n-i+1)个元素。 (n-i+1) i 移动次数(n-i+1) 1(插入到第1个数a1前) 2 (插入到第2个数a2前) 3 (插入到第3个数a3前) (插入到第3个数a3后) 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 等差数列求和公式: ((首项+末项)×项数)/2 线性表(a1,a2,a3)平局移动元素个数: (¼)*( )=1.5

14 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。
1.2.2 线性表的顺序存储结构 1.顺序表基本概念 1) 顺序存储结构： 2.顺序表的基本运算 ——插入和删除 2) 第i个元素地址 2)顺序表删除运算： 定义：指将表中第i个元素从线性表中去掉。 原表长为n：( a1，a2，…ai-1，ai ，ai+1， … an ) 新表长为n-1：( a1，a2，…ai-1，ai+1， …， an ) 步骤： (1)将ai+1 ~ an， 顺序向前移动 (2)表长减一

15 时间消耗与插入运算相同，平均移动元素次数：
举例：(删除第五个元素21) 67 41 26 21 4 8 9 16 67 41 26 4 8 9 16 67 时间性能分析： 时间消耗与插入运算相同，平均移动元素次数： qi:在第i个位置上作插入的概率。设qi=1/n 共需移动(n-i)个元素。

16 <例>在一线性表(a1,a2,a3)中删除任意一数i，求平局移动元素次数:
作业：有一数组，存储十个数， 编程序删除其中任意一个数。 <例>在一线性表(a1,a2,a3)中删除任意一数i，求平局移动元素次数: i 移动次数(n-i) 1(删除第1个数a1) 2 (删除第2个数a2) 3 (删除第3个数a3) 线性表(a1,a2,a3)平局移动元素个数: (1/3)*(2+1+0)=1

17 1.2 线性表 1.顺序表基本概念 2.顺序表的基本运算 3.顺序表优点和缺点 优点：
1.2.2 线性表的顺序存储结构 1.顺序表基本概念 2.顺序表的基本运算 3.顺序表优点和缺点 优点： 逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。 缺点： 插入和删除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。

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

19 结构体元素 结构体元素的地址 结构体元素的成员是地址型数据
zhang 335 3108＃ 2548# name p strcpy(p->name,”zhang”)； p->sum=335; p->next=? sum next 结构体元素的成员是地址型数据 struct student { char name[10]; int sum; struct student *next; }; struct student *p;

20 有四个结构体元素： p3 p1 p2 head zhang 335 3108＃ 2548# bai 328 3148＃ 3108# zhao
352 3188＃ 3148# wu 347 0＃ 3188# p3 p1 p2 head

21 有四个结构体元素： head zhang 335 3108＃ 2548# bai 328 3148＃ 3108# zhao 352
3188＃ 3148# wu 347 0＃ 3188# head

22 （1）头指针变量head──指向链表的首结点。
zhang 335 3108＃ 2548# bai 328 3148＃ 3108# zhao 352 3188＃ 3148# wu 347 NULL 3188# （1）头指针变量head──指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域──存储结点本身的信息。 2）指针域──指向后继结点的指针。 （3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志 struct student { char name[10]; int sum; struct student *next; };

23 1.2 线性表 定义：线性表的链式存储结构称为线性链表 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 定义：线性表的链式存储结构称为线性链表 线性链表中 结点组成： 数据域: 一部分存放数据元素值 指针域: 存放指针,用于指向该结点的 前一个结点或后一个结点 分类：单链表、循环单链表、双向链表

24 (bat，cat，eat，fat，hat，jat，lat，mat)
<例>有一线性表: (bat，cat，eat，fat，hat，jat，lat，mat) 其单链表示意图如下： ……… …… hat 200 ……. cat 135 eat 170 …. mat Null bat 130 fat 110 jat 205 lat 160 …… 110 130 135 160 头指针 head 170 200 205 链尾 简化为： 略 165

25 也就是说：LinkList等价与struct node
head bat cat eat mat ^ … 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 新的类型名代换旧的类型名， 也就是说：LinkList等价与struct node 例如：若头指针名是head，则把链表称为表head。 用C语言描述的单链表如下： struct node { char name[20]; struct node *next; }; struct node *head; typedef struct node { char name[20]; struct node *next; }LinkList; LinkList *head;

26 1.2 线性表 3 .单链表: 例：线性单链表( A, B, C, D, E, F ) 1.2.3 线性表的链式存储结构 链式存储结构特点:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 定义：由n个结点链接，且每个结点中只包含一个指针域的链表。 例：线性单链表( A, B, C, D, E, F ) 逻辑状态 A B C D E head F 其中: head称为单链表的头指针,指向表中的第一个结点

27 物理状态 A B C D E F 头指针 存储地址 数据域 指针域 19 E 7 F NULL B 25 A 13 C 31 D 1
head A B C D E F 物理状态 头指针 存储地址 数据域 指针域 19 1 7 13 19 25 31 E 7 F NULL B 25 A 13 C 31 D 1 单链表存取:必须从头指针开始进行，依次顺着指针向链尾方向扫描。找到各个元素,因此说线性表的链式存储结构是一种顺序存储的存储结构。

28 （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向
B C D E F head A B C D E F 带头节点的单链表 编程：创建带头节点的单链表。 程序算法： （1）定义三个结构体类型的指针变量head, p, s （2）利用malloc函数开辟头结点，由head, p共同来指向 （3）再利用malloc函数开辟相应的内存空间，由s来指向 （4）由键盘输入数据，赋给s所指向的内存空间 （5）p->next=s; （6）p=s; （7）回到第（3）步; 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

29 head=p=(strutc node*) malloc(sizeof(struct node));
对带头结点的复杂链表的基本操作——创建 head p 程序算法： （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));

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

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

32 A B C D E F A B C D E F 带头节点的单链表 head head 编程：创建带头节点的单链表。
typedef struct node {char 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(sizeof(Linklist)); s->data=ch; p->next=s; p=s; } p->next=NULL; 带头节点的单链表 编程：创建带头节点的单链表。 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

33 Linklist *head,*p,*s; char ch;
带头节点的单链表 typedef struct node {char 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; ··············· data next B 2000 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

34 Linklist *head,*p,*s; char ch;
typedef s struct node {char 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; ··············· A 用户输入为：ABC<回车> 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

35 Linklist *head,*p,*s; char ch;
typedef s s struct node {char 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; ··············· A B 用户输入为：ABC<回车> 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

36 Linklist *head,*p,*s; char ch;
typedef s s struct node {char 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; ··············· A B C NULL 用户输入为：ABC<回车> 题采取带头结点的单链表形式，此种存储形式的优点是简化了做插入、删除操作的边界情况的处理，如插入元素为表中第一个元素，删除元素为表中第一个元素的情况等。

37 1.2 线性表 3 .单链表: 在指针p所指结点之后插入一个指针s所指的结点 修改p和s所指结点的指针域的指针即可
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: (1)单链表插入：增加新结点,修改链接指针 后插结点 在指针p所指结点之后插入一个指针s所指的结点 修改p和s所指结点的指针域的指针即可

38 插入步骤 修改s指针域,使其指向p结点的后继结点:snext=pnext 修改p指针域, 使其指向新结点s: pnext＝s p A
B C X s 考虑上述两步骤若颠倒会怎样？

39 插入步骤 修改s指针域,使其指向p结点的后继结点:snext=pnext 修改p指针域, 使其指向新结点s: pnext＝s p A
B C X s 它们占用着内存空间，程序却找不到它们了 考虑上述两步骤若颠倒会怎样？ 后面的结点都将从链表中脱离

40 1.2 线性表 3 .单链表: 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: (2)单链表删除：不需要移动元素,仅修改指针链接 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可

41 C B A C B A 删除步骤 qnext＝qnextnext 修改q结点指针域 qnext＝pnext p free(p);
先找到p的前驱结点q 修改q结点指针域 qnext＝pnext C p B A 删除前 free(p); q p C B A 删除后

42 1.2 线性表 3 .单链表: 4.循环链表 特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。 带头节点的循环链表

43 优点：从表中任一结点出发均可找到表中其它结点。
对带头结点的单循环链表head为空的判定条件是 head->next=head 带头结点的空循环链表

44 1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 5.双向链表 定义：在双向链表中，每个结点有两个指针域，next 指向后继结点，prior指向前趋结点。 data prior next 结点构成：

45 对指向双向链表任一结点的指针p，有下面的关系： p->next->priou=p->priou->next=p
作用：可以方便地沿向前或向后两个方向查找。克服单链表中每个结点只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找的不足。 next p head ... an a2 a1 next next prious prious prior 对指向双向链表任一结点的指针p，有下面的关系： p->next->priou=p->priou->next=p

46 1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 5.双向链表 (1)插入结点：在p指针所指的结点后插入一个结点q，只需要修改p,q结点的prior和next域即可。 p 插入前 c b a x 待插入的结点:q

47 ①p结点作为q结点的前驱:q->prior=p；
a b c ④ ① ② ③ x q 确定新结点q的前驱和后继 ①p结点作为q结点的前驱:q->prior=p； ②p结点的后继作为q结点的后继:q ->next=p->next； ③q结点作为p 结点的后继结点的前驱结点:p->next->prior=q ④q结点作为p结点的后继:p->next=q； (p的后继指向新结点q)

48 1.2 线性表 3 .单链表: 4.循环链表 5.双向链表 1.2.3 线性表的链式存储结构 链式存储结构特点: 2.线性链表:
线性表的链式存储结构 链式存储结构特点: 2.线性链表: 3 .单链表: 4.循环链表 5.双向链表 (2)删除结点：删除P指针所指结点，只需修改P指针的前驱和后继结点的next，prior域即可。 p 删除前 c b a

49 ① p a b c ② ① p的后继结点作为p结点前驱结点的后继 (a c) p->prior->next = p->next； ② p的前驱结点作为p结点后继结点的前驱 ( a c) p->next->prior= p->prior； free(p)；

50 1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。
习题讲解 1. 线性表的顺序存储结构和线性表的链式存储结构分别是______。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 2. 在单链表中，增加头结点的目的是______。 A. 方便运算的实现 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现 BA

51 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取
3 用链表表示线性表的优点是______。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取 4.某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为200,则第12个元素的存储地址是_______. A B C D. 244 AD

52 5. 下列对于线性链表的描述中正确的是______。(05.4月 ） A）存储空间不一定是连续，且各元素的存储顺序是任意的
B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 A

53 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空
6. 线性表是（） A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 7．在一个长度为n的线性表中，删除值为x的元素时需要比较元 素和移动元素的总次数为（） A. （n+1）/2 B.n/2 C. n D.n+1 8. 一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1) 位置插入一个新元素时，需要从后面向前依次后移（ ）个元 素。 A. n-i B. n-i C. n-i D. i ACC ——详见《计算机基础综合实训教程》P175

54 9.设单链表中指针p指向结点ai,若要删除ai之后的结点（若存 在），则需修改指针的操作为（）。
A. p->next= p->next->next B. p=p->next C. p=p->next->next D. next=p 10.设单链表中指针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所指向的结点之后插入一个新结 点，则需要相继修改（）个指针域的值。 A B C D.4 AAB

55 12.不带头结点的单链表L为空的判定条件是（）。 A. L= = NULL B. L->next = = NULL
C. L->next = = L D. L! = NULL 13．带头结点的单链表L为空的判定条件是（）。 A. L= = NULL B. L->next = = NULL C. L->next = = L D. L! = NULL 14.在一个带有头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A B C D.6 15.在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（） A. p->prior B. p->next C. p->next->next D. p->prior ->prior 16.线性表采用链式存储时，其地址（） A. 必须是连续的 B. 一定是不连续的 C. 部分地址必须是连续的 D. 连续与否均可以 ABCBD

56 1.数据结构分为逻辑结构和存储结构，循环队列属 于 ———— 结构。（05.9月）
填空题 1.数据结构分为逻辑结构和存储结构，循环队列属 于 ———— 结构。（05.9月） 存储结构 2.在一个单链表中删除指针p所指向结点时，应执行一下操作： q=p->next; p->data= p->next->data; p->next=_____； free(q); p->next->next p q A B B C

57 4.假定指向单链表中第一个结点的表头指针为head，则向该单链 表的表头插入指针p所指向的新结点时，首先执行_____赋值操
3. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把___ __的值赋给q->next，然后把_____的值赋给p->next。 p->next q 4.假定指向单链表中第一个结点的表头指针为head，则向该单链 表的表头插入指针p所指向的新结点时，首先执行_____赋值操 作，然后执行_____赋值操作。 p->next=head head=p head p

58 5. 在一个单链表中删除指针p所指向结点的后继结点时，需要把_____的值赋给p->next指针域。
p->next->next 循环 6. 在_____链表中，既可以通过设定一个头指针也可 以通过设定一个尾指针来确定它，即通过头指针或 尾指针可以访问到该链表中的每个结点。 7. 在一个带有头结点的双向循环链表中的p所指向的结 点之前插入一个指针s所指向结点时,可执行如下操作： (1) s ->prior=_____； (2) p->prior->next=s; (3) s->next=_____; (4) p->prior=_____; p->prior p s p s

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

60 14.设head为单循环链表L的头结点，则L为空表的条件是______。
head->next=head 15.假设以S和X分别表示进栈和退栈操作，则对输入序列a, b, c ,d, e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是 ______。 bceda 16. 在一个长度为n的顺序表中的删除第i个元素（0≤i≤n-1），需 要向前移动______个元素。 n-i 17. 线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的 概率相同，则删除一个元素平均需要移动元素的个数是 。 (n-1)/2 18.一含N个元素的顺序表，若在第i个元素之前插入一个元素，需移动 个元素。 n-i+1

61 19.从链表种删除q结点之后的p结点，语句为：q->next= 。
p->next 20.链表中每个结点包含两部分内容，一部分为数据域，另一部 分为 域。 指针 21. 在单链表中，要删除某一指定的结点，必须找到该结点的 _______。 前驱

62 B) (*p).next=(*q).next; free(q); C) q=(*q).next; (*p).next=q; free(q);
练1 假定建立了以下链表结构，指针p、q分别指向如图所示的结点，则以下可以将q所指结点从链表中删除并释放该结点的语句组是 A) free(q); p->next=q->next; B) (*p).next=(*q).next; free(q); C) q=(*q).next; (*p).next=q; free(q); D) q=q->next;p->next=q;p=p->next; free(p); head 8 4 3 p q date next

63 练2 若已建立如下图所示的单向链表结构,在该链表结构中，指针p、s分别指向图中所示结点，则不能将s所指的结点插入到链表末尾仍构成单向链表的语句组是 A) p =p->next; s->next=p; p->next=s; B) p =p->next; s->next=p->next; p->next=s; C) s->next=NULL; p=p->next; p->next=s; D) p=(*p).next; (*s).next=(*p).next; (*p).next=s; head E F \0 p date next G s