数据结构考察八题
**1. 试写一算法，实现线性表就地逆置
（1）顺序表，利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）；
（2）单链表，带头结点。**
（1）该算法要求利用原表的存储空间将线性表逆置，也就是不能再新建一个表将元素插入其中，因此只需交换顺序表的第一个和倒数第一个元素、第二个和倒数第二个元素…以此类推，就可以逆置顺序表。
```C
//顺序表的类型定义：
typedef struct {
ElemType *data; //顺序表的元素
int length; //顺序表的当前长度
} SqList; //顺序表的类型定义
//创建顺序表：
Status CreateSqList(SqList &L, int n) {
ElemType *p;
L.data = (ElemType *)malloc(n * sizeof(ElemType));
if(!L.data)
printf("\n分配失败\n");
printf("请依次输入顺序表的数据元素:\n");
for(p=L.data; p< L.data+n; p++)
scanf("%d ", p);
L.length = n;
if(L.length)
printf("顺序表创建成功，它的长度为:%d\n", L.length);
return OK;
}
//逆置顺序表中元素：
Status SqListReverse(SqList &L) {
int i;
ElemType x; //临时数据元素，用来交换
for(i=0; i< L.length/2; i++) //交换顺序表的第一个和倒数第一个元素、第二个和倒数第二个元素…以此类推，就可以逆置顺序表，只需遍历表的一半
{ x = L.data[i];
L.data[i] = L.data[L.length-i-1];
L.data[L.length-i-1] = x;
}
return OK;
}
//主函数：
int main() {
SqList L;
CreateSqList(L, 10); //假设表中有10个元素
SqListReverse(L); //逆置顺序表
return OK;
}
```
（2）带头结点的单链表原地逆置只需将单链表每个结点中的next指针改为指向其前一个结点，即原来的第一个结点变为最后一个结点，next指针为空，原来的最后一个结点变为第一个结点，原来的头结点指向原来的最后一个结点。
```C
//单链表的类型定义：
typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
} LNode, *LinkList;
//利用头插法建立带头结点的单链表
LinkList List_HeadInsert(LinkList &L) { //头插法建立单链表
LNode *s;
int x;
L = (LinkList *) malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //初始为空链表
scanf("%d", &x); //输入结点的值
while (x != 9999) { //输入9999表示结束
s = (LNode *) malloc(sizeof(LNode)); //创建新结点
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}
//带头结点的单链表原地逆置：
Status LinkListReverse(Linklist &L) {
/*
* 三个指针, p 为要反转的结点, pre 为 p 前面的结点, r 是保存 p 后继的指针
* 初始状态 p 指向第一个元素, r 指向第二个元素
*/
LNode *pre = L, *p = L->next, *r = p->next;
/* 将第一个结点后继指针置空, 否则逆置后的链表中的最后一个元素和倒数第二个元素之间会形成环 */
p->next = NULL;
/*
* 如果 r 不为空, 三个指针前进一个单位.
* 否则链表只有一个结点, 直接执行 while 后的 L->next = p
* 循环中将 p 反转指向其前面的结点 pre, r 是 p 的后继
* 假设链表有 n 个元素, 则循环可将前 n - 1 个元素逆置
* 之后 p 指向第 n 个元素.
*/
while (r != NULL)
{
/* 指针依次进一 */
pre = p;
p = r;
r = r->next;
/* 逆置 */
p->next = pre;
}
/* 头结点指向逆置之后的第一个结点 */
L->next = p;
return OK;
}
//主函数：
int main() {
LinkList L;
List_HeadInsert(L);
LinkListReverse(L);
return OK;
}
```
**2. 请利用两个栈来模拟一个队列(可以不考虑栈满情况)。
已知栈的三个运算定义如下：
int S_Push(Stack &s,ElemType x);//元素 x 入栈；
int S_Pop(Stack &s,ElemType &x);//栈顶元素出栈，赋给变量 x；
int S_isEmpty(Stack s);//判栈是否为空。
利用栈的运算来实现该队列的三个运算：
int Q_En(Stack & s1,Stack & s2,ElemType x);//插入一个元素入队列；
int Q_De(Stack & s1,Stack & s2,ElemType &x);//删除一个元素出队列；
int Q_isEmpty(Stack s1,Stack s2);//判队列是否为空。**
栈的特点是后进先出，队列的特点是先进先出。用两个栈S1和S2模拟队列时，令S1执行入栈操作模拟入队，S2执行出栈操作模拟出队。本题无需考虑栈满情况。
入队时，将元素直接插入S1中。
出队时，若S2不空，则将S2栈顶元素出栈；若S2为空且S1为空，则队列中没有元素，无法执行出队操作；若S2为空且S1不空，则先将S1中元素全部逐一转入S2，最后将S2栈顶元素出栈。
判空条件为S1和S2都为空时，则队列为空。
```C
//栈的类型定义：
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //存放栈中元素
int top=-1; //栈顶指针，初始为-1
} Stack;
//插入一个元素入队列：
int Q_En(Stack & s1, Stack & s2, ElemType x) {
Push(s1, x);
return 1;
}
//删除一个元素出队列：
int Q_De(Stack & s1, Stack & s2, ElemType &x) {
if (!S_isEmpty(s2))
S_Pop(s2, x);
else if (S_isEmpty(s1)) {
printf("队列为空\n");
return 0;
}
else {
while (!S_isEmpty(s1)) {
S_Pop(s1, x);
S_Push(s2, x);
}
S_Pop(s2, x);
}
return 1;
}
//判队列是否为空：
int Q_isEmpty(Stack s1,Stack s2)
{
if(S_isEmpty(S1)&&S_isEmpty(S2))
return 1;
else
return 0;
}
```
**3. 试写一算法，判断两个字符串是否可以循环匹配。例如：s1="abcaaaab"和 s2="aaaababc"匹配。**
若两个字符串可以循环匹配，则两个字符串必须长度相同，且在字符串s3=s1+s1中一定可以找到字符串s2。在字符串s3中寻找s2时使用KMP算法。
```C
//字符串的类型定义：
#define MaxLen 255 //预定义最大串长为255
typedef struct{
char ch[MaxLen]; //每个分量存储一个字符
int length;
}SString;
//KMP算法：
void get_next(SString T,int next[]) { //求next数组
int i=1,j=0;
next[1]=0;
while(iT.length)
return i-T.length; //匹配成功
else
return 0;
}
//判断字符串能否循环匹配：
int SStringCycleMatch(SString s1, SString s2) {
if (s1.length!=s2.length) //若长度不相等则无法循环匹配
return 0;
SString s3;
strcat(s3.ch,s1.ch);strcat(s3.ch,s1.ch); //令s3=s1+s1
if (Index_KMP(s3,s2,&next[0]))
return 1;
else
return 0;
}
//主函数：
int main(){
SString s1,s2;
gets(s1.ch); s1.length = strlen(s1.ch);
gets(s2.ch); s2.length = strlen(s2.ch);
get_next(s2,next);
if (SStringCycleMatch(s1,s2)==1)
printf("可以循环匹配\n");
else
printf("不可以循环匹配\n");
return 0;
}
```
**4. 以三元组顺序表存储稀疏矩阵，实现两个矩阵相乘。**
稀疏矩阵中每一个元素都是一个三元组，有行数row，列数col，以及数据域value。
两个稀疏矩阵相乘时，将第一个矩阵的第一个三元组和第二个矩阵的所有三元组进行匹配，若第一个三元组的列数和第二个矩阵中的一个三元组的行数相同，那么这两个元素可以相乘，得到结果矩阵的第一个三元组；接着将第一个矩阵的第二个三元组和第二个矩阵的所有三元组进行匹配，若第一个矩阵的第二个三元组的列数和第二个矩阵中的一个三元组的行数相同，那么这两个元素可以相乘，得到结果矩阵的第二个三元组…以此类推，直到第一个矩阵的所有三元组遍历完成，就得到了整个结果矩阵。
最后将结果矩阵进行重新排序，按照行数优先，列数次优先的原则。
```C
//三元组的类型定义：
typedef struct {
int row; //此处的行列值从1开始，没有第0行和第0列
int col;
ElemType value; //矩阵第row行第col列对应的值
} Triple;
//稀疏矩阵的类型定义：
typedef struct {
Triple *data; //非零三元组表
int row_num; //矩阵的总行数
int col_num; //矩阵的总列数
int non_zero; //矩阵总的非零值的个数
} TSMatrix;
//稀疏矩阵相乘：
//当第一个矩阵的列值等于第二个矩阵的行值时，两个矩阵相乘并将结果存在result矩阵中
void MultSMatrix(TSMatrix *matrix1, TSMatrix *matrix2, TSMatrix *result) {
int i = 0;
int j = 0;
int k = 0;
int q;
if (matrix1->cols != matrix2->rows) //如果两个矩阵的行数或者列数不相同
printf("这两个矩阵无法相乘\n");
else {
//为结果矩阵分配内存空间
result->data = (Triple *) malloc(sizeof(Triple) * (matrix1->rows * matrix2->cols));
result->rows = matrix1->rows;//结果矩阵的行数为第一个矩阵的行数
result->cols = matrix2->cols;//结果矩阵的列数为第二个矩阵的列数
for (k = 0; k < matrix1->rows * matrix2->cols; k++)
(result->data + k)->value = 0;
k = 0;
while (i < matrix1->NoZero) { //当两个矩阵的元素都没有处理完时
for (j = 0; j < matrix1->NoZero; j++)
//如果matrix1的第i个元素的列值与matrix2的第j个元素的行值相同，则进行相乘
if ((matrix1->data + i)->col == (matrix2->data + j)->row) {
(result->data + k)->row = (matrix1->data + i)->row;//result的第k个元素的行值为第一个矩阵的第i个元素对应的行值
(result->data + k)->col = (matrix2->data + j)->col;//result的第k个元素的列值为第二个矩阵的第j个元素对应的列值
//result的第k个元素的value值为第一个矩阵的第i个元素的value值与第二个矩阵的第j个元素的value值相乘的结果
(result->data + k)->value = (matrix1->data + i)->value * (matrix2->data + j)->value;
//用当前result的第k个元素与前k-1个元素的行列值进行比较：若相等，将第k项对应的value值加到第q项
for (q = 0; q < k; q++)
if ((result->data + k)->row == (result->data + q)->row &&
(result->data + k)->col == (result->data + q)->col) {
(result->data + q)->value += (result->data + k)->value;
k--; //将k-1的目的是与下面的k+1对应，使k值不变，因为相等时将该项的结果与加到之前的结果上，故不需要生成新的项
}
k++;
}
i++;
}
result->NoZero = k;
//重新为result->data分配适合大小的存储空间
result->data = (Triple *) realloc(result->data, sizeof(Triple) * (result->NoZero));
}
}
//主函数：
int main() {
TSMatrix MatrixA, MatrixB, Result;
printf("请输入第一个矩阵的行数 列数 非零元素数：\n");
scanf("%d %d %d", &MatrixA.rows, &MatrixA.cols, &MatrixA.NoZero);
MatrixA.data = (Triple *) malloc(sizeof(Triple) * MatrixA.NoZero);
for (int i = 0; i < MatrixA.NoZero; ++i) {
printf("请输入第一个矩阵的第%d个三元组：\n", i + 1);
scanf("%d %d %d", &MatrixA.data[i].row, &MatrixA.data[i].col, &MatrixA.data[i].value);
}
printf("请输入第二个矩阵的行数 列数 非零元素数：\n");
scanf("%d %d %d", &MatrixB.rows, &MatrixB.cols, &MatrixB.NoZero);
MatrixB.data = (Triple *) malloc(sizeof(Triple) * MatrixB.NoZero);
for (int i = 0; i < MatrixB.NoZero; ++i) {
printf("请输入第二个矩阵的第%d个三元组：\n", i + 1);
scanf("%d %d %d", &MatrixB.data[i].row, &MatrixB.data[i].col, &MatrixB.data[i].value);
}
MultSMatrix(&MatrixA, &MatrixB, &Result);
printf("结果矩阵为：\n");
for (int i = 0; i < Result.NoZero; ++i)
printf("(%d,%d,%d)\n", Result.data[i].row, Result.data[i].col, Result.data[i].value);
}
```
**5. 设计求某个结点在二叉树中的双亲结点算法。**
假设二叉树b采用链式存储结构，使用递归求指定值为x的结点的双亲结点，若当前结点的左孩子或右孩子的值与x相等，则返回当前节点的值，否则继续比较当前结点的左右孩子的左右孩子的值与x是否相等，直到找到为止，否则返回NULL。
```C
//二叉树的类型定义：
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
//求结点x在二叉树中的双亲结点：
int FindParent(BiTree T,Elemtype x){
if(T){
if((T->lchild)&&T->lchild->data==x) { //左孩子不为空 ，判断左孩子与x是否相等
printf("x的双亲结点为%c\n", T->data);
return 1;
}
if((T->rchild)&&T->rchild->data==x) { //左孩子不为空 ，判断左孩子与x是否相等
printf("x的双亲结点为%c\n", T->data);
return 1;
}
else{
FindParent(T->lchild,x);
FindParent(T->rchild,x);
}
}
return 0;
}
```
**6. 设计一个利用广度优先遍历实现的有向图拓扑排序算法。**
因为拓扑排序需要用到入度，因此先求所有顶点的入度。
拓扑排序序列的第一个点一定是入度为0的顶点，因为没有任何边指向它。接下来的点应该是在入度为0的顶点之后，所以它们只能被前面的顶点所指，把刚才那些顶点所指的点的入度减一，如果减之后有入度为0的顶点就把它加入序列。再不断重复上一步操作，拓扑排序就完成了。用一个栈存储入度为0的顶点，如果最后出栈的顶点数小于总顶点数，则说明有环。
```C
//边表结点的类型定义：
typedef struct node//边表结点
{
int adjvex;//该边所指向结点对应的下标
struct node *next;//该边所指向下一个结点的指针
} eNode;
//顶点表结点的类型定义：
typedef struct headnode//顶点表结点
{
int in;//顶点入度
char vertex;//顶点数据
eNode *firstedge;//指向第一条边的指针，边表头指针
} hNode;
//图的类型定义：
typedef struct//邻接表（图）
{
hNode adjlist[Max];//以数组的形式存储
int n, e;//顶点数，边数
} linkG;
//创建图：
//以邻接表的存储结构创建图
linkG *creat(linkG *g) {
int i, k;
eNode *s;//边表结点
int n1, e1;
char ch;
g = (linkG *) malloc(sizeof(linkG));//申请结点空间
printf("请输入顶点数和边数：");
scanf("%d%d", &n1, &e1);
g->n = n1;
g->e = e1;
printf("顶点数：%d 边数：%d\n", g->n, g->e);
printf("请输入顶点信息（字母）：");
getchar();//因为接下来要输入字符串，所以getchar用于承接上一条命令的结束符
for (i = 0; i < n1; i++) {
scanf("%c", &ch);
g->adjlist[i].vertex = ch;//获得该顶点数据
g->adjlist[i].firstedge = NULL;//第一条边设为空
}
printf("\n打印顶点下标及顶点数据：\n");
for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据
{
printf("顶点下标：%d 顶点数据：%c\n", i, g->adjlist[i].vertex);
}
getchar();
int i1, j1;//相连接的两个顶点序号
for (k = 0; k < e1; k++)//建立边表
{
printf("请输入边：");
scanf("%d %d", &i1, &j1);
s = (eNode *) malloc(sizeof(eNode)); //申请边结点空间
s->adjvex = j1; //边所指向结点的位置，下标为j1
s->next = g->adjlist[i1].firstedge; //将当前s的指针指向当前顶点上指向的结点
g->adjlist[i1].firstedge = s; //将当前顶点的指针指向s
}
return g;//返回指针g
}
//求所有顶点入度：
void inDegree(linkG *g) //求图顶点入度
{
eNode *p;
int i;
for (i = 0; i < g->n; i++) //循环将顶点入度初始化为0
g->adjlist[i].in = 0;
for (i = 0; i < g->n; i++) //循环每个顶点
{
p = g->adjlist[i].firstedge; //获取第i个链表第1个边结点指针
while (p != NULL) //当p不为空（边存在）
{
g->adjlist[p->adjvex].in++; //该边终点结点入度+1
p = p->next; //p指向下一个边结点
}
}
}
//拓扑排序：
void TopologicalOrder(linkG *g)//拓扑排序
{
eNode *p;
int i, k, gettop;
int top = 0;//用于栈指针的下标索引
int count = 0;//用于统计输出顶点的个数
int *stack = (int *) malloc(g->n * sizeof(int));//用于存储入度为0的顶点
for (i = 0; i < g->n; i++)//第一次搜索入度为0的顶点
{
if (g->adjlist[i].in == 0)
stack[++top] = i;//将入度为0的顶点进栈
}
while (top != 0)//当栈不为空时
{
gettop = stack[top--];//出栈,并保存栈顶元素（下标）
printf("%c ", g->adjlist[gettop].vertex);
count++;//统计顶点
//接下来是将邻接点的入度减一，并判断该点入度是否为0
p = g->adjlist[gettop].firstedge;//p指向该顶点的第一条边的指针
while (p)//当p不为空时
{
k = p->adjvex;//相连接的顶点（下标）
g->adjlist[k].in--;//该顶点入度减一
if (g->adjlist[k].in == 0) {
stack[++top] = k;//如果入度为0，则进栈
}
p = p->next;//指向下一条边
}
}
if (count < g->n)//如果输出的顶点数少于总顶点数，则表示有环
printf("\n有环\n");
free(stack);//释放空间
}
//主函数：
int main() {
linkG *g = NULL;
g = creat(g); //创建图
inDegree(g); //求入度
TopologicalOrder(g); //拓扑排序
return 0;
}
```
**7. 设计算法实现利用二叉排序树进行排序。**
对于二叉排序树的任何一个非叶子结点，要求左子结点的值比当前节点的值小，右子结点的值比当前节点的值大，如果有相同的值，可以将该节点放在左子结点或右子结点。
因此总体思路是先将要排序的数构建成一个二叉排序树，再对该二叉排序树进行中序遍历即可得到按升序排列的数。
```C
//二叉排序树的类型定义：
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//栈的类型定义：
typedef struct {
BiTree *base;
BiTree *top;
int stacksize;
} Sqstack;
//初始化一个栈，用于中序遍历：
#define STACK_INIT_SIZE 100
void InitStack(Sqstack &S) {
S.base = (BiTree *) malloc(STACK_INIT_SIZE * sizeof(BiTNode));
if (!S.base)
exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
//二叉排序树的查找：
void SearchBST(BiTree T, int key, BiTree f, BiTree &p) {
if (!T)
p = f;
else if (T->data == key)
p = T;
else if (T->data < key)
SearchBST(T->rchild, key, T, p);
else
SearchBST(T->lchild, key, T, p);
}
//创建二叉排序树：
void CreatBST(BiTree &T, int e) {
BiTree p, s, q;
SearchBST(T, e, NULL, p);//找到带插入的位置。
s = (BiTree) malloc(sizeof(BiTNode));
s->data = e;
s->lchild = NULL;
s->rchild = NULL;
if (!p)T = s;
else if (e == p->data)//当待排序列中有相同的元素时，将其放在相同元素的右孩子位置。原来的右子树放在其右节点域。
{
q = p->rchild;
p->rchild = s;
s->rchild = q;
} else if (e < p->data)
p->lchild = s;
else
p->rchild = s;
}
//中序遍历二叉排序树：
#define STACK_INCREMENT 10
void InOrderTravese(BiTree T) {
BiTree p;
Sqstack Sqt;
InitStack(Sqt);
p = T;
while (p || Sqt.base != Sqt.top) {
if (p) {
if (Sqt.top - Sqt.base >= Sqt.stacksize) {
Sqt.base = (BiTree *) realloc(Sqt.base, (Sqt.stacksize + STACK_INCREMENT) * sizeof(BiTNode));
if (!Sqt.base)
exit(OVERFLOW);
Sqt.top = Sqt.base + Sqt.stacksize;
Sqt.stacksize += STACK_INCREMENT;
}
*Sqt.top++ = p;
p = p->lchild;
} else {
p = *--Sqt.top;
printf("%d ", p->data);
p = p->rchild;
}
}
printf("\n");
}
//主函数：
#define MAXSIZE 50
int main() {
int length;
int bst[MAXSIZE];
BiTree BST;
BST = (BiTree) malloc(sizeof(BiTNode));
BST = NULL;
printf("请输入待排序序列的个数N (N<%d)：", MAXSIZE);
scanf("%d", &length);
printf("请输入待排序的值：\n");
for (int i = 0; i < length; i++)
scanf("%d", &bst[i]);
for (int i = 0; i < length; i++)
CreatBST(BST, bst[i]);
printf("中序遍历二叉排序树：\n");
InOrderTravese(BST);
}
```
**8. 设计算法实现小顶堆的插入，设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。**
小顶堆就是一棵完全二叉树，非叶子结点的值不大于左孩子和右孩子的值。
插入x时，先将x插入到二叉树的最后一个结点，再根据小顶堆的定义，自底而上递归调整x的位置。
使用数组实现小顶堆。
```
//小顶堆的插入：
void MinHeapInsert(int array[], int n, int x) {//n为数组原长
array[n + 1] = x; //先把x插入到二叉树最后一个结点
int a = n + 1; //指向x的角标
int b;
while (a != 1) {
if (array[a] < array[a / 2]) { //如果x比双亲结点小，就交换x和双亲结点
b = array[a];
array[a] = array[a / 2];
array[a / 2] = b;
a /= 2; //指向x的角标减半
} else break;
}
}
//主函数：
int main() {
int n;
printf("请输入元素k的个数：\n");scanf("%d",&n);
int MinHeap[n+2];MinHeap[0]=0; //数组从第1个位置开始使用，第0个位置为0
printf("请输入小顶堆：\n");
for (int i = 1; i <= n; ++i)
scanf("%d",&MinHeap[i]);
int x;
printf("请输入x：\n");scanf("%d",&x);
MinHeapInsert(MinHeap, n, x);
for (int j = 1; j <= n+1; ++j)
printf("%d ", MinHeap[j]);
return 0;
}
```