进阶-数据结构部分：1、数据结构入门

飞书文档https://x509p6c8to.feishu.cn/wiki/HRLkwznHiiOgZqkqhLrcZNqVnLd

一、存储结构

顺序存储

链式存储

二、常用数据结构

2.1、栈

先进后出

场景：

后退/前进功能：网页浏览器中的后退和前进按钮可以使用栈来实现。在浏览网页时，每次访问一个新页面时，当前页面的信息将被推入栈中。当用户点击后退按钮时，程序将从栈中弹出最近的访问页面，并显示上一个页面。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_STACK_SIZE 100typedef struct {char url[MAX_STACK_SIZE];
} StackItem;typedef struct {StackItem items[MAX_STACK_SIZE];int top;
} Stack;void initStack(Stack *stack) {stack->top = -1;
}int isStackEmpty(Stack *stack) {return stack->top == -1;
}int isStackFull(Stack *stack) {return stack->top == MAX_STACK_SIZE - 1;
}void push(Stack *stack, char *url) {if (isStackFull(stack)) {printf("Stack overflow!\n");return;}stack->top++;strcpy(stack->items[stack->top].url, url);
}char* pop(Stack *stack) {if (isStackEmpty(stack)) {printf("Stack underflow!\n");return NULL;}char *url = stack->items[stack->top].url;stack->top--;return url;
}int main() {char inputurl[MAX_STACK_SIZE];int choice;Stack stack;initStack(&stack);while (1){printf("------》1:入栈\n");printf("------》2:出栈\n");scanf("%d",&choice);switch (choice){case 1:printf("请输入入栈内容：");scanf("%s",inputurl);push(&stack,inputurl);printf("入栈成功\n");break;case 2:if (!isStackEmpty(&stack)) {char *url = pop(&stack);printf("出栈：%s\n", url);}else{printf("已没有数据\n");}break;default:printf("无效操作\n");break;}}return 0;
}

2.2、队列

场景：

编写代码，实现演唱会购票用户（id、座位区域（A、B、C））购票与出票。

分析：

按购票顺序先后处理，先购票先出票

#include <stdio.h>#define MAX_AREA_SIZE 10
#define MAX_QUEUE_SIZE 5typedef struct {int id;char area[MAX_AREA_SIZE];
} User;typedef struct {User data[MAX_QUEUE_SIZE];int front; //队列头位置int rear;  //队列尾位置
} Queue;/*** @brief 初始化队列* 初始化时，由于队列为空，队列头和尾位置都在0* @param q*/
void initQueue(Queue *q) {q->front = q->rear = 0;
}/*** @brief 判断队列是否为空* 当队列头位置和尾位置相同时，队列为空* @param q* @return int*/
int isQueueEmpty(Queue *q) {return q->front == q->rear;
}/*** @brief 判断队列是否满* 当队列尾位置+1等于队列头位置时，队列满（队列尾位置追上头位置）* @param q* @return int*/
int isQueueFull(Queue *q) {return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}/*** @brief 入队* 先判断队列是否满，然后存储数据到队列尾位置，队列尾位置+1* @param q* @param s* @return int*/
int enqueue(Queue *q, User *s) {if (isQueueFull(q)) {return 0;}printf("id=%d, area=%s ", s->id, s->area);q->data[q->rear] = *s;q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;return 1;
}
/*** @brief 出队* 先判断队列是否空，然后读取队列头的数据，队列头位置+1* @param q* @param s* @return int*/
int dequeue(Queue *q, User *s) {if (isQueueEmpty(q)) {return 0;}*s = q->data[q->front];printf("id=%d, area=%s\n", s->id, s->area);q->front = (q->front + 1) % MAX_QUEUE_SIZE;return 1;
}int main() {int id = 0;User user;int choice;Queue q;initQueue(&q);while (1){printf("------》1:顾客购票\n");printf("------》2:工作人员出票\n");scanf("%d",&choice);switch (choice){case 1:printf("请输入购票区域：");user.id = id ++;scanf("%s",user.area);if(enqueue(&q, &user) == 1)printf("支付成功，等待工作人员处理\n");elseprintf("支付失败，当前无票\n");break;case 2:printf("出票:");User s;if (!dequeue(&q, &s)) {printf("已没有购票需要处理\n");}break;default:printf("无效操作\n");break;}}return 0;
}

2.3、链表

场景：实现一个用户信息管理系统，支持插入、查找、删除

分析：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义用户结构体
typedef struct User {char name[50];int age;struct User *next;
} User;// 初始化链表头节点
User *head = NULL;// 插入用户信息
void insertUser() {User *newUser = (User *) malloc(sizeof(User));printf("请输入用户名：");scanf("%s", newUser->name);printf("请输入年龄：");scanf("%d", &newUser->age);newUser->next = NULL;if (head == NULL) {head = newUser;} else {User *temp = head;while (temp->next != NULL) {temp = temp->next;}temp->next = newUser;}printf("用户信息插入成功！\n");
}// 删除用户信息
void deleteUser() {if (head == NULL) {printf("链表为空，无法删除用户信息！\n");return;}char name[50];printf("请输入要删除的用户名：");scanf("%s", name);User *temp = head;User *prev = NULL;while (temp != NULL && strcmp(temp->name, name) != 0) {prev = temp;temp = temp->next;}if (temp == NULL) {printf("未找到要删除的用户信息！\n");return;}if (prev == NULL) {head = temp->next;} else {prev->next = temp->next;}free(temp);printf("用户信息删除成功！\n");
}// 查找用户信息
void findUser() {if (head == NULL) {printf("链表为空，无法查找用户信息！\n");return;}char name[50];printf("请输入要查找的用户名：");scanf("%s", name);User *temp = head;while (temp != NULL && strcmp(temp->name, name) != 0) {temp = temp->next;}if (temp == NULL) {printf("未找到要查找的用户信息！\n");} else {printf("用户名：%s，年龄：%d\n", temp->name, temp->age);}
}int main() {int choice;while (1) {printf("请选择要执行的操作：\n");printf("1. 插入用户信息\n");printf("2. 删除用户信息\n");printf("3. 查找用户信息\n");printf("4. 退出程序\n");printf("请输入操作编号：");scanf("%d", &choice);switch (choice) {case 1:insertUser();break;case 2:deleteUser();break;case 3:findUser();break;case 4:exit(0);default:printf("输入的操作编号有误，请重新输入！\n");break;}}return 0;
}