一、数据结构-链表介绍

链表：在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由一系列节点（链表中每一个元素称为节点/结点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

链表可以分为单向链表和双向链表两种形式。在单向链表中，每个节点只保存指向下一个节点的指针，而在双向链表中，每个节点同时保存指向上一个节点和下一个节点的指针。

二、链表操作

插入：在链表的任意位置插入一个节点；删除：从链表中删除一个节点；查找：在链表中查找指定的数据；修改：修改链表中节点的数据；遍历：按照顺序依次访问链表中的每个节点。

三、创建和释放

1. 创建节点

<code>// 创建一个新节点

Node* createNode(ElemType data)

{

Node* newNode = (Node*)malloc(sizeof(Node));

if(newNode != NULL)

{

newNode -> data = data; // 设置数据

newNode -> next = NULL; // 新节点的下一个节点为空

}

return newNode;

}

2. 创建空链表

// 创建一个空链表

linkedList* createLinkedList()

{

linkedList* list = (linkedList*)malloc(sizeof(linkedList));

if(list != NULL)

{

list -> head = NULL; // 头指针为空

list -> length = 0; // 链表长度为0

}

return list;

}

3. 释放空间

// 释放链表的内存

void freeLinkedList(linkedList* list)

{

if(list == NULL)

return;

Node* current = list -> head;

while(current != NULL)

{

Node* temp = current;

current = current -> next;

free(temp); // 释放节点内存

}

free(list); // 释放链表内存

}

四、链表操作各部分代码实现

1. 插入

// 在链表的指定位置插入节点

void insertNode(linkedList* list, int pos, ElemType data)

{

if(list == NULL || pos < 0 || pos > list -> length)

return;

Node* newNode = createNode(data); // 创建新节点

if(newNode == NULL)

return;

if(pos == 0)

{

newNode -> next = list -> head; // 将新节点插入到链表头部

list -> head = newNode; // 更新头指针

}

else

{

Node* current = list -> head;

for(int i =0; i < pos - 1; i++) // 找到插入位置的前一个节点

{

current = current -> next;

}

newNode -> next = current -> next; // 新节点指向原来位置的节点

current -> next = newNode; // 前一个节点指向新节点

}

list -> length ++; // 链表长度加 1

}

2. 删除

// 删除链表的指定位置的节点

void deleteNode(linkedList* list, int pos)

{

if(list == NULL || pos < 0 || pos >= list -> length)

return;

Node* temp;

if(pos == 0)

{

temp = list -> head; // 保存头节点

list -> head = list -> head -> next; // 更新头指针

}

else

{

Node* current = list -> head;

for(int i = 0; i < pos - 1; i++) // 找到要删除节点的前一个节点

{

current = current -> next;

}

temp = current -> next; // 保存要删除的节点

current -> next = temp -> next; // 前一个节点指向要删除节点的下一个节点

}

free(temp); // 释放节点内存

list -> length--; // 链表长度减1

}

3. 修改

// 查找链表中指定数据的位置

int findNode(linkedList* list, ElemType data)

{

if(list == NULL)

return -1;

Node* current = list -> head;

int pos = 0;

while(current != NULL) // 遍历链表

{

if(current -> data == data) // 找到数据相同的节点

return pos;

current = current -> next;

pos++;

}

return -1; // 数据不存在

}

4. 查找

// 查找链表中指定数据的位置

int findNode(linkedList* list, ElemType data)

{

if(list == NULL)

return -1;

Node* current = list -> head;

int pos = 0;

while(current != NULL) // 遍历链表

{

if(current -> data == data) // 找到数据相同的节点

return pos;

current = current -> next;

pos++;

}

return -1; // 数据不存在

}

5. 遍历

// 遍历，打印链表的所有节点数据

void printLinkedList(linkedList* list)

{

if(list == NULL)

return;

Node* current = list -> head;

while(current != NULL)

{

printf("%d ",current -> data);

current = current -> next;

}

printf("\n");

}

