石 家 庄 铁 道 大 学
实 验 报 告
课程名称： 数据结构与算法设计 任课教师： 刘 丹 实验日期： 2024.12.11
班 级： 信2305-3 姓 名： 徐戌 学 号： 20234316
实验项目名称：实验一
一、 实验目的
掌握顺序表的基本操作。
掌握单链表的基本操作。
掌握循环链表的基本操作。
二、 实验内容
三、 设计文档
四、 源程序
链表逆置：
include <stdio.h>
include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode createlist(); /裁判实现，细节不表*/
struct ListNode *reverse( struct ListNode *head );
void printlist( struct ListNode *head )
{
struct ListNode *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *head;
head = createlist();
head = reverse(head);
printlist(head);
return 0;
}
struct ListNode* reverse(struct ListNode* head)
{
struct ListNode* q = head, * t, * p = NULL;
while (q)
{
t = q->next;
q->next = p;
p = q; 9
q = t;
}
return p; }
7-1 线性表A，B顺序存储合并
include <stdio.h>
include <stdlib.h>
void mergeAndRemoveDuplicates(int *A, int lenA, int *B, int lenB) {
int *C = (int *)malloc((lenA + lenB) * sizeof(int)); // 合并后的数组
int i = lenA - 1, j = lenB - 1, k = 0; // i, j分别为A和B的指针，k为C的指针
// 合并A和B到C，C要保持非递减顺序
while (i >= 0 && j >= 0) {
if (A[i] < B[j]) {
C[k++] = A[i--];
} else {
C[k++] = B[j--];
}
}
// 如果A还有剩余元素
while (i >= 0) {
C[k++] = A[i--];
}
// 如果B还有剩余元素
while (j >= 0) {
C[k++] = B[j--];
}
// 去重：将去重后的元素存回C，并打印结果
int last = C[0];
printf("%d", last); // 第一个元素先输出
for (int i = 1; i < k; i++) {
if (C[i] != last) {
printf(",%d", C[i]);
last = C[i];
}
}
free(C); // 释放内存
}
int main() {
int A[100], B[100];
int lenA = 0, lenB = 0;
// 输入表A
while (1) {
scanf("%d", &A[lenA]);
if (A[lenA] == -1) break;
lenA++;
}
// 输入表B
while (1) {
scanf("%d", &B[lenB]);
if (B[lenB] == -1) break;
lenB++;
}
mergeAndRemoveDuplicates(A, lenA, B, lenB);
return 0;
}
7-2 双向循环链表应用
include <stdio.h>
include <stdlib.h>
// 双向循环链表结点结构
typedef struct Node {
int data;
struct Node* prior; // 指向前驱节点
struct Node* next; // 指向后继节点
} Node;
// 创建一个新的结点
Node* create_node(int data) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->prior = new_node->next = new_node; // 初始化为自己指向自己（循环链表）
return new_node;
}
// 创建双向循环链表
Node* create_list(int arr[], int n) {
if (n == 0) return NULL;
Node* head = create_node(arr[0]);
Node* tail = head;
for (int i = 1; i < n; i++) {
Node* new_node = create_node(arr[i]);
tail->next = new_node;
new_node->prior = tail;
tail = new_node;
}
// 最后一个节点的next指向头结点，头结点的prior指向最后一个节点
tail->next = head;
head->prior = tail;
return head;
}
// 在双向循环链表中查找指定值的结点
Node* find_node(Node* head, int value) {
Node* current = head;
if (head == NULL) return NULL;
do {
if (current->data == value) return current;
current = current->next;
} while (current != head);
return NULL;
}
// 交换p指向结点和它的前驱结点
void swap_nodes(Node* p) {
if (p == NULL || p->prior == p) return; // 如果p是链表的头结点或链表只有一个结点，无法交换
Node* prev = p->prior;
Node* next = p->next;
// 调整前驱节点的next和p的prior指向
prev->next = p->next;
p->prior = prev->prior;
// 调整p的next和后继节点的prior指向
p->next = prev;
prev->prior = p;
// 如果p是链表的头结点，需要更新头结点的prior指向p
if (p->prior != NULL) {
p->prior->next = p;
}
if (next != NULL) {
next->prior = prev;
}
}
// 输出链表
void print_list(Node* head) {
if (head == NULL) return;
Node* current = head;
do {
printf("%d", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
int main() {
int N;
scanf("%d", &N);
if (N <= 0) {
printf("error\n");
return 0;
}
int arr[N];
for (int i = 0; i < N; i++) {
if (scanf("%d", &arr[i]) != 1) {
printf("error\n");
return 0;
}
}
int value_to_swap;
scanf("%d", &value_to_swap);
// 创建双向循环链表
Node* head = create_list(arr, N);
// 查找目标结点
Node* p = find_node(head, value_to_swap);
if (p == NULL) {
printf("未找到%d\n", value_to_swap);
} else {
// 交换p与它的前驱结点
swap_nodes(p);
// 输出修改后的链表
print_list(head);
}
return 0;
}
7-3 修改数组（蓝桥杯）
include <stdio.h>
include <stdlib.h>
define MAX_VAL 1000000
// 使用一个简单的哈希表来检查是否有重复的元素
typedef struct HashSet {
int *data;
} HashSet;
// 创建一个哈希表
HashSet* create_hashset(int size) {
HashSet* set = (HashSet)malloc(sizeof(HashSet));
set->data = (int)calloc(size, sizeof(int)); // 使用 calloc 初始化为 0
return set;
}
// 向哈希表中插入一个元素
void insert(HashSet* set, int value) {
set->data[value] = 1;
}
// 检查哈希表中是否存在该元素
int contains(HashSet* set, int value) {
return set->data[value] == 1;
}
// 释放哈希表的内存
void free_hashset(HashSet* set) {
free(set->data);
free(set);
}
int main() {
int N;
// 输入 N
if (scanf("%d", &N) != 1 || N < 1 || N > 100000) {
printf("error\n");
return 0;
}
int A[N];
// 输入数组 A
for (int i = 0; i < N; i++) {
if (scanf("%d", &A[i]) != 1 || A[i] < 1 || A[i] > 1000000) {
printf("error\n");
return 0;
}
}
HashSet* set = create_hashset(MAX_VAL + 1); // 创建哈希表
for (int i = 0; i < N; i++) {
while (contains(set, A[i])) { // 如果当前值已经存在
A[i]++; // 增加该元素的值
}
insert(set, A[i]); // 将当前修改后的元素插入哈希表
}
// 输出最终的数组
for (int i = 0; i < N; i++) {
printf("%d ", A[i]);
}
printf("\n");
// 释放哈希表
free_hashset(set);
return 0;
}
五、 个人体会
链表逆置是一个常见的数据结构操作，通常用于改变链表中节点的顺序。在实现链表逆置的过程中，我遇到一些问题，比如说链表的头节点弄错了位置应该是从尾到头，而我刚开始设计实验的时候是从到尾以至于我刚开始不会做，我采取了一些列措施比如说循环倒序，使得数字能够从小到大排序。还有就是链表储存问题：内存分配失败，在扩容过程中，内存不足，导致内存分配失败。解决方案：在尝试分配新内存之前，先检查系统是否有足够的可用内存。如果内存不足，可以尝试释放一些不再使用的内存，或者抛出异常并处理。
实验感想：通过这次链表实验，我对链表这一数据结构有了更深入的理解。实验中，我实现了链表的基本操作，如插入、删除、查找和逆置等，这不仅巩固了理论知识，还提高了实际编程能力。特别是在调试过程中，我遇到了指针错误和内存泄漏等问题，通过逐步排查和修复，我学会了如何更有效地解决问题。此外，实验还让我认识到数据结构选择的重要性，不同的应用场景需要不同的数据结构来优化性能。总体来说，这次实验不仅提升了我的编程技能，也增强了我对算法和数据结构的兴趣和信心。