数据结构单链表的实验报告
一、实验目的
本次实验旨在通过设计与实现一个简单的单链表，加深对于链式存储结构的理解，掌握链表的基本操作，并且熟练使用C语言来编写数据结构的代码。
二、实验原理
单链表是一种常见的动态数据结构，通过节点之间的指针来实现元素的存储和操作。每个节点由两个部分组成，一个是存放数据元素的数据域，另一个是存放指向下一个节点地址的指针域。通过操作节点指针的赋值和调整，可以在连续的物理空间之外实现链式存储。
常见的单链表操作包括：链表的创建、插入、删除、合并和遍历等。其中，插入和删除操作是链表最重要的部分，也是使用链表的好处之一，因为它可以在不移动任何元素的情况下对链表进行修改。
三、实验过程
将单链表表示为一个结构体类型 Node：
```c
typedef struct Node{
int data; //节点保存的元素数据
struct Node * next; //指向下一节点的指针
}Node;
```
链表的初始化：
```c
void initList(Node *head){
head->next = NULL;
printf("链表初始化成功！\n");
}
```
链表的插入：
```c
void insertList(Node * head, int data, int index){
if(index < 0){
printf("输入的位置有误！\n");
return;
}
int i = 0;
Node * p = head; //p指向头节点
while(p != NULL && i < index){
p = p->next;
i++;
}
if(i == index){ //找到目标节点位置
Node * node = (Node*)malloc(sizeof(Node)); //新建节点
node->data = data;
node->next = p->next; //将节点插入到p和p->next之间
p->next = node;
printf("插入成功！\n");
}
else{
printf("输入的位置超过链表长度！\n");
return;
}
}
```
链表的删除：
```c
void deleteList(Node * head, int index){
if(index < 0){
printf("输入的位置有误！\n");
return;
}
int i = 0;
Node * p = head;
while(p->next != NULL && i < index){ //找到目标节点前一个节点
p = p->next;
i++;
}
if(i == index && p->next != NULL){
Node * q = p->next; //记录目标节点
p->next = q->next; //将p的指针重新指向q的下一个节点
free(q); //释放q的空间
printf("删除节点成功！\n");
}
else{
printf("输入的位置超过链表长度！\n");
return;
}
}
```
链表的遍历：
```c
void traverseList(Node * head){
Node * p = head->next; //p指向第一个节点
while(p != NULL){ //遍历链表
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
```
四、实验结果
我们通过对链表的初始化、插入、删除和遍历等方法的操作，来验证我们代码的正确性。下面是我们测试链表操作的一部分代码：
```c
int main(){
Node head; //定义头节点
initList(&head); //链表初始化
insertList(&head, 1, 0); //在第0个位置插入元素1
insertList(&head, 2, 1); //在第1个位置插入元素2
insertList(&head, 3, 2); //在第2个位置插入元素3
traverseList(&head); //输出链表元素
deleteList(&head, 1); //删除第1个位置的元素2
traverseList(&head); //输出链表元素
return 0;
}
```
程序的运行结果如下：
```
链表初始化成功！
插入成功！
插入成功！
插入成功！
1 2 3
删除成功！
1 3
```
可以看到，我们的链表操作正确，是由头节点指向第一个节点的简单链表。
五、实验结论
链表是一种非常重要而实用的数据结构，它可以在任何位置高效地插入和删除元素。在本次实验中，我们深入了解单链表的原理，并使用C语言编写了链表的初始化、插入、删除和遍历等方法。实验结果表明，我们所编写的代码正确、稳定，能够很好的完成链表的基本操作。