五、完整代码

#include <stdio.h>

#include <stdlib.h>

typedef int ElemType;

// 定义链表节点

typedef struct Node{

ElemType data;

struct Node* next;

}Node;

// 定义链表结构

typedef struct{

Node* head; // 头指针

int length; // 链表长度

}linkedList;

// 创建一个新节点

Node* createNode(ElemType data)

{

Node* newNode = (Node*)malloc(sizeof(Node));

if(newNode != NULL)

{

newNode -> data = data; // 设置数据

newNode -> next = NULL; // 新节点的下一个节点为空

}

return newNode;

}

// 创建一个空链表

linkedList* createLinkedList()

{

linkedList* list = (linkedList*)malloc(sizeof(linkedList));

if(list != NULL)

{

list -> head = NULL; // 头指针为空

list -> length = 0; // 链表长度为0

}

return list;

}

// 在链表的指定位置插入节点

void insertNode(linkedList* list, int pos, ElemType data)

{

if(list == NULL || pos < 0 || pos > list -> length)

return;

Node* newNode = createNode(data); // 创建新节点

if(newNode == NULL)

return;

if(pos == 0)

{

newNode -> next = list -> head; // 将新节点插入到链表头部

list -> head = newNode; // 更新头指针

}

else

{

Node* current = list -> head;

for(int i =0; i < pos - 1; i++) // 找到插入位置的前一个节点

{

current = current -> next;

}

newNode -> next = current -> next; // 新节点指向原来位置的节点

current -> next = newNode; // 前一个节点指向新节点

}

list -> length ++; // 链表长度加 1

}

// 删除链表的指定位置的节点

void deleteNode(linkedList* list, int pos)

{

if(list == NULL || pos < 0 || pos >= list -> length)

return;

Node* temp;

if(pos == 0)

{

temp = list -> head; // 保存头节点

list -> head = list -> head -> next; // 更新头指针

}

else

{

Node* current = list -> head;

for(int i = 0; i < pos - 1; i++) // 找到要删除节点的前一个节点

{

current = current -> next;

}

temp = current -> next; // 保存要删除的节点

current -> next = temp -> next; // 前一个节点指向要删除节点的下一个节点

}

free(temp); // 释放节点内存

list -> length--; // 链表长度减1

}

// 更新链表的指定位置的节点数据

void updateNode(linkedList* list, int pos, ElemType data)

{

if(list == NULL || pos < 0 || pos >= list -> length)

return;

Node* current = list -> head;

for(int i = 0; i < pos; i++) // 找到要更新的节点

{

current = current -> next;

}

current -> data = data; // 更新节点数据

}

// 查找链表中指定数据的位置

int findNode(linkedList* list, ElemType data)

{

if(list == NULL)

return -1;

Node* current = list -> head;

int pos = 0;

while(current != NULL) // 遍历链表

{

if(current -> data == data) // 找到数据相同的节点

return pos;

current = current -> next;

pos++;

}

return -1; // 数据不存在

}

// 遍历，打印链表的所有节点数据

void printLinkedList(linkedList* list)

{

if(list == NULL)

return;

Node* current = list -> head;

while(current != NULL)

{

printf("%d ",current -> data);

current = current -> next;

}

printf("\n");

}

// 释放链表的内存

void freeLinkedList(linkedList* list)

{

if(list == NULL)

return;

Node* current = list -> head;

while(current != NULL)

{

Node* temp = current;

current = current -> next;

free(temp); // 释放节点内存

}

free(list); // 释放链表内存

}

int main()

{

linkedList* list = createLinkedList(); // 创建一个链表

insertNode(list, 0, 10);

insertNode(list, 1, 20);

insertNode(list, 2, 30);

printLinkedList(list);

updateNode(list, 1, 25);

printLinkedList(list);

deleteNode(list, 2);

printLinkedList(list);

int pos = findNode(list, 30);

printf("pos = %d\n", pos);

freeLinkedList(list);

return 0;

}