【數據結構與算法】數據結構初階：詳解順序表和鏈表（一）

🔥個人主頁：艾莉絲努力練劍

?專欄傳送門：《C語言》、《數據結構與算法》

🍉學習方向：C/C++方向

??人生格言：為天地立心，為生民立命，為往圣繼絕學，為萬世開太平?

前言：上篇文章我們介紹了復雜度的概念，我們通過一個個經典的例子?，對時間復雜度和空間復雜度的概念進行了剖析，結合圖像，讓大家更加直觀地理解知識點，我們對比了常見的復雜度，展示了各種各樣的排序算法的復雜度表格，通過輪轉數組這一道力扣題向大家展示了“算法思路有很多種”名不虛傳，我們通過三種不同的思路（超出時間限制、通過、時間復雜度O(n)空間復雜度O(1)的情況下通過）詳解了算法和復雜度的關系。

本篇文章，我們就要開始介紹順序表和鏈表相關的知識點了，在初階的數據結構與算法階段，我們把知識點分成三部分，復雜度作為第一部分，順序表和鏈表、棧和隊列、二叉樹為第二部分，排序為第二部分，我們已經介紹完了第一部分：算法復雜度，從本文開始，我們就正式進入第二部分中的順序表和鏈表部分內容的學習啦。

正文

一、線性表

線性表（Linear List）是指n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表有：順序表、鏈表、棧、隊列、字符串……

線性表在邏輯上是線性結構，也就是說是連續的一條直線。但是在物理上不一定，線性表在物理上的存儲形式通常是數組和鏈式結構。

由此可見線性表還可分為兩種結構：線性結構和邏輯結構。

所謂邏輯結構就是人為想象出來的。

二、順序表

（一）順序表的概念

概念：順序表是一段用物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。那么我們可不可以說，數組就是順序表？或者說，順序表就是數組？可以這么說嗎？如果不能這么說，那么數組和順序表又有什么區別呢？

順序表的底層結構是數組，對數組的封裝，實現了常見的增刪查改等接口。

換句話說，數據結構完成的就是順序表的增刪查改等接口函數的實現。

舉個例子，數組和順序表的關系可以拿蒼蠅小館和米其林五星級餐廳類比一下——

（二）順序表的分類

順序表分為靜態順序表和動態順序表。

1、靜態順序表

靜態順序表就是使用定長數組存儲元素。

靜態順序表缺陷：空間給少了不夠用，給多了造成空間浪費。

2、動態順序表

動態順序表就是按需申請空間存儲進行存儲。

（三）順序表的結構

我們分別介紹靜態順序表和動態順序表的結構——

（四）動態順序表的實現

靜態順序表和動態順序表，我們這里就實現一下動態順序表，但并不是說靜態順序表就沒有學習的必要了。這一點要明確。

我們要分成三個文件來實現，因為是順序表，我們就取個名字叫"SeqList"，用三個文件實現一個功能我們在掃雷游戲那里就接觸過了，我們簡單分析一下三個文件各自的分工：

我們分別創建三個文件：SeqList.h頭文件、SeqList.c文件、test.c測試文件——

下面我們會分別介紹三個文件的書寫，每個小標題下面的第一個代碼是動態順序表的代碼實現。在代碼下面則是抽絲剝繭展開來的詳解。?

動態順序表的實現（包含尾插）

（1）SeqList.h

#pragma once
#include<stdio.h>//定義動態順序表的結構
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;//存儲數據int size;//有效數據個數int capacity;//空間大小
}SL;//typedef struct SeqList SL;void SLInit(SL s);

?（2）SeqList.c

#define  _CRT_SECURE_NO_WARNINGS  1#include"SeqList.h"
#include"stdio.h"
#include"test.c"
#include<stdlib.h>void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{//空間不夠if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity);if (tmp == NULL);{perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->size++] = x;
}

?（3）test.c

#define  _CRT_SECURE_NO_WARNINGS  1#include"SeqList.h"void test01()
{SL sl;SLInit(&sl);//具備了一個空的順序表SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);
}int main()
{test01();return 0;
}

（五）詳解順序表書寫

這里涉及到了結構體的知識，我們學習數據結構要對結構體有足夠的認識。

#pragema once#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}//增刪查改等接口函數

這里.h文件的第一行我們看到的代碼的作用，博主在C語言專欄的這篇文章里面介紹過——預處理深入詳解：預定義符號、宏、命名約定、命令行定義、條件編譯、頭文件的包含

我給大家截過來看一下——?

#pragma once

功能就是可以避免頭文件被重復包含。

如果你不想這樣定義，也可以寫成這樣，作用是等價的——

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}//增刪查改等接口函數
#endif  //__TEST_H__

我們定義的時候要注意，為什么這里數據類型不用define來定義？類型我們一般用typedef來定義的，定義一個普通的常量，我們是用#define，比如這里我們定義N是一個常量100。

