一、顺序表和链表习题
1. 顺序表就地逆置
#include <stdio.h>
// 定义顺序表结构
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int length;
} SqList;
// 就地逆置顺序表
void reverseList(SqList *L) {
int i, temp;
for (i = 0; i < L->length / 2; i++) {
// 交换对称位置的元素
temp = L->data[i];
L->data[i] = L->data[L->length - 1 - i];
L->data[L->length - 1 - i] = temp;
}
}
2. 删除顺序表中值为 e 的所有元素
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int length;
} SqList;
// 删除值为 e 的所有元素
void deleteElem(SqList *L, int e) {
int k = 0, i;
// 统计值不为 e 的元素个数
for (i = 0; i < L->length; i++) {
if (L->data[i] != e) {
L->data[k++] = L->data[i];
}
}
L->length = k;
}
3. 有序顺序表中插入元素 e 保持有序
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int length;
} SqList;
// 有序插入元素 e
void insertElem(SqList *L, int e) {
int i;
// 找到插入位置
for (i = L->length - 1; i >= 0 && L->data[i] > e; i--) {
L->data[i + 1] = L->data[i];
}
L->data[i + 1] = e;
L->length++;
}
4. 计算单链表中数据域值为 x 的结点个数
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结点结构
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
// 计算值为x的结点个数
int countNodes(LinkList L, int x) {
int count = 0;
LNode *p = L->next;
while (p != NULL) {
if (p->data == x) {
count++;
}
p = p->next;
}
return count;
}
5. 判断单链表是否递增有序
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
// 判断链表是否递增有序
int isIncreasing(LinkList L) {
LNode *p = L->next;
if (p == NULL) {
return 1; // 空链表视为有序
}
while (p->next != NULL) {
if (p->data > p->next->data) {
return 0; // 不是递增有序
}
p = p->next;
}
return 1; // 是递增有序
}
6. 单链表就地逆置
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
// 单链表就地逆置
void reverseList(LinkList L) {
LNode *p = L->next;
L->next = NULL;
LNode *q;
while (p != NULL) {
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
第六题这个 LNode *p = L->next; L->next = NULL; LNode *q;没看懂
这段代码是单链表就地逆置算法的核心部分，我们可以逐步拆解来理解其原理：
LNode *p = L->next; // 步骤1：初始化指针p，指向第一个实际节点（跳过头节点）
L->next = NULL; // 步骤2：将头节点的next置空，作为逆置后链表的尾节点
LNode *q; // 步骤3：声明临时指针q，用于保存后续节点
为什么这样做？
单链表的就地逆置采用头插法思想，核心是将原链表的节点逐个 "摘下"，再反向插入到头节点后面：
指针 p 的作用：
p初始指向原链表的第一个节点（L->next），它负责遍历原链表的所有节点。L->next = NULL： 头节点
L的next置空后，原链表的头节点变成了逆置后链表的尾节点（尾节点的next必须为NULL）。临时指针 q： 在每次移动
p之前，用q保存p的下一个节点（q = p->next），防止原链表断裂后无法继续遍历。
完整逆置过程示例
假设原链表为：L(头节点) -> 1 -> 2 -> 3 -> NULL
初始状态：
p=1，L->next=NULL第一次循环：
q = p->next（q=2）p->next = L->next（1->next=NULL）L->next = p（L->next=1）p = q（p=2） 此时链表：L -> 1 -> NULL，剩余节点：2 -> 3 -> NULL第二次循环：
q = p->next（q=3）p->next = L->next（2->next=1）L->next = p（L->next=2）p = q（p=3） 此时链表：L -> 2 -> 1 -> NULL，剩余节点：3 -> NULL第三次循环：
q = p->next（q=NULL）p->next = L->next（3->next=2）L->next = p（L->next=3）p = q（p=NULL） 最终链表：L -> 3 -> 2 -> 1 -> NULL（完成逆置）
简单说，这段代码的作用是初始化逆置所需的指针，为后续的节点 "头插" 操作做准备，通过逐步移动指针实现链表方向的反转。
二、栈和队列的基本操作
1. 顺序栈的基本操作
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
// 顺序栈结构定义
typedef struct {
int data[MAXSIZE];
int top;
} SqStack;
// 初始化栈
void InitStack(SqStack *S) {
S->top = -1;
}
// 判断栈空
int StackEmpty(SqStack S) {
return S.top == -1;
}
// 入栈
int Push(SqStack *S, int e) {
if (S->top == MAXSIZE - 1) {
return 0;
}
S->top++;
S->data[S->top] = e;
return 1;
}
// 出栈
int Pop(SqStack *S, int *e) {
if (StackEmpty(*S)) {
return 0;
}
*e = S->data[S->top];
S->top--;
return 1;
}
// 获取栈顶元素
int GetTop(SqStack S, int *e) {
if (StackEmpty(S)) {
return 0;
}
*e = S.data[S.top];
return 1;
}
2. 链栈的基本操作
#include <stdio.h>
#include <stdlib.h>
// 链栈结点结构定义
typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode, *LinkStack;
// 初始化链栈
void InitStack(LinkStack *S) {
*S = NULL;
}
// 判断链栈空
int StackEmpty(LinkStack S) {
return S == NULL;
}
// 入栈
int Push(LinkStack *S, int e) {
StackNode *p = (StackNode *)malloc(sizeof(StackNode));
if (!p) {
return 0;
}
p->data = e;
p->next = *S;
*S = p;
return 1;
}
// 出栈
int Pop(LinkStack *S, int *e) {
if (StackEmpty(*S)) {
return 0;
}
StackNode *p = *S;
*e = p->data;
*S = p->next;
free(p);
return 1;
}
// 获取栈顶元素
int GetTop(LinkStack S, int *e) {
if (StackEmpty(S)) {
return 0;
}
*e = S->data;
return 1;
}
3. 循环队列的基本操作
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
// 循环队列结构定义
typedef struct {
int data[MAXSIZE];
int front, rear;
} SqQueue;
// 初始化循环队列
void InitQueue(SqQueue *Q) {
Q->front = Q->rear = 0;
}
// 判断循环队列空
int QueueEmpty(SqQueue Q) {
return Q.front == Q.rear;
}
// 入队
int EnQueue(SqQueue *Q, int e) {
if ((Q->rear + 1) % MAXSIZE == Q->front) {
return 0;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}
// 出队
int DeQueue(SqQueue *Q, int *e) {
if (QueueEmpty(*Q)) {
return 0;
}
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return 1;
}
// 获取队头元素
int GetHead(SqQueue Q, int *e) {
if (QueueEmpty(Q)) {
return 0;
}
*e = Q.data[Q.front];
return 1;
}
4. 链队列的基本操作
#include <stdio.h>
#include <stdlib.h>
// 链队列结点结构定义
typedef struct QNode {
int data;
struct QNode *next;
} QNode, *QueuePtr;
// 链队列结构定义
typedef struct {
QueuePtr front, rear;
} LinkQueue;
// 初始化链队列
void InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q->front) {
exit(1);
}
Q->front->next = NULL;
}
// 判断链队列空
int QueueEmpty(LinkQueue Q) {
return Q.front == Q.rear;
}
// 入队
int EnQueue(LinkQueue *Q, int e) {
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p) {
return 0;
}
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
return 1;
}
// 出队
int DeQueue(LinkQueue *Q, int *e) {
if (QueueEmpty(*Q)) {
return 0;
}
QueuePtr p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) {
Q->rear = Q->front;
}
free(p);
return 1;
}
// 获取队头元素
int GetHead(LinkQueue Q, int *e) {
if (QueueEmpty(Q)) {
return 0;
}
*e = Q.front->next->data;
return 1;
}
三、顺序表、单链表基本操作
1. 顺序表的基本操作
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
// 顺序表结构定义
typedef struct {
int data[MAXSIZE];
int length;
} SqList;
// 初始化顺序表
void InitList(SqList *L) {
L->length = 0;
}
// 插入元素
int ListInsert(SqList *L, int i, int e) {
if (i < 1 || i > L->length + 1 || L->length >= MAXSIZE) {
return 0;
}
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i - 1] = e;
L->length++;
return 1;
}
// 删除元素
int ListDelete(SqList *L, int i, int *e) {
if (i < 1 || i > L->length) {
return 0;
}
*e = L->data[i - 1];
for (int j = i; j < L->length; j++) {
L->data[j - 1] = L->data[j];
}
L->length--;
return 1;
}
// 查找元素
int LocateElem(SqList L, int e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1;
}
}
return 0;
}
2. 单链表的基本操作
#include <stdio.h>
#include <stdlib.h>
// 单链表结点结构定义
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
// 初始化单链表
void InitList(LinkList *L) {
*L = (LNode *)malloc(sizeof(LNode));
if (!*L) {
exit(1);
}
(*L)->next = NULL;
}
// 头插法创建单链表
void CreateListHead(LinkList *L, int n) {
LinkList p;
*L = (LNode *)malloc(sizeof(LNode));
(*L)->next = NULL;
for (int i = 0; i < n; i++) {
p = (LNode *)malloc(sizeof(LNode));
scanf("%d", &p->data);
p->next = (*L)->next;
(*L)->next = p;
}
}
// 插入元素
int ListInsert(LinkList *L, int i, int e) {
LinkList p = *L, s;
int j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p || j > i - 1) {
return 0;
}
s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
// 删除元素
int ListDelete(LinkList *L, int i, int *e) {
LinkList p = *L, q;
int j = 0;
while (p->next && j < i - 1) {
p = p->next;
j++;
}
if (!p->next || j > i - 1) {
return 0;
}
q = p->next;
*e = q->data;
p->next = q->next;
free(q);
return 1;
}
// 查找元素
LNode *LocateElem(LinkList L, int e) {
LNode *p = L->next;
while (p && p->data != e) {
p = p->next;
}
return p;
}
四、问答题
问题 1：循环队列的优点，判断循环队列的空和满
- 优点：循环队列解决了普通顺序队列 “假溢出” 的问题，能充分利用队列的存储空间。
- 判空：当队头指针front等于队尾指针rear时，循环队列为空。
- 判满：通常采用 “牺牲一个单元” 的方法，即当 (rear + 1) % 队列长度 == front 时，循环队列为满。
问题 2：栈和队列的区别
- 栈的特点：是一种 “先进后出”（FILO）的线性数据结构，元素只能从栈顶进行插入和删除操作。
- 队列的特点：是一种 “先进先出”（FIFO）的线性数据结构，元素从队尾插入，从队头删除。
- 使用场景：
- 栈：常用于函数调用、递归实现、表达式求值（如中缀转后缀）、括号匹配等场景，比如在递归函数执行时，调用栈保存函数的调用信息。
- 队列：常用于任务调度（如操作系统中的进程调度）、消息队列、广度优先搜索（BFS）等场景，比如打印任务队列，按提交顺序依次打印。
问题 3：递归
- 递归：是指在函数的定义中直接或间接调用自身的一种方法。
- 优点：代码简洁，能清晰地表达问题的求解思路，尤其是对于具有递归性质的问题（如斐波那契数列、树的遍历等），递归实现更直观。
- 缺点：可能会存在栈溢出的风险（当递归深度过大时）；并且由于递归过程中需要保存大量的调用栈帧，在时间和空间效率上可能不如非递归实现。
问题 4：递归借助什么数据结构执行，入口语句和出口语句一般用什么语句实现
- 数据结构：递归程序在执行时，借助栈（系统栈或自定义栈）来实现，系统会自动为递归函数的每次调用创建栈帧，保存局部变量、返回地址等信息。
- 入口与出口语句：
- 入口语句：一般通过函数自身的调用来实现，即递归调用语句。
- 出口语句：通常用条件判断语句（如
if语句）来实现递归的终止条件，当满足该条件时，不再进行递归调用，开始返回。
五、题5
问题①
问题② （解决方法：画试管图）
（1）判断 435612 是否能得到
不能。
- 分析：出栈序列中，当 4、3、5、6 依次出栈后，栈中剩余元素为 1、2（1 在栈底，2 在 1 之上）。此时下一个要出栈的是 1，但根据栈 “先进后出” 的特性，2 在 1 上面，必须 2 先出栈，1 才能出栈，所以无法得到 435612 这个出栈序列。
（2）判断 325641 是否能得到
能。
- 进栈出栈序列：
- 进栈 1、进栈 2、进栈 3；出栈 3、出栈 2；
- 进栈 4、进栈 5；出栈 5；
- 进栈 6；出栈 6；
- 出栈 4、出栈 1。
（3）判断 154623 是否能得到
不能。
- 分析：出栈序列中，1 先出栈后，进栈 2、3、4、5；然后 5、4 出栈，此时栈中元素为 2、3（2 在栈底，3 在 2 之上）。接下来要出栈的是 6，进栈 6 后出栈 6，之后要出栈的是 2，但 3 在 2 上面，必须 3 先出栈，2 才能出栈，所以无法得到 154623 这个出栈序列。
（4）判断 135426 是否能得到
能。
- 进栈出栈序列：
- 进栈 1；出栈 1；
- 进栈 2、进栈 3；出栈 3；
- 进栈 4、进栈 5；出栈 5；
- 出栈 4、出栈 2；
- 进栈 6；出栈 6。
六、题6
画试管分层图可得3
七、题7
八、题8
循环队列结构定义
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data; // 存储数据的数组
int front; // 队头指针
int rear; // 队尾指针
int capacity; // 数组容量
int size; // 队列中元素个数
} DynamicCircularQueue;
初始化队列
void initQueue(DynamicCircularQueue *queue, int initCapacity) {
queue->data = (int *)malloc(initCapacity * sizeof(int));
if (!queue->data) {
printf("内存分配失败\n");
exit(1);
}
queue->front = 0;
queue->rear = 0;
queue->capacity = initCapacity;
queue->size = 0;
}
入队操作（支持扩容）
int enQueue(DynamicCircularQueue *queue, int value) {
// 队列满，扩容
if (queue->size == queue->capacity) {
int newCapacity = queue->capacity * 2;
int *newData = (int *)malloc(newCapacity * sizeof(int));
if (!newData) {
printf("内存分配失败\n");
return 0;
}
// 复制原队列元素到新数组
int j = 0;
for (int i = queue->front; i != queue->rear; i = (i + 1) % queue->capacity) {
newData[j++] = queue->data[i];
}
free(queue->data);
queue->data = newData;
queue->front = 0;
queue->rear = j;
queue->capacity = newCapacity;
}
// 入队
queue->data[queue->rear] = value;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->size++;
return 1;
}
出队操作（支持缩容）
int deQueue(DynamicCircularQueue *queue, int *value) {
if (queue->size == 0) {
printf("队列为空\n");
return 0;
}
*value = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size--;
// 元素数量少于容量的1/4且容量大于初始容量，缩容
if (queue->size < queue->capacity / 4 && queue->capacity > 10) {
int newCapacity = queue->capacity / 2;
int *newData = (int *)malloc(newCapacity * sizeof(int));
if (!newData) {
printf("内存分配失败\n");
return 0;
}
// 复制原队列元素到新数组
int j = 0;
for (int i = queue->front; i != queue->rear; i = (i + 1) % queue->capacity) {
newData[j++] = queue->data[i];
}
free(queue->data);
queue->data = newData;
queue->front = 0;
queue->rear = j;
queue->capacity = newCapacity;
}
return 1;
}