第2章 线性表
本章主要内容：
1、 线性表的概念、特点、及其基本操作定义
2、线性表的顺序存储结构及其算法实现
3、线性表的链式存储结构及其算法实现
4、 循环链表及其线性表的应用
本章重点难点：
1、线性表的存储结构及算法实现。
2、链式存储结构及算法实现。
3、循环链表
2.1 线性表的定义和基本操作
2.1.1 线性表的定义及特点
1. 线性表的定义
线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。n表示线性表中数据元素的个数,称为线性表的长度(简称表长)。当n=0时， 线性表为空， 称为空线性表。
线性表的逻辑结构通常用数学中的向量形式表示：
L=( a1,a2,...,ai-1,ai,ai+1,...,an ) 或者
L=( a0,a1,...,ai-1,ai,ai+1,...,an-1 )
其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，元素的数据类型可以是可以表示出的任何类型。
例 1：分析下列线性表的数据类型：
La=（34，89，765，12，90，-34，22） ； Lb=(January, February，March，April，May，June，July，August，September，October，November，December，World, China,Welcome)；
Lc=（stu1,stu2,...,stu50) ；其中，数据元素stui的数据类型为：
struct student{
char Num; //学号
char *name; //姓名
};
2、线性表的特点。
除第一个元素外，每个元素有且仅有唯一一个直接前驱，第一个元素无直接前驱，除最后一个元素外，每个元素有且仅有唯一一个直接后继，最后一个元素无直接后继。1-1这种次序描述了元素之间的 1 对 1关系。此外，我们所研究的线性表的元素个数是有限的，各元素的数据类型是相同德，且数据元素可以是任意类型。
数据结构习题集答案(C语言版严蔚敏)
第2章 线性表
2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3 在什么情况下用顺序表比链表好？
解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。
2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。
解：
2.5 画出执行下列各行语句后各指针及链表的示意图。
L=(LinkList)malloc(sizeof(LNode)); P=L;
for(i=1;i<=4;i++){
P->next=(LinkList)malloc(sizeof(LNode));
P=P->next; P->data=i*2-1;
}
P->next=NULL;
for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);
for(i=1;i<=3;i++) Del_LinkList(L,i);
解：
2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
141
第7章 树与森林
习 题
1． 一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？
2． 对于图7-16所示的树，试给出：
（1）双亲数组表示法示意图。
（2）孩子链表表示法示意图。
（3）孩子兄弟链表表示法示意图。
3． 画出图7-17所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。
I D E F G C B A
N M K J H
D B C
I G
H A F
E J
图7-16 第2题图
图7-17 第3题图
4． 将如图7-18所示的二叉树转换成相应的森林。
H G D E F C B A
图7-18 第4题图
5． 在具有n（n>1）个结点的各棵树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？其中深度最大的那棵树的深度是多少？它共有多少叶子和非叶子结点？
6． 画出和下列已知序列对应的树T。
（1）树的先根次序访问序列为：GFKDAIEBCHJ。
（2）树的后根次序访问次序为：DIAEKFCJHBG。
7． 画出和下列已知序列对应的森林F。
（1）森林的前序次序访问序列为：ABCDEFGHIJKL。
（2）森林的中序次序访问次序为：CBEFDGAJIKLH。
8． 对以孩子兄弟链表表示的树编写计算树的深度的算法。 142
第7章 树与森林
9． 对以孩子链表表示的树编写计算树的深度的算法。
10．对以双亲链表表示的树编写计算树的深度的算法。
《数据结构练习题》线性表
线性表及其实现
1设一顺序表中元素值递增有序。写一算法，将元素x插到表中适当的位置，并保持顺序表的有序性，且分析算法的时间复杂度。
2设有两个按元素值递增有序的顺序表A和B，编一程序将A 表和B表归并成一个新的递增有序的顺序表C（值相同的元素均保留在C表中）。
3按下面两种情况分别编写算法删除顺序表中值相同的多余
元素：
（1）顺序表元素值递增有序；
（2）顺序表元素值无序。
4已知L是无表头结点的单链表，且P结点既不是首结点，也不是尾结点，试从下列提供的语句中选出合适的语句序列。
(1) 在P结点后插入S结点：__________
(2) 在P结点前插入S结点：__________
(3) 在表首插入S结点：__________
(4) 在表尾插入S结点：__________
① P->next = S;
② P->next = P->next->next;
③ P->next = S->next;
④ S->next = P->next;
⑤ S->next = L;
⑥ S->next = P;
⑦ S->next = NULL;
⑧ Q = P;
⑨ while (P->next != Q) P = P->next;
while (Q->next != NULL) Q = Q->next;
P = Q;
P = L; L = S;
L = P;
5已知P结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。
(1) 在P结点后插入S结点：______________
(2) 在P结点前插入S结点：______________
(3) 删除P结点的直接后继结点：______________
(4) 删除P结点的直接前驱结点：______________
(5) 删除P结点：______________
① P->next = P->next->next;
