一、鏈表的基本操作

初始化

通常會用頭指針來標識一個單鏈表，頭指針為NULL時表示一個空表。但是，為了操作方便，會在單鏈表的名列前茅個結點之前附加一個結點，稱為頭結點。頭結點的數據域可以不設任何信息，也可以記錄表長等信息。頭結點的指針域指向線性表的名列前茅個元素結點。如下圖所示：

頭結點和頭指針的區分：不管帶不帶頭結點，頭指針始終指向單鏈表的名列前茅個結點，而頭結點是帶頭結點的單鏈表中的名列前茅個結點，結點內通常不存儲信息。

?那么單鏈表的初始化操作就是申請一個頭結點，將指針域置空。

void InitList(LinkList &L){

??? L = (LNode *)malloc(sizeof(LinkList));

??? L->next = NULL;

}

建立單鏈表

頭插法建立單鏈表

所謂頭插法建立單鏈表是說將新結點插入到當前鏈表的表頭，即頭結點之后。：

算法思想：首先初始化一個單鏈表，其頭結點為空，然后循環插入新結點*s：將s的next指向頭結點的下一個結點，然后將頭結點的next指向s。

實現代碼：

//頭插法建立單鏈表

LinkList HeadInsert(LinkList &L){

??? InitList(L); //初始化

??? int x;

??? cin>>x;

??? while(x!=9999){ //輸入9999表示結束

??????? LNode *s = (LNode *)malloc(sizeof(LNode));

??????? s->data = x;

??????? s->next = L->next;

??????? L->next = s;

??????? cin>>x;

??? }

??? return L;

}

需要指出的是，頭插法建立的單鏈表中結點的次序和輸入數據的順序不一致，是相反的。若希望兩者的順序是一致的，則可采用尾插法建立單鏈表。

尾插法建立單鏈表

所謂尾插法建立單鏈表，就是將新結點插入到當前鏈表的表尾。如下圖所示：

算法思想：首先初始化一個單鏈表，然后聲明一個尾指針r，讓r始終指向當前鏈表的尾結點，循環向單鏈表的尾部插入新的結點*s，將尾指針r的next域指向新結點，再修改尾指針r指向新結點，也就是當前鏈表的尾結點。最后別忘記將尾結點的指針域置空。

?實現代碼：

//尾插法建立單鏈表

LinkList TailInsert(LinkList &L){

??? InitList(L);

??? LNode *s,*r=L;

??? int x;

??? cin>>x;

??? while(x!=9999){

??????? s = (LNode *)malloc(sizeof(LNode));

??????? s->data = x;

??????? r->next = s;

??????? r = s;

??????? cin>>x;

??? }

??? r->next = NULL;

??? return L;

}

遍歷單鏈表

算法思想：聲明一個指針p，從頭結點指向的名列前茅個結點開始，如果p不為空，那么就輸出當前結點的值，并將p指向下一個結點，直到遍歷到最后一個結點為止。

實現代碼：

//遍歷操作

void PrintList(LinkList L){

??? LNode *p = L->next;

??? while(p){

??????? cout<data<<” “;

??????? p = p->next;

??? }

??? cout<

}

求單鏈表的長度

算法思想：聲明一個指針p，p指向頭結點指向的名列前茅個結點，如果p指向的結點不為空，那么長度加一，將p指向下一個結點，直到遍歷到最后一個結點為止。

實現代碼：

//求單鏈表的長度

int Length(LinkList L){

??? LNode *p = L->next;

??? int len = 0;

??? while(p){

??????? len++;

??????? p = p->next;

??? }

??? return len;

}

延伸閱讀：

二、線性表基本架構

對于一個線性表來說。不管它的具體實現如何，但是它們的方法函數名和實現效果應該一致(即使用方法相同、達成邏輯上效果相同，差別的是運行效率)。線性表的概念與Java的接口/抽象類有那么幾分相似。非常知名的就是List的Arraylist和LinkedList，List是一種邏輯上的結構，表示這種結構為線性表，而ArrayList，LinkedList更多的是一種物理結構(數組和鏈表)。

所以基于面向對象的編程思維，我們可以將線性表寫成一個接口，而具體實現的順序表和鏈表的類可以實現這個線性表的方法，提高程序的可讀性，還有一點比較重要的，記得初學數據結構與算法時候實現的線性表都是固定類型(int),隨著知識的進步，我們應當采用泛型來實現更合理。至于接口的具體設計如下：

package LinerList;

public interface ListInterface {???

??? void Init(int initsize);//初始化表

??? int length();

??? boolean isEmpty();//是否為空

??? int ElemIndex(T t);//找到編號

??? T getElem(int index) throws Exception;//根據index獲取數據

??? void add(int index,T t) throws Exception;//根據index插入數據

??? void delete(int index) throws Exception;

??? void add(T t) throws Exception;//尾部插入

??? void set(int index,T t) throws Exception;

??? String toString();//轉成String輸出???

}

上一篇

依次插入結點法生成二叉排序樹是什么意思?

下一篇

什么是樹的特殊類問題?