定義：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列
線性表的順序存儲(chǔ)的結(jié)構(gòu)代碼注盈。
#define MAXSIZE 20 /*存儲(chǔ)空間初始分配量*/
typedef int ElemType; /*Elemtype類型根據(jù)實(shí)際情況而定引润， 這里假設(shè)為int*/
typedef struct
ElemType data [MAXSIZE);
int length;
} SqList;
這里飞崖，我們就發(fā)現(xiàn)描述順序存儲(chǔ)結(jié)構(gòu)需要三個(gè)屬性:
- 存儲(chǔ)空間的起始位置:數(shù)組data ，它的存儲(chǔ)位置就是存儲(chǔ)空間的存儲(chǔ)位置颖御。
- 線性表的最大存儲(chǔ)容量: 數(shù)組長(zhǎng)度MaxSize 银酬。
- 線性表的當(dāng)前長(zhǎng)度: length .
線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
- 無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
- 可以快速地存取表中任一位置的元素
缺點(diǎn)
- 插入和刪除操作需要移動(dòng)大量元素
- 當(dāng)線性表長(zhǎng)度變化較大時(shí)嘲更，難以確定存儲(chǔ)空間的容量
- 造成存儲(chǔ)空間的"碎片"
頭指針與頭結(jié)點(diǎn)的區(qū)別
頭指針
- 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，著鏈表有頭結(jié)點(diǎn)揩瞪，則是指向頭結(jié)點(diǎn)的指針
- 頭指針有標(biāo)識(shí)作用赋朦，所以常用頭指針冠以鏈表的名字
- 無論鏈表是否為空.頭指針均不為空。頭指針是鏈表由與必要元素
頭結(jié)點(diǎn)
- 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的李破，放在第一個(gè)的結(jié)點(diǎn)之前宠哄，其數(shù)據(jù)域一鍛無意義(也可存儲(chǔ)鏈表的長(zhǎng)度)
- 有了頭結(jié)點(diǎn).對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其它結(jié)點(diǎn)操作就統(tǒng)一
- 頭結(jié)點(diǎn)不一定是鏈表的必要元素
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素嗤攻，這組存儲(chǔ)單元可以是連續(xù)的毛嫉，也可以是不連續(xù)的。這就意味著妇菱，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置
為了表示每個(gè)數(shù)據(jù)元素al 與其直接后繼數(shù)據(jù)元素al+1 之間的邏輯關(guān)系承粤， 對(duì)
數(shù)據(jù)元素a1來說,除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指向其直接后繼的信息(即直接后繼的存儲(chǔ)位置)闯团。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域辛臊，把存儲(chǔ)直接后繼位置的域稱為指針域。 指針域中存儲(chǔ)的信息稱做指針或鏈房交。這兩部分信息組成數(shù)據(jù)元素ai 的存儲(chǔ)映像彻舰，稱為結(jié)點(diǎn)(Node) 。
n 個(gè)結(jié)點(diǎn)( al 的存儲(chǔ)映像) 鏈結(jié)成一個(gè)鏈表涌萤，即為線性表( a1 淹遵， a2,…, an ) 的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域负溪，所以叫做單鏈表。
線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)頭指針與頭結(jié)點(diǎn)的異同
頭指針
- 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針济炎，著鏈表有頭結(jié)點(diǎn)川抡，則是指向頭結(jié)點(diǎn)的指針
- 頭船指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字
- 無論鏈表是否為空.頭指針均不為空。頭指針是鏈表的必要元素
頭結(jié)點(diǎn)
- 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的崖堤，放在第一個(gè)元素的結(jié)點(diǎn)之前侍咱，其數(shù)據(jù)域一般無意義(也可存儲(chǔ)鏈表的長(zhǎng)度)
- 有了頭結(jié)點(diǎn).對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了
- 頭結(jié)點(diǎn)不一定是鏈表的必要元素
單鏈表整表創(chuàng)建的算法思路:
- 聲明一結(jié)點(diǎn)p 和計(jì)數(shù)器變量i ;
- 初始化一空鏈表L;
- 讓L的頭結(jié)點(diǎn)的指針指向NULL 密幔，即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表i
- 循環(huán):
- 生成一新結(jié)點(diǎn)賦值給p;
- 隨機(jī)生成一數(shù)字賦值給p 的數(shù)據(jù)域p->data;
- 將p插入到頭結(jié)點(diǎn)與前一新結(jié)點(diǎn)之間楔脯。
獲得鏈表第i個(gè)數(shù)據(jù)的算法思路:
- 聲明一個(gè)結(jié)點(diǎn)p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j 從1 開始;
- 當(dāng)j<i 時(shí)胯甩，就遍歷鏈表昧廷，讓p 的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)偎箫， j 累加1;
- 若到鏈表末尾p 為空木柬，則說明第i 個(gè)元素不存在;
- 否則查找成功，返回結(jié)點(diǎn)p 的數(shù)據(jù)淹办。
單鏈表第i 個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路:
- 聲明一結(jié)點(diǎn)p 指向鏈表第一個(gè)結(jié)點(diǎn)眉枕，初始化j 從1 開始i
- 當(dāng)j<i 時(shí)，就遍歷鏈表怜森，讓p 的指針向后移動(dòng)速挑，不斷指向下一結(jié)點(diǎn)， j 累加1;
- 若到鏈表末尾p 為空副硅，則說明第i 個(gè)元素不存在i
- 否則查找成功姥宝，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)s;
- 將數(shù)據(jù)元素e 賦值給s->也ta ;
- 單鏈表的插入標(biāo)準(zhǔn)語句s->next=p->next; p->next=s ;
- 返回成功。
單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路:
- 聲明一結(jié)點(diǎn)p 指向鏈表第一個(gè)結(jié)點(diǎn)想许， 初始化j 從1 開始j
- 當(dāng)j<i就遍歷鏈表伶授，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)j累加1
- 若到鏈表末尾p 為空流纹，則說明第i個(gè)元素不存在;
- 否則查找成功糜烹，將欲刪除的結(jié)點(diǎn)p->next賦值給q ;
- 單鏈表的刪除標(biāo)準(zhǔn)語句p->next=q->next;
- 將q結(jié)點(diǎn)中的數(shù)據(jù)賦值給e，作為返回;
- 釋放q結(jié)點(diǎn);
- 返回成功漱凝。
單鏈表整表刪除的算法思路如下:
- 聲明一結(jié)點(diǎn)p 和q ;
- 將第一個(gè)結(jié)點(diǎn)賦值給p;
- 循環(huán):
- 將下一結(jié)點(diǎn)賦值給q;
- 釋放p;
- 將q 賦值給p 疮蹦。
單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)
存儲(chǔ)分配方式
- 順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素
- 單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的元素
時(shí)間性能
- 查找
- 順序存儲(chǔ)結(jié)構(gòu)o(1)
- 插入和刪除
- 單鏈表o(n)
- 順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一半的元素茸炒，時(shí)間為o(n)
- 單鏈表在線出某位置的指針后愕乎，插入和刪除的時(shí)間僅為o(1)
空間性能
- 順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了壁公，浪費(fèi)感论，分小了易發(fā)生上溢
- 單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配紊册，元素個(gè)數(shù)也也不受限制
歡迎關(guān)注比肄，后續(xù)貼上相關(guān)代碼和新的內(nèi)容，總結(jié)備忘……
