碼字不易，對(duì)你有幫助 點(diǎn)贊/轉(zhuǎn)發(fā)/關(guān)注 支持一下作者

微信搜公眾號(hào)：不會(huì)編程的程序圓

看更多干貨，獲取第一時(shí)間更新

【數(shù)據(jù)結(jié)構(gòu)輕松學(xué)】系列 Github ：https://github.com/hairrrrr/Date-Structure

本文的代碼已上傳至 Github

看更好的排版，閱讀原文：
https://mp.weixin.qq.com/s/QhRWUPCxZPm1ViojONscWg

目錄

toc

正文

一 順序表

1. 結(jié)構(gòu)

靜態(tài)順序表

使用定長數(shù)組

#define N 100
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[N]; // 定長數(shù)組
    size_t size; // 有效數(shù)據(jù)的個(gè)數(shù)
}SeqList;

動(dòng)態(tài)順序表

typedef int DataType; // 可擴(kuò)展性

typedef struct SeqList
{
    DataType* array; // 指向動(dòng)態(tài)開辟的數(shù)組
    size_t size; // 有效數(shù)據(jù)個(gè)數(shù)
    size_t capicity; // 容量空間的大小
}SeqList;

2. 接口實(shí)現(xiàn)

void SeqListPushBack(plist sl, DataType data); // 尾插
void SeqListPushFront(plist sl, DataType data); // 頭插

void SeqListPopBack(plist sl); // 尾刪
void SeqListPopFront(plist sl); // 頭刪

void SeqListInsert(plist sl, size_t pos, DataType data); // pos 位插入 x
void SeqListRemove(plist sl, size_t pos); // pos 位刪除

void SeqListInit(plist sl, size_t capacity); // 初始化
void SeqListDestory(plist sl); // 銷毀

void SeqListPrint(plist sl); // 打印
void SeqListCheckCapacity(plist sl); // 檢查空間是否已經(jīng)滿，如果滿了，就擴(kuò)容

3. 順序表的優(yōu)劣勢(shì)

劣勢(shì)：

1. 中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(N)
2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
3. 增容一般是呈2倍的增長，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間

優(yōu)勢(shì)：

空間連續(xù)，支持隨機(jī)訪問。

二 鏈表

image

1. 無頭單向非循環(huán)鏈表

接口實(shí)現(xiàn)：

typedef int Type;

typedef struct Node
{
    struct Node* _next;
    Type _data;
}Node;

//實(shí)現(xiàn)不帶頭單向非循環(huán)鏈表
typedef struct SingleList
{
    Node* _head; // head: 表示鏈表真正的頭結(jié)點(diǎn)，即第一個(gè)有效的數(shù)據(jù)的位置
}SingleList;


void singleListInit(SingleList* sl); 

Node* creatNode(Type data); 

void singleListPushBack(SingleList* sl, Type data);

void singleListPopBack(SingleList* sl);

void singleListPushFront(SingleList* sl, Type data);

void singleListPopFront(SingleList* sl);

void singleListInsertAfter(Node* pos, Type data);

void singleListEraseAfter(Node* pos);

Node* find(SingleList* sl, Type data);

void singleListPrint(SingleList* sl);

void singleListDestroy(SingleList* sl);

2. 帶頭雙向循環(huán)鏈表

接口實(shí)現(xiàn)

typedef int DataType;

// 結(jié)點(diǎn)類型
typedef struct ListNode
{
    DataType data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

// 表頭
typedef struct ListHead {
    ListNode* head;
}ListHead;


// 接口
void ListCreate(ListHead* plist);

void ListDestory(ListHead* plist);

void ListPrint(ListHead* plist);

void ListPushBack(ListHead* plist, DataType data);

void ListPopBack(ListHead* plist);

void ListPushFront(ListHead* plist, DataType data);

void ListPopFront(ListHead* plist);

ListNode* ListFind(ListHead* plist, DataType data);

void ListInsert(ListNode* pos, DataType data);

void ListErase(ListNode* pos);

3. 鏈表的優(yōu)劣勢(shì)

優(yōu)勢(shì)：

以節(jié)點(diǎn)為單位存儲(chǔ)，不支持隨機(jī)訪問

劣勢(shì)：

1. 任意位置插入刪除時(shí)間復(fù)雜度為O(1)
2. 沒有增容問題，插入一個(gè)開辟一個(gè)空間。

查看【數(shù)據(jù)結(jié)構(gòu)輕松學(xué)】更詳細(xì)的目錄： https://github.com/hairrrrr/Date-Structure

不要忘記 star 呦~

歡迎大家在 評(píng)論區(qū)/私信 提出問題/指正錯(cuò)誤，謝謝觀看。

我是程序圓，我們下次再見。