考研資料結構模板：順序表、鏈表、堆疊、佇列
前言
- 代碼風格偏向于考研風格而非演算法競賽風格，
- 代碼實作參考《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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/stack.data[stack.top--]; // 洗掉元素并將指標前移
return true;
}
讀取堆疊頂元素
bool SeqStackGetTop(SeqStack &stack, int &data) {
if (stack.top == -1) {
return false; // 沒有元素
}
data = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/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 = https://www.cnblogs.com/kkelin/archive/2023/04/17/node->data;
queue.front = node; // 新的頭節點
delete head; // 釋放空間
return true;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550265.html
標籤：其他