实验一 线性表
一、实验目的和要求
本次实验的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列 例题，上机通过，并观察其结果，然后独立完成后面的实验题。（1学时）
二、实验内容和原理
1.建立如图1-1所示链表。 2.输出元素25 的位置。 3.输出第5个元素。 5.输出删除第4个元素后的链表 60 4.在第3个元素前插入值为98的元素后输出链表。
图表 a-1链表图示
2.已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb 归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。 例如： La=(1 ,7, 8) Lb=(2, 4, 6, 8, 10, 11) Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11)
3. 将这两个有序链表合并成一个有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
4. 用 BF算法求字符串t在字符串s的位置。
5. 正序建立单链表，并打印输出该单链表。
6. 通过一趟遍历，确定长度为n的单链表中值最大的元素并输出。
7. 设数组a={11，33，44，68，77}，数组b={22，33，77,88，99｝，两个数组均为链式存储 （1）求a和b的并集, 统计并集中元素的个数。 （2）求a和b的交集, 统计交集中元素的个数。 （3）在数组a中插入55，保持数组a有序。 （4）在数组b中删除元素77。
三、主要仪器设备
笔记本电脑
四、操作方法与实验步骤
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct node {
int data;
struct node* next;
};
int main() {
int i;
struct node* head = (struct node*)malloc(sizeof(struct node)); // 初始化链表头节点
head->next = NULL; // 设置头节点的next指针为NULL
struct node* q = head; // 使用q作为遍历指针
struct node* target = NULL; // 用于存储目标节点
struct node* prev = NULL; // 用于存储目标节点的前一个节点
int position = 1; // 记录当前节点位置
for (i = 0; i < 7; i++) {
struct node* p = (struct node*)malloc(sizeof(struct node)); // 分配新的节点
printf("Please input the data: ");
scanf_s("%d", &p->data); // 输入数据并赋值给新节点
p->next = NULL; // 新节点的初始next指针为NULL
q->next = p; // 将新节点连接到链表的末尾
q = p; // 更新q指向新节点，准备下一次迭代
if (p->data == 25) {
target = p;
}
if (position == 5) {
printf("The 5th element is: %d\n", p->data);
}
position++;
}
// 输出元素25的位置
if (target != NULL) {
printf("The position of element 25 is: %d\n", position - 1);
}
else {
printf("Element 25 not found in the list\n");
}
// 输出删除第4个元素后的链表
struct node* current = head->next;
struct node* temp;
position = 1;
while (current != NULL) {
if (position == 3) {
prev->next = current->next;
temp = current;
current = current->next;
free(temp);
}
else {
printf("%d --> ", current->data);
prev = current;
current = current->next;
}
position++;
}
printf("\n");
// 在第3个元素前插入值为98的元素
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = 98;
new_node->next = prev->next;
prev->next = new_node;
// 打印最终链表
current = head->next;
while (current != NULL) {
printf("%d --> ", current->data);
current = current->next;
}
printf("\n");
// 释放动态分配的内存
current = head;
while (current != NULL) {
struct node* temp = current;
current = current->next;
free(temp);
}
return 0;
}
图表 b 1-2运行结果
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 合并两个有序线性表为一个新的有序线性表
void merge(int La[], int Lb[], int La_len, int Lb_len, int Lc[]) {
int i = 0, j = 0, k = 0;
while (i < La_len && j < Lb_len) {
if (La[i] <= Lb[j]) {
Lc[k++] = La[i++];
}
else {
Lc[k++] = Lb[j++];
}
}
while (i < La_len) {
Lc[k++] = La[i++];
}
while (j < Lb_len) {
Lc[k++] = Lb[j++];
}
}
int main() {
int La[] = { 1, 7, 8 };
int Lb[] = { 2, 4, 6, 8, 10, 11 };
int La_len = 3;
int Lb_len = 6;
int Lc[MAX_SIZE];
merge(La, Lb, La_len, Lb_len, Lc);
printf("Merged List Lc: ");
for (int i = 0; i < La_len + Lb_len; i++) {
printf("%d ", Lc[i]);
}
printf("\n");
return 0;
}
图表 c 1-3运行结果
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct node {
int data;
struct node* next;
};
// 合并两个有序链表为一个有序链表，结果存储在La中
void merge(struct node* La, struct node* Lb) {
struct node* Lc = La;
struct node* pa = La->next;
struct node* pb = Lb->next;
struct node* pc = Lc;
while (pa != NULL && pb != NULL) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
}
else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = (pa != NULL) ? pa : pb;
// 释放Lb表的表头结点
free(Lb);
}
// 打印链表
void printList(struct node* head) {
struct node* current = head->next;
while (current != NULL) {
printf("%d --> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
// 创建链表La
struct node* La = (struct node*)malloc(sizeof(struct node));
La->next = NULL;
struct node* pa = La;
int La_data[] = { 1, 7, 8 };
for (int i = 0; i < 3; i++) {
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = La_data[i];
newNode->next = NULL;
pa->next = newNode;
pa = newNode;
}
// 创建链表Lb
struct node* Lb = (struct node*)malloc(sizeof(struct node));
Lb->next = NULL;
struct node* pb = Lb;
int Lb_data[] = { 2, 4, 6, 8, 10, 11 };
for (int i = 0; i < 6; i++) {
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = Lb_data[i];
newNode->next = NULL;
pb->next = newNode;
pb = newNode;
}
printf("List La: ");
printList(La);
printf("List Lb: ");
printList(Lb);
merge(La, Lb);
printf("Merged List Lc: ");
printList(La);
return 0;
}
图表 d 1-4运行结果
#include <stdio.h>
#include <string.h>
int bruteForce(char s[], char t[]) {
int s_len = strlen(s);
int t_len = strlen(t);
for (int i = 0; i <= s_len - t_len; i++) {
int j;
for (j = 0; j < t_len; j++) {
if (s[i + j] != t[j]) {
break;
}
}
if (j == t_len) {
return i + 1; // 返回匹配成功的子序列第一个字符的序号（从1开始）
}
}
return 0; // 匹配失败，返回0
}
int main() {
char s[] = "abracadabra";
char t[] = "cad";
int position = bruteForce(s, t);
if (position != 0) {
printf("String '%s' found at position %d in string '%s'\n", t, position, s);
}
else {
printf("String '%s' not found in string '%s'\n", t, s);
}
return 0;
}
图表 e 1-5运行结果
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct Node {
int data;
struct Node* next;
};
// 函数用于在链表末尾插入新节点
void insertNode(struct Node** head, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head;
new_node->data = data;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
// 函数用于打印输出链表
void printList(struct Node* node) {
while (node != NULL) {
printf("%d --> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
// 正序建立单链表
insertNode(&head, 1);
insertNode(&head, 2);
insertNode(&head, 3);
insertNode(&head, 4);
insertNode(&head, 5);
// 打印输出单链表
printf("Linked List: ");
printList(head);
return 0;
}
图表 f 1-6
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct Node {
int data;
struct Node* next;
};
// 函数用于在链表末尾插入新节点
void insertNode(struct Node** head, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head;
new_node->data = data;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
// 函数用于找出链表中值最大的元素并输出
void findMax(struct Node* head) {
if (head == NULL) {
printf("Linked list is empty.\n");
return;
}
int max = head->data;
struct Node* current = head;
while (current != NULL) {
if (current->data > max) {
max = current->data;
}
current = current->next;
}
printf("The maximum value in the linked list is: %d\n", max);
}
int main() {
struct Node* head = NULL;
// 正序建立单链表
insertNode(&head, 10);
insertNode(&head, 5);
insertNode(&head, 20);
insertNode(&head, 15);
insertNode(&head, 8);
// 找出链表中值最大的元素并输出
findMax(head);
return 0;
}
图表 g 1-7
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct Node {
int data;
struct Node* next;
};
// 函数用于在链表末尾插入新节点
void insertNode(struct Node** head, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head;
new_node->data = data;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
// 函数用于打印输出链表
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// 函数用于求两个链表的并集
void unionLists(struct Node* a, struct Node* b) {
struct Node* result = NULL;
struct Node* current = a;
// 将数组a中的元素加入并集中
while (current != NULL) {
insertNode(&result, current->data);
current = current->next;
}
// 将数组b中不在并集中的元素加入并集中
current = b;
while (current != NULL) {
struct Node* temp = result;
int found = 0;
while (temp != NULL) {
if (temp->data == current->data) {
found = 1;
break;
}
temp = temp->next;
}
if (!found) {
insertNode(&result, current->data);
}
current = current->next;
}
printf("Union of arrays a and b: ");
printList(result);
}
// 函数用于求两个链表的交集
void intersectionLists(struct Node* a, struct Node* b) {
struct Node* result = NULL;
struct Node* current = a;
// 将数组a中的元素加入交集中
while (current != NULL) {
struct Node* temp = b;
while (temp != NULL) {
if (temp->data == current->data) {
insertNode(&result, current->data);
break;
}
temp = temp->next;
}
current = current->next;
}
printf("Intersection of arrays a and b: ");
printList(result);
}
// 函数用于在有序链表中插入元素，保持有序性
void insertSorted(struct Node** head, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
if (*head == NULL || data < (*head)->data) {
new_node->next = *head;
*head = new_node;
}
else {
struct Node* current = *head;
while (current->next != NULL && current->next->data < data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
// 函数用于删除链表中指定元素
void deleteNode(struct Node** head, int data) {
struct Node* temp = *head;
struct Node* prev = NULL;
if (temp != NULL && temp->data == data) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != data) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Element not found in the list.\n");
return;
}
prev->next = temp->next;
free(temp);
}
int main() {
struct Node* a = NULL;
struct Node* b = NULL;
// 插入元素到数组a和数组b
int a_values[] = { 11, 33, 44, 68, 77 };
int b_values[] = { 22, 33, 77, 88, 99 };
for (int i = 0; i < 5; i++) {
insertNode(&a, a_values[i]);
insertNode(&b, b_values[i]);
}
// 求并集
unionLists(a, b);
// 求交集
intersectionLists(a, b);
// 在数组a中插入元素55，保持有序
insertSorted(&a, 55);
printf("Array a after inserting 55: ");
printList(a);
// 在数组b中删除元素77
deleteNode(&b, 77);
printf("Array b after deleting 77: ");
printList(b);
return 0;
}
图表 h 1-8
五、实验数据记录和处理
见四。
六、实验结果与分析
七、讨论、心得
链表具有动态性，可以方便地插入和删除节点，但在访问元素时需要遍历整个链表，时间复杂度为O(n)。链表的插入和删除操作相对容易，但在查找特定元素时效率较低。这让我思考了链表的优势和劣势，以及在不同场景下选择链表或数组的依据。
实验二 栈和队列
一、实验目的和要求
本次实验的主要目的是为了使学生熟练掌握栈和队列的基本操作在顺序存储结 构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下 列例题，上机通过，并观察其结果，然后独立完成后面的实验题。（1学时）
二、实验内容和原理
一、栈的基本操作
1.在顺序存储结构上实现栈的下述基本功能 （1）初始化一个空顺序栈。 （2）顺序栈的入栈操作的程序。 （3）顺序栈的出栈操作的程序。 （4）取栈顶元素。 （5）顺序栈的遍历。
2.在链式存储结构上实现栈的下述基本功能 （1）初始化一个空链栈。 （2）链栈的入栈操作的程序。 （3）链栈的出栈操作的程序。 （4）取栈顶元素。 （5）链栈的遍历。
二、队列的基本操作
1.在顺序存储结构上实现队列的下述基本功能 （1）编写顺序队列的入队操作的程序 （2）编写顺序队列的出队操作的程序 （3）编写顺序队列的初始化操作的程序 （4）编写顺序队列的求队列长度操作的程序 （5）编写顺序队列的遍历队列操作的程序。
2.在链式存储结构上实现队列的下述基本功能 （1）编写链式队列的入队操作的程序 （2）编写链式队列的出队操作的程序 （3）编写链式队列的初始化操作的程序 （4）编写链式队列的求队列长度操作的程序 （5）编写链式队列的遍历队列操作的程序
三、主要仪器设备
笔记本电脑
四、操作方法与实验步骤
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义顺序栈结构体
struct Stack {
int data[MAX_SIZE];
int top;
};
// 函数用于初始化一个空顺序栈
void initStack(struct Stack* stack) {
stack->top = -1;
}
// 函数用于判断栈是否为空
int isEmpty(struct Stack* stack) {
return (stack->top == -1);
}
// 函数用于判断栈是否已满
int isFull(struct Stack* stack) {
return (stack->top == MAX_SIZE - 1);
}
// 函数用于入栈操作
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack overflow. Cannot push element.\n");
}
else {
stack->top++;
stack->data[stack->top] = value;
printf("Pushed element: %d\n", value);
}
}
// 函数用于出栈操作
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow. Cannot pop element.\n");
return -1;
}
else {
int popped = stack->data[stack->top];
stack->top--;
return popped;
}
}
// 函数用于取栈顶元素
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. No top element.\n");
return -1;
}
else {
return stack->data[stack->top];
}
}
// 函数用于遍历栈
void traverseStack(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. Cannot traverse.\n");
}
else {
printf("Stack elements: ");
for (int i = stack->top; i >= 0; i--) {
printf("%d ", stack->data[i]);
}
printf("\n");
}
}
int main() {
struct Stack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("Top element: %d\n", peek(&stack));
int popped = pop(&stack);
if (popped != -1) {
printf("Popped element: %d\n", popped);
}
traverseStack(&stack);
return 0;
}
图表 i 2-1
#include <stdio.h>
#include <stdlib.h>
// 定义链栈节点结构体
struct Node {
int data;
struct Node* next;
};
// 定义链栈结构体
struct Stack {
struct Node* top;
};
// 函数用于初始化一个空链栈
void initStack(struct Stack* stack) {
stack->top = NULL;
}
// 函数用于判断栈是否为空
int isEmpty(struct Stack* stack) {
return (stack->top == NULL);
}
// 函数用于入栈操作
void push(struct Stack* stack, int value) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = value;
new_node->next = stack->top;
stack->top = new_node;
printf("Pushed element: %d\n", value);
}
// 函数用于出栈操作
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow. Cannot pop element.\n");
return -1;
}
else {
struct Node* temp = stack->top;
int popped = temp->data;
stack->top = temp->next;
free(temp);
return popped;
}
}
// 函数用于取栈顶元素
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. No top element.\n");
return -1;
}
else {
return stack->top->data;
}
}
// 函数用于遍历栈
void traverseStack(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty. Cannot traverse.\n");
}
else {
struct Node* current = stack->top;
printf("Stack elements: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
}
int main() {
struct Stack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("Top element: %d\n", peek(&stack));
int popped = pop(&stack);
if (popped != -1) {
printf("Popped element: %d\n", popped);
}
traverseStack(&stack);
return 0;
}
图表 j 2-2
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义顺序队列结构体
struct Queue {
int data[MAX_SIZE];
int front;
int rear;
};
// 函数用于初始化一个空顺序队列
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
// 函数用于判断队列是否为空
int isEmpty(struct Queue* queue) {
return (queue->front == -1);
}
// 函数用于判断队列是否已满
int isFull(struct Queue* queue) {
return ((queue->rear + 1) % MAX_SIZE == queue->front);
}
// 函数用于入队操作
void enqueue(struct Queue* queue, int value) {
if (isFull(queue)) {
printf("Queue is full. Cannot enqueue element.\n");
}
else {
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->data[queue->rear] = value;
printf("Enqueued element: %d\n", value);
}
}
// 函数用于出队操作
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue element.\n");
return -1;
}
else {
int dequeued = queue->data[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
}
else {
queue->front = (queue->front + 1) % MAX_SIZE;
}
return dequeued;
}
}
// 函数用于求队列长度
int queueLength(struct Queue* queue) {
if (isEmpty(queue)) {
return 0;
}
else {
return (queue->rear - queue->front + 1 + MAX_SIZE) % MAX_SIZE;
}
}
// 函数用于遍历队列
void traverseQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot traverse.\n");
}
else {
printf("Queue elements: ");
int i = queue->front;
while (i != queue->rear) {
printf("%d ", queue->data[i]);
i = (i + 1) % MAX_SIZE;
}
printf("%d\n", queue->data[i]);
}
}
int main() {
struct Queue queue;
initQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
printf("Queue length: %d\n", queueLength(&queue));
int dequeued = dequeue(&queue);
if (dequeued != -1) {
printf("Dequeued element: %d\n", dequeued);
}
traverseQueue(&queue);
return 0;
}
图表 k 2-3
#include <stdio.h>
#include <stdlib.h>
// 定义链队列节点结构体
struct Node {
int data;
struct Node* next;
};
// 定义链队列结构体
struct Queue {
struct Node* front;
struct Node* rear;
};
// 函数用于初始化一个空链队列
void initQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}
// 函数用于判断队列是否为空
int isEmpty(struct Queue* queue) {
return (queue->front == NULL);
}
// 函数用于入队操作
void enqueue(struct Queue* queue, int value) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = value;
new_node->next = NULL;
if (isEmpty(queue)) {
queue->front = new_node;
queue->rear = new_node;
}
else {
queue->rear->next = new_node;
queue->rear = new_node;
}
printf("Enqueued element: %d\n", value);
}
// 函数用于出队操作
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue element.\n");
return -1;
}
else {
struct Node* temp = queue->front;
int dequeued = temp->data;
if (queue->front == queue->rear) {
queue->front = NULL;
queue->rear = NULL;
}
else {
queue->front = queue->front->next;
}
free(temp);
return dequeued;
}
}
// 函数用于求队列长度
int queueLength(struct Queue* queue) {
int length = 0;
struct Node* current = queue->front;
while (current != NULL) {
length++;
current = current->next;
}
return length;
}
// 函数用于遍历队列
void traverseQueue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot traverse.\n");
}
else {
struct Node* current = queue->front;
printf("Queue elements: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
}
int main() {
struct Queue queue;
initQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
printf("Queue length: %d\n", queueLength(&queue));
int dequeued = dequeue(&queue);
if (dequeued != -1) {
printf("Dequeued element: %d\n", dequeued);
}
traverseQueue(&queue);
return 0;
}
图表 l 2-4
五、实验数据记录和处理
见四。
六、实验结果与分析
七、讨论、心得
栈和队列在实现上有不同的特点，栈的操作通常比队列快，因为栈只需要操作栈顶元素，而队列需要操作队首和队尾。栈常用于递归、表达式求值、括号匹配等场景。
注意栈空和栈满情况：在进行栈操作时，要考虑栈空和栈满的情况。在尝试从空栈中弹出元素或向满栈中添加元素时，需要进行相应的处理，避免出现错误。
注意避免栈溢出：栈的大小是有限的，如果不加限制地不断入栈，可能会导致栈溢出。在编程时，要注意控制栈的大小，避免出现栈溢出的情况。
实验三 树和二叉树
一、实验目的和要求
熟悉树和二叉树（重点是二叉树）的各种表示方法和各种遍历方式，掌握有关 算法的实现，了解树在计算机科学及其它工程技术中的应用。（2学时）
二、实验内容和原理
1.建立二叉树。 2.先序遍历二叉树。 3.中序遍历二叉树。 4.后序遍历二叉树。 5.计算树的高度。 6.统计结点的个数。
[问题描述] 任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进 行遍历。
[输入] 一棵二叉树的结点若无子树，则可将其子树看作“#”，输入时，按照前序序列的 顺序输入该结点的内容。对下图，其输入序列为ABD##EH###CF#I##G##。
[输出] 若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树 不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。
[存储结构] 采用二叉链表存储。
[算法的基本思想] 采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右 子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后 访问根结点。
思考练习：
1.编写递归算法，计算二叉树中叶子结点的数目。
2. 编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。
3. 试着将上述例题用非递归程序实现。
三、主要仪器设备
笔记本电脑
四、操作方法与实验步骤
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;
void PreOrderTraverse(BiTree T) {
if (T == NULL)
return;
printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T) {
if (T == NULL)
return;
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T) {
if (T == NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
void CreateBiTree(BiTree* T) {
char ch;
scanf_s("%c", &ch);
if (ch == '#')
*T = NULL;
else {
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T)
exit(-1);
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
int Depth(BiTree T) {
if (T == NULL)
return 0;
int left_depth = Depth(T->lchild);
int right_depth = Depth(T->rchild);
return (left_depth > right_depth) ? (left_depth + 1) : (right_depth + 1);
}
int NodeCount(BiTree T) {
if (T == NULL)
return 0;
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
int main() {
BiTree T;
printf("Please input the binary tree in preorder sequence: ");
CreateBiTree(&T);
if (T == NULL) {
printf("THIS IS A EMPTY BINARY TREE\n");
}
else {
printf("\nPreorder traversal: ");
PreOrderTraverse(T);
printf("\nInorder traversal: ");
InOrderTraverse(T);
printf("\nPostorder traversal: ");
PostOrderTraverse(T);
printf("\n");
printf("Depth of the binary tree: %d\n", Depth(T));
printf("Number of nodes in the binary tree: %d\n", NodeCount(T));
}
return 0;
}
图表 m 3-1
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
int countLeafNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int leafNodeCount = countLeafNodes(root);
std::cout << "Number of leaf nodes in the binary tree: " << leafNodeCount << std::endl;
// 释放内存
delete root->left->left;
delete root->left->right;
delete root->right->left;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
图表 n 3-2
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
TreeNode* findKthNode(TreeNode* root, int& k) {
if (root == nullptr) {
return nullptr;
}
if (k == 1) {
return root;
}
TreeNode* left = findKthNode(root->left, k);
if (left != nullptr) {
return left;
}
k--;
return findKthNode(root->right, k);
}
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int k = 3; // 寻找第3个位置的结点
TreeNode* kthNode = findKthNode(root, k);
if (kthNode != nullptr) {
std::cout << "Node at position " << k << " in preorder sequence: " << kthNode->data << std::endl;
}
else {
std::cout << "Node at position " << k << " not found." << std::endl;
}
// 释放内存
delete root->left->left;
delete root->left->right;
delete root->right->left;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
图表 o 3-3
#include <iostream>
#include <stack>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
TreeNode* findKthNode(TreeNode* root, int k) {
if (root == nullptr) {
return nullptr;
}
std::stack<TreeNode*> nodeStack;
TreeNode* current = root;
int count = 0;
while (current != nullptr || !nodeStack.empty()) {
while (current != nullptr) {
nodeStack.push(current);
current = current->left;
}
current = nodeStack.top();
nodeStack.pop();
count++;
if (count == k) {
return current;
}
current = current->right;
}
return nullptr;
}
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int k = 3; // 寻找第3个位置的结点
TreeNode* kthNode = findKthNode(root, k);
if (kthNode != nullptr) {
std::cout << "Node at position " << k << " in preorder sequence: " << kthNode->data << std::endl;
}
else {
std::cout << "Node at position " << k << " not found." << std::endl;
}
// 释放内存
delete root->left->left;
delete root->left->right;
delete root->right->left;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
图表 p 3-4
五、实验数据记录和处理
见四。
六、实验结果与分析
七、讨论、心得
在树和二叉树的操作中，递归是一种常见的实现方式，如树的遍历、查找等操作可以通过递归实现。实验中，我理解了递归在树和二叉树操作中的应用，同时也尝试了迭代的实现方式，对比它们的优缺点。在某些情况下，递归和迭代的性能可能有所不同。递归的函数调用会带来额外的开销，而迭代则可以更直接地控制循环过程。递归实现简洁、易于理解，能够直接反映问题的本质结构，如树的前序、中序、后序遍历等。递归的缺点是可能导致函数调用栈溢出，尤其是在树的深度较大时，需要考虑优化递归算法，如尾递归优化。
实验四 图
一、实验目的和要求
熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技 术中的应用。（4学时）
二、实验内容和原理
[问题描述] 给定一个图，设计一个程序，找出一条从某一顶点A到另一顶点B边数最少的 一条路径。
[输入] 图的顶点个数N，图中顶点之间的关系及要找的路径的起点A和终点B。
[输出] 若A到B无路径，则输出“Thereisnopath”，否则输出A到B路径上各顶点。
[存储结构] 图采用邻接矩阵的方式存储。
[算法的基本思想] 采用广度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点 VA1,VA2,...,VAK, 访问遍之后,若没有访问 B，则继续访问与 VA1 邻接的顶点 VA11,VA12,...,VA1M，再访问与 VA2邻接顶点...，如此下去，直至找到B，最先到达B 点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访 问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不 存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶 点的前驱顶点记录下来，以便输出时回溯。
思考练习：
1. 采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。
2. 试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图 中是否存在有顶点Vi到Vj顶点的路径(i≠j)。
三、主要仪器设备
笔记本电脑
四、操作方法与实验步骤
#include<stdio.h>
int number;
typedef struct {
int q[20];
int f, r;
}queue;
int nodelist[20][20];
queue Q;
int z[20];
int a, b, n, i, j, x, y;
int finished;
void enq(queue* Q, int x) {
Q->q[Q->r] = x;
if (Q->r == 19)
Q->r = 0;
else
Q->r++;
if (Q->r == Q->f)
printf("Overflow!\n");
}
static auto front(queue* Q) {
if (Q->r == Q->f)
printf("Underflow!\n");
else
return(Q->q[Q->f]);
}
void deq(queue* Q) {
if (Q->r == Q->f)
printf("Underflow!\n");
else {
if (Q->f == 19)
Q->f = 0;
else
Q->f++;
}
}
int qempty(queue Q) {
if (Q.f == Q.r)
return 1;
else
return 0;
}
void readgraph() {
printf("\nPlease input n:");
scanf_s("%d", &n);
printf("Please input nodelist[i][j]:\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
scanf_s("%d", &nodelist[i][j]);
}
printf("\n");
printf("List-link is bulit\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++)
printf("%3d", nodelist[i][j]);
printf("\n");
}
}
void shortest(int a, int b) {
if (a == b)
nodelist[a][a] = 2;
else {
enq(&Q, a);
nodelist[a][a] = 2;
finished = 0;
while (!qempty(Q) && !finished) {
a = front(&Q);
deq(&Q);
j = 1;
while ((j <= n) && !finished) {
if ((nodelist[a][j] == 1) && (nodelist[j][j] != 2)) {
enq(&Q, j);
nodelist[j][j] = 2;
z[j] = a;
if (j == b)/*&&(nodelist[a][j]==1))*/
finished = 1;
}
if (!finished)
j++;
}
}
if (!finished) printf("There is no path.");
}
}
void writepath(int a, int b) {
i = b;
while (i != a) {
printf("%d <- ", i);
i = z[i];
}
printf("%d", a);
}
int main()
{
readgraph();
printf("Please input a:");
scanf_s("%d", &a);
printf("Please input b:");
scanf_s("%d", &b);
Q.f = 0; Q.r = 0;
shortest(a, b);
if (finished)
writepath(a, b);
}
图表 q 4-1
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
int countConnectedComponents(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, graph, visited);
count++;
}
}
return count;
}
int main() {
// 无向图的邻接表表示
vector<vector<int>> graph = {
{1, 2}, // 0与1、2相连
{0, 2}, // 1与0、2相连
{0, 1, 3}, // 2与0、1、3相连
{2, 4}, // 3与2、4相连
{3} // 4与3相连
};
int connectedComponents = countConnectedComponents(graph);
cout << "Number of connected components: " << connectedComponents << endl;
return 0;
}
图表 r 4-2
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
bool hasPath(vector<vector<int>>& graph, int start, int end, vector<bool>& visited) {
if (start == end) {
return true;
}
visited[start] = true;
for (int neighbor : graph[start]) {
if (!visited[neighbor] && hasPath(graph, neighbor, end, visited)) {
return true;
}
}
return false;
}
bool hasDirectedPath(vector<vector<int>>& graph, int start, int end) {
int n = graph.size();
vector<bool> visited(n, false);
return hasPath(graph, start, end, visited);
}
int main() {
// 有向图的邻接表表示
vector<vector<int>> graph = {
{1}, // 0指向1
{2, 3}, // 1指向2、3
{4}, // 2指向4
{5}, // 3指向5
{3}, // 4指向3
{} // 5没有出边
};
int start = 0; // 起始顶点Vi
int end = 5; // 终点顶点Vj
if (hasDirectedPath(graph, start, end)) {
cout << "There is a path from V" << start << " to V" << end << endl;
}
else {
cout << "There is no path from V" << start << " to V" << end << endl;
}
return 0;
}
图表 s 4-3
五、实验数据记录和处理
见四。
六、实验结果与分析
七、讨论、心得
深度优先搜索（DFS）实现方式：
1.递归实现：
在递归实现中，我们可以定义一个递归函数来进行深度优先搜索。从起始节点开始，递归地访问其相邻节点，并标记已访问过的节点，直到遍历完所有节点或达到终止条件。递归实现简洁直观，但可能会导致栈溢出问题。
2.栈实现：
使用栈来模拟递归的过程，将起始节点入栈，然后循环弹出栈顶节点，访问其相邻节点并入栈，直到栈为空。栈实现避免了递归调用带来的栈溢出问题，适用于大规模数据和深度较大的图或树。
广度优先搜索（BFS）实现方式：
队列实现：
使用队列来实现广度优先搜索，将起始节点入队，然后循环出队队首节点，访问其相邻节点并入队，直到队列为空。广度优先搜索按层级遍历节点，适用于寻找最短路径、拓扑排序等场景。
实验五 查找和排序
一、实验目的和要求
通过本次实验，掌握查找表上的有关查找方法，掌握线性表的排序方法，并分 析时间复杂度。（4学时）
二、实验内容和原理
查找：[问题描述] 将折半查找算法写成完整的程序，并上机通过。
[输入] 有序表（12,23,28,35,37,39,50,60,78,90）及待查找记录 23,58。
[输出] 记录不存在。
[存储结构] 输入23，表中存在待查找记录，则显示该记录在表中位置2，输入58显示该 有序表采用顺序方式存储。
[算法的基本思想] 首先用待查找记录与查找区间中间位置记录比较，若相等则查找成功，返回该 记录在表中的位置数，若小于中间位置记录，则修改区间上界为中间位置减 1，若 大于中间位置记录，则修改区间下界为中间位置加 1，在新的区间内继续查找。当 查找区间下界大于上界，则该记录不存在。
排序：[问题描述] 将快速排序算法写成完整的程序上机通过，并统计递归深度。
[输入] 待排序记录个数n，各待排序记录值。
[输出] n个记录由小到大排列的结果。
[存储结构] 待排序记录顺序存储。
[算法的基本思想] 快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组，将所有关键字小于或等于标准的记录都放在它的位置之前，将所有关键字大于标准的记录都放在它的位置之后。对这两组再进行快速排序，直到完全有序。每递归1次，递归深度加1。
加强练习：
1.给定关键字序列{23,11,32,55,90,78,5,8,66,88}，请用下列方法进行排序。 （1）冒泡排序。 （2）简单选择排序。
2.设计一个用链表表示的直接选择排序算法，并用程序实现。 算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已排序序 列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后面，让r指向 这个结点。反复执行这个过程，直到排好序。
3．对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排 在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为 O(N)
三、主要仪器设备
笔记本电脑
四、操作方法与实验步骤
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
int main() {
vector<int> arr = { 12, 23, 28, 35, 37, 39, 50, 60, 78, 90 };
int target1 = 23;
int target2 = 58;
int index1 = binarySearch(arr, target1);
int index2 = binarySearch(arr, target2);
if (index1 != -1) {
cout << "记录存在，位置为: " << index1 + 1 << endl;
}
else {
cout << "记录不存在" << endl;
}
if (index2 != -1) {
cout << "记录存在，位置为: " << index2 + 1 << endl;
}
else {
cout << "记录不存在" << endl;
}
return 0;
}
图表 t 5-1
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& arr, int low, int high, int& depth) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high, int& depth) {
if (low < high) {
int pi = partition(arr, low, high, depth);
depth++; // 递归深度加1
quickSort(arr, low, pi - 1, depth);
quickSort(arr, pi + 1, high, depth);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int depth = 0;
quickSort(arr, 0, n - 1, depth);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "Recursion depth: " << depth << endl;
return 0;
}
图表 u 5-2
五、实验数据记录和处理
见四。
六、实验结果与分析
七、讨论、心得
冒泡排序是一种简单直观的排序算法，通过不断交换相邻元素将最大（或最小）元素冒泡到顶端。其时间复杂度为O(n^2)。
快速排序是一种高效的排序算法，通过分治和递归的方式将数组分割成较小的子数组进行排序。其平均时间复杂度为O(n log n)。
标签：node,queue,struct,int,太原理工,计科,printf,实验报告,data From： https://blog.csdn.net/m0_74626628/article/details/140289108