1.線性表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使 用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串...
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的， 線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
2.順序表
2.1概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存 儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：
1. 靜態(tài)順序表：使用定長數(shù)組存儲元素。
就是給定長度的數(shù)組和有效數(shù)據(jù)個數(shù)。
2. 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
指的是在堆區(qū)開辟出來的動態(tài)數(shù)組，給定數(shù)據(jù)個數(shù)和容量空間大小。
2.2接口實現(xiàn)
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空 間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間 大小，所以下面我們實現(xiàn)動態(tài)順序表。
//順序表的動態(tài)儲存
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a; //指向動態(tài)開辟的數(shù)組
int size; //有效數(shù)據(jù)個數(shù)
int capacity; //容量空間的大小
}SL;
//基本增刪查改接口
void SLInit(SL* ps); //順序表初始化
void SLPushBack(SL* ps，SLDataType x); //順序表尾插
void SLPushFront(SL* ps，SLDataType x); //順序表頭插
void SLPopBack(SL* ps); //順序表尾刪
void SLPopFront(SL* ps); //順序表頭刪
void SLInsert(SL* ps, int pos, SLDataType x); //順序表在pos位插入x
void SLErase(SL* ps, int pos); //順序表刪除pos位的值
int SLFind(SL* psl, SLDataType x); //順序表查找
void SLPrint(SL* ps); //順序表的打印
void SLDestroy(SL* ps); //順序表的銷毀順序表難度較低，接下來我們主要對鏈表進行刨析，理解了鏈表，順序表就手到擒來了。
3.鏈表
3.1鏈表的結(jié)構(gòu)及概念
概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表 中的指針鏈接次序?qū)崿F(xiàn)的 。
其實鏈表就好比作一輛火車，由一條牽引鏈鏈接每一節(jié)車廂。
現(xiàn)實數(shù)據(jù)結(jié)構(gòu)如下；
注意：
- 從上圖可知，鏈?zhǔn)浇Y(jié)構(gòu)邏輯上是連續(xù)的，但是在物理上不一定是連續(xù)的。
- 現(xiàn)實中的節(jié)點是從堆區(qū)上申請出來的。
- 從堆區(qū)上申請出來的空間，是按照一定的策略分配的，可能連續(xù)，也可能不連續(xù)。
3.2鏈表的分類
鏈表可以分為8種鏈表結(jié)構(gòu)：
1.單向或者雙向
2.帶頭或者不帶頭
3.循環(huán)或不循環(huán)
還有倆種分別是：無頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表。
1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié) 構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。
2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都 是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶 來很多優(yōu)勢，實現(xiàn)反而簡單了。
?3.3鏈表的實現(xiàn)
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x); //動態(tài)申請節(jié)點
void SListPrint(SLTNode* plist); //打印單鏈表
void SListPushBack(SLTNode** pphead, SLTDataType x); //單鏈表尾插
void SListPushFront(SLTNode** pphead, SLTDataType x); //單鏈表頭插
void SListPopBack(SLTNode** pphead); //單鏈表尾刪
void SListPopFront(SLTNode** pphead); //單鏈表頭刪
SLTNode* SLFind(SLTNode* phead, SLTDataType x); //單鏈表查找3.4雙向鏈表的實現(xiàn)
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
ListNode* ListCreate(); // 創(chuàng)建返回鏈表的頭結(jié)點.
void ListDestroy(ListNode* pHead); // 雙向鏈表銷毀
void ListPrint(ListNode* pHead); // 雙向鏈表打印
void ListPushBack(ListNode* pHead, LTDataType x); // 雙向鏈表尾插
void ListPushFront(ListNode* pHead,LTDataType x); // 雙向鏈表頭插
void ListPopBack(ListNode* pHead); // 雙向鏈表尾刪
void ListPopFront(ListNode* pHead); // 雙向鏈表頭刪
bool LTEmpty(ListNode* pHead);
ListNode* ListFind(ListNode* pHead, LTDataType x); // 雙向鏈表查找
void ListErase(ListNode* pos); // 雙向鏈表刪除pos位置的結(jié)點
void LTInsert(ListNode* pos, LTDataType x); // 雙向鏈表在pos的前面進行插入
4.順序表和鏈表的區(qū)別
文章來源：http://www.zghlxwxcb.cn/news/detail-807455.html
好啦，本節(jié)知識就到這啦，關(guān)注博主，讓我們一起開碼??！?文章來源地址http://www.zghlxwxcb.cn/news/detail-807455.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】順序表和鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
