目錄
- 一. 前言
- 二. 順序表
- 1. 順序表的特點
- 2. 代碼實現
- 三. 鏈表
- 1. 單向鏈表代碼實現
- 2.雙向鏈表代碼實現
- 四. 順序表與鏈表的區別
- 總結
一. 前言
順序表和鏈表是最基礎的兩種線性表實現方式。它們各有特點,適用于不同的應用場景。本文將詳細介紹這兩種數據結構的實現原理、C語言代碼實現以及它們的優缺點對比。
二. 順序表
順序表是用一段連續的物理地址依次存儲數據元素的線性結構,采用數組存儲。
1. 順序表的特點
優點:
- 可以通過下標直接訪問元素
- 不需要額外的空間存儲元素之間的關系
缺點:
- 會造成一定的空間浪費
- 插入刪除效率低
2. 代碼實現
- 申請空間時,在無法確定空間大小時我們需要動態申請空間。
//將int重命名為SLTDatatype
typedef int SLTDatatype;
//順序表創建一個結構體
typedef struct SeqList
{SLDataType* arr; //存儲數組的指針int size; //有效個數int capacity; //最大容量
}SL;
- 初始化和銷毀順序表
//初始化順序表
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//銷毀順序表
void SLDestroy(SL* ps)
{if(ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
- 空間不足時開辟空間
//空間為空時開辟四個空間,不為空空間裝滿時擴大二倍
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}
- 插入數據
尾插:在判斷空間足夠時直接size位置插入然后size++;
頭插:通過循環把元素全部向后移一位,把插入的數據放在下標為0的位置,size++;
//尾插
void SLPushBack(SL* ps, SLTDataType x)
{assert(ps);//進入函數判斷空間是否足夠SLCheckCapacity(ps);//空間足夠在隊尾插入數據,把size加一ps->arr[ps->size++] = x;
}//頭插
void SLPushFront(SL* ps, SLTDataType x)
{assert(ps);//進入函數判斷空間是否足夠SLCheckCapacity(ps);//將數據整體向后挪動一位for (int i = ps->size; i > 0 ; i--){ps->arr[i] = ps->arr[i - 1];}//把數據插入在下標為0的位置上ps->arr[0] = x;ps->size++;
}
- 刪除數據
尾刪:通過size–,限制下標訪問;
頭刪:通過循環從下標為1開始向前移動一位,size–;
//尾刪
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}//頭刪
void SLPopFront(SL* ps)
{assert(ps && ps->size);//數據整體向前挪動一位for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
- 查找指定值
//通過遍歷數組來查找 返回下標
int SLFind(SL* ps, SLTDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}
- 指定位置插入數據
pos位置前插入和pos位置后插入都是通過循環把元素后移然后在指定位置下標插入;
//指定位置之前插入數據
//pos為指定位置的下標
void SLInsert(SL* ps, int pos, SLTDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);//判斷空間是否足夠SLCheckCapacity(ps);//pos及之后數據向后挪動一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//指定位置之后插入數據
SLInsertAfter(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos之前的數據向后挪動一位for (int i = ps->size;i > pos+1;i--){ps->arr[i] = ps->arr[i-1];}ps->arr[pos+1] = x;ps->size++;
}
- 刪除指定位置的數據
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos后面的數據向前挪動一位for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
- SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定義動態順序表的結構
typedef int SLTDataType;
//順序表創建一個結構體
typedef struct SeqList
{SLTDataType* arr; //存儲數據int size; //有效數據個數int capacity; //空間大小
}SL;//初始化順序表
void SLInit(SL* ps);
//銷毀順序表
void SLDestroy(SL* ps);void SLPrint(SL* ps);
//尾插
void SLPushBack(SL* ps, SLTDataType x);
//頭插
void SLPushFront(SL* ps, SLTDataType x);//尾刪
void SLPopBack(SL* ps);
//頭刪
void SLPopFront(SL* ps);//查找
int SLFind(SL* ps, SLTDataType x);
//指定位置之前插?數據
void SLInsert(SL* ps, int pos, SLTDataType x);
//指定位置之后插入數據
void SLInsertAfter(SL* ps, int pos, SLTDataType x);
//刪除pos位置的數據
void SLErase(SL* ps, int pos);
- SeqList.c
#include"SeqList.h"//初始化順序表
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//銷毀順序表
void SLDestroy(SL* ps)
{if(ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}//打印順序表的數據
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//空間為空時開辟四個空間,不為空空間裝滿時擴大二倍
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}//隊尾插入數據
void SLPushBack(SL* ps, SLTDataType x)
{assert(ps);//進入函數判斷空間是否足夠SLCheckCapacity(ps);//空間足夠在隊尾插入數據,把size加一ps->arr[ps->size++] = x;
}//隊頭插入數據
void SLPushFront(SL* ps, SLTDataType x)
{assert(ps);//進入函數判斷空間是否足夠SLCheckCapacity(ps);//將數據整體向后挪動一位for (int i = ps->size; i > 0 ; i--){ps->arr[i] = ps->arr[i - 1];}//把數據插入在下標為0的位置上ps->arr[0] = x;ps->size++;
}//通過遍歷數組來查找 返回下標
int SLFind(SL* ps, SLTDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}//指定位置之前插入數據
//pos為指定位置的下標
void SLInsert(SL* ps, int pos, SLTDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);//判斷空間是否足夠SLCheckCapacity(ps);//pos及之后數據向后挪動一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//指定位置之后插入數據
SLInsertAfter(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos之前的數據向后挪動一位for (int i = ps->size;i > pos+1;i--){ps->arr[i] = ps->arr[i-1];}ps->arr[pos+1] = x;ps->size++;
}//刪除指定位置的數據
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos后面的數據向前挪動一位for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
三. 鏈表
鏈表是一種非連續、非順序的存儲結構,通過指針將一組零散的內存塊串聯起來。常見的鏈表有單鏈表、雙向鏈表和循環鏈表。
1. 單向鏈表代碼實現
- SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;
//定義結構體
typedef struct SListNode
{SLTDataType data;//節點的值struct SListNode *next;//指向下一個節點的指針
}SLTNode;//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾刪
void SLTPopBack(SLTNode** pphead);
//頭刪
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* phead, SLTDataType x);//刪除指定pos節點位置的數據
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除指定pos節點位置之后的數據
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SLisDesTroy(SLTNode** pphead);//打印鏈表
void SLTPrint(SLTNode** pphead);
- SList.c
#include "SList.h"//申請節點
SLTNode* STLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){printf("申請內存失敗!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//打印鏈表
void SLTPrint(SLTNode* pphead)
{SLTNode* ptail = pphead;while (ptail){printf("%d->", ptail->data);ptail = ptail->next;}printf("NULL\n");
}
尾插:通過循環遍歷到最后一個節點,把最后一個節點指向插入的節點;
頭插:將插入的節點指向頭節點,再把插入節點改為頭節點;
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//*pphead 是指向第一個節點的指針SLTNode* newnode = STLBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = STLBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
尾刪:循環遍歷到最后一個節點,free釋放掉節點;
頭刪:創建一個指向頭節點下一節點的位置,再free釋放掉節點
//尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;//prev->next = NULL;}}
//頭刪
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode *ptail = *pphead;*pphead = ptail->next;free(ptail);ptail = NULL;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之前插入數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos && *pphead);SLTNode* newnode = STLBuyNode(x);if (pos== *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* newnode = STLBuyNode(x);newnode->next = phead->next;phead->next = newnode;
}//刪除指定pos節點位置的數據
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos && *pphead);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//刪除指定pos節點位置之后的數據
void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//銷毀鏈表
void SLisDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
2.雙向鏈表代碼實現
這里示例的是雙向帶頭循環鏈表
雙向鏈表我們在前面加上一個頭節點head,next指向下一個節點的指針,prev指向上一個節點的指針。
- List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定義雙向鏈表結構
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next; //指向下一個節點的指針struct ListNode* prev; //指向前一個節點的指針
}LTNode;//初始化
LTNode* LTInit();
//銷毀---為了保持接口一致性
void LTDesTroy(LTNode* phead);
//在雙向鏈表中,增刪改查都不會改變頭節點
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);
//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);
//判斷是否為空
bool LTEmpty(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插?數據
void LTInsert(LTNode* pos, LTDataType x);//刪除pos位置的節點
void LTErase(LTNode* pos);
尾插:
phead = 頭節點; phead->prev = 尾節點; newnode = 插入節點;
1. newnode->prev = phead->prev; 插入節點的prev指向尾節點
2. newnode->next = phead; 插入節點的next指向頭節點
3. phead->prev->next = newnode;改變尾節點next指向插入節點
4. phead->prev = newnode; 改變頭節點prev指向插入節點
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
頭插:
phead = 頭節點; newnode = 插入節點 ; phead->next = 尾節點;
1. newnode->next = phead->next; 插入節點的next指向頭節點指向的下一個節點
2. newnode->prev = phead; 插入節點的prev指向頭節點
3. phead->next->prev = newnode;頭節點指向下一個節點的prev指向插入節點
4. phead->next = newnode; 頭節點的next指向插入節點
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
尾刪:
1. LTNode* del = phead->prev;創建一個指針指向頭節點的prev
2. del->prev->next = phead; 將del上一個的next指向頭節點
3. phead->prev = del->prev; 將頭節點的prev指向del的prev
4. 最后釋放節點free(del)
//尾刪
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
頭刪:
1. LTNode* del = phead->next;創建一個指針指向頭節點的next
2. del->next->prev = phead; 將del下一個的prev指向頭節點
3. phead->next = del->next; 將頭節點的next指向del的next
4. 最后釋放節點free(del)
//頭刪
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
- List.c
#include"List.h"
//申請節點
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//初始化
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}
//銷毀
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//銷毀頭結點free(phead);phead = NULL;
}
//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}
//判斷是否為空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//未找到return NULL;
}//在pos位置之后插?數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}//刪除pos位置的節點
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
四. 順序表與鏈表的區別
特性 | 順序表 | 單向鏈表 | 雙向鏈表 |
---|---|---|---|
內存布局 | 連續的空間 | 節點通過指針鏈接,內存不連續 | 節點通過兩個指針鏈接,內存不連續 |
訪問方式 | 隨機訪問(通過下標直接訪問)O(1) | 順序訪問(從頭節點開始遍歷)O(n) | 隨機訪問(可以正向和反向遍歷)O(n) |
插入/刪除 | 需要移動元素O(n) | 只需修改指針指向O(1) | 只需修改指針指向O(1) |
內存占用 | 僅存儲數據 | 每個節點存儲的數據和指向下一個節點的指針 | 每個節點存儲數據和兩個指針 |
適用場景 | 需要頻繁的隨機訪問 | 需要頻繁的插入和刪除,且不需要隨機訪問 | 需要頻繁插入和刪除,且需要雙向遍歷的場景 |
總結
本篇文章到這里就結束啦!通過前面的介紹,相信大家對順序表、單向鏈表和雙向鏈表都有了更清晰的認識。順序表憑借其高效的隨機訪問能力,在對數據快速定位有較高要求的場景中發揮著關鍵作用;單向鏈表以其靈活的插入和刪除操作,在數據頻繁變動且無需隨機訪問的情境下展現出優勢;雙向鏈表則在兼具單向鏈表靈活性的基礎上,通過支持雙向遍歷,進一步拓展了應用范圍。文章中如果大家發現有不對的地方可以直接指出,博主會積極改正。還希望大家多多諒解,最后感謝大家的點贊、收藏、評論和收藏。