严蔚敏数据结构讲义(第02章 线性表)
第02章线性表
本章知识结构：
线性表的特点：
1.有唯一的头；
2.唯一的尾；
3.除头外都有一个直接前驱；
4.除尾外都有一个直接后继。
2.1线性表的类型定义
一、线性表是n（n>=0）个数据元素的有限序列——有限个元素；元素之间有次序。
长度：表中元素的个数。
存储容量：整个线性表所占的空间。
位序：元素所在位置的序号，即第几个。
线性表的基本操作：1.访问（元素查询，定位）；2.插入元素；3.删除元素。
线性表的抽象数据类型定义（三元法定义）ADT List{数据对象；数据关系；基本操作}
2.2顺序表(sequence)——线性表的顺序表示与实现
一、特点：
1.逻辑地址相邻，物理地址也相邻；
2.优点：可随机访问；
缺点：插入、删除不方便。
二、实现：一维数组
三、C语言知识复习
（一）typedef int DataType；给整型int定义一个别名DataType，之后就可以使用DataType定义整型变量了，例如： DataType x，y=8；
（二）结构体类型的定义
struct card{int num； char name[20]；……}——定义了一个结构体card
（三）结构体变量的定义
struct card stu1，stu2；——其中struct card是一个整体，表示结构体类型名
（四）给结构体类型名定义别名
typedef struct card DataType；给结构体struct card定义一个别名DataType
（五）给匿名结构体定义别名
typedef struct
{int month;
int day;
int year;} Date； //该结构体为匿名结构体，相当于类的匿名对象。即该结构体无名称，只有别名
class PC； new PC().action()； //匿名对象的使用
（六）sizeof函数：
返回一个对象或者类型所占的内存字节数。如：sizeof(int)——2
（七）用typedef定义指针型别名
typedef char *String； //声明String为字符指针类型
typedef struct node{……} *LinkList； //声明LinkList为struct node类型的指针
（八）malloc函数和free函数—— memory allocation内存分配
1. 函数原型及说明：
void *malloc(long NumBytes)：该函数分配了NumBytes个字节，并返回了指向这块内存的指针。如
果分配失败，则返回一个空指针（NULL）。关于分配失败的原因，应
该有多种，比如说空间不足就是一种。
void free(void *FirstByte)：该函数是将之前用malloc分配的空间还给程序或者是操作系统，也
就是释放了这块内存，让它重新得到自由。
2. 函数的使用：
char *Ptr = NULL;
Ptr = (char *)malloc(100 * sizeof(char));
//malloc()函数的类型是(void *),任何类型的指针都可以转换成
(void *),但是最好还是在前面进行强制类型转换
（九）calloc函数
功能: 在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；
如果分配不成功，返回NULL。
跟malloc的区别：
calloc在动态分配完内存后，自动初始化该内存空间为零，而malloc不初始化，里边数据是随机的垃圾数据。
（十）realloc函数
原型：extern void *realloc(void *mem_address, unsigned int newsize);
语法：指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。
头文件：#include
返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。
注意：这里原始内存中的数据还是保持不变的。当内存不再使用时，应使用free()函数将内存块释放。四、线性表的结构定义——存储结构
typedef struct{
ElemTpye *elem； //存储空间首地址
int length； //存储长度
int ListSize； //存储容量
}
五、线性表的插入
1.检查i值是否超出所允许的范围（1≤i≤n+1），若超出，则进行“超出范围”错误处理；
2.检查容量是否已满，若已满则需扩充存储容量；
3.将线性表的第i个元素和它后面的所有元素均向后移动一个位置；
4.将新元素写入到空出的第i个位置上；
5.使线性表的长度增1。
六、顺序表的删除
七、顺序表的查找
八、线性表合并
九、顺序存储优缺点
2.3链表——线性表的链式表示与实现
一、线性链表/单链表
（一）结点结构定义
（二）基本运算
1.建单链表
（1）头插法建单链表
ListLink HeadInsertCreateList() //头插法创建单链表
{
ListLink head,s;
char ch;
head=NULL;
printf("Please input character(#->stop).\n");
ch=getchar();
while(ch!='#')
{
s =(ListLink)malloc(sizeof(ListNode)); //申请空间
s->data = ch; //结点数据域赋值
s->next = head; //将新节点的指针域指向头指针(即指向第一个数据元素地址)
head = s; //将头指针指向新结点
ch = getchar(); //继续接收键盘字符,循环创建数据元素
}
return head;
}
（2）尾插法建单链表
ListLink TailInsertCreateList() //尾插法创建单链表
{
ListLink head,tail,s; //head头指针；tail尾指针；s临时指针
char ch;
head = NULL;
tail = head; //起始时,单链表无数据元素，头指针和尾指针都为空
printf("Please input character(#->stop).\n");
ch=getchar();
while(ch!='#')
{
s =(ListLink)malloc(sizeof(ListNode)); //申请空间
s->data = ch; //结点数据域赋值
s->next = NULL; //新结点作为最后一个结点出现，所以将新结点的指针域置空if(tail==NULL) //尾结点为空，此时插入第一个元素，应将头指针指向之，之后头指针保持不变 {
head = s;
tail = s; //第一个元素进入，尾指针也要指向第一个元素
}
else
tail->next = s; //第个及以后的元素插入都是直接将元素链入尾部
tail = s; //将尾指针指向新结点
ch = getchar(); //继续接收键盘字符,循环创建数据元素
}
return head;
}
2.查找
（1）按值查找
linklist *LOCATE(linklist *head,datatype key)
{ linklist *p;
p＝head->next; //头结点不属于表
while(p!=NULL)
if (p->data!=key)
p＝p->next;
else break;
return p;
}
（2）按位置(序号)查找——可拓展到遍历
linklist *GET(linklist *head,int i)
{ int j;
linklist *p;
p ＝head;j ＝0;
while((p->next!=NULL)&&(j
if (i==j) return p; else return NULL; }
3.插入元素
（1）单个结点后插操作
//后插元素，L 为单链表头指针，在q 所指向的元素后面插入一个元素，值为e ListLink ListInsertAfter(ListLink L, ListLink p, DataType e) {
ListLink q = (ListLink)malloc(sizeof (ListNode)); if (q==NULL) {
printf("Memory allocation Error.\n"); exit(0); }
q->data = e;
q->next = p->next; p->next = q; return L; }
（2）单个结点前插操作
InsertBefore(linklist *head,linklist *p,datatype x) { linklist *s,*q;
s ＝malloc(sizeof(linklist)); s->data ＝x; q ＝head;
while(q->next!=p) q ＝q->next; s->next ＝p;q->next ＝s; }
4.删除元素
（1）删除后继结点
二、
按位置查找(即访问第i 个元素)的时间复杂度是)1(O ；——Add i =Add 0+(i-1)*d 按值查找（即查找值为x 的元素），需要比较(n+1)/2次，时间复杂度为)(n O ； 插入元素需要平均移动节点n/2个；
——设线性表有n 个元素，如果要在第1个元素位置插入元素，则需要移动n 个元素；如果要在第2个元素位置插入，则需要移动n-1个元素…，如果要在第n 个元素位置插入需要移动1个；如果要在最末尾插入元素，则不需要移动元素，即移动0个元素，列出所有要移动元素的和，n + (n-1) + (n-2) + … + 1 + 0，最终的n(n+1)/2。插入总次数为n+1，所以移动平均数为[n(n+1)/2]÷(n+1) = n/2。
删除元素的平均时间复杂度为(n-1)/2。 链式存储：
查找(访问)第i 个元素的时间复杂度是)(n O ；——从第1个找第2个，再通过第2个找第3个，… 插入元素的平均时间复杂度为)1(O ； 删除元素的平均时间复杂度为)1(O 。
二、 静态链表与动态链表
静态链表：
所有结点都是在程序中定义，不是临时开辟的，也不能用完后释放。静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。静态链表使用结构体数组来实现线性链表的功能。因为其用游标cur 来指示下一个数据元素的存储位置，因此存取数据时静态链表与线性链表（单链表）是相似的。线性链表在存取第i 个元素时，是先找到第一个元素，然后根据链接依次找到第2个、第3个…，直到找到第i 个，所以静态链表在存取表中第i 个元素的时间同i 有关。 动态链表：
在需要时才开辟一个结点的存储单元。
无论是静态链表还是动态链表，都是链式存储，所以静态链表和动态链表在元素的插入、删除操作上类似，不需要做元素的移动。 三、 线性表查找元素的方法通常有顺序查找和折半查找两种。顺序查找适合于顺序存储和链式存储；折半查找
只适合于顺序存储。 四、 线性表的头指针、头结点、表头结点
表头结点表示线性表中第一个存储数据的结点，即第一个数据元素的结点。
线性表有的有头结点，有的没有头结点，头结点是在线性表第一个数据元素结点的前面再加一个结点，该结点同数据结点结构相同，但是不存储数据，只是用来标识线性表的起始位置。
如果线性表有头结点，则指向头结点的指针叫头指针；如果线性表没有头结点，则指向表头结点的指针叫头指针。
第一章 栈、队列和数组
一、用单链表表示栈，总是链表头对应栈的栈顶，链表尾对应栈的栈尾；
用单链表表示队列时，用链表头对应队列的队头，链表尾对应队列的队尾。 二、 对称矩阵a ij 进行压缩存储，如果按行存储下三角阵，则LOC(i,j)的存放位置：
LOC(i,j) =
j i i ++2)
1( (i ≥j ，即元素位于下三角时) LOC(i,j) =
i j j ++2
)
1( (i ＜j ，即元素位于上三角时) 三、 使用循环队列来判断一个队列是空是满（队头front ，队尾rear ，队列最大容量为max ）：
判断栈满：front == (rear + 1)%max
判断栈空：front == rear ——>栈空
计算队列中元素的个数：(rear – front + max) % max
四、 后缀表达式
前序遍历是前缀式==波兰式 中序遍历是中缀式
后续遍历是后缀式==逆波兰式
第二章 树和二叉树
一、 树的基本概念
1． 结点的度：结点的分支数，即结点分叉的总数（不含父叉）。 2． 结点的层次（高度）：结点处在树的第几层，根结点的层次是1。
3． 树的度：树中所有结点度的最大值——即最茂密的那个结点的分叉数。 4． 树的深度（高度）：树中所有结点层次的最大值——树枝的最大深度。 二、 二叉树 （一）属性
1． 二叉树第i 层上至多有2i-1个结点。
2． 深度为k 的二叉树至多有2k -1个结点，最少有k 个结点。
3． 二叉树叶子结点数总比度为2的结点个数多1。—— 110+=n n
4． 二叉树的度最多为2，但不一定为2，有可能为0（只含一个根结点的树），也有可能为1（一个根结点
只含左子树，无右子树）。
（二）存储结构
1．顺序存储：
将二叉树补成完全二叉树（无结点的地方补0），然后按层次存储。
2．链式存储
（1）二叉链表：数据域；左指针指向左子树；右指针指向右子树。方便找子树，不方便找双亲。
（2）三叉链表：数据域；左指针指向左子树；右指针指向右子树；双亲指针指向双亲。
（三）二叉树的遍历——先序、中序和后序，都是以根结点出现的次序而言的。
先序：先根，再左，再右。——前缀（波兰式）
中序：先左，再根，再右。——中缀
后序：先左，再右，再根。——后缀（逆波兰式）
1．一个前序遍历+一个后序遍历不能唯一确定一个二叉树。
2．一个中序遍历+一个前序遍历能唯一确定一棵二叉树；一个中序遍历+一个后序遍历也能唯一确定一棵二叉树。（即只要是含有中序遍历，即可确定一棵二叉树）。
3．无论先序、中序还是后序遍历，二叉树叶子结点的相对排列顺序不变，因为都是先左后右。
（四）线索二叉树
Tag
三、特殊二叉树（满二叉树和完全二叉树）
（一）满二叉树
深度为k的满二叉树，第k层的结点数为2k-1，总结点数为2k-1。
（二）完全二叉树
定义：(1)叶子结点只能出现在树的最高两层 (2)树的层次排列无间断编号。
1．深度为k的完全二叉树最多结点数为2k-1（满二叉树），最少为2k-1（深度为k-1的满二叉树+1）。
2．满二叉树为完全二叉树。
log + 1。
3．具有n个结点的完全二叉树的深度为??n2
4．完全二叉树的n0 = n2 + 1。
5．完全二叉树的n1 = 0 或 n1 = 1。
6．完全二叉树的总结点数 n = n0 + n1 + n2 = 2n0 - 1 + n1 =2n1+1+n1（=2n0 或2n0-1；=2n1+1或2n1+2）四、树和森林
（一）树的存储结构
1．双亲表示法：顺序存储，便于查找双亲。
2．孩子表示法：顺序 + 链式
3．孩子兄弟表示法：二叉链表，左指第一个孩子，右指第一个兄弟。
（二）森林和二叉树的相互转换
1．一般树转化为二叉树：
将树按孩子兄弟法表示，左子树只保留父亲和长子关系，右子树是年龄最近的两个兄弟的连线。
一般树转化为二叉树之后，根结点没有右子树。
2．森林转换为二叉树
先将森林中的各树转化为二叉树，然后把第1棵树的根结点作为总二叉树的根结点，把第2棵树的根结点作为第1棵树根结点的右子树，把第3棵树的根结点作为第2棵树的右子树……
（1）森林转换为二叉树，则森林中第1棵树即变成二叉树根结点的左子树；其余树合起来变成二树根结点的右子树；可如此推演，第2棵树是整个二叉树根结点的右子树中的左子树……
3．二叉树转化为森林
将二叉树根结点的右子树的每个分叉的根结点之间的连线都断开，即成森林。
（三）树和森林的遍历
1．树的遍历
（1）先根遍历：先访问树的根结点，再依次先根访问树的各子树。
树的先根遍历得到的序列与对应的二叉树的先根遍历序列相等。
（2）后根遍历：依次后根遍历各子树，最后访问根结点。
树的后根遍历得到的序列与相应的二叉树的中序序列相等。
2． 森林的遍历
（1） 先序遍历：依次从左至右对森林中的每一棵树进行先根遍历。 （2） 中序遍历：依次从左至右对森林中的每一棵树进行后根遍历。 五、 树的应用
（一）二叉排序树：
左小右大根中间，二叉排序树的中序遍历序列即是元素的有序序列（自小到大或自大到小）
平均查找长度：ASL=
结点总数
1
∑该层结点数量 结点层数
比如，一个有12个元素的序列，生成二叉树之后，根结点有20=1个元素；第2层，有22-1=2个元素；第3层有23-1=4个元素；在第4层有12-（1+2+4）=5个元素，则其ASL=(1*1+2*2+3*4+4*5)/12=37/12 （二）平衡二叉树——排序树，是二叉查找树的另一种形式
平衡二叉树又被称为AVL 树（区别于AVL 算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
（三）哈夫曼树和哈弗曼编码
1．结点之间的路径长度：树上结点之间的分支数目（即从A 点到B 点，需要走几个树枝）。 2．树的路径长度：从树的根结点到每一个终端结点的路径长度之和。
3．结点的带权路径长度：从树的根到该终端结点的路径长度与结点上权值的乘积。 4．树的带权路径长度：树中所有终端结点的带权路径长度之和。
5．哈夫曼树：带权路径长度最小的二叉树称为最优二叉树，即哈夫曼树。 6．构造哈夫曼树的步骤：——哈夫曼树没有度为1的结点，所以n=2n 0-1。
7．哈夫曼编码：哈夫曼树上左0右1，从根到结点的树枝对应的0、1所形成的编码。
第三章 图
一、 图的基本概念 （一） 图的定义及术语
1． 图的定义
（1） 图：图是若干顶点和若干边的集合。若只有顶点而无边，则称顶点离散；有边则称顶点关联。 （2） 顶点：图中的数据元素。
（3） 边：若顶点u 和顶点v 之间有关联(即有连线)，且连线无方向性，则称(u ，v)为边。
（4） 弧：若顶点u 和顶点v 之间有关联(即有连线)，且连线有方向性，则称或
（7） 无向图：图中顶点之间的关联无方向性（即顶点之间由边相连）的图。 （8） 有向图：图中顶点之间的关联有方向性（即顶点之间由弧相连）的图。
（9） 完全图：任意两个顶点之间都有边的无向图（2
)
1(-=
n n e ）。 （10） 有向完全图：任意两个顶点之间都有两条弧相连的有向图（)1(-=n n e ）。 2． 图中边(弧)与图的顶点的关系
（1） 无向图中边e 和顶点n 之间的关系：2
)
1(0-≤
≤n n e （2） 有向图中边e 和顶点n 之间的关系：)1(0-≤≤n n e
（3） 稀疏图、稠密图：有很少边或者弧的图(n n e log <)叫稀疏图；反之称为稠密图。
3． 权：边或者弧上的数称为权，表示从一个顶点到另一个顶点的距离或花费。
4． 子图：从一个图中选其部分顶点及这些顶点之间的关联(边或弧)组成的新图称为原图的子图。 5． 度：和顶点v 相关联的边或弧的条数，称为顶点v 的度，记作：TD(v)。 6． 有向图中顶点v 的度：
和顶点v 有关联的弧的数量。这些弧包括v 指向其他顶点的弧，也包括其他顶点指向v 的弧。 7． 出度OD(v)：由顶点v 射向其他顶点的弧的总条数。 8． 入度ID(v)：射向v 的弧的总条数。
9． 图中所有顶点度的和与顶点、边、弧的关系：
（1） 无向图中所有顶点度的和，是图中所有边的总数的2倍。（因为一个边对应两个度） （2） 有向图中所有顶点度的和，是图中所有弧的总数的2倍。（因为一个弧也对应两个度，一个出度，
一个入度，所以对有向图有：
所有顶点出度数总和=所有顶点入度数总和=图中弧的总数=
2
图中所有结点度的总和
（二） 图的连通性
1． 路径和回路
（1） 路径：顶点V i 走到V j 所经历的顶点序列（包括V i 和V j ）。
（2） 有向路径：在有向图中顶点V i 走到V j 所经历的顶点序列（包括V i 和V j ）。 （3） 简单路径：路径上没有重复顶点的路径。
（4） 路径长度：路径中边或者弧的数量即为路径长度。
（5） 回路/环路：路径的起始顶点=路径的重点顶点，则称该路径为回路或环路。
（6） 简单回路/简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 （7） 非简单回路：除第一个顶点和最后一个顶点之外，其余顶点有重复出现的回路。 2． 图的连通性
（1） 顶点之间连通：若顶点v 和u 之间有路径（即由v 到u 可达），则称v 和u 是连通的。 （2） 连通图：图中任何两个顶点之间都连通。
n 个顶点的无向图，要想达到连通，最少需要n-1条边，此时图为树状结构； n 个顶点的有向图，要想达到连通，最少需要 n 条边，此时图为环状结构。
（3） 强连通图：有向图的任何两个顶点正向连通，逆向也连通，则称该有向图为强连通图。 （4） 连通分量和极大连通子图
连通分量：无向图的最大连通子图，可能含有回路——“最大”指的是依附于连通分量中顶点的所有
边都加上。
强连通分量：有向图的极大强连通子图称为其强连通分量。 极大连通子图： 3． 连通图的生成树问题
连通图的生成树就是一棵树，是一没有环路的连通图。生成树若有n 个顶点，则其边定为n-1个。
二、 图的存储及基本操作 （一） 邻接矩阵法——顺序存储，用n*n 的矩阵A 来保存图
1. 表示方法
对无向图：v i ,v j 之间有边，则a ij =a ji =1，否则a ij =a ji =0，为对称矩阵。
对有向图：v i 向v j 有弧，则a ij =1，否则a ij =0，不一定是对称矩阵，除非两节点之间是双向连通的。
对带权图：v i ,v j 之间有边（弧），则a ij =相应的权，否则a ij =INFINITY 2. 相关求解
（1） 判断v i 和v j 之间是否有边(弧)，看a ij 的值是1还是0。 （2） 求无向图顶点v i 的度：第i 行或第i 列元素之和。 （3） 求有向图顶点v i 的出度：第i 行元素之和。
求有向图顶点v i 的入度：第i 列元素之和。
（4） 求带权图顶点v i 的出度：第i 行元素非零元素个数。
求带权图顶点v i 的入度：第i 列元素非零元素个数。
（二） 邻接表法——链式存储
1． 表示方法
将图中的所有顶点用一个n 个元素的数组来表示；对应每个顶点的边各有一个链表表示。链表的首元素是顶点，第二个元素是顶点最先访问的邻接点，第三个元素是顶点其次访问的邻接点…… 2． 相关知识点
（1） 对无向图，若有n 个顶点，e 条边，则邻接表中n 个头结点，2e 个表结点。 （2） 对无向图，顶点v i 的度，是第i 个单链表中表结点的个数。
（3） 对有向图，第i 个单链表中表结点的个数仅仅是v i 的出度OD(v i )；若要求入度，则需要遍历整个邻
接表。——v i 的入度是v i 结点在整个邻接表中出现的次数。
（4） 逆邻接表——链表中的表元素是所有指向v i 顶点的弧的邻接点。即邻接表是出度弧，而你邻接表则
是入度弧。
（5） 在邻接表上很容易就能找到当前结点的所有邻接顶点，但要判断v i 、v j 是否相邻，则要搜索第i 个
和第j 个单链表。
（三） 十字链表法 （四） 邻接多重表法 三、 图的遍历——深度优先遍历的复杂度与广度优先遍历的复杂度相等 （一） 深度优先遍历——是一个递归过程，可利用堆栈实现
以邻接矩阵表示时：深度优先遍历的时间复杂度为)(2n O ;
以邻接表表示时：深度优先遍历的时间复杂度为)(e n O +——结点个数+边的个数; 时间复杂度是：)(n O
（二） 广度优先遍历——利用队列实现，是一个非递归过程
以邻接矩阵表示时：深度优先遍历的时间复杂度为)(2n O ;
以邻接表表示时：深度优先遍历的时间复杂度为)(e n O +——结点个数+边的个数; 时间复杂度是：)(n O
四、 图的基本应用 （一） 最小（代价）生成树
1． Prim 算法
先从图中任意选取一个顶点A ；接下来选取与A 关系代价最小的一条边，将边和对应的邻接点B 画出；再以A 、B 为新集合，寻找到达AB 集合最短的路径邻接点C ，画出与C 的边；再以A 、B 、C 为新集合……
2． Kruskal 算法——时间复杂度)log (e e O
将图中所有边去掉，只保留顶点，然后寻找所有边中最短的一个，将这条边画出；然后再寻找剩余的所有边中，值最小的，依次画出，如果边画出后图中形成了回路，则该边取消，碰到值相等的两条不同边，
可任选其一先画，画毕再选另一条，如此直到所有顶点都被连通。
（二） 最短路径
见视频29集，34分之后。 （三） 拓扑排序
1． 有向无环图：一个无环的有向图，简称DAG 。是描述含有公共子式的表达式的有效工具。 2． 拓扑排序
（1） 从图总选择一个入度为0的顶点且输出之。
（2） 从图中删掉该顶点及其所有以该顶点为弧尾的弧。
反复执行这两个步骤，直到所有的顶点都被输出，则输出的序列就是这个无环有向图的拓扑序列。
（四） 关键路径
1． 边活动网
在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示互动的开销，则此带权的有向图称为 边活动网（Activity on edge network ），简称AOE 网。 2． 关键路径
把边活动网中从开始顶点到完成顶点的最长路径长度，称之为关键路径。 3． 几个相关的概念
源点：入度为0的顶点（即只有出度的顶点） 汇点：出度为0的顶点（即只有入度的顶点） 4． 关键活动 5． 关键路径算法 6． 算法分析
第四章 查找
一、 查找的基本概念 （一） 查找的定义 （二） 各种术语
1． 查找表 2． 静态查找表 3． 动态查找表 4． 关键字
5． 查找表的存储结构 6． 查找算法的时间效率 二、 顺序查找法——顺序存储或链式存储，元素可无序，时间复杂度为)(n O （一） 基本思路
依次从头开始往尾元素比较查找。 （二） 算法分析
1． 在不等概率情况下，∑==
+++=n
i i
i n n C
P C P C P C P ASL 1
2211...，其中P i 为查找到第i 个元素的概率，C i
为找到列表中第i 个元素时所需要的关键字比较次数。
例题：对长度为3的顺序表进行从后往前的顺序查找，查找第一个元素的概率1/2，查找第二个元素的概率是1/3，查找第三个元素的概率为1/6，则查找任一元素的平均查找长度为？（7/3） 答：查找第一个元素的概率是1/2，需要比较的次数为3（因为从后向前）；
查找第二个元素的概率是1/3，需要比较的次数为2（因为从后向前）； 查找第三个元素的概率是1/6，需要比较的次数为1（因为从后向前）；
故ASL = 161231321
?+
?+? = 3
7
2． 在等概率情况下，查找某个元素的概率都是相等的，即
n 1，故顺序查找的平均查找长度为2
1+n 。 三、 折半查找法——必须顺序存储，元素必须有序，可以使用递归、非递归算法，时间复杂度)(log 2n O （一） 基本思想
1． 先以整个表作为查找范围，用给定值k 与中间位置结点（low=1；high=n ；??
?
???+=2high low mid ）的关键字进行比较，相等则查找成功；
2． 若不等，则重新规划新的查找区间，仍然让k 与mid 结点进行比较； 3． 依次进行，直到找到对应的k 或找不到退出。 （二） 算法分析
1． 查找某一个元素，比较的次数最多不超过：??1log 2+n 2． 算法的平均时间复杂度为)(log 2n O 3． 折半查找的判定树
4． 平均查找长度（Average Search Length ）ASL
（1） 精确查找长度
要想精确求得具有n 个结点的有序表其平均查找长度，必须将此有序表按照类似完全二叉树形式画出，然后依次计算各结点的查找长度，然后求和，再除以n 。例如：
上图有11个元素，按照判定树画出之后，⑥的查找长度为1，因为⑥处于第1层；3、9处于第2层，所以查找长度为2；…… 最后整棵判定树的查找长度加和为：1*1 + 2*2 + 3*4 + 4*4 = 33，所
以该树的平均查找长度为
11
33 （2） 等概率平均查找长度——满二叉树的平均查找长度
∑∑==--+≈-++=??
?????==n i j
i j i bs n n n n j n C n ASL 122111)1(log 1)1(log 1211
四、 B -树及其基本操作、B +树的基本概念
（一）B-树的定义
B-树是一种平衡的多路查找树，特点如下：
1．B-树的阶m ：表示任一结点最多有m 个子结点。 2．结点关键字的数量：
根结点的关键字个数11-≤≤m n ；非根结点关键字个数112-≤≤-??
?
?
??m n m 。
解释：根结点的关键字至多等于阶数m ，至少1个；非根结点的关键字至多m-1，至少12
-??
????m
3．非叶结点的子树数量：
m n x =+≤1（——即结点关键字数量加1），且m x m ≤≤??
?
???2。
解释：任何结点的子树最多为m 棵（等于阶数）；
根结点——至少有2棵子树；非根结点子树——最少为??
?
?
??2m 。 4．结点的排序：非叶结点中的多个关键字均自小至大有序排列，且左子树小于根，右子树大于根。
5．叶子结点：不带信息，且在同一层。 （二）B-树的操作
（三）B +
树的基本概念 五、 散列表 （一） 哈希表的定义
1． 哈希函数：标识关键字k 与关键字所处位置的函数f(k) 2． 哈希表：利用哈希函数建立的表，也称Hash 表或散列表。 （二） 哈希函数的构造方法
1． 直接定址法： 2． 数字分析法： 3． 平方取中法： 4． 折叠法： 5． 随机函数法： 6． 除留取余法： （三） 哈希表冲突及其解决办法
1． 与散列表查找效率相关的因素：
（1） 装填因子散列表的长度
要存储的元素个数
=
α ——与散列表的长度无关
（2） 所采用的散列函数
（3） 解决冲突的方法（解决方法不好将会导致继续冲突） 2． 处理冲突的方法
（1） 开放定址法：——H i =（H(key) + d i ）% m i=1,2,…k(k<=m-1)
①线性探测再散列：d i =1,2,…m-1；
②二次探测再散列：d i =12,-12,22，-22,32，-32，…，2k ±(k<=m/2)； ③伪随机探测再散列：d i =伪随机数序列 （2） 再哈希法： （3） 链地址法：
（4） 建立一个公共溢出区 六、 查找算法的分析与应用
第五章 内部排序
一、 排序的基本概念 （一） 排序的定义
1． 排序
2． 稳定排序、不稳定排序
3． 内部排序、外部排序 4． 排序过程的两项基本工作 （二） 排序的分类
1． 插入排序 2． 交换排序 3． 选择排序 4． 归并排序 5． 基数排序 （三） 排序算法的效率 （四） 待排序序列的参考存储结构 二、 插入排序
（一） 直接插入排序——需做n-1趟，时间复杂度为)(2n O ，稳定排序 （二） 折半插入排序——需做n-1趟，时间复杂度为)(2n O ，稳定排序。
与直接插入相比，比较次数减少，移动次数不变
三、 起泡排序——需做n-1趟，时间复杂度为)(2n O ，稳定排序。
（一） 基本思想
交换排序的一种，对所有相邻两个关键字进行比较，交换。第1趟比较，最大者移到最右侧；第2趟，次最大者移动到次最右侧，…… （二） 算法 四、 简单选择排序——算法简单，速度较慢，不稳定排序，时间复杂度为)(2n O 。
五、 希尔排序——改进的插入排序，又称“缩小增量排序”，不稳定，时间复杂度为)(5.1n O 。 六、 快速排序——改进的冒泡排序， 七、 堆排序
举例：将序列(503,87,512,61,908,170,897,275,653,462)进行堆排序。 解：
1． 先将如上序列按层次画成完全二叉树
2． 通过筛选，将最小值求出
（1） 从根结点503开始，依次检查各层是否符合堆的特点（即双亲结点小于左右子树），若不符合，则
将双亲结点和子结点中较小者进行交换。
503先和87交换；503再和61交换；503再和275交换；同时512和170交换，908和462交换
（2）此时，第2、3、4层都符合堆的要求，但根结点又不符合堆要求，继续调整（87和61交换）
（3）此时，便是第一步建堆结束，第一步结束后，最小值61上堆顶。
3．堆顶（即最小值61）已选出，也就是说在后面的排序中61已不再进行排序，所以将61和当前序列中的最后一个908进行交换，得到一个新的不符合堆要求的完全二叉树。
4．重复步骤2，得到次最小值87。
5． 接下来的过程中，87已不需再排序，所以87和倒数第2个数653交换，再重复步骤2，得到170。
6． 继续以上步骤，直到最后结果。
八、 二路归并排序 九、 基数排序 十、 各种内部排序算法的比较 十一、 内部排序算法的应用
《数据结构》第二章习题参考答案 殷人昆版
《数据结构》第二章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题 （1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题
严蔚敏版数据结构课后习题答案-完整版
第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据
类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
数据结构线性表实验报告
序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并
退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include
数据结构第二章课后习题题解
2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i]
} } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node （A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n) 堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout< 数据结构复习题集 一、判断题 1.线性表的长度是线性表所占用的存储空间的大小。( F ) 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。( F ) 3.在对链队列做出队操作时，不会改变front指针的值。( F ) 4.如果两个串含有相同的字符，则说它们相等。( F ) 5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。(T ) 6.已知一棵树的先序序列和后序序列，一定能构造出该树。( F ) 7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。(T ) 8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。( F ) 9.对一个堆按层次遍历，不一定能得到一个有序序列。(T ) 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。(T ) 11. 线性表的逻辑顺序与物理顺序总是一致的。( F ) 12. 线性表的顺序存储表示优于链式存储表示。( F ) 13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。(T ) 14. 二维数组是其数组元素为线性表的线性表。( F ) 15. 每种数据结构都应具备三种基本运算：插入、删除和搜 索。(T ) 16.（101，88，46，70，34，39，45，58，66，10）是堆；(T ) 17.将一棵树转换成二叉树后，根结点没有左子树；( F ) 18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(F) 19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T ) 20.用一组地址连续的存储单元存放的元素一定构成线性表。(F) 21.堆栈、队列和数组的逻辑结构都是线性表结构。( T ) 22.给定一组权值，可以唯一构造出一棵哈夫曼树。( F) 23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。( T) 24.在平均情况下，快速排序法最快，堆积排序法最节省空间。( T) 25.快速排序法是一种稳定性排序法。( F ) 二.选择题: 1.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。 A.23415 B.54132 C.31245 D.1425 3 2．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。 A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n 3．二叉树在线索化后，仍不能有效求解的问题是（D）。 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 学 《数据结构》课程 实验报告 实验名称：线性表基本操作的实现实验室(中心)： 学生信息： 专业班级： 指导教师： 实验完成时间： 2016 实验一线性表基本操作的实现 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容及要求 1.顺序线性表的建立、插入、删除及合并。 2.链式线性表的建立、插入、删除及连接。 三、实验设备及软件 计算机、Microsoft Visual C++ 6.0软件 四、设计方案（算法设计） ㈠采用的数据结构 本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。 ㈡设计的主要思路 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入； 2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作； 3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入； 4.对前面建立的链表进行插入、删除及连个链表的连接操作； ㈢算法描述 1、顺序表 void Init(sqlist &);//初始化顺序表 BOOL Inse(sqlist &,int,char); //在线性表中插入元素 BOOL del(sqlist&,int,char &); //在线性表中删除元素 int Loc(sqlist,char); //在线性表中定位元素 void print(sqlist); //输出顺序表 void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并 2、链表 void CreaL(LinkList &,int); //生成一个单链表 BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素 BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素 void LPrint(LinkList); //显示单链表所有元素 void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接 五、程序代码 1、顺序表 #include 第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B 第一章 1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。 算法是语句序列解决特定问题的固有程序片段。数据结构是确定数据间的关系。从具体问题抽象出一个合适的数学模型、然后设计一个解决此数学模型的算法，最后编写出程序。寻求数学模型的是指就是数据结构要完成的工作。参看书p1前两段的描述。 2. 数据结构的概念，它包含哪三方面的内容？ 数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。参看书p3 包含三方面的内容:1、数据之间的逻辑关系2、数据在计算机中的存储方式3、在数据上定义的运算的集合。 3. 数据、数据元素、数据项的基本概念。举例说明数据元素和数据项的联系与区别。 数据：描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑或处理。 数据项：数据项是具有独立含义的最小标识单位，是数据元的一个具体值，是数据记录中最基本的、不可分的有名数据单位。 例1：class A { int c[123]; int i; }; class B { A a; } B b; b.a是数据项，B是数据元素 例2：一本书的数目信息为一个数据元素，而数目信息中每一项（如书名、作者名等）为一个数据项 4. 从逻辑结构来看，数据结构有哪四种基本结构，各自的特点是什么？ 1、集合（数据元素之间同属于一个集合，再无其他关系） 2、线性结构（数据元素之间存在一对一的关系） 3、树形结构（数据元素之间一对多的关系） 4、图状结构或网状结构（数据元素之间多对多的关系） 5. 从物理结构来看，数据结构有哪两种基本结构，各自的特点是什么？ 1、顺序存储结构 特点：借助元素在存储器中的相应位置来表示数据元素之间的逻辑关系。 2、链式存储结构 特定：借助元素在存储地址的指针表示数据元素之间的逻辑关系。 6. 算法的5个特征，4个评价标准是什么？ 特征:有穷性、确定性、可行性、输入、输出。 评价标准：正确性、可读性、健壮性、效率与低存储量需求。 7. 描述时间复杂度。 实验报告 实验一线性表 实验目的： 1.理解线性表的逻辑结构特性； 2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。 实验原理： 线性表顺序存储结构下的基本算法； 线性表链式存储结构下的基本算法； 实验内容： 2－21设计单循环链表，要求： （1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。 （2）设计一个测试主函数，实际运行验证所设计单循环链表的正确性。 2－22 .设计一个有序顺序表，要求： （1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。 （2）设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。 （3）设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。 程序代码： 2－21（1）头文件LinList.h如下： typedef struct node { DataType data; struct node *next; }SLNode; /*（1）初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1); 《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i数据结构_实验1_线性表的基本操作
(完整版)数据结构课后习题及解析第二章
数据结构实验一题目一线性表实验报告
严蔚敏数据结构题集(C语言版)完整
《数据结构》实验一 线性表及其应用
(完整版)数据结构第二章线性表1答案
数据结构实验一题目一线性表实验报告
严蔚敏版数据结构复习题
数据结构线性表的应用实验报告
数据结构实验线性表基本操作
数据结构 线性表 课后答案
数据结构老师给的复习要点(严蔚敏版)
数据结构线性表实验报告
最新《数据结构》 第二章 线性表习题
- 数据结构课后习题答案第二章 线性表
- 数据结构第2章 线性表 教案
- 数据结构第二章线性表
- 数据结构习题及答案与实验指导(线性表)2
- 《数据结构》第二章线性表习题与解答
- 数据结构线性表
- 第二章线性表
- 《数据结构及其应用》笔记含答案 第二章_线性表
- 数据结构第二章课后答案
- 数据结构第2章线性表习题及答案
- 数据结构练习题 第二章 线性表 习题及答案
- 数据结构与算法习题：第二章 线性表
- 数据结构四次课-第2章线性表
- 《数据结构》第二章 线性表.ppt
- 数据结构第二章习题(2)
- 数据结构课后习题答案第二章 线性表
- 数据结构李春葆 第2章 线性表
- (完整版)数据结构第二章线性表1答案
- 数据结构第二章课后习题题解
- 《数据结构》 第二章 线性表习题