一、開篇引入
作為計算機專業的學生，順序表、鏈表、棧、隊列、堆是《數據結構》課程的核心基礎，也是算法刷題、工程開發的"必備工具",但新手剛接觸時,常容易混淆各結構的特性，也難以用C語言實現，本文就從概念原理出發，用C語言完成這些數據結構的實現，手把手幫助新手徹底搞懂這些核心結構。
二、數據結構的實現
1.順序表
順序表是線性表的一種，滿足邏輯結構和物理結構雙線性
邏輯結構:數組元素之間呈"一對一"的先後順序，是邏輯上的線性結構，可能與實際結構並不相同
物理結構:底層基於數組實現，數組的內存空間是連續且不可分割，因此數據在物理存儲上也連續
1.1.順序表的結構:
點擊查看代碼
typedef struct SeqList {
SLdatatype* data;//數組的指針
int size;//有效數據的個數
int capacity;//數組的實際空間
}SL;
1.2.順序表的接口:
點擊查看代碼
//初始化順序表
void InitSL(SL* ps);
//銷燬順序表
void DestroySL(SL* ps);
//申請空間
void SLbuy(SL* ps, SLdatatype x);
//打印
void SLprint(SL ps);
//頭插
void SLpushfront(SL* ps, SLdatatype x);
//尾插
void SLpushback(SL* ps, SLdatatype x);
//在指定位置之前插入數據
void SLInsert(SL* ps, int pos, SLdatatype x);
//尾刪
void SLpopback(SL* ps);
//頭刪
void SLpopfront(SL* ps);
//刪除指定位置的數據
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLdatatype x);
1.3.順序表的實現:
點擊查看代碼
//初始化
void InitSL(SL* ps) {
ps->data = NULL;
ps->capacity = ps->size = 0;
}
//銷燬
void DestroySL(SL* ps) {
if (ps->data) {
free(ps->data);
}
ps->data = NULL;
ps->capacity = ps->size = 0;
}
//打印順表表中的元素
void SLprint(SL s) {
for (int i = 0; i < s.size; i++) {
printf("%d", s.data[i]);
}
printf("\n");
}
//申請空間
void SLbuy(SL* ps) {
//如果不這樣capacity = 0 時，capacity就永遠為0
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//這裏是relloc(擴容)，如果是malloc就是重新開闢了一塊空間，那麼原來的數據就丟失了
SLdatatype* tmp = (SLdatatype*)realloc(ps->data, newcapacity * sizeof(SLdatatype));
if (tmp == NULL) {
perror("SLpushback():realloc Fail");
exit(1);
}
//這裏申請完空間後注意重新賦值capacity
ps->capacity = newcapacity;
ps->data = tmp;
}
//尾插
void SLpushback(SL* ps,SLdatatype x) {
assert(ps);
if (ps->capacity == ps->size) {
SLbuy(ps);
}
//push完size++
ps->data[ps->size++] = x;
}
//頭插
void SLpushfront(SL* ps, SLdatatype x) {
assert(ps);
if (ps->capacity == ps->size) {
SLbuy(ps);
}
for (int i = ps->size; i > 0; i--) {
ps->data[i] = ps->data[i - 1];
}
//push完size++
ps->data[0] = x;
ps->size++;
}
//任意位置插入
void SLInsert(SL* ps, int pos, SLdatatype x) {
assert(ps);
//防止越界的問題
assert(pos >= 0 && pos <= ps->size);
if (ps->capacity == ps->size) {
SLbuy(ps);
}
for (int i = ps->size; i > pos; i--) {
ps->data[i] = ps->data[i - 1];
}
ps->data[pos] = x;
ps->size++;
}
//尾刪
void SLpopback(SL* ps) {
assert(ps);
assert(ps->size);
//刪完後size--
--(ps->size);
}
//頭刪
void SLpopfront(SL* ps) {
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++) {
ps->data[i] = ps->data[i + 1];
}
--(ps->size);
}
//任意位置刪
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i<ps->size-1; i++) {
ps->data[i] = ps->data[i + 1];
}
ps->size--;
}
int SLFind(SL* ps, SLdatatype x) {
assert(ps);
for (int i = 0; i < ps->size; i++) {
if (ps->data[i] == x) {
return i;
break;
}
}
//只要返回無效的下標就行
return -1;
}
2.鏈表
邏輯結構線性，物理結構離散
邏輯結構:數據元素之間通過指針建立"一對一"的先後順序，邏輯上呈線性。
物理結構:節點的內存地址並不連續，不能連續訪問
2.1.鏈表的結構:
點擊查看代碼
typedef int SlDatatype;
typedef struct Slistnode {
SlDatatype data;
struct Slistnode* next;
}Slnode;
2.2.鏈表的接口:
點擊查看代碼
//鏈表的申請空間
Slnode* SlistBuy(SlDatatype x);
//鏈表的打印
void SlistPrint(Slnode* phead);
//鏈表的尾插
void SlistPushback(Slnode** phead, SlDatatype data);
//鏈表的頭插
void SlistPushhead(Slnode** pphead, SlDatatype data);
//鏈表的尾刪
void Slistdeleteback(Slnode** pphead);
//鏈表的頭刪
void Slistdeletehead(Slnode** pphead);
//鏈表的查找
Slnode* SlistFind(Slnode** pphead, SlDatatype x);
//鏈表指定位置之前插入節點
void Slistinert(Slnode** pphead, Slnode* pos, SlDatatype x);
//鏈表指定位置之後插入節點
void Slistinertback(Slnode* pos, SlDatatype x);
//鏈表指定位置刪除節點
void SlistErase(Slnode** pphead, Slnode* pos);
//鏈表指定位置之後刪除節點
void SlistsEraseBack(Slnode* pos);
2.3.鏈表的實現:
點擊查看代碼
//申請空間
Slnode* SlistBuy(SlDatatype x) {
Slnode* newnode = (Slnode*)malloc(sizeof(Slnode));
if (newnode == NULL) {
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//鏈表的打印
void SlistPrint(Slnode* phead) {
Slnode* tmp = phead;
while (tmp) {
printf("%d->", tmp->data);
tmp=tmp->next;
}
printf("NULL\n");
}
//鏈表的尾插->傳二級指針，因為只要涉及改變參數的都要地址拷貝
void SlistPushback(Slnode** pphead, SlDatatype data) {
//尋找尾部
assert(pphead);
Slnode* tmp = *pphead;
Slnode*newnode = SlistBuy(data);
if (tmp== NULL) {
*pphead = newnode;
}
else {
while (tmp->next) {
tmp=tmp->next;
}
tmp->next = newnode;
newnode->data = data;
newnode->next = NULL;
}
}
//鏈表的頭插
void SlistPushhead(Slnode** pphead, SlDatatype data) {
assert(pphead);
Slnode* tmp = *pphead;
Slnode* newnode = SlistBuy(data);
if (tmp == NULL) {
*pphead= newnode;
}
else {
*pphead = newnode;
newnode->data = data;
newnode->next = tmp;
}
}
//鏈表的尾刪
void Slistdeleteback(Slnode** pphead) {
assert(pphead && *pphead);
Slnode* tmp = *pphead;
Slnode* prev = *pphead;
if (tmp -> next ==NULL) {
free(*pphead);
*pphead = NULL;
}
else {
while (tmp->next) {
prev = tmp;
tmp = tmp->next;
}
}
free(tmp);
tmp = NULL;
prev->next = NULL;
}
void Slistdeletehead(Slnode** pphead) {
assert(pphead && *pphead);
Slnode* cmp = *pphead;
*pphead = cmp->next;
free(cmp);
cmp = NULL;
}
void Slistinert(Slnode** pphead, Slnode* pos, SlDatatype x) {
assert(pphead&&pos&&*pphead);
Slnode* newnode = SlistBuy(x);
Slnode* prev = *pphead;
Slnode* pur = *pphead;
if (pos == *pphead) {
SlistPushhead(pphead, x);
}
else {
while (pur != pos) {
prev = pur;
pur = pur->next;
}
prev->next = newnode;
newnode->next = pur;
}
}
Slnode* SlistFind(Slnode** pphead, SlDatatype x) {
assert(pphead && *pphead);
int Flag = 0;
Slnode* tmp = *pphead;
while (tmp) {
if (tmp->data == x) {
Flag = 1;
return tmp;
}
tmp = tmp->next;
}
if (Flag == 0) {
return NULL;
}
}
void Slistinertback(Slnode* pos, SlDatatype x) {
assert(pos);
Slnode* newnode = SlistBuy(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SlistErase(Slnode** pphead, Slnode* pos) {
assert(pphead && pos);
Slnode* prev = *pphead;
Slnode* pur = *pphead;
if (pos == *pphead) {
Slnode* toDel = *pphead;
*pphead = toDel->next;
free(toDel);
return;
}
while (pur != pos) {
prev = pur;
pur = pur->next;
}
prev->next = pur->next;
free(pur);
pur = NULL;
}
void SlistsEraseBack(Slnode* pos) {
assert(pos&&pos->next);
Slnode* tmp = pos->next;
pos->next = tmp->next;
free(tmp);
tmp = NULL;
}
簡單總結一下鏈表和順序表的不同點:
緩存:由於CPU的運行速率超快，與內存不同頻，需要把內存中的內容先轉到寄存器中，而寄存器由於空間有限，所以要先轉到緩存器中，然後等寄存器運行結束後，再將緩存器中的內容轉到寄存器中。(簡單的理解)
順序表的緩存利用率高:數組由於空間連續，緩存器一次取順序表的內容就可以一大片一大片的取，緩存命中率就高，而鏈表由於空間不一定連續，所以就只能一次一次的取，效率就慢，緩存命中率就低。
3.棧
棧是一種後進先出的線性表，僅允許在棧頂進行插入和刪除
3.1.棧的實現選擇:如果是用鏈表實現，我們就需要頻繁的找尾，而每次找尾的時間複雜度為O(N)，並且再刪除尾部的時候還要保存上一節點，操作繁瑣。所以我們選擇了更易操作的數組實現。
3.2.棧的結構:
點擊查看代碼
typedef int STdatatype;
typedef struct Stack {
STdatatype* a;
int top;
int capacity;
}ST;
3.3.棧的接口:
點擊查看代碼
//棧的初始化
void STinit(ST* pst);
//棧的銷燬
void STdestroy(ST* pst);
//入棧
void STpush(ST* pst,STdatatype x);
//出棧
void STpop(ST* pst);
//取棧頂數據
STdatatype STtop(ST* pst);
//判空
int STempty(ST* pst);
//獲取數據個數
int STsize(ST* pst);
3.4.棧的實現:
點擊查看代碼
void STinit(ST* pst) {
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STdestroy(ST* pst) {
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STpush(ST* pst,STdatatype x) {
assert(pst);
if (pst->capacity == pst->top) {
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
STdatatype* tmp = (STdatatype*)realloc(pst->a,newcapacity*sizeof(STdatatype));
if (tmp == NULL) {
perror("STPush():realloc():Fail");
return;
}
pst->capacity = newcapacity;
pst->a = tmp;
}
pst->a[pst->top++] = x;
}
void STpop(ST* pst) {
assert(pst);
assert(pst->top);
pst->top--;
}
STdatatype STtop(ST* pst) {
assert(pst);
assert(pst->top);
return pst->a[pst->top - 1];
}
int STempty(ST* pst) {
assert(pst);
return pst->top == 0;
}
int STsize(ST* pst) {
assert(pst);
int size = pst->top;
return size;
}
利用棧可以解決經典算法題(https://leetcode.cn/problems/valid-parentheses/)
思路:
1.若遇到左括號就入棧
2.若遇到右括號就嘗試與棧頂的左括號匹配
代碼實現:
點擊查看代碼
bool isValid(char* s) {
ST st;
STinit(&st);
//遍歷字符串
while(*s){
//如果是左括號就入棧
if(*s == '(' || *s == '[' || *s == '{'){
STpush(&st,*s);
}
//如果是右括號就嘗試與左括號匹配
else{
if(STempty(&st)){
STdestroy(&st);
return false;
}
char top = STtop(&st);
STpop(&st);
if((top == '(' && *s != ')') ||
(top == '[' && *s != ']') ||
(top == '{' && *s != '}')){
STdestroy(&st);
return false;
}
}
++s;
}
bool ret = STempty(&st);
STdestroy(&st);
return ret;
}
4.隊列
隊列是一種先進先出的線性表，在隊頭刪除，在隊尾插入
4.1.隊列的應用:醫院抽號機，還有社交平台上的好友推薦
4.2.隊列的實現選擇:如果用數組實現，每次刪除的是首元素，這樣首元素後面的元素就得向前移動，時間複雜度為O(N)，所以我們用鏈表更易實現
4.3.隊列的結構:特殊點:額外用一個結構體封裝了它的頭節點，尾節點，以及大小，這樣傳參數的時候就能只傳一個參數了
點擊查看代碼
typedef int Qdatatype;
typedef struct QueueNode {
struct QueueNode* next;
Qdatatype val;
}QNode;
typedef struct Queue {
QNode* phead;
QNode* ptail;
int size;
}Queue;
4.4.隊列的接口:
點擊查看代碼
//隊列的初始化
void QueueInit(Queue* pq);
//隊列的銷燬
void QueueDestroy(Queue* pq);
//隊頭數據的刪除
void QueuePop(Queue* pq);
//隊尾插入數據
void QueuePush(Queue* pq, Qdatatype x);
//獲取隊頭的數據
Qdatatype QueueFront(Queue* pq);
//獲取隊尾的數據
Qdatatype QueueBack(Queue* pq);
//隊列的長度
int QueueSize(Queue* pq);
//隊列的判空
bool QueueEmpty(Queue* pq);
4.5.隊列的實現:
點擊查看代碼
void STinit(ST* pst) {
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STdestroy(ST* pst) {
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STpush(ST* pst,STdatatype x) {
assert(pst);
if (pst->capacity == pst->top) {
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
STdatatype* tmp = (STdatatype*)realloc(pst->a,newcapacity*sizeof(STdatatype));
if (tmp == NULL) {
perror("STPush():realloc():Fail");
return;
}
pst->capacity = newcapacity;
pst->a = tmp;
}
pst->a[pst->top++] = x;
}
void STpop(ST* pst) {
assert(pst);
assert(pst->top);
pst->top--;
}
STdatatype STtop(ST* pst) {
assert(pst);
assert(pst->top);
return pst->a[pst->top - 1];
}
int STempty(ST* pst) {
assert(pst);
return pst->top == 0;
}
int STsize(ST* pst) {
assert(pst);
int size = pst->top;
return size;
}
學了隊列可以嘗試一下這道題(https://leetcode.cn/problems/design-circular-queue/description/)
總結一下棧和隊列的區別
棧和隊列的核心區別就是:一個後進先出，一個先進先出
用兩個隊列實現棧(https://leetcode.cn/problems/implement-stack-using-queues/)
用兩個棧實現隊列(https://leetcode.cn/problems/implement-queue-using-stacks/)
思路如下:
5.堆
特殊的完全二叉樹,分為大堆和小堆
大堆:父節點>=子節點
小堆:父節點<=子節點
5.1.堆的存儲特性:
物理上基於數組存儲，邏輯上表現為完全二叉樹
對於一個下標為i的節點：
若存在子節點
左孩子的節點下標:2i + 1
右孩子的節點下標:2i + 2
父節點下標:(i - 1)/2
5.2.堆的結構:
點擊查看代碼
typedef int Hpdatatype;
//堆(完全二叉樹)的底層還是一個數組
typedef struct Heap {
Hpdatatype* a;
int size;
int capacity;
}Heap;
5.3.堆的接口:
點擊查看代碼
//交換函數
void Swap(Hpdatatype* ph1, Hpdatatype* ph2);
//向上調整法
void AdjustUp(Hpdatatype* a, int child);
//向下調整法
void AdjustDown(Hpdatatype* a, int size, int parent);
//堆的初始化
void HeapInit(Heap* php);
//堆的銷燬
void HeapDestroy(Heap* php);
//堆的插入數據
void HeapPush(Heap* php, Hpdatatype x);
//堆的刪除堆頂數據
void HeapPop(Heap*php);
//堆的獲取堆頂數據
Hpdatatype HeapTop(Heap* php);
//堆的判空
bool HeapEmpty(Heap* php);
5.4.堆的實現:
點擊查看代碼
void HeapInit(Heap* php) {
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
void HeapDestroy(Heap* php) {
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
void Swap(Hpdatatype* hp1, Hpdatatype* hp2) {
assert(hp1 && hp2);
Hpdatatype tmp = *hp1;
*hp1 = *hp2;
*hp2 = tmp;
}
void HeapPush(Heap* php, Hpdatatype x) {
//實現小堆
int child = php->size;
int parent = (child - 1) / 2;
//判斷空間夠不夠
if (php->capacity == php->size) {
int newcapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);
Hpdatatype* tmp = (Hpdatatype*)realloc(php->a,newcapacity * sizeof(Hpdatatype));
if (tmp == NULL) {
perror("HeapPush():realloc():fail");
return;
}
php->capacity = newcapacity;//變化過後capacity沒有改變
php->a = tmp;
}
php->a[child] = x;
php->size++;
//當child = 0 的時候停止
AdjustUp(php->a, child);
}
void HeapPop(Heap* php) {
//每次pop的意義是把次小的數推上堆頂
assert(php);
assert(php->size);
//首先先將堆頂的數據與堆尾的數據交換
Swap(&php->a[0], &php->a[php->size - 1]);
--php->size;
//再使用向下查找算法
AdjustDown(php->a, php->size, 0);
}
Hpdatatype HeapTop(Heap* php) {
assert(php);
assert(php->size);
return php->a[0];
}
bool HeapEmpty(Heap* php) {
assert(php);
return php->size == 0;
}
void AdjustUp(Hpdatatype* a, int child){
//向上和向下調整法的時間複雜度都為O(N)
int parent = (child - 1) / 2;
while (child > 0) {
//如果不滿足就重複交換child 和 parent 的值
if (a[child] < a[parent]) {
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
//當child > parent 的時候停止
else {
break;
}
}
}
void AdjustDown(Hpdatatype * a, int size, int parent) {
int lesschild = 2 * parent + 1;
//結束條件是到達葉子
while (lesschild < size) {
//假設法找到字節點中較小的那個
if (lesschild + 1<size && a[lesschild] > a[lesschild + 1]) {
lesschild++;
}
//將較小的子節點與父節點相比較
if (a[lesschild] < a[parent]) {
Swap(&a[lesschild], &a[parent]);
parent = lesschild;
lesschild = 2 * parent + 1;
}
else {
break;
}
}
}
5.5.堆排序:
點擊查看代碼
void HeapSort(Hpdatatype* a, int size) {
int parent = (size - 2) / 2;
while (parent--) {
AdjustDown(a, size, parent);//已經調成小堆的形式
}
while (size) {
Swap(&a[0], &a[size - 1]);
size--;
AdjustDown(a, size, 0);
}
}
三、結語
數據結構是計算機學科的基石，掌握順序表、鏈表、棧、隊列、堆的核心特性和實現，是後續學習樹、圖、排序算法的基礎。建議結合LeetCode算法題反覆練習，將理論轉化為實戰能力。
