資料結構導論(第二章線性表）-有解無憂

一、線性表的基本概念

線性表的邏輯結構線性表是一種最簡單、最常見的資料結構

線性表是由n（n≥0）個資料元素（結點）a1，a2，a3，……an組成的有限序列，資料元素的個數n定義為表的長度，當n=0時，稱為空表

將非空的線性表（n＞0）記作：L=（a1，a2，a3，……，an） a1：起始結點，an：終端結點， a1稱為a2的直接前驅，a3稱為a2的直接后繼

線性表的特點：

線性表中只有1個起始結點，1個終端結點，起始結點沒有直接前驅，有1個直接后繼，
終端結點有1個直接前驅，沒有直接后繼，
除這2個結點外，每個結點都有且只有1個直接前驅和1個直接后繼

二、線性表的順序存盤

線性表順序存盤的方法：將表中的結點依次存放在計算機記憶體中的一組連續存盤單元中，

資料元素在線性表中的鄰接關系決定其在存盤空間中的存盤位置；即邏輯結構中相鄰的結點，其存盤位置也相鄰，

用順序存盤實作的線性表稱為順序表，

順序表上的基本運算： 插入（Insert）、洗掉（Delete）、定位（Locate）

=======================插入=========================

線性表的插入運算：是指在表的位置i上，插入一個新結點x，使長度為n的線性表（a1，a2，……，ai，……，an）變為長度為n+1的線性表（a1，……，x，……，an）

插入時的主義事項：

當表空間已滿，不可再做插入操作，
當插入位置是非法位置，不可做正常的插入操作，

順序表插入操作程序

將表中位置為n ，n-1，…，i上的結點，依次后移到位置n+1，n，…，i+1 上，空出位置i，
在位置i上插入新結點x，（當插入位置i=n+1時，無須移動結點，直接將x插入表的末尾）
該順序表長度加1

插入演算法的分析：

假設線性表中含有n個資料元素，在進行插入操作時，有n+1個位置可插入，每個位置插入資料的概率是：1/(n+1); 在位置i插入時，要移動n-i+1個資料，
假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數為：

需要移動：10-4+1=7 ；7個節點

======================洗掉=====================

線性表的洗掉運算：是指將表的位置i的結點刪去，使長度為n的線性表（a1，a2，……，ai，……，an）變成長度為n-1的線性表（a1，a2，……，ai-1，ai+1，……，an）

注意事項：當要洗掉元素的位置i不在表長范圍內時，為非法位置，不能做正常的洗掉操作

順序表洗掉操作程序

若i=n，則只要洗掉終端結點，無須移動結點；
若1≤i≤n-1，則必須將表中位置 i+1，i+2，……，n的結點，依次前移到位置i，i+1，…，n-1上，以填補洗掉操作造成的空缺，（僅當洗掉位置i=n時，才無須移動結點，直接令表長度-1即可）
該表長度減1

假設線性表中含有n個資料元素，在進行洗掉操作時，有n個位置可洗掉，在位置i洗掉時，要移動n-i個資料，

結論：順序存盤結構表示的線性表，在做插入或洗掉操作時，平均需要移動大約一半的資料元素，當線性表的資料元素量較大，并且經常要對其做插入或洗掉操作時，這一點需要考慮

===================定位=====================

定位:從第一個元素a1起，依次和x比較，直到找到一個與x相等的資料元素，則回傳它在順序表中的存盤下標或序號；當查遍整個表都沒找到與x相等的元素，回傳0，

定位演算法的分析:

定位運算的功能是查找出線性表L中值等于x的結點序號的最小值，當不存在這種結點時，結果為0，

i從0開始，作為掃描順序表時的下標：

最好情況下，第1個元素就是x值，此時查找比較次數為1，
最壞情況下，最后1個元素是x值，此時查找比較次數為n，
故平均查找長度為（n+1）/2，

順序表的特點：

設線性表中所有結點的型別相同，則每個結點所占用存盤空間大小亦相同，
假設表中每個結點占用L個存盤單元，其中第一個單元的存盤地址則是該結點的存盤地址，
并設表中開始結點a1的存盤地址是d，那么結點ai的存儲地址LOC（ai）

順序表的優點：

無需為表示結點間的邏輯關系而增加額外存盤空間
可以方便地隨機存取表中的任一結點

順序表的缺點：

• 插入和洗掉運算不方便，必須移動大量的結點
• 順序表要求占用連續的空間，存盤分配只能預先進行，因此當表長變化較大時，難以確定合適的存盤規模

三、線性表的鏈式存盤

結點結構：

鏈表的具體存盤表示為：

用一組任意的存盤單元來存放，
鏈表中結點的邏輯次序和物理次序不一定相同，還必須存盤指示其后繼結點的地址資訊

=================單鏈表===================

單鏈表：所有結點通過指標鏈接而組成，
NULL：空指標，
Head：頭指標，
尾指標：指向最后一個元素（尾結點）的指標，

單鏈表的一般圖示法：由于我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指標

單鏈表各個結點在記憶體中的存盤位置（物理位置）并不一定連續

頭結點：一般不存資料，利用Head存放該結點地址，在單鏈表中，增加頭結點的目的是方便運算

單鏈表特點總結：

鏈表由頭指標唯一確定，單鏈表可以用頭指標的名字來命名，頭指標名是head3的鏈表可稱為表head3，
起始節點又稱為首結點，無直接前驅，故在無頭結點時，設頭指標head指向首結點，
終端結點又稱尾結點，無直接后繼，故終端結點的指標域為空，即NULL，
除頭結點之外的結點為表結點，為運算操作方便，頭結點中不存資料，

單鏈表的實作：

1、初始化

建立一個空的單鏈表L，InitiateLinkList（L）一個空的單鏈表是一個頭指標和一個頭結點構成的
假設已定義指標變數t，令t指向一個頭結點并令頭結點的next為NULL
注意：產生頭結點時由malloc函式產生一個新節點；動態分配記憶體函式malloc函式格式:（資料型別*）malloc（sizeof（資料型別））如：int *p;p=（int *）malloc（sizeof（int））

空表由一個頭指標和一個頭結點組成，演算法描述如下：LinkList InitiateLinkList( )//建立一個空的單鏈表{LinkList head; //頭指標head=malloc (sizeof (Node) ) ; //動態構建一結點，它是頭結點head->next=NULL;return head;}在演算法中，變數head是鏈表的頭指標，它指向新創建的結點，即頭結點，一個空單鏈表僅有一個頭結點，它的指標域為NULL，

2、求表長

在單鏈表存盤結構中，線性表的長度等于單鏈表所含結點的個數（不含頭結點）

步驟：

1，令計數器j為0
2，令p指向頭結點
3，當下一個結點不空時，j加1，p指向下一個結點
4，j的值即為鏈表中結點個數，即表長度

int lengthLinklist (LinkList head){     Node *p;    p=head; j=0;    while( p->next != NULL )    { p=p->next;    j++;    }    return(j);}

3、讀表元素步驟：查找第i個結點

1、令計數器j為0
2、令p指向頭結點
3、當下一個結點不空時，并且j<i時，j加1，p指向下一個結點
4、如果j等于i，則p所指結點為要找的第i結點否則，鏈表中無第i結點

Node * GetlinkList( LinkList head, int i ){     Node *p;    p=head->next; int c=1;    while ((c<i) && (p!=NULL) ){ p=p->next;        c++;    }    if(i= =c) return(p);    else return NULL;}

4、洗掉節點

演算法思路（此演算法描述洗掉第i個結點）

① 找到第i-1個結點；若存在繼續，否則結束；

② 洗掉第i個結點，并釋放對應的記憶體，結束

洗掉運算是將表的第i個結點刪去，

（1）找到ai-1的存盤位置p

（2）令p-＞next指向ai的直接后繼結點

（3）釋放結點ai的空間，將其歸還給"存盤池" ，

演算法的實作

在單鏈表中洗掉第 i 個結點的基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指標，

void DeleteLinklist(LinkList head, int i)    //洗掉表head的第i個結點    {    Node *q;    if(i==1) q=head;    else q=GetLinklist(head, i-1); //先找待刪結點的直接前驅    if(q !== NULL && q->next != NULL) //若直接前驅存在且待刪結點存在    {        p=q->next; //p指向待刪結點        q->next=p->next; //移出待刪結點        free(p); //釋放已移出結點p的空間    }    else exit (“找不到要洗掉的結點”); //結點不存在}

注意：free(p)是必不可少的，因為當一個結點從鏈表移出后，如果不釋放它的空間，它將變成一個無用的結點，它會一直占用著系統記憶體空間，其他程式將無法使用這塊空間

5. 定位

定位運算是對給定表元素的值，找出這個元素的位置，對于單鏈表，給定一個結點的值，找出這個結點是單鏈表的第幾個結點，定位運算又稱為按值查找

具體步驟：

1、令p指向頭結點
2、令i=0
3、當下一個結點不空時，p指向下一個結點,同時i的值加1
4、直到p指向的結點的值為x，回傳i+1的值，
5、如果找不到結點值為x的話，回傳值為0

int LocateLinklist(LinkList head, DataType x)    //求表head中第一個值等于x的結點的序號，若不存在這種結點，回傳結果為0    {    Node *p=head; //p是作業指標    p=p->next; //初始時p指向首結點    int i=0; //i代表結點的序號，這里置初值為    while (p != NULL && p->data != x) //訪問鏈表    {    i++;    p=p->next;    }    if (p!=NULL) return i+1;    else return 0;}

6、插入

插入運算是將值為x的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間，

具體步驟：

（1）找到ai-1存盤位置p
（2）生成一個資料域為x的新結點*s
（3）令結點*p的指標域指向新結點
（4）新結點的指標域指向結點ai

void InsertLinklist (LinkList head, DataType x, int i)    //在表head的第i個資料元素結點之前插入一個以x為值的新結點    {    Node *p,*q;    if (i==1) q=head;    else q=GetLinklist (head, i-1); //找第 i-1個資料元素結點    if (q==NULL) //第i-1個結點不存在    exit(“找不到插入的位置”);    else    {        p=malloc(sizeof (Node) );p->data=https://www.cnblogs.com/jalja/p/x; //生成新結點        p->next=q->next; //新結點鏈域指向*q的后繼結點        q->next=p; //修改*q的鏈域    }}

注意：鏈接操作p->next=q->next和q->next=p兩條陳述句的執行順序不能顛倒，否則結點 *q的鏈域值（即指向原表第i個結點的指標）將丟失，

7、清除單鏈表中值為x的重復結點

步驟：

1）找到值為x的第一個結點位置，p指向該結點
2）從p所指結點開始向后查找，若存在值為x的結點，令q指向x結點前一個執行洗掉操作繼續查找直到鏈表末尾

void PurgeLinklist(LinkList head)    //洗掉表head中多余的重復結點    {        Node *p,*q,*r;        q=head->next; //q指示當前檢查結點的位置，置其初值指向首結點        while(q!=NULL) //當前檢查結點*q不是尾結點時，尋找并洗掉它的重復結點    {        p=q; //作業指標p指向*q        while(p->next!=NULL) //當*p的后繼結點存在時,將其資料域與*q資料域比較        { if (p->next->data=https://www.cnblogs.com/jalja/p/=q->data) //若*(p->next)是*q的重復結點            {                r=p->next; //r指向待刪結點                p->next = r->next; //移出結點* (p->next)，p->next指向原來* (p->next)的后繼結點                free (r);            }            else p=p->next; //否則，讓p指向下一個結點        }            q=q->next; //更新檢查結點    }}

四、順序表的演算法

線性表的基本運算

1，初始化 Initiate(L) 建立一個空表L=()，L不含資料元素，

2，求表長度 Length(L) 回傳線性表L的長度，

3、取表元 Get(L,i) 回傳線性表第i個資料元素，當i不滿足 1≤i≤Length(L)時，回傳一特殊值

4、定位 Locate(L,x) 查找線性表中資料元素值等于x的結點序號，若有多個資料元素值與x相等，運算結果為這些結點中序號的最小值，若找不到該結點，則運算結果為0

5、插入 Insert(L,x,i) 在線性表L的第i個資料元素之前插入一個值為x的新資料元素，引數i的合法取值范圍是1≤i≤n+1，操作結束后線性表L由（a1，a2，…，ai-1， ai，ai+1，.…，an )變為(a1，a2， …，ai-1，x， ai，ai+1，.…，an )，表長度加 1，

6、洗掉 Delete(L,i) 洗掉線性表L的第i個資料元素ai，i的有效取值范圍是1≤i≤n，洗掉后線性表L由(a1，a2，…，ai-1， ai，ai+1，.…，an )變為 (a1，a2，…，ai-1，ai+1，.…，an )，表長度減1