1.單鏈表的定義

? ? ? ? 單鏈表解決了順序表需要大量連續(xù)存儲單元的缺點，但單鏈表附加指針域，存儲密度較順序表低（考點?。。?/span>。由于單鏈表的元素離散地分布在存儲空間中，所以單鏈表是非隨機存取的存儲結構，即不能直接找到表中某個特定的結點。當查找某個特定結點時，需要從表頭開始遍歷。

????????通常使用頭指針來標識一個單鏈表，如單鏈表L，頭指針為NULL時表示一個空表。為了操作上的方便，可以在單鏈表的第一個結點之前附加一個頭結點。頭結點一般不存儲數(shù)據(jù)，它的數(shù)據(jù)域可以不設任何信息，或記錄表長等信息；頭結點的指針域指向線性表的第一個元素結點。

為什么要引入頭結點呢？

引入頭結點后，可以帶來兩個優(yōu)點：

①由于第一個數(shù)據(jù)結點的位置被存放在頭結點的指針域中，因此在鏈表第一個位置上的操作和在表的其他位置上的操作一致，無須進行特殊處理。

②無論鏈表是否為空，其頭指針都是指向頭結點的非空指針（空表中頭結點的指針域為空），因此空表和非空表的操作也得到了統(tǒng)一。

單鏈表的結點類型定義

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

關于定義的幾點說明：

1.在單鏈表的定義中不能省略結構體名稱LNode（第2行中）。原因：在該結構體內部使用到了該結構體類型去定義next指針域。

2.第5行中的重命名LNode和*LinkList的意義：

這里相當于以下兩句：

typedef struct LNode LNode;//將結構體重命名為LNode

typedef struct LNode *LinkList;//將結構體的指針重命名為LinkList

LNode和LinkList的區(qū)別：

1. LNode是一個具象的結構體類型，指向的是包含某個數(shù)據(jù)類型的數(shù)據(jù)域和指針域的結構體類型。
2. 而LinkList是LNode的指針類型，它占用一定的內存空間，內存空間中存放的值是一個LNode類型結構體的地址。

2.單鏈表的基本操作實現(xiàn)

（1）頭插法建立單鏈表

LinkList list_head_insert(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));//申請頭節(jié)點空間
    L->next=NULL;
    ElemType x;
    scanf("%d", &x);
    LNode* s;//用來指向申請的新節(jié)點

    while(x!=9999)//輸入9999表示結束
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;//s的next指向原本鏈表的第一個節(jié)點
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

【注】：這里有一個常見的錯誤：分配結點空間的語句

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

錯誤寫法：L = (LinkList)malloc(sizeof(LinkList));

要謹記：LinkList是LNode的指針類型，不代表結構體（該指針一般占用8個字節(jié)的空間）而這里需要的是分配的LNode大小的空間。

頭插法建立單鏈表 時間復雜度分析

采用頭插法建立單鏈表時，讀入數(shù)據(jù)的順序與生成的鏈表中的元素順序相反。每個結點插入的時間為O(1)，設單鏈表長為n，則總時間復雜度為O(n).

（2）尾插法建立單鏈表?

尾插法的特點：

始終存在一個尾指針r指向鏈表的尾部，且讀入數(shù)據(jù)的順序與生成鏈表中元素的順序相同。

LinkList list_tail_insert(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    ElemType x;
    scanf("%d", &x);
    LNode *s, *r=L;//s用來指向申請的新節(jié)點，r始終指向鏈表尾部
    while(x!=9999)//輸入9999表示結束
    {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;//新節(jié)點給尾節(jié)點的next指針
        r=s;//r要指向新的尾部
        scanf("%d", &x);
    }
    r->next = NULL;//讓尾節(jié)點為Null
    return L;
}

尾插法建立單鏈表的時間復雜度分析?

?尾插法的時間復雜度與頭插法相同，都是O(n)。

?（3）按位查找結點

//按位置查找
LNode* GetElem(LinkList L, int SearchPos)
{
    int i=0;
    if(SearchPos<0)
    {
        return NULL;
    }
    while(i<SearchPos && L!=NULL)
    {
        L=L->next;
        i++;
    }
    return L;
}

?按位查找的時間復雜度

按位查找的時間復雜度為：O(n)

（4）按值查找

LNode *LocateElem(LinkList L, ElemType e)
{
    LNode *p = L->next;
    while(p!=NULL && p->data!=e)
        p = p->next;
    return p;
}

?按值查找的時間復雜度?

按值查找的時間復雜度為：O(n)

（5）在第i個位置上插入結點?

LinkList ListFrontInsert(LinkList L, int InsertPos, ElemType InsertVal)//注意：插入不會改變鏈表的頭節(jié)點（指針）L，和順序表不同，這里的形參不需要使用&
{
    LinkList p = GetElem(L, InsertPos-1);//GetElem函數(shù)中已自帶InsertPos-1是否合法的檢查
    if(NULL==p)
        return false;
    LinkList q;
    q = (LNode*) malloc(sizeof (LNode));
    q->data = InsertVal;
    q->next = p->next;//①
    p->next = q;//②
    return L;
}

?【注】：①②兩句的順序不能顛倒！（代碼的第9和第10行）

插入結點的時間復雜度分析

插入算法的主要時間開銷在于查找第i-1個元素，時間復雜度為O(n)。

若在給定的結點后面插入新結點，則時間復雜度僅為O(1).

