如何在C语言中实现链表、栈和队列等数据结构?
在C语言中实现链表、栈和队列等数据结构需要定义相关的数据结构和操作。下面我会给出每种数据结构的简单实现示例。
- 链表(LinkedList)
链表是由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。
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\n"); |
|
return NULL; |
|
} |
|
newNode->data = data; |
|
newNode->next = NULL; |
|
return newNode; |
|
} |
|
// 在链表末尾添加节点 |
|
void appendNode(Node** head, int data) { |
|
Node* newNode = createNode(data); |
|
if (!*head) { |
|
*head = newNode; |
|
return; |
|
} |
|
Node* temp = *head; |
|
while (temp->next) { |
|
temp = temp->next; |
|
} |
|
temp->next = newNode; |
|
} |
|
// 打印链表 |
|
void printList(Node* head) { |
|
Node* temp = head; |
|
while (temp) { |
|
printf("%d ", temp->data); |
|
temp = temp->next; |
|
} |
|
printf("\n"); |
|
} |
|
int main() { |
|
Node* head = NULL; |
|
appendNode(&head, 1); |
|
appendNode(&head, 2); |
|
appendNode(&head, 3); |
|
printList(head); |
|
return 0; |
|
} |
- 栈(Stack)
栈是一种后进先出(LIFO)的数据结构。
c复制代码
#include <stdio.h> |
|
#include <stdlib.h> |
|
#define MAX_STACK_SIZE 100 |
|
typedef struct Stack { |
|
int top; |
|
unsigned capacity; |
|
int* array; |
|
} Stack; |
|
Stack* createStack(unsigned capacity) { |
|
Stack* stack = (Stack*)malloc(sizeof(Stack)); |
|
if (!stack) { |
|
printf("Memory error\n"); |
|
return NULL; |
|
} |
|
stack->top = -1; |
|
stack->capacity = capacity; |
|
stack->array = (int*)malloc(stack->capacity * sizeof(int)); |
|
if (!stack->array) { |
|
printf("Memory error\n"); |
|
return NULL; |
|
} |
|
return stack; |
|
} |
|
int isFull(Stack* stack) { |
|
return stack->top == stack->capacity - 1; |
|
} |
|
int isEmpty(Stack* stack) { |
|
return stack->top == -1; |
|
} |
|
void push(Stack* stack, int item) { |
|
if (isFull(stack)) { |
|
printf("Stack is full\n"); |
|
return; |
|
} |
|
stack->array[++stack->top] = item; |
|
} |
|
int pop(Stack* stack) { |
|
if (isEmpty(stack)) { |
|
printf("Stack is empty\n"); |
|
return INT_MIN; |
|
} |
|
return stack->array[stack->top--]; |
|
} |
|
int main() { |
|
Stack* stack = createStack(MAX_STACK_SIZE); |
|
push(stack, 1); |
|
push(stack, 2); |
|
push(stack, 3); |
|
printf("%d\n", pop(stack)); |
|
printf("%d\n", pop(stack)); |
|
return 0; |
|
} |
- 队列(Queue)
队列是一种先进先出(FIFO)的数据结构。
c复制代码
#include <stdio.h> |
|
#include <stdlib.h> |
|
#define MAX_QUEUE_SIZE 100 |
|
typedef struct Queue { |
|
int front, rear; |
|
unsigned capacity; |
|
int* array; |
|
} Queue; |
|
Queue* createQueue(unsigned capacity) { |
|
Queue* queue = (Queue*)malloc(sizeof(Queue)); |
|
if (!queue) { |
|
printf("Memory error\n"); |
|
return NULL; |
|
} |
|
queue->front = queue->rear = -1; |
|
queue->capacity = capacity; |
|
queue->array = (int*)malloc(queue->capacity * sizeof(int)); |
|
if (!queue->array) { |
|
printf("Memory error\n"); |
本文含有隐藏内容,请 开通VIP 后查看