定義
線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種狭瞎，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列细移。數(shù)據(jù)元素是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下一般不同熊锭。
在稍復(fù)雜的線性表中弧轧，一個(gè)數(shù)據(jù)元素可由多個(gè)數(shù)據(jù)項(xiàng)（item）組成，此種情況下常把數(shù)據(jù)元素稱為記錄（record）碗殷，含有大量記錄的線性表又稱文件（file）精绎。
線性表中的個(gè)數(shù)n定義為線性表的長(zhǎng)度，n=0時(shí)稱為空表锌妻。在非空表中每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置代乃，如用ai表示數(shù)據(jù)元素，則i稱為數(shù)據(jù)元素ai在線性表中的位序仿粹。
線性表的相鄰元素之間存在著序偶關(guān)系襟己。如用（a1引谜，…，ai-1擎浴，ai员咽，ai+1，…贮预，an）表示一個(gè)順序表贝室，則表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1仿吞，稱ai-1是ai的直接前驅(qū)元素滑频，ai+1是ai的直接后繼元素。當(dāng)i=1,2唤冈，…峡迷，n-1時(shí)，ai有且僅有一個(gè)直接后繼你虹，當(dāng)i=2绘搞，3，…傅物，n時(shí)夯辖，ai有且僅有一個(gè)直接前驅(qū)
抽象數(shù)據(jù)類型
所謂的抽象數(shù)據(jù)類型就是把數(shù)據(jù)類型和相關(guān)炒作綁在一起.
線性表的物理存儲(chǔ)結(jié)構(gòu)
線性表有兩種物理存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
線性表的順序存儲(chǔ)結(jié)構(gòu)
- 順序存儲(chǔ)結(jié)構(gòu)指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
- 線性表順序存儲(chǔ)的結(jié)構(gòu)的結(jié)構(gòu)代碼
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int length;//線性表當(dāng)前長(zhǎng)度
}Sqlist;
- 順序存儲(chǔ)結(jié)構(gòu)封裝需要三個(gè)屬性
①存儲(chǔ)空間的起始位置,數(shù)組data,它的存儲(chǔ)位置就是線性表存儲(chǔ)空間的存儲(chǔ)位置
②線性表的最大存儲(chǔ)容量:數(shù)組長(zhǎng)度MaxSize
③線性表的當(dāng)前長(zhǎng)度:length
獲取元素操作
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等.
//初始條件:順序線性表L已存在
//操作結(jié)果:用e返回L中第i個(gè)數(shù)據(jù)元素的值
Status GetElem(sqlist L, int i ,ElemType *e){
if(L.length == 0 || i< 1 || i>L.length ){
returen ERROR;
}
*e = L.data[i-1];
return OK;
}
插入新元素
插入算法的基本思路
① 如果插入位置不合理,拋出異常
② 如果線性長(zhǎng)度大于等于數(shù)組長(zhǎng)度,拋出異扯危或動(dòng)態(tài)增加數(shù)組容量
③從最后一個(gè)元素開始向前遍歷到第i個(gè)位置,分別將他們都向后移動(dòng)一個(gè)位置
④ 將要插入元素填入位置i處
⑤ 線性表長(zhǎng)+1
Status ListInsert(Sqlist *L ,int i, ElemType e ){
int k;
if(L->length == MAXSIZE)//順序線性表已滿{
return ERROR;
}
if(i<1 | | i>L->length+1)//當(dāng)I不在范圍內(nèi)時(shí){
return ERROR;
}
if(i<=L->length)//若插入數(shù)據(jù)位置不在表尾{
//將要插入位置后數(shù)據(jù)元素向后移動(dòng)一位
for(k = L->length-1;k>=I -1;k--){
L->data[k+1] = L->data[K];
}
}
L->data[I-1] = e;//將新元素插入
L->length++;
return OK;
刪除操作
刪除算法的思路
①如果刪除位置不合理拋出異常
②取出刪除元素
③從刪除元素位置開始遍歷到最后一個(gè)元素位置,分別將他們都向前移動(dòng)一個(gè)位置
④表長(zhǎng)-1
Status ListDelete(Sqlist *L ,int i, ElemType e ){
int k;
if(L->length == 0){
return ERROR;
}
if(i<1 | | i>L->length){
return ERROR;
}
*e = L->data[I-1]
if(i<=L->length){
for(k =I; k<L->length;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
插入和刪除時(shí)間復(fù)雜度分析
- 最好情況:插入和刪除操作剛好要求放在最后一個(gè)位置,因?yàn)椴灰苿?dòng)人和元素所以時(shí)間復(fù)雜度為O(1)
- 最壞情況:如果插入和刪除位置都是第一個(gè),那就意味著要移動(dòng)所有元素向后或向前,所以這個(gè)時(shí)間復(fù)雜度為O(n)
- 平均情況:就取中間值O((n-1)/2),其復(fù)雜度簡(jiǎn)后還是O(n)
- 線性表的順序存儲(chǔ)結(jié)構(gòu),在存讀數(shù)據(jù)時(shí),不管是哪個(gè)位置,時(shí)間復(fù)雜度都是O(1)蒿褂。而在插入或刪除時(shí),時(shí)間復(fù)雜度都是O(n)
- 說明它比較適合元素個(gè)數(shù)比較穩(wěn)定,不經(jīng)常插入和刪除元素,而更多的操作是存取數(shù)據(jù)的應(yīng)用
線性表順序存儲(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ǔ)空間的碎片
線性表的鏈性存儲(chǔ)結(jié)構(gòu)
線性表的順序存儲(chǔ)結(jié)構(gòu)最大缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量元素,需要耗費(fèi)時(shí)間,其原因就在于相鄰兩元素的存儲(chǔ)位置也具有鄰居關(guān)系,它們?cè)趦?nèi)存中的位置是緊挨著,中間沒有間隙,無法快速的插入和刪除,所以要移動(dòng)大量元素,于是就有了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
定義
- 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)就是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素,這組存儲(chǔ)單元可以在內(nèi)存中未被占用的仍以位置
- 比起順序存儲(chǔ)結(jié)構(gòu)每個(gè)數(shù)據(jù)元素秩序要存儲(chǔ)一個(gè)位置就可以了。現(xiàn)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,除了要存儲(chǔ)數(shù)據(jù)元素信息外,還要存儲(chǔ)它餓后續(xù)元素的存儲(chǔ)地址(指針)
- 我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域,把存儲(chǔ)直接后繼位置的域稱為指針域卒暂。指針域中存儲(chǔ)的信息稱為指針或鏈.這兩部分?jǐn)?shù)據(jù)元素稱為存儲(chǔ)映像,稱為節(jié)點(diǎn)(Node)
- n 個(gè)節(jié)點(diǎn)鏈接成一個(gè)鏈表,即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
-
因此此鏈表的每個(gè)節(jié)點(diǎn)中只包含一個(gè)指針域,多以叫做單鏈表
單鏈表
對(duì)于線性表來說,總得有個(gè)頭有個(gè)尾,鏈表也不例外啄栓。我們把鏈表中的第一個(gè)節(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針,最后一個(gè)節(jié)點(diǎn)指針為空(NULL)
頭指針與頭結(jié)點(diǎn)的異同
頭指針:
- 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針,若鏈表有頭結(jié)點(diǎn),則是指向頭結(jié)點(diǎn)的指針
- 頭指針具有標(biāo)識(shí)作用,所以常用頭指針冠以鏈表的名字(指針變量的名字)
- 無論鏈表是否為空,頭指針均不為空
- 頭指針是鏈表的必要元素
頭結(jié)點(diǎn):
- 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便we設(shè)立的,放在第一個(gè)元素的節(jié)點(diǎn)之前,其數(shù)據(jù)一般無意義(但也可以用來存放鏈表的長(zhǎng)度)
- 有了頭結(jié)點(diǎn),對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)起操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了
-
頭結(jié)點(diǎn)不一定是鏈表的必須要素
單鏈表圖例
單鏈表的存儲(chǔ)結(jié)構(gòu)
在C語言中可以用結(jié)構(gòu)指針來描述單鏈表
typedef struct Node{
ElemType data; //數(shù)據(jù)域
struct Node* Next;//指針域
}Node;
typedef struct Node* LinkList;
//可以看出結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成
單鏈表的讀取
- 在線性表的順序存儲(chǔ)結(jié)構(gòu)中,我們要計(jì)算任意一個(gè)元素的存儲(chǔ)位置是很容易的,但在單鏈表中由于第I個(gè)元素到底在哪?我們壓根沒辦法一開始就知道,必須得從第一個(gè)節(jié)點(diǎn)開始挨個(gè)找.
- 獲得鏈表第i個(gè)數(shù)據(jù)的算法思路
①聲明一個(gè)節(jié)點(diǎn)p指向鏈表第一個(gè)節(jié)點(diǎn),初始化j從1開始
②當(dāng)j<i時(shí),就遍歷鏈表,讓p的指針向后移動(dòng),不斷指向下一個(gè)節(jié)點(diǎn),j+1
③若到鏈表末尾p為空,則說明第i個(gè)元素不存在
④否則查找成功,返回節(jié)點(diǎn)P的數(shù)據(jù)
上代碼:
Status GetElem(LinkList L, int I, ElemType *e){
int j;
LinkList p;
p = L->next;
j = 1;
while(p && j <i){
p = p->next;
++j;
}
if( !p || j>i){
return ERROR;
}
*e = p->data;
return OK;
}
- 說白了就是從頭開始找,直到第i個(gè)元素為止
- 由于這個(gè)算法的時(shí)間復(fù)雜度取決于i的位置每當(dāng)i=1時(shí),則不需要遍歷,而i=n時(shí)則需要遍歷n-1次才可以.因此最壞情況的時(shí)間復(fù)雜度為O(n)
- 由于單鏈表的結(jié)構(gòu)中沒有有定義表長(zhǎng),所以不能實(shí)現(xiàn)直到要循環(huán)多少次,因此不方便用for來控制循環(huán)
- 其核心思想叫做"工作指針后移" ,這其實(shí)也是很多算法的常用技術(shù)
單鏈表的插入
如圖我們發(fā)現(xiàn)不用改變其他結(jié)點(diǎn),只需要讓s->next和p->next的指針做一點(diǎn)改變即可
s->next = p->next;
p->next = s;
單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)算法思路:
- 聲明一結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn),初始化j從1開始
- 當(dāng)j<1時(shí),就遍歷鏈表,讓p的指針向后移動(dòng),不斷指向下一結(jié)點(diǎn),j累計(jì)+1
- 若到鏈表末尾p為空,則說明第i個(gè)元素不存在
- 否則查找成功,在系統(tǒng)中生成一個(gè)空節(jié)點(diǎn)s;
- 將數(shù)據(jù)元素e復(fù)制給s->data
- 單鏈表的插入剛才兩個(gè)標(biāo)準(zhǔn)語句
- 返回成功
Status ListInsert(LinkList *L ,int I, ELemType e){
int j;
LinkList p,s;
p = *L;
j = 1;
while(p && j<1){
p = p->next;
j++;
}
if( !p || j>1){
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
單鏈表的刪除
![]()
假設(shè)a2的結(jié)點(diǎn)為q,要實(shí)現(xiàn)結(jié)點(diǎn)q刪除單鏈表的操作,其實(shí)就是將它的前結(jié)點(diǎn)的指針繞過指向后繼結(jié)點(diǎn)即可
即: p->next = p->next->next;
單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)算法思路:
- 聲明一結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn),初始化j=1
- 當(dāng)j<1時(shí),就遍歷鏈表,讓p的指針向后移動(dòng),不斷指向下一結(jié)點(diǎn),j累計(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)
Status ListDelete(LinkList *L ,int I, ELemType *e){
int j;
LinkList p,q;
p = *L;
j = 1;
while(p->next && j<1){
p = p->next;
++j;
}
if( !(p->next) || j>1){
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
效率PK
- 我們發(fā)現(xiàn)無論是單鏈表插入還是刪除算法,它們其實(shí)都是由兩部分組成:第一部分就是遍歷查找第i個(gè)元素,第二部分就是實(shí)現(xiàn)插入和刪除元素;
- 從整個(gè)算法來說,我們很容易可以推測(cè)出它們的時(shí)間復(fù)雜度都是O(n);
- 再詳細(xì)點(diǎn)分析:如果我們不知道第i元素的指針位置;單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上與線性表的順序存儲(chǔ)結(jié)構(gòu)是沒有太大優(yōu)勢(shì)的
- 但如果,我們希望從第i和位置開始,插入連續(xù)10個(gè)元素,對(duì)于順序存儲(chǔ)結(jié)構(gòu)意味著,每一次插入都需要移動(dòng)n-i個(gè)位置,多以每次都是0(n);二而單鏈表,我們只需要在第一次時(shí),找到第i個(gè)位置的指針,此時(shí)為O(n),接下來只是簡(jiǎn)單的通過賦值移動(dòng)指針而已,時(shí)間復(fù)雜度都是O(1)
- 顯然,對(duì)于插入或刪除數(shù)據(jù)越頻繁的操作,單鏈表的優(yōu)勢(shì)就是越是明顯的
單鏈表的整表創(chuàng)建
- 對(duì)于順序存儲(chǔ)結(jié)構(gòu)的線性表的整表創(chuàng)建,我們可以用數(shù)組的初始化來直觀理解
- 而單鏈表和順序存儲(chǔ)結(jié)構(gòu)就不一樣了,他不像順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)那么集中,他的數(shù)據(jù)可以是分散在內(nèi)存各個(gè)角落的,他的增長(zhǎng)也是動(dòng)態(tài)的
- 對(duì)于每個(gè)鏈表來說,它所占用空間的大小和位置是不需要事先分配劃定的,可以根據(jù)系統(tǒng)的情況和實(shí)際的需求即時(shí)生成
創(chuàng)建單鏈表的過程是一個(gè)動(dòng)態(tài)生成鏈表的過程,從空表的初始狀態(tài)起,依次建立各元素結(jié)點(diǎn)并逐個(gè)插入鏈表
單鏈表的整表創(chuàng)建的算法思路如下:
- 聲明一結(jié)點(diǎn)p和計(jì)數(shù)器變量i
- 初始化一空鏈表L
- 讓L的頭結(jié)點(diǎn)的指針指向Null,即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表
- 循環(huán)實(shí)現(xiàn)后繼結(jié)點(diǎn)的賦值和插入
頭插法建立單鏈表
頭插法從一個(gè)空表開始,生成新結(jié)點(diǎn),讀取數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到結(jié)束為止
簡(jiǎn)單來說,就是把新加進(jìn)的元素放在表頭后的第一個(gè)位置
- 先讓新結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)之后
- 然后讓表頭的next指向新結(jié)點(diǎn)
上代碼
void CreatListHead(LinkList *L, int n){
LinkList p;
int I;
srand(time(0));初始化隨機(jī)數(shù)
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for (I = 0 ;I <n; I++){
p =(LinkList)malloc(sizeof(Node));
p->data = rand()%100+1;
p->next = (*L)->next;
(*L )->next = p;
}
}
頭部法生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序是相反的
尾部發(fā)建立單鏈表
上代碼
void CreatListTail(LinkList *L, int n){
LinkList p,r;
int I;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for( I = 0;i<n;i++){
p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;
r->next = p;
r = p;
}
r->next = NULL;
}
單鏈表的整表刪除
單鏈表整表刪除的算法思路
- 聲明結(jié)點(diǎn)p和q
- 將第一個(gè)結(jié)點(diǎn)賦值給p,下一個(gè)結(jié)點(diǎn)賦值給q
- 循環(huán)執(zhí)行釋放p和將q賦值給p的操作
上代碼
Status ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q = p->next;
free(p);
p=q;
}
(*L)->next = NULL;
return OK;
}
單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)
從存儲(chǔ)分配方式,時(shí)間性能,空間性能三方面來對(duì)比
存儲(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)
- 單鏈表在計(jì)算出某位置的指針后,插入和刪除時(shí)間僅為O(1)
空間性能
- 順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間,分大了,容易造成空間浪費(fèi),分小了,容易發(fā)生溢出
- 單鏈表不需要分配存儲(chǔ)空間,只要有就可以分配,元素個(gè)數(shù)也不受限制
綜上:若線性表需要頻繁的查找,很少進(jìn)行插入和刪除操作宜采用順序存儲(chǔ)結(jié)構(gòu);若需頻繁插入和刪除時(shí),宜采用單鏈表結(jié)構(gòu)