【注】：在單鏈表的插入操作中，不會改變頭結點指針L，因此不需要使用&類型（這一點與順序表不同，順序表的插入操作會改變整個表，在順序表的插入函數(shù)中形參需要使用&）

（6）刪除結點操作

//刪除第i個位置的元素
bool ListDelete(LinkList L, int i) 
{
    LinkList p= GetElem(L, i-1);
    if(NULL==p)
    {
        return false;
    }
    LinkList q = p->next;
    //這里可能會有疑問，如果不定義指針q，用p->next=p->next->next可以嗎
    //這樣是不行的，因為被刪除的節(jié)點沒有了指針指向，無法free
    p->next = q->next;//斷鏈
    free(q);//釋放被刪除節(jié)點的空間
}

【注】：在刪除節(jié)點操作中，需要定義兩個指針p和q，p指向刪除位置i的前一個位置的結點，p指向需要被刪除的結點。這里可能會產生疑問，為什么一定要定義指針q呢？用語句p->next=p->next->next不是也可以達到刪除節(jié)點的效果嗎?

原因：這樣是不好的！如果不定義指針q，在p->next=p->next->next之后就無法再找到刪除的結點空間，無法free掉這塊空間。一般前面使用malloc分配的空間在后面使用完成后都需要free掉。

刪除結點的時間復雜度分析

刪除結點算法的時間開銷也主要在于查找第i-1個元素，時間復雜度為O(n).

整體代碼演示

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//頭插法新建鏈表
LinkList list_head_insert(LinkList &L)
    L = (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    ElemType x;
    scanf("%d", &x);
    LNode* s;//用來指向申請的新節(jié)點

    while(x!=9999)//輸入9999表示輸入結束
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;//s的next指向原本鏈表的第一個節(jié)點
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

//尾插法新建鏈表
//尾插法的特點：定義一個尾指針r總指向鏈表的尾部
LinkList list_tail_insert(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    ElemType x;
    scanf("%d", &x);
    LNode *s, *r=L;//s用來指向申請的新節(jié)點，r始終指向鏈表尾部
    while(x!=9999)
    {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;//新節(jié)點給尾節(jié)點的next指針
        r=s;//r要指向新的尾部
        scanf("%d", &x);
    }
    r->next = NULL;//讓尾節(jié)點為Null
    return L;
}

//鏈表打印
void print_list(LinkList L)
{
    L = L->next;//沒有使用引用，外面的L不會發(fā)生改變
    while(L!=NULL)
    {
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

//按位查找
//查找返回一個節(jié)點
LNode *GetElem(LinkList L, int SearchPos)
{
    if(SearchPos<1)
    {
        return NULL;
    }
    int j=1;//計數(shù)，初始為1
    LNode *p=L->next;
    while(p!=NULL && j<SearchPos)
    {
        p=p->next;
        j++;
    }
    return p;
}

//按值查找
LNode *LocateElem(LinkList L, ElemType e)
{
    LNode *p = L->next;
    while(p!=NULL && p->data!=e)
        p = p->next;
    return p;
}

//向第i個位置插入元素
//使用GetElem找到第i-1個節(jié)點的位置（地址、指針）
bool ListFrontInsert(LinkList L, int InsertPos, ElemType InsertVal)
{
    LinkList p = GetElem(L, InsertPos-1);//GetElem函數(shù)中已自帶InsertPos-1是否合法的檢查
    if(NULL==p)
        return false;
    LinkList q;
    q = (LNode*) malloc(sizeof (LNode));
    q->data = InsertVal;
    q->next = p->next;
    p->next = q;
    return true;
}

//刪除第i個位置的元素
bool ListDelete(LinkList L, int i) 
{
    //判斷i的合法性已經在GetElem中定義過
    //若i=1也是合法的，此時i-1=0,返回頭指針
    LinkList p= GetElem(L, i-1);
    if(NULL==p)
    {
        return false;
    }
    LinkList q = p->next;
    //此時可能會說，不定義q，用p->next=p->next->next
    //這樣是不行的，因為被刪除的節(jié)點沒有了指針指向，無法free
    p->next = q->next;//斷鏈
    free(q);//釋放被刪除節(jié)點的空間
}

int main() {
    //輸入1 2 3 4 5 6 7 8 9 9999
    LinkList L;//L是鏈表頭，是結構體指針類型，大?。?個字節(jié)
//    list_head_insert(L);//頭插法新建鏈表
    list_tail_insert(L);
    print_list(L);
    //查找
    LinkList search;//查找指針
    //按位置查找
    search=GetElem(L, 2);//返回一個指針
    if(search!=NULL)
    {
        printf("Succeeded in searching by serial number\n");
        printf("%d\n", search->data);
    }else{
        printf("Failed in searching by serial number\n");
    }
    //按值
    search=LocateElem(L, 6);
    if(search!=NULL)
    {
        printf("Succeeded in searching by serial number\n");
        printf("%d\n", search->data);
    }else{
        printf("Failed in searching by serial number\n");
    }

    //在第2個位置上插入99
    bool ret;
    ret=ListFrontInsert(L, 2, 99);
    print_list(L);
    //刪除鏈表第4個位置的元素
    ListDelete(L, 4);
    print_list(L);
    return 0;
}

輸入：1 2 3 4 5 6 7 8 9999（用空格隔開）?

實驗結果：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-742913.html

?

到了這里，關于【數(shù)據(jù)結構】——單鏈表的基本操作（帶頭結點）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！