#define  N  100

我們這樣定義的好處就是不需要再在代碼中一個一個去修改了——

#pragema oncestruct SeqList
{int a[10];int size;
}

如果我們想順序表存儲的不是10，而是100，或者1000，我們一般這樣定義：

#pragema once#define  N  100struct SeqList
{SQDataType a[N];int size;
}

a[ ]里面放N，當我們想改的時候，直接在定義里面把N改一下就可以了，不用在代碼里面一個一個去改。像順序表存儲的數據類型，我們這樣定義——

typedef int SLDataType;

我們這樣定義有什么好處？很簡單，比如我們上面的頭文件里面定義了一個數據類型叫SLDATAType，現在在代碼里面我們定義它是int類型，如果我要存的是char類型，我把這里改成char就行了，如果我要存的是double，我把這里改成double就可以了。

typedef char SLDataType;
typedef float SLDataType;
typedef double SLDataType;

是不是這個道理？這樣我們就不需要考慮別的，直接在定義里面修改就可以了。這就是我們這樣定義的好處。

定義完了，我們就要進行一下初始化。

初始化我們可以考慮用一個循環來初始化，也可以像下面這樣用一個memset函數來初始化，memset函數是按字節對其進行初始化。

#pragema once#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}//增刪查改等接口函數
void SeqListInit(struct SeqList sl);

我們C語言里面結構體不能直接寫結構體名稱，uu們是不是覺得這樣太長了，我們可以簡寫：

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}
typedef struct SeqList SL;
void SeqListInit(struct SeqList sl);
//增刪查改等接口函數
#endif  //__TEST_H__

當然我們還可以這樣寫（有很多書上包括很多老師是這樣寫的）：

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[N];int size;
}SL;
void SeqListInit(struct SeqList sl);
//增刪查改等接口函數
#endif  //__TEST_H__

那我們就可以不寫那么長一截了，直接寫簡寫“SL”——

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[N];int size;
}SL;
void SeqListInit(SL sl);
//增刪查改等接口函數
#endif  //__TEST_H__

是不是簡單多了？這里再提醒一下uu們，我們敲代碼不要一股腦敲完了再測試，我們可以敲一個測試一個，代碼如果很長，一股腦寫完可能出問題了一時半會兒找不到bug，這是一個很好的代碼書寫習慣，是前輩們總結出來的經驗教訓，大家也應當學習一下這種書寫方式。?

寫程序的時候，奮筆疾書、一頓操作，寫完一運行幾十個錯誤，再反復調試了一兩個小時，再一運行，又報了幾十個錯誤，自己都快崩潰了。?

那我們寫一個測試一個，有問題也只在這幾行代碼里面，方便我們查找，犯不上自己嚇自己~

順序表就是數組嘛，uu們可能覺得這個N還不好理解，我們可以在定義的時候寫成這樣——

#ifdef __TEST_H__
#define __TEST_H__#define  MAX_SIZE  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
void SeqListInit(SL s);
//增刪查改等接口函數
#endif  //__TEST_H__

這樣是不是更容易理解，我們一看便知，這是數組最大的大小。

#include"SeqList.h"void SeqListInit(SL s)
{memset(sl.a,0,sizeof(SQDataType)*MAX_SIZE);sl.size = 0;
//sl.a說明是按字節初始化
//初始化多少個字節呢？MAX_SIZE個
//每個有多大呢？sizeof(SQDataType)——SQDataType這個類型每一個的大小
}

這里我們就能更明顯地感覺到我們定義數組大小為MAX_SIZE的好處了，我們想把數組大小改一下是不是只要在.h文件的定義這里改一下就把所有包含了.h文件的數組大小都改掉了？很方便。

定義數據類型和定義數組大小同理，本質上都是增強了程序可維護性（不用所有地方都去改）。

那我們現在開始寫一點測試一點，我們程序要輸入輸出，包含一個頭文件，我們不知道的話再查一下memset的頭文件，<cstring>或者<string.h>這兩個頭文件是一樣的——

#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增強程序可維護性
#define  MAX_SIZE  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
void SeqListInit(SL s);
//增刪查改等接口函數
#endif  //__TEST_H__

然后我們來到test.c文件，先寫一個簡單的——

#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(SL s1);
//調接口進行初始化
}int main()
{return 0;
}

定義完了，我們先來試著跑一跑，調試的時候我們可以結合VS調試技巧中介紹過的技巧，F9打斷點，按F5調試，運行到斷點處。

所以這里我們就不能這么寫，要把前面的改一改：

1、靜態順序表?

我們C語言里面學過一個通訊錄的東西，就是這個結構。定義一個宏就寫死了。

（1）SeqList.h

