1、簡(jiǎn)介
- 線(xiàn)性表的數(shù)據(jù)對(duì)象集合為 {a1报咳，a2侠讯，.....挖藏，an }暑刃，每個(gè)元素的類(lèi)型均為 DataType
- 其中，除第一個(gè)元素 a1 外膜眠，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素岩臣，除最后一個(gè)元素 an 外溜嗜，每一個(gè)元素有且只有一個(gè)直接后繼元素
- 數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系
2、基本操作
InitList(*L) 初始化操作架谎，建立一個(gè)空的線(xiàn)性表L
ListEmpty(L) 若線(xiàn)性表為空炸宵，返回 true，否則返回 false
ClearList(*L) 將線(xiàn)性表清空
GetElem(L, i, *e) 將線(xiàn)性表 L 中的第 i 個(gè)位置元素值返回給 e
LocateElem(L, e) 在線(xiàn)性表 L 中查找給定值 e 相等的元素谷扣，如果查找成功土全，返回該元素在表中序號(hào)表示成功；
否則会涎，返回 0 表示失敗
ListInsert(*L, i, e) 在線(xiàn)性表 L 中的第 i 個(gè)位置插入新元素 e
ListDelete(*L, i, *e) 刪除線(xiàn)性表 L 中第 i 個(gè)位置元素裹匙，并用 e 返回其值
ListLength(L) 返回線(xiàn)性表 L 中的元素個(gè)數(shù)
3、存儲(chǔ)結(jié)構(gòu)
3.1末秃、順序存儲(chǔ)結(jié)構(gòu)
-
用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素 (用一維數(shù)組來(lái)實(shí)現(xiàn))
線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)代碼如下
#define MAXSIZE 20 // 存儲(chǔ)空間初始分配量
typedef int ElemType; // ElemType 類(lèi)型根據(jù)實(shí)際情況而定概页，這里假設(shè)為 int
typedef struct{
ElemType data[MAXSIZE]; // 數(shù)組存儲(chǔ)數(shù)據(jù)元素，最大值 MAXSIZE
int length; // 線(xiàn)性表當(dāng)前長(zhǎng)度
}SqList;
- 獲取元素
將線(xiàn)性表 L 中的第 i 個(gè)位置元素值返回給 e
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/* 初始條件：順序線(xiàn)性表L已存在练慕，1≤i≤ListLength(L) */
/* 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值,注意i是指位置惰匙，第1個(gè)位置的數(shù)組是從0開(kāi)始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
- 插入元素
在線(xiàn)性表 L 中的第 i 個(gè)位置插入新元素 e
/* 初始條件：順序線(xiàn)性表L已存在,1≤i≤ListLength(L)， */
/* 操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e铃将，L的長(zhǎng)度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length == MAXSIZE) /* 順序線(xiàn)性表已經(jīng)滿(mǎn) */
return ERROR;
if (i<1 || i > L->length+1)/* 當(dāng)i比第一位置小或者比最后一位置后一位置還要大時(shí) */
return ERROR;
if (i <= L->length) /* 若插入數(shù)據(jù)位置不在表尾 */
{
for(k = L-> length; k >= i;k--) /* 將要插入位置之后的數(shù)據(jù)元素向后移動(dòng)一位 */
L->data[k] = L->data[k - 1];
}
L->data[i-1]=e; /* 將新元素插入 */
L->length++;
return OK;
}
- 刪除元素
刪除線(xiàn)性表 L 中第 i 個(gè)位置元素项鬼，并用 e 返回其值
/* 初始條件：順序線(xiàn)性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素劲阎，并用e返回其值秃臣，L的長(zhǎng)度減1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length == 0) /* 線(xiàn)性表為空 */
return ERROR;
if (i<1 || i>L->length) /* 刪除位置不正確 */
return ERROR;
*e = L->data[i-1];
if (i < L->length) /* 如果刪除不是最后位置 */
{
for(k = i-1; k < L->length-1; k++)/* 將刪除位置后繼元素前移 */
L->data[k]=L->data[k+1];
}
L->length--;
return OK;
}
- 總結(jié)
優(yōu)點(diǎn)：１、無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
2哪工、可以快速地存取表中任一位置的元素
缺點(diǎn)：１奥此、插入和刪除操作需要移動(dòng)大量的元素
２雁比、當(dāng)線(xiàn)性表長(zhǎng)度變化較大時(shí)稚虎，難以確定存儲(chǔ)空間的容量
３偎捎、造成存儲(chǔ)空間的 "碎片"
3.2蠢终、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
-
如下圖所示，如同一條鏈子一樣存儲(chǔ)信息
- 為了表示每個(gè)數(shù)據(jù)元素 ai 與其直接后繼數(shù)據(jù)元素 ai+1 之間的邏輯關(guān)系茴她，對(duì)數(shù)據(jù)元素 ai 來(lái)說(shuō)寻拂，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息(即直接后繼的存儲(chǔ)位置)丈牢。
我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱(chēng)為數(shù)據(jù)域祭钉，把存儲(chǔ)直接后繼位置的域稱(chēng)為指針域。
指針域中存儲(chǔ)的信息稱(chēng)為指針或鏈己沛。這兩部分信息組成數(shù)據(jù)元素 a1 的存儲(chǔ)映像慌核，稱(chēng)為節(jié)點(diǎn) (Node)
- 頭指針與頭結(jié)點(diǎn)的異同
頭指針：
1距境、頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)垮卓，則是指向頭結(jié)點(diǎn)的指針
2垫桂、頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字
頭結(jié)點(diǎn)：
1粟按、頭結(jié)點(diǎn)是為了操作統(tǒng)一和方便而設(shè)立的诬滩，放在第一元素的結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義(也可存放鏈表的長(zhǎng)度)
2灭将、有了頭結(jié)點(diǎn)碱呼，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了
3宗侦、頭結(jié)點(diǎn)不一定是鏈表必須要素 - 單鏈表存儲(chǔ)結(jié)構(gòu)
typedef int ElemType; /* ElemType類(lèi)型根據(jù)實(shí)際情況而定愚臀，這里假設(shè)為int */
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定義LinkList */
- 單鏈表的讀取
/* 初始條件：順序線(xiàn)性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* 聲明一結(jié)點(diǎn) p */
p = L->next; /* 讓 p 指向鏈表 L 的第一個(gè)結(jié)點(diǎn) */
j = 1; /* j 為計(jì)數(shù)器 */
while (p && j<i) /* p 不為空或者計(jì)數(shù)器 j 還沒(méi)有等于 i 時(shí)矾利，循環(huán)繼續(xù) */
{
p = p->next; /* 讓 p 指向下一個(gè)結(jié)點(diǎn) */
++j;
}
if ( !p || j>i )
return ERROR; /* 第 i 個(gè)元素不存在 */
*e = p->data; /* 取第 i 個(gè)元素的數(shù)據(jù) */
return OK;
}
- 單鏈表的插入
/* 初始條件：順序線(xiàn)性表 L 已存在,1 ≤ i ≤ ListLength(L) */
/* 操作結(jié)果：在 L 中第 i 個(gè)位置之前插入新的數(shù)據(jù)元素 e姑裂，L 的長(zhǎng)度加 1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i) /* 尋找第i個(gè)結(jié)點(diǎn) */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* 第i個(gè)元素不存在 */
s = (LinkList)malloc(sizeof(Node)); /* 生成新結(jié)點(diǎn)(C語(yǔ)言標(biāo)準(zhǔn)函數(shù)) */
s->data = e;
s->next = p->next; /* 將p的后繼結(jié)點(diǎn)賦值給s的后繼 */
p->next = s; /* 將s賦值給p的后繼 */
return OK;
}
- 單鏈表的刪除
/* 初始條件：順序線(xiàn)性表 L 已存在，1 ≤ i ≤ ListLength(L) */
/* 操作結(jié)果：刪除L的第 i 個(gè)數(shù)據(jù)元素男旗，并用 e 返回其值舶斧，L 的長(zhǎng)度減 1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
while (p->next && j < i) /* 遍歷尋找第 i 個(gè)元素 */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* 第i個(gè)元素不存在 */
q = p->next;
p->next = q->next; /* 將q的后繼賦值給p的后繼 */
*e = q->data; /* 將q結(jié)點(diǎn)中的數(shù)據(jù)給e */
free(q); /* 讓系統(tǒng)回收此結(jié)點(diǎn)，釋放內(nèi)存 */
return OK;
}
- 單鏈表的整表創(chuàng)建
頭插法
/* 隨機(jī)產(chǎn)生n個(gè)元素的值察皇，建立帶表頭結(jié)點(diǎn)的單鏈線(xiàn)性表L（頭插法） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); /* 初始化隨機(jī)數(shù)種子 */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; /* 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /* 生成新結(jié)點(diǎn) */
p->data = rand()%100+1; /* 隨機(jī)生成100以?xún)?nèi)的數(shù)字 */
p->next = (*L)->next;
(*L)->next = p; /* 插入到表頭 */
}
}
尾插法
/* 隨機(jī)產(chǎn)生n個(gè)元素的值茴厉，建立帶表頭結(jié)點(diǎn)的單鏈線(xiàn)性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0)); /* 初始化隨機(jī)數(shù)種子 */
*L = (LinkList)malloc(sizeof(Node)); /* L為整個(gè)線(xiàn)性表 */
r=*L; /* r為指向尾部的結(jié)點(diǎn) */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /* 生成新結(jié)點(diǎn) */
p->data = rand()%100+1; /* 隨機(jī)生成100以?xún)?nèi)的數(shù)字 */
r->next=p; /* 將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn) */
r = p; /* 將當(dāng)前的新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn) */
}
r->next = NULL; /* 表示當(dāng)前鏈表結(jié)束 */
}
- 單鏈表的整表刪除
/* 初始條件：順序線(xiàn)性表L已存在。操作結(jié)果：將L重置為空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向第一個(gè)結(jié)點(diǎn) */
while(p) /* 沒(méi)到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 頭結(jié)點(diǎn)指針域?yàn)榭?*/
return OK;
}
- 單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)
存儲(chǔ)分配方式: 1什荣、順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素
2矾缓、單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線(xiàn)性表的元素
時(shí)間性能: 1稻爬、查找: 順序存儲(chǔ)結(jié)構(gòu)O(1)嗜闻； 單鏈表O(n)
2、插入和刪除: 順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一半的元素桅锄，時(shí)間O(n)琉雳；
單鏈表在找出某位置的指針后，插入和刪除時(shí)間僅為O(1)
空間性能: 1友瘤、順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間翠肘，分大了，浪費(fèi)辫秧；分小了束倍，易發(fā)生浪費(fèi)
2、單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配肌幽，元素個(gè)數(shù)也不受限制
- 經(jīng)驗(yàn)性結(jié)論
若線(xiàn)性表需要頻繁查找，很少進(jìn)行插入和刪除操作時(shí)抓半，宜采用順序存儲(chǔ)結(jié)構(gòu)喂急。
若需要頻繁插入和刪除時(shí)，宜采用單鏈表結(jié)構(gòu)
4笛求、靜態(tài)鏈表
用數(shù)組來(lái)代替指針廊移，來(lái)描述單鏈表。
我們把這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表
優(yōu)點(diǎn): 在插入和刪除操作時(shí)探入，只需要修改游標(biāo)狡孔，不需要移動(dòng)元素，從而改進(jìn)了在順序存儲(chǔ)結(jié)構(gòu)中的插入和刪除操作需要移動(dòng)大量元素的缺點(diǎn)
缺點(diǎn): 沒(méi)有解決連續(xù)存儲(chǔ)分配帶來(lái)的表長(zhǎng)難以確定的問(wèn)題蜂嗽；失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的特性
5苗膝、循環(huán)鏈表
將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)植旧，這種頭尾相接的單鏈表稱(chēng)為單循環(huán)鏈表辱揭，簡(jiǎn)稱(chēng)循環(huán)鏈表
6、雙向鏈表
雙向鏈表是在單鏈表的每個(gè)結(jié)點(diǎn)中病附，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域问窃。
所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼完沪，另一個(gè)指向直接前驅(qū)域庇。
線(xiàn)性表結(jié)構(gòu)圖解
