考研数据结构模板：顺序表、链表、栈、队列
前言
- 代码风格偏向于考研风格而非算法竞赛风格。
- 代码实现参考《2024数据结构王道复习指导》。
- 注释详细、保证看懂。
- 下面是已实现的数据结构模板：
- 顺序表SeqList
- 链表LinkList
- 双链表DLinkList
- 顺序栈SeqStack
- 循环顺序队列CircleQueue
- 链队列LinkQueue
顺序表SeqList
顺序表定义
// 定义顺序表
struct SeqList {
int *data; // 数据动态分配
int length, maxLength; // 当前长度、最大长度
};
// 最大容量
#define SEQ_LIST_MAX_SIZE 100
// 初始容量
#define SEQ_LIST_INIT_SIZE 10
初始化
void SeqListInitial(SeqList &list) {
list.maxLength = SEQ_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 < 1 || 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 < list.length; i++) { // 复制数组
memory[i] = list.data[i];
}
delete list.data; // 释放原来的空间
list.data = memory;
list.maxLength = maxLength;
}
}
for (int i = list.length; 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 < 1 || 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 < 1 || 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 < length; i++) { // 尾插法插入所有元素
LinkListNode *next = new LinkListNode();
next->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 < index; i++) { // 找到插入位置的前驱
p = p->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 < index; i++) { // 查找删除位置的前驱
p = p->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 <= index; i++) { // 遍历链表
p = p->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 < index; i++) { // 找到插入位置的前驱
p = p->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 < index; i++) {
p = p->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;
}
原文链接：https://www.cnblogs.com/kkelin/p/17324548.html
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：考研数据结构模板：顺序表、链表、栈、队列 - Python技术站
微信扫一扫 
支付宝扫一扫 