c++链表实现（c++链表实现队列）

链表是一种常用的数据结构，它由一系列节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。链表的特点是可以动态地添加和删除节点，而且可以方便地遍历和访问节点。在C语言中，我们可以通过指针来实现链表。

多级标题：

一、简介

二、链表的定义与节点结构

三、链表的基本操作

3.1 创建链表

3.2 在链表中插入节点

3.3 在链表中删除节点

3.4 遍历链表

3.5 查找链表中的节点

四、示例代码

五、总结

内容详细说明：

一、简介

在计算机科学中，链表是一种常用的数据结构，它由一系列节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。链表的特点是可以动态地添加和删除节点，而且可以方便地遍历和访问节点。在C语言中，我们可以通过指针来实现链表。

二、链表的定义与节点结构

链表由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。下面是链表节点的定义：

```c

typedef struct Node {

int data; // 数据元素

struct Node* next; // 指向下一个节点的指针

} Node;

```

在上述定义中，我们使用了一个结构体表示链表的节点，并给结构体取名为Node。其中，data表示数据元素，next表示指向下一个节点的指针。

三、链表的基本操作

链表的基本操作包括创建链表、在链表中插入节点、在链表中删除节点、遍历链表和查找链表中的节点。

3.1 创建链表

创建链表需要首先构造一个头节点，并将头节点的指针指向NULL表示链表为空。

```c

Node* createList() {

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

head->next = NULL;

return head;

```

在上述代码中，我们使用malloc函数动态分配了一个头节点，并将其指针指向NULL。

3.2 在链表中插入节点

在链表中插入节点需要找到插入位置，并调整指针指向。

```c

void insertNode(Node* head, int value) {

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

newNode->data = value;

newNode->next = NULL;

Node* cur = head;

while (cur->next != NULL) {

cur = cur->next;

}

cur->next = newNode;

```

在上述代码中，我们首先创建一个新的节点，并将其数据元素设置为插入值，然后找到链表的末尾，并将新节点插入到末尾节点的后面。

3.3 在链表中删除节点

在链表中删除节点需要找到待删除节点的前一个节点，然后调整指针指向。

```c

void deleteNode(Node* head, int value) {

Node* cur = head;

while (cur->next != NULL && cur->next->data != value) {

cur = cur->next;

}

if (cur->next != NULL) {

Node* temp = cur->next;

cur->next = cur->next->next;

free(temp);

}

```

在上述代码中，我们首先找到待删除节点的前一个节点，然后将其指针指向待删除节点的后一个节点，并释放待删除节点的内存。

3.4 遍历链表

遍历链表即访问链表中的每个节点并输出数据元素。

```c

void traverseList(Node* head) {

Node* cur = head->next;

while (cur != NULL) {

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

cur = cur->next;

}

printf("\n");

```

在上述代码中，我们使用一个指针cur来遍历链表中的每个节点，并输出其数据元素。

3.5 查找链表中的节点

查找链表中的节点需要遍历链表并逐个比较数据元素。

```c

Node* findNode(Node* head, int value) {

Node* cur = head->next;

while (cur != NULL && cur->data != value) {

cur = cur->next;

}

return cur;

```

在上述代码中，我们使用一个指针cur来遍历链表中的每个节点，并判断是否与待查找的值相等。

四、示例代码

下面是一个使用链表实现的简单示例代码：

```c

#include

#include

typedef struct Node {

int data;

struct Node* next;

} Node;

Node* createList() {

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

head->next = NULL;

return head;

void insertNode(Node* head, int value) {

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

newNode->data = value;

newNode->next = NULL;

Node* cur = head;

while (cur->next != NULL) {

cur = cur->next;

}

cur->next = newNode;

void deleteNode(Node* head, int value) {

Node* cur = head;

while (cur->next != NULL && cur->next->data != value) {

cur = cur->next;

}

if (cur->next != NULL) {

Node* temp = cur->next;

cur->next = cur->next->next;

free(temp);

}

void traverseList(Node* head) {

Node* cur = head->next;

while (cur != NULL) {

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

cur = cur->next;

}

printf("\n");

Node* findNode(Node* head, int value) {

Node* cur = head->next;

while (cur != NULL && cur->data != value) {

cur = cur->next;

}

return cur;

int main() {

Node* list = createList();

insertNode(list, 1);

insertNode(list, 2);

insertNode(list, 3);

printf("Original list: ");

traverseList(list);

deleteNode(list, 2);

printf("Updated list: ");

traverseList(list);

Node* foundNode = findNode(list, 3);

if (foundNode != NULL) {

printf("Found node: %d\n", foundNode->data);

} else {

printf("Node not found.\n");

}

return 0;

```

以上示例代码演示了链表的创建、插入、删除、遍历和查找操作。

五、总结

链表是一种常用的数据结构，可以动态地添加和删除节点，并方便地遍历和访问节点。在C语言中，我们可以使用指针来实现链表。通过本文的介绍，你应该对链表在C语言中的实现有了一定的了解。