数据结构0X-线性结构-链表栈队列

**数据结构0X - 线性结构 - 链表、栈、队列**

在计算机科学中，数据结构是指组织和存储数据的方式。线性结构是一种最基本的数据结构，它将元素按顺序排列起来。在本文中，我们将讨论链表、栈和队列这三个重要的线性结构。

### 链表链表是一种特殊的线性结构，每个元素都有一个指向下一个元素的引用（或称为“后继者”）。这种结构允许快速插入或删除元素，而不需要移动其他元素。

#### 链表的定义

ctypedef struct Node {
 int data;
 struct Node* next; // 指向下一个元素的指针} Node;

#### 链表的操作链表支持以下基本操作：

* **插入**:在链表中插入新元素。
* **删除**:从链表中删除指定元素。
* **查找**:在链表中找到指定元素。

####例子：单向链表

c#include <stdio.h>
#include <stdlib.h>

// 链表结点结构体定义typedef struct Node {
 int data;
 struct Node* next; // 指向下一个元素的指针} Node;

// 创建新结点函数Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 if (!newNode) {
 printf("Memory error
");
 return NULL;
 }
 newNode->data = data;
 newNode->next = NULL; // 新结点的下一个元素为NULL return newNode;
}

// 链表插入函数void insertNode(Node** head, int data) {
 Node* newNode = createNode(data);
 if (*head == NULL) { // 如果链表为空，直接将新结点作为头结点 *head = newNode;
 return;
 }
 Node* current = *head; // 遍历链表找到最后一个元素 while (current->next != NULL) {
 current = current->next;
 }
 current->next = newNode; // 将新结点作为最后一个元素的下一个元素}

// 链表删除函数void deleteNode(Node** head, int data) {
 if (*head == NULL) return; // 如果链表为空，直接返回 Node* current = *head;
 if (current->data == data) { // 如果头结点的值等于要删除的值，则将下一个元素作为新头结点 *head = current->next;
 free(current);
 return;
 }

 while (current->next != NULL) {
 if (current->next->data == data) { // 找到要删除的元素 Node* temp = current->next; // 将要删除的元素暂存 current->next = current->next->next; // 将下一个元素作为当前元素的下一个元素 free(temp); //释放要删除的元素的内存 return;
 }
 current = current->next;
 }
}

// 链表打印函数void printList(Node* head) {
 Node* current = head;
 while (current != NULL) {
 printf("%d ", current->data);
 current = current->next;
 }
 printf("
");
}

### 栈栈是一种特殊的线性结构，它遵循后进先出的原则（LIFO）。这意味着最后添加的元素将首先被移除。

#### 栈的定义

ctypedef struct Stack {
 int* data;
 int top; // 栈顶指针 int capacity; // 栈容量} Stack;

#### 栈的操作栈支持以下基本操作：

* **push**:将元素添加到栈顶。
* **pop**:从栈顶移除元素。
* **peek**:查看栈顶元素。

####例子：链式栈

c#include <stdio.h>
#include <stdlib.h>

// 栈结点结构体定义typedef struct Node {
 int data;
 struct Node* next; // 指向下一个元素的指针} Node;

// 创建新结点函数Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 if (!newNode) {
 printf("Memory error
");
 return NULL;
 }
 newNode->data = data;
 newNode->next = NULL; // 新结点的下一个元素为NULL return newNode;
}

// 栈创建函数Stack* createStack(int capacity) {
 Stack* stack = (Stack*)malloc(sizeof(Stack));
 if (!stack) {
 printf("Memory error
");
 return NULL;
 }
 stack->data = (int*)malloc(capacity * sizeof(int));
 if (!stack->data) {
 free(stack);
 printf("Memory error
");
 return NULL;
 }
 stack->top = -1; // 初始栈顶指针为-1 stack->capacity = capacity;
 return stack;
}

// 栈添加元素函数void push(Stack* stack, int data) {
 if (stack->top == stack->capacity -1) { // 如果栈已满，则扩容 stack->data = (int*)realloc(stack->data,2 * stack->capacity * sizeof(int));
 stack->capacity *=2;
 }
 stack->data[++stack->top] = data; // 将元素添加到栈顶}

// 栈移除元素函数void pop(Stack* stack) {
 if (stack->top == -1) return; // 如果栈为空，则直接返回 free(stack->data + stack->top); //释放栈顶元素的内存 stack->top--; // 将栈顶指针减一}

// 栈查看元素函数int peek(Stack* stack) {
 if (stack->top == -1) return -1; // 如果栈为空，则返回-1 return stack->data[stack->top]; // 返回栈顶元素的值}

### 队列队列是一种特殊的线性结构，它遵循先进先出的原则（FIFO）。这意味着第一个添加的元素将首先被移除。

#### 队列的定义

ctypedef struct Queue {
 int* data;
 int front; // 队头指针 int rear; // 队尾指针 int capacity; // 队容量} Queue;

#### 队列的操作队列支持以下基本操作：

* **enqueue**:将元素添加到队尾。
* **dequeue**:从队头移除元素。
* **peek**:查看队头元素。

####例子：链式队列

c#include <stdio.h>
#include <stdlib.h>

// 队列结点结构体定义typedef struct Node {
 int data;
 struct Node* next; // 指向下一个元素的指针} Node;

// 创建新结点函数Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 if (!newNode) {
 printf("Memory error
");
 return NULL;
 }
 newNode->data = data;
 newNode->next = NULL; // 新结点的下一个元素为NULL return newNode;
}

// 队列创建函数Queue* createQueue(int capacity) {
 Queue* queue = (Queue*)malloc(sizeof(Queue));
 if (!queue) {
 printf("Memory error
");
 return NULL;
 }
 queue->data = (int*)malloc(capacity * sizeof(int));
 if (!queue->data) {
 free(queue);
 printf("Memory error
");
 return NULL;
 }
 queue->front =0; // 初始队头指针为0 queue->rear = -1; // 初始队尾指针为-1 queue->capacity = capacity;
 return queue;
}

// 队列添加元素函数void enqueue(Queue* queue, int data) {
 if (queue->rear == queue->capacity -1) { // 如果队列已满，则扩容 queue->data = (int*)realloc(queue->data,2 * queue->capacity * sizeof(int));
 queue->capacity *=2;
 }
 queue->data[++queue->rear] = data; // 将元素添加到队尾}

// 队列移除元素函数void dequeue(Queue* queue) {
 if (queue->front == -1 && queue->rear == -1) return; // 如果队列为空，则直接返回 free(queue->data + queue->front); //释放队头元素的内存 queue->front++; // 将队头指针加一}

// 队列查看元素函数int peek(Queue* queue) {
 if (queue->front == -1 && queue->rear == -1)