#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增強程序可維護性
#define  MAX_SIZE  10//100個、500個有點太大了，先來10個
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
//增刪查改等接口函數
void SeqListInit(SL*ps);
void SeqListPushBack(SL*ps,SQDataType x);//尾插
void SeqListPushFront(SL*ps,SQDataType x);//頭插
void SeqListPopBack(SL*ps);//頭刪
void SeqListPopFront(SL*ps);//尾刪
#endif

這里uu們如果有其他明明也是可以的，博主這里是跟cpp的STL庫——標準庫——的命名走的。這是一種比較規范的命名形式——

void SeqListPushBack(SL*ps,SQDataType x);//尾插
void SeqListPushFront(SL*ps,SQDataType x);//頭插
void SeqListPopBack(SL*ps);//頭刪
void SeqListPopFront(SL*ps);//尾刪

當然這里還有其他的接口，我們還是老原則，寫一個測試一個。?

（2）SeqList.c（靜態順序表）

#include"SeqList.h"void SeqListInit(SL*p s)
{memset(ps->a,0,sizeof(SQDataType)*MAX_SIZE);ps->size = 0;
}
//頭插  尾插  頭刪  尾刪
void SeqListPushBack(SL*ps,SQDataType x);
{if(ps->size >= MAX_SIZE){printf("SeqList is Full\n");return;}ps->a[ps->size] = x;ps->size++;
}
//下面的大致也是上面這樣，就不介紹了
void SeqListPushFront(SL*ps,SQDataType x);
void SeqListPopBack(SL*ps);
void SeqListPopFront(SL*ps);

從這里我們可以看出靜態順序表結構不是一個好的順序表，存儲1001個，你定義MAX_SIZE為10000，是不是浪費了空間，靜態順序表存在的問題總結一下就是：

給少了不夠用，給多了用不完浪費空間，不能很好地控制。

正因如此，我們選擇更加靈活的動態順序表，靜態順序表我們就介紹到這里。

（3）test.c

#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);
//調接口進行初始化
}int main()
{TestSeqListl();return 0;
}

為什么要寫指針呢，因為形參是實參的一份臨時拷貝，形參和實參空間相互獨立，我們要傳地址，這樣形參改變不會影響實參，傳地址為什么可以影響呢？

2、動態順序表

(1)尾插

（1）SeqList.h

#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增強程序可維護性
typedef int SQDataType;typedef struct SeqList
{SQDataType*a;int size;     //有效數據的個數int capacity;//容量
}SL;
//增刪查改等接口函數
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListPushBack(SL*ps,SQDataType x);//頭插
void SeqListPushFront(SL*ps,SQDataType x);//尾插
void SeqListPopBack(SL*ps);//頭刪
void SeqListPopFront(SL*ps);//尾刪
#endif

（2）SeqList.c（動態順序表）

#include"SeqList.h"void SeqListInit(SL*ps)
{
//粗暴一點，先置為空，再改成0，然后capacity也改為0ps->a = NULL;ps->size = 0;ps->capacity = 0;
//當然我們也可以直接malloc
}
//頭插  尾插  頭刪  尾刪
void SeqListPushBack(SL*ps,SQDataType x);
{//滿了就要擴容if(ps->size == ps->capacity){//擴容一般擴兩倍，一個一個太慢了，三倍又太多了，cpp標準庫一般是擴兩倍//我們有兩種思路，一種是新開辟一個兩倍的空間，然后把原來的內容復制過去，另一種是reallocint newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//第一次給多少沒什么講究，給個10也可以，只是說一開始不要給太大，給太大就浪費了//動態管理，就是開始給小一點，不夠了慢慢增加//最小給個1SQDataType* tmp = realloc(ps->a,ps->capacity*2*sizeof(SQDataType));//realloc有可能失敗if(tmp == NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;//ps->capacity *= 2;//這里就不是乘兩倍了，直接是等于newcapacityps->capacity = newcapacity;}}ps->a[ps->size] = x;ps->size++;  
}
void SeqListPushFront(SL*ps,SQDataType x);
void SeqListPopBack(SL*ps);
void SeqListPopFront(SL*ps);void SeqListPrint(SL*ps)
{for(int i = 0;i < ps->size;++i){printf("%d ",ps->a[i]);}printf("\n");
}

（3）test.c

#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPushBack(&sl,6);SeqListPushBack(&sl,7);SeqListPushBack(&sl,8);SeqListPushBack(&sl,9);SeqListPushBack(&sl,10);SeqListPushBack(&sl,11);SeqListPrint(&sl);
}int main()
{TestSeqListl();return 0;
}

這種就是尾插，只要內存夠，我們可以繼續插。不會像靜態順序表那樣，它不需要定義多少個，不夠了就增容，可以一直尾插下去，這就是動態順序表相較于靜態順序表的優越性。

那么uu們可能要問了，realloc不是在原來空間的基礎上擴容嗎？如果原來空間是0怎么辦呢？