数据结构单链表的实验报告

一、实验目的

本次实验旨在通过设计与实现一个简单的单链表，加深对于链式存储结构的理解，掌握链表的基本操作，并且熟练使用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语言编写了链表的初始化、插入、删除和遍历等方法。实验结果表明，我们所编写的代码正确、稳定，能够很好的完成链表的基本操作。