考研数据结构模板：顺序表、链表、栈、队列前言
- 代码风格偏向于考研风格而非算法竞赛风格。
- 代码实现参考《2024数据结构王道复习指导》。
- 注释详细、保证看懂。
- 下面是已实现的数据结构模板：
- 顺序表SeqList
- 链表LinkList
- 双链表DLinkList
- 顺序栈SeqStack
- 循环顺序队列CircleQueue
- 链队列LinkQueue
顺序表SeqList顺序表定义
// 定义顺序表struct SeqList { int *data; // 数据动态分配 int length, maxLength; // 当前长度、最大长度};// 最大容量#define SEQ_LIST_MAX_SIZE 100// 初始容量#define SQL_LIST_INIT_SIZE 10初始化
void SeqListInitial(SeqList &list) { list.maxLength = SQL_LIST_INIT_SIZE; list.data = new int[list.maxLength]; list.length = 0;}判断是否为空
bool SeqListIsEmpty(SeqList &list) { return list.length == 0;}查询元素长度
int SeqListLength(SeqList &list) { return list.length;}打印元素
void SeqListPrint(SeqList &list) { for (int i = 0; i < list.length; i++) { printf("%d ", list.data[i]); }}插入元素
bool SeqListInsert(SeqList &list, int index, int data) { if (index list.length + 1) { // index范围必须在[1, list.SeqListLength + 1] return false; // 下标溢出 } if (list.length == list.maxLength) { // 空间不足，申请空间 if (list.length == SEQ_LIST_MAX_SIZE) { return false; // 空间溢出 } else { int maxLength; // 下一次申请空间的长度 if (list.length * 2 < SEQ_LIST_MAX_SIZE) { maxLength = list.length * 2; // 容量每次扩大两倍 } else { maxLength = SEQ_LIST_MAX_SIZE; } int *memory = new int[maxLength]; // 创建一块存储空间 for (int i = 0; i = index; i--) { // 移动数组 list.data[i] = list.data[i - 1]; } list.length++; list.data[index - 1] = data; // 插入元素 return true;}删除元素
bool SeqListRemove(SeqList &list, int index, int &data) { if (index list.length) { // index取值范围为[1, list.SeqListLength] return false; // 溢出 } data = list.data[index - 1]; // 保存删除的数据 for (int i = index; i < list.length; i++) { // 移动元素 list.data[i - 1] = list.data[i]; } list.length--; return true;}查询元素位置
int SeqListFindIndex(SeqList &list, int data) { for (int i = 0; i < list.length; i++) { // 遍历数组 if (list.data[i] == data) { return i + 1; } } return -1; // 找不到则返回-1}查询位置上的元素值
bool SeqListGet(SeqList &list, int index, int &data) { if (index list.length) { // 下标范围在[1, list.length]之间 return false; } data = list.data[index - 1]; // 保存元素 return true;}链表LinkList链表定义
// 单链表节点struct LinkListNode { int data; LinkListNode *next;};// 单链表struct LinkList { LinkListNode *head; // 头指针 LinkListNode *tail; // 尾指针};空元素初始化
void LinkListInitial(LinkList &list) { LinkListNode *node = new LinkListNode(); // 初始化头节点 list.head = node; list.tail = node;}数组初始化
void LinkListInitial(LinkList &list, int data[], int length) { LinkListNode *node = new LinkListNode(); list.head = node; list.tail = node; for (int i = 0; i data = data[i]; list.tail->next = next; list.tail = list.tail->next; }}查询元素长度
int LinkListLength(LinkList &list) { int length = 0; LinkListNode *p = list.head->next; while (p != NULL) { // 遍历链表直到为空 length++; p = p->next; } return length;}打印元素
void LinkListPrint(LinkList &list) { if (list.head == list.tail) { return; } LinkListNode *p = list.head->next; while (p != NULL) { // 遍历所有元素，直到为空 printf("%d ", p->data); p = p->next; }}插入元素
bool LinkListInsert(LinkList &list, int index, int data) { if (index < 1) { // 下标范围必须大于等于1 return false; } LinkListNode *p = list.head; // 用于保存插入位置的前驱 for (int i = 1; i next; if (p == NULL) { return false; // 不存在此下标 } } LinkListNode *node = new LinkListNode(); // 插入元素 node->data = data; node->next = p->next; p->next = node; return true;}删除元素
bool LinkListRemove(LinkList &list, int index, int &data) { if (index < 1) { // 下标范围必须大于等于1 return false; } LinkListNode *p = list.head; // 用于保存插入位置的前驱 for (int i = 1; i next; if (p == NULL) { return false; // 不存在此下标 } } LinkListNode *node = p->next; // 执行删除操作 data = node->data; // 保存删除节点的值 p->next = node->next; delete node; // 释放空间 return true;}查询位置上的元素值
bool LinkListGet(LinkList &list, int index, int &data) { if (index < 1) { // 下标范围必须大于等于1 return false; } LinkListNode *p = list.head; for (int i = 1; i next; if (p == NULL) { return false; // 不存在此下标 } } data = p->data; return true;}双链表DLinkList双链表定义
// 双链表节点struct DLinkListNode { int data; DLinkListNode *prev, *next; // 前驱与后继节点};// 双链表struct DLinkList { DLinkListNode *head; // 头节点};初始化
void DLinkListInitial(DLinkList &list) { DLinkListNode *head = new DLinkListNode(); // 创建头节点 list.head = head;}打印元素
void DLinkListPrint(DLinkList &list) { DLinkListNode *p = list.head; while (p->next != NULL) { p = p->next; printf("%d ", p->data); }}插入元素
bool DLinkListNodeInsert(DLinkList &list, int index, int data) { if (index < 1) { // 下标范围必须大于等于1 return false; } DLinkListNode *p = list.head; for (int i = 1; i next; if (p == NULL) { return false; // 不存在此下标 } } DLinkListNode *node = new DLinkListNode(); // 插入元素 node->data = data; node->next = p->next; if (p->next != NULL) { p->next->prev = node; } node->prev = p; p->next = node; return true;}删除元素
bool DLinkListRemove(DLinkList &list, int index) { if (index < 1) { // 下标范围必须大于等于1 return false; } DLinkListNode *p = list.head; // 找到删除位置的前驱 for (int i = 1; i next; if (p == NULL) { return false; // 不存在此下标 } } DLinkListNode *q = p->next; // 被删除的元素 if (q == NULL) { // 当q为链表末尾时，则被删除的元素不存在 return false; } p->next = q->next; if (q->next != NULL) { q->next->prev = p; } delete q; // 释放空间 return true;}顺序栈SeqStack顺序栈定义
// 最大空间#define SEQ_STACK_MAX_SIZE 100// 顺序栈struct SeqStack { int data[SEQ_STACK_MAX_SIZE]; int top; // 栈顶指针};初始化
void SeqStackInitStack(SeqStack &stack) { stack.top = -1; // 使用-1标识为空栈}判断是否为空
bool SeqStackIsEmpty(SeqStack &stack) { return stack.top == -1;}进栈
bool SeqStackPush(SeqStack &stack, int data) { if (stack.top == SEQ_STACK_MAX_SIZE - 1) { return false; // 空间不够 } stack.data[++stack.top] = data; // 指针后移并添加元素 return true;}出栈
bool SeqStackPop(SeqStack &stack, int &data) { if (stack.top == -1) { return false; // 没有元素 } data = stack.data[stack.top--]; // 删除元素并将指针前移 return true;}读取栈顶元素
bool SeqStackGetTop(SeqStack &stack, int &data) { if (stack.top == -1) { return false; // 没有元素 } data = stack.data[stack.top]; return true;}循环顺序队列CircleQueue循环顺序队列定义
// 最大空间#define CIRCLE_QUEUE_MAX_SIZE 10// 循环顺序队列struct CircleQueue { int data[CIRCLE_QUEUE_MAX_SIZE]; int front, rear; // 头指针和尾指针};初始化
void CircleQueueInit(CircleQueue &queue) { queue.front = queue.rear = 0;}判断队列是否为空
bool CircleQueueIsEmpty(CircleQueue &queue) { return queue.front == queue.rear;}判断队列是否已满
bool CircleQueueIsFull(CircleQueue &queue) { return (queue.rear + 1) % CIRCLE_QUEUE_MAX_SIZE == queue.front; // 队尾的下一个位置是队头，则说明队满}获取队列长度
int CircleQueueLength(CircleQueue &queue) { return (queue.rear - queue.front + CIRCLE_QUEUE_MAX_SIZE) % CIRCLE_QUEUE_MAX_SIZE;}进队
bool CircleQueuePush(CircleQueue &queue, int data) { if (CircleQueueIsFull(queue)) { // 如果队列已满，则无法进队 return false; } queue.data[(queue.rear++) % CIRCLE_QUEUE_MAX_SIZE] = data; // 取模实现循环 return true;}出队
bool CircleQueuePop(CircleQueue &queue, int &data) { if (CircleQueueIsEmpty(queue)) { // 如果队列为空，则无法出队 return false; } data = queue.data[(queue.front++) % CIRCLE_QUEUE_MAX_SIZE]; return true;}链队列LinkQueue链队列定义
// 链队列节点struct LinkQueueNode { int data; LinkQueueNode *next;};// 链队列struct LinkQueue { LinkQueueNode *front, *rear; // 头指针和尾指针};初始化
void LinkQueueInit(LinkQueue &queue) { LinkQueueNode *head = new LinkQueueNode(); // 头节点 queue.front = queue.rear = head;}判断队列是否为空
bool LinkQueueIsEmpty(LinkQueue &queue) { return queue.front == queue.rear;}获取队列长度
int LinkQueueLength(LinkQueue &queue) { int length = 0; // 遍历链表直到为空 LinkQueueNode *p = queue.front->next; while (p != NULL) { length++; p = p->next; } return length;}进队
void LinkQueuePush(LinkQueue &queue, int data) { LinkQueueNode *node = new LinkQueueNode(); // 头节点 node->data = data; queue.rear->next = node; queue.rear = queue.rear->next;}出队
bool LinkQueuePop(LinkQueue &queue, int &data) { if (LinkQueueIsEmpty(queue)) { return false; // 队列为空 } LinkQueueNode *head = queue.front; // 头节点 LinkQueueNode *node = head->next; data = node->data; queue.front = node; // 新的头节点 delete head; // 释放空间 return true;}