線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

在前面線性表順序存儲(chǔ)的優(yōu)缺點(diǎn)里面我們談到了線性表的一些不足译红，最大的缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量元素，在線性表比較大的時(shí)候采用順序存儲(chǔ)很是不方便站宗，效率低秧骑。
效率低的原因
當(dāng)插入和刪除時(shí)，就要移動(dòng)大量元素蠕蚜，仔細(xì)分析后尚洽，發(fā)現(xiàn)原因就在于相鄰兩元素的存儲(chǔ)位置也具有鄰居關(guān)系。它們編號(hào)是1, 2, 3, ……, n,它們?cè)趦?nèi)存中的位置也是挨著的靶累，中間沒有空隙腺毫，當(dāng)然就無(wú)法快速介入，而刪除后挣柬，當(dāng)中就會(huì)留出空隙潮酒，自然需要彌補(bǔ)。問題就出在這里邪蛔。
解決的思路
哪有空位就放到哪里急黎，而讓每個(gè)元素知道它下一個(gè)元素的位置在哪里，這樣，我們可以在第一個(gè)元素時(shí)叁熔，就知道第二個(gè)元素的位置（內(nèi)存地址）委乌，而找到它；在第二個(gè)元素時(shí)荣回，再找到第三個(gè)元素的位置（內(nèi)存地址）這樣所有的元素我們就都可以通過遍歷而找到遭贸。
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的心软，也可以是不連續(xù)的壕吹。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置删铃，比如下圖：

image.png

鏈表的一些基本概念
為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系耳贬，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息之外猎唁，還需存儲(chǔ)一個(gè)指示其直接后繼的信息(即直接后繼的存儲(chǔ)位置)咒劲。
數(shù)據(jù)域：我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域。
指針域：存儲(chǔ)直接后繼位置的域稱為指針域诫隅。
指針/鏈：指針域中存儲(chǔ)的信息稱做指針或鏈腐魂。
結(jié)點(diǎn)(Node)：數(shù)據(jù)域與指針域這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)(Node)

image.png

n個(gè)結(jié)點(diǎn)（ai的存儲(chǔ)映像）鏈結(jié)成一個(gè)鏈表逐纬，即為線性表（ai, a2…蛔屹，an）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域豁生。因?yàn)橹羔樣蛑写鎯?chǔ)的信息稱做鏈兔毒，而且這個(gè)鏈每個(gè)結(jié)點(diǎn)都只有一個(gè)，所以叫做單鏈表甸箱。
單鏈表的頭指針育叁、頭結(jié)點(diǎn)與首元結(jié)點(diǎn)
單鏈表也是一種線性表，所以總得有個(gè)頭有個(gè)尾芍殖。鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針擂红，那么整個(gè)鏈表的存取就必須是從頭指針開始進(jìn)行了。之后的每一個(gè)結(jié)點(diǎn)围小，其實(shí)就是上一個(gè)的后繼指針指向的位置。
這里有個(gè)地方要注意树碱，就是對(duì)頭指針概念的理解肯适，這個(gè)很重要〕砂瘢“鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針”框舔，如果鏈表有頭結(jié)點(diǎn)，那么頭指針就是指向頭結(jié)點(diǎn)數(shù)據(jù)域的指針。

image.png

頭結(jié)點(diǎn)是為了操作的統(tǒng)一與方便而設(shè)立的刘绣，放在第一個(gè)元素結(jié)點(diǎn)之前樱溉，其數(shù)據(jù)域一般無(wú)意義（當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等等）纬凤。
有了頭結(jié)點(diǎn)后福贞，對(duì)在第一個(gè)元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，其操作與對(duì)其它結(jié)點(diǎn)的操作統(tǒng)一了停士。
首元結(jié)點(diǎn)也就是第一個(gè)元素的結(jié)點(diǎn)挖帘，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。
頭結(jié)點(diǎn)不是鏈表所必需的恋技。
在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中拇舀，頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)蜻底，則頭指針就是指向鏈表頭結(jié)點(diǎn)的指針骄崩。
頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字薄辅。
無(wú)論鏈表是否為空要拂，頭指針均不為空。頭指針是鏈表的必要元素长搀。
單鏈表也可以沒有頭結(jié)點(diǎn)宇弛。如果沒有頭結(jié)點(diǎn)的話，那么單鏈表就會(huì)變成這樣：

image.png

單鏈表的結(jié)構(gòu)體定義與聲明

定義一個(gè)結(jié)構(gòu)體來描述單鏈表的結(jié)點(diǎn)

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定義LinkList */

從這個(gè)結(jié)構(gòu)定義中源请，我們知道枪芒，結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域存放后繼結(jié)點(diǎn)地址的指針域組成。
假設(shè)p是指向線性表第i個(gè)元素的指針谁尸，則該結(jié)點(diǎn)ai的數(shù)據(jù)域我們可以用p->data來表示舅踪，p->data的值是一個(gè)數(shù)據(jù)元素，結(jié)點(diǎn)ai的指針域可以用 p->next來表示良蛮，p->next的值是一個(gè)指針抽碌。p->next指向誰(shuí)呢？當(dāng)然是指向第i+1個(gè)元素决瞳，即指向ai+1的指針货徙。

image.png

關(guān)于結(jié)構(gòu)體 struct Node *next; 這么一句代碼，不可以寫成 int *next 皮胡，next是指向下一個(gè)Node痴颊，所以其類型必須是Node。int *next 只能指向int屡贺，而不能指向Node蠢棱。所以必須定義為 Node 類型锌杀，但是 Node 是結(jié)構(gòu)體，所以前面還得加上個(gè) struct泻仙。

關(guān)于C語(yǔ)言的struct

typedef為C語(yǔ)言的關(guān)鍵字糕再，作用是為一種數(shù)據(jù)類型定義一個(gè)新名字。這里的數(shù)據(jù)類型包括內(nèi)部數(shù)據(jù)類型（int,char等）和自定義的數(shù)據(jù)類型（struct等）玉转。

在編程中使用typedef目的一般有兩個(gè)突想，一個(gè)是給變量一個(gè)易記且意義明確的新名字，另一個(gè)是簡(jiǎn)化一些比較復(fù)雜的類型聲明冤吨。
結(jié)構(gòu)體中的 typedef struct Node 的意思就是蒿柳，為自定義的數(shù)據(jù)類型定義一個(gè)新名字 Node。第二句就是聲明自定義數(shù)據(jù)類型 Node 了漩蟆。

單鏈表的初始化

首先我們?cè)趍ain函數(shù)中 LinkList L; 這么定義了一個(gè)鏈表垒探。因?yàn)樾枰獙?duì)鏈表本身進(jìn)行操作，那么假設(shè)函數(shù)定義為 InitList()怠李，那么需要地址傳遞圾叼，寫成 i=InitList(&L);。
第一步就是：創(chuàng)建一個(gè)頭結(jié)點(diǎn)捺癞，并且讓頭指針指向這個(gè)頭結(jié)點(diǎn)夷蚊。
其實(shí)頭指針也有了。參數(shù) *L 傳入的 L其實(shí)就是鏈表的首地址髓介，也就是頭指針惕鼓。接下來也就是在內(nèi)存開辟一個(gè)區(qū)域來作為頭結(jié)點(diǎn)。

*L=(LinkList) malloc (sizeof(Node)); //創(chuàng)建一個(gè)結(jié)點(diǎn)

此處返回給L的是一個(gè)指針唐础，并且賦給了頭指針箱歧。L其實(shí)就是頭結(jié)點(diǎn)，L則為頭指針一膨。
接下來還得給鏈表的首元結(jié)點(diǎn)賦值為 NULL呀邢，因?yàn)?L是頭結(jié)點(diǎn)，那么 (L)->next就是首元結(jié)點(diǎn)豹绪，所以 (L)->next=NULL; 這么寫就能讓首元結(jié)點(diǎn)的指針域?yàn)榭占厶省Ｋ院瘮?shù)設(shè)計(jì)完畢了。

/* 初始化順序線性表 */
Status InitList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node)); /* 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) */
    if(!(*L)) /* 存儲(chǔ)分配失敗 */
    {
        return ERROR;
    }
    (*L)->next=NULL; /* 指針域?yàn)榭?*/

    return OK;
}

*L=(LinkList)malloc(sizeof(Node)); 這一句代碼里面瞒津，L是個(gè)指針蝉衣，指向頭結(jié)點(diǎn)。L就是指頭結(jié)點(diǎn)巷蚪。if(!(L)) 就是頭結(jié)點(diǎn)分配失敗买乃。

單鏈表的插入與遍歷操作

image.png

假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)結(jié)點(diǎn)p钓辆、p->next和s之間邏輯關(guān)系的變化，只需將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p和p->next之間即可。

image.png

先把結(jié)點(diǎn)s的指針next指向a_i+1前联，即 s->next = p->next. 然后再把a(bǔ)_i的指針next指向s功戚，即 p->next = s. 用代碼描述則為：

s->next = p->next;
p->next = s;

也就是說讓p的后繼結(jié)點(diǎn)變成s的后繼結(jié)點(diǎn)，而不再是p的后繼似嗤，相當(dāng)于砍斷了p與其后繼結(jié)點(diǎn)的關(guān)聯(lián)啸臀。然后再把結(jié)點(diǎn)s變成 p的后繼結(jié)點(diǎn)，s也就變成了 p->next烁落。
如果先p->next=s;再s->next=p->next;會(huì)怎么樣乘粒？此時(shí)第一句會(huì)使得將p->next給覆蓋成s的地址了。那么s->next=p->next伤塌，其實(shí)就等于s->next=s灯萍，這樣真正的擁有ai+1數(shù)據(jù)元素的結(jié)點(diǎn)就沒了上級(jí)。這樣的插入操作就是失敗的
單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路：

聲明一結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)每聪，初始化j從1開始旦棉；
當(dāng)j < i時(shí)，就遍歷鏈表药薯，讓p的指針向后移動(dòng)绑洛，不斷指向下一結(jié)點(diǎn)，j累加1;
若到鏈表末尾p為空童本，則說明第i個(gè)元素不存在真屯；
否則査找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)s;
將數(shù)據(jù)元素e賦值給s->data;
單鏈表的插入標(biāo)準(zhǔn)語(yǔ)句s->next=p->next; p->next=s;
返回成功穷娱。
函數(shù)設(shè)計(jì)如下：

/* 初始條件：順序線性表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;     /* 聲明一個(gè)結(jié)點(diǎn) p鄙煤，指向頭結(jié)點(diǎn) */
    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;
}

單鏈表的刪除某個(gè)元素的操作

image.png

單鏈表刪除第i個(gè)數(shù)據(jù)結(jié)點(diǎn)的算法思路：

聲明一結(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->next賦值給q;
單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句p->next=q->next;
將q結(jié)點(diǎn)中的數(shù)據(jù)賦值給e,作為返回嗦董；
釋放q結(jié)點(diǎn)；
返回成功瘦黑。
設(shè)計(jì)的函數(shù)如下：

   /* 初始條件：順序線性表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; // 聲明一結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)
    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;
}

分析一下剛才我們的單鏈表插入和刪除算法咬扇，我們發(fā)現(xiàn)，它們其實(shí)都是由兩部分組成：第一部分就是遍歷査找第i個(gè)元素廊勃；第二部分就是插入和刪除元素懈贺。

從整個(gè)算法來說，我們很容易推導(dǎo)出：它們的時(shí)間復(fù)雜度都是0(n)坡垫。如果在我們不知道第i個(gè)元素的指針位置梭灿，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線性表的順序存儲(chǔ)結(jié)構(gòu)是沒有太大優(yōu)勢(shì)的冰悠。但如果我們希望從第i個(gè)位置堡妒，插入10個(gè)元素，對(duì)于順序存儲(chǔ)結(jié)構(gòu)意味著屿脐，每一次插入都需要移動(dòng)n-i個(gè)元素涕蚤，每次都是0(n〕。而單鏈表的诵，我們只需要在第一次時(shí)万栅，找到第i個(gè)位置的指針，此時(shí)為0(n),接下來只是簡(jiǎn)單地通過賦值移動(dòng)指針而已西疤，時(shí)間復(fù)雜度都是0(1)烦粒。顯然，對(duì)于插入或刪除數(shù)據(jù)越頻繁的操作代赁，單鏈表的效率優(yōu)勢(shì)就越是明顯扰她。

獲取單鏈表中的指定位置的元素

在單鏈表中，由于第i個(gè)元素到底在哪是沒辦法一開始就知道芭碍，必須得從頭開始找徒役。我們可以先設(shè)計(jì)一下單鏈表實(shí)現(xiàn)獲取第i個(gè)元素的數(shù)據(jù)的操作GetElem()函數(shù)。

聲明一個(gè)結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)窖壕，初始化j從1開始忧勿；
當(dāng)j < i時(shí)，就遍歷鏈表瞻讽，讓p的指針向后移動(dòng)鸳吸，不斷指向下一結(jié)點(diǎn)，j累加1;
若到鏈表末尾P為空速勇，則說明第i個(gè)元素不存在晌砾；

否則査找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)烦磁。
函數(shù)設(shè)計(jì)如下：

/* 初始條件：順序線性表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還沒有等于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;
}

說白了，就是從頭開始找呕乎，直到第i個(gè)元素為止猴蹂。由于這個(gè)算法的時(shí)間復(fù)雜度取決于i的位置，當(dāng)i=l時(shí)楣嘁，則不需遍歷，第一個(gè)就取出數(shù)據(jù)了珍逸，而當(dāng)i=n時(shí)則遍歷n-1次才可以逐虚。因此最壞情況的時(shí)間復(fù)雜度是0(n)。
用while的條件控制谆膳，當(dāng)循環(huán)執(zhí)行完畢之后就可以鎖定目標(biāo)結(jié)點(diǎn)p叭爱。這里的主要核心思想就是“工作指針后移”，就是先聲明一個(gè)結(jié)點(diǎn)漱病，這個(gè)結(jié)點(diǎn)與鏈表的首元結(jié)點(diǎn)一致买雾，循環(huán)遍歷下去。

查找某數(shù)在單鏈表中的位置

這里也同樣需要用到“工作指針”杨帽。首先聲明一個(gè)工作指針漓穿，并讓它指向鏈表的首元結(jié)點(diǎn) LinkList p=L->next。參數(shù) L 其實(shí)就是頭指針注盈，L->next 就是頭結(jié)點(diǎn)晃危。然后用工作指針遍歷鏈表，當(dāng) p->data 與傳入的查找數(shù) e 相等老客，返回其位置即可僚饭。
方法體設(shè)計(jì)如下：

/* 初始條件：順序線性表L已存在 */
/* 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系的數(shù)據(jù)元素的位序。 */
/* 若這樣的數(shù)據(jù)元素不存在胧砰，則返回值為0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到這樣的數(shù)據(jù)元素 */
                return i;
        p=p->next;
    }

    return 0;
}

用頭插法實(shí)現(xiàn)單鏈表整表創(chuàng)建

單鏈表整表創(chuàng)建的算法思路：

聲明一結(jié)點(diǎn)p和計(jì)數(shù)器變量i鳍鸵；
初始化一空鏈表L；
讓L的頭結(jié)點(diǎn)的指針指向NULL,即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表尉间；
循環(huán)：
- 生成一新結(jié)點(diǎn)賦值給p;
- 隨機(jī)生成一數(shù)字賦值給P的數(shù)據(jù)域p->data;
- 將p插入到頭結(jié)點(diǎn)與前一新結(jié)點(diǎn)之間偿乖。
  頭插法創(chuàng)建鏈表的函數(shù)：

/*  隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎ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以內(nèi)的數(shù)字 */
        p->next = (*L)->next;
        (*L)->next = p;                     /*  插入到表頭 */
    }
}

image.png

用尾插法實(shí)現(xiàn)單鏈表整表創(chuàng)建

我們把每次新結(jié)點(diǎn)都插在終端結(jié)點(diǎn)的后面乌妒，這種算法稱之為尾插法汹想。

/*  隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎ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è)線性表 */
    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以內(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é)束 */
}

完整的程序如下：

#include "stdio.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */

typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼撤蚊，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實(shí)際情況而定古掏，這里假設(shè)為int */

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
/* 定義LinkList */
typedef struct Node *LinkList;

/* 初始化順序線性表 */
Status InitList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node)); /* 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) */
    if(!(*L)) /* 存儲(chǔ)分配失敗 */
    {
        return ERROR;
    }
    (*L)->next=NULL; /* 指針域?yàn)榭?*/

    return OK;
}

/* 初始條件：順序線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
    while(p)
    {
        i++;
        p=p->next;
    }
    return i;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素輸出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

Status visit(ElemType c)
{
    printf("-> %d ",c);
    return OK;
}

/* 初始條件：順序線性表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還沒有等于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;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系的數(shù)據(jù)元素的位序丧枪。 */
/* 若這樣的數(shù)據(jù)元素不存在，則返回值為0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到這樣的數(shù)據(jù)元素 */
                return i;
        p=p->next;
    }

    return 0;
}

/*  隨機(jī)產(chǎn)生n個(gè)元素的值庞萍，建立帶表頭結(jié)點(diǎ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以內(nèi)的數(shù)字 */
        p->next = (*L)->next;
        (*L)->next = p;                         /*  插入到表頭 */
    }
}

/*  隨機(jī)產(chǎn)生n個(gè)元素的值拧烦，建立帶表頭結(jié)點(diǎ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è)線性表 */
    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以內(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é)束 */
}

/* 初始條件：順序線性表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;     /* 聲明一個(gè)結(jié)點(diǎn) p恋博，指向頭結(jié)點(diǎn) */
    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;
}

/* 初始條件：順序線性表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;
}

int main()
{
    LinkList L;
    Status i;
    int j,k,pos,value;
    char opp;
    ElemType e;

    i=InitList(&L);
    printf("鏈表L初始化完畢本鸣，ListLength(L)    =%d\n",ListLength(L));

    printf("\n1.整表創(chuàng)建（頭插法） \n2.整表創(chuàng)建（尾插法） \n3.遍歷操作 \n4.插入操作 \n5.刪除操作 \n6.獲取結(jié)點(diǎn)數(shù)據(jù) \n7.查找某個(gè)數(shù)是否在鏈表中 \n0.退出 \n請(qǐng)選擇你的操作：\n");
    while(opp != '0'){
        scanf("%c",&opp);
        switch(opp){
            case '1':
                  CreateListHead(&L,10);
                printf("整體創(chuàng)建L的元素(頭插法)：\n");
                ListTraverse(L);
                printf("\n");
                break;

            case '2':
                CreateListTail(&L,10);
                printf("整體創(chuàng)建L的元素(尾插法)：\n");
                ListTraverse(L);
                printf("\n");
                break;

            case '3':
                ListTraverse(L);
                printf("\n");
                break;

            case '4':
                printf("要在第幾個(gè)位置插入元素疫衩？");
                scanf("%d",&pos);
                printf("插入的元素值是多少？");
                scanf("%d",&value);
                ListInsert(&L,pos,value);
                ListTraverse(L);
                printf("\n");
                break;

            case '5':
                printf("要?jiǎng)h除第幾個(gè)元素荣德？");
                scanf("%d",&pos);
                ListDelete(&L,pos,&e);
                printf("刪除第%d個(gè)元素成功闷煤，現(xiàn)在鏈表為：\n", pos);
                ListTraverse(L);
                printf("\n");
                break;

            case '6':
                printf("你需要獲取第幾個(gè)元素？");
                scanf("%d",&pos);
                GetElem(L,pos,&e);
                printf("第%d個(gè)元素的值為：%d\n", pos, e);
                printf("\n");
                break;

            case '7':
                printf("輸入你需要查找的數(shù)：");
                scanf("%d",&pos);
                k=LocateElem(L,pos);
                if(k)
                    printf("第%d個(gè)元素的值為%d\n",k,pos);
                else
                    printf("沒有值為%d的元素\n",pos);
                printf("\n");
                break;

            case '0':
                exit(0);
        }
    }

}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末涮瞻，一起剝皮案震驚了整個(gè)濱河市鲤拿，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌饲宛，老刑警劉巖皆愉，帶你破解...
沈念sama閱讀 217,542評(píng)論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異艇抠，居然都是意外死亡幕庐，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,822評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門家淤，熙熙樓的掌柜王于貴愁眉苦臉地迎上來异剥，“玉大人，你說我怎么就攤上這事絮重≡┦伲” “怎么了？”我有些...
開封第一講書人閱讀 163,912評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵青伤，是天一觀的道長(zhǎng)督怜。經(jīng)常有香客問我，道長(zhǎng)狠角，這世上最難降的妖魔是什么号杠？我笑而不...
開封第一講書人閱讀 58,449評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮，結(jié)果婚禮上姨蟋，老公的妹妹穿的比我還像新娘屉凯。我一直安慰自己，他們只是感情好眼溶，可當(dāng)我...
茶點(diǎn)故事閱讀 67,500評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布悠砚。她就那樣靜靜地躺著，像睡著了一般堂飞。火紅的嫁衣襯著肌膚如雪灌旧。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,370評(píng)論 1贊 302
城市分裂傳說
那天绰筛，我揣著相機(jī)與錄音节榜，去河邊找鬼。笑死别智，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的稼稿。我是一名探鬼主播薄榛，決...
沈念sama閱讀 40,193評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼让歼！你這毒婦竟也來了敞恋？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,074評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤谋右，失蹤者是張志新（化名）和其女友劉穎硬猫，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體改执，經(jīng)...
沈念sama閱讀 45,505評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡啸蜜，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,722評(píng)論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了辈挂。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片衬横。...
茶點(diǎn)故事閱讀 39,841評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖终蒂，靈堂內(nèi)的尸體忽然破棺而出蜂林，到底是詐尸還是另有隱情，我是刑警寧澤拇泣，帶...
沈念sama閱讀 35,569評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布噪叙，位于F島的核電站，受9級(jí)特大地震影響霉翔，放射性物質(zhì)發(fā)生泄漏睁蕾。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,168評(píng)論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一早龟、第九天我趴在偏房一處隱蔽的房頂上張望惫霸。院中可真熱鬧猫缭，春花似錦、人聲如沸壹店。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,783評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)硅卢。三九已至射窒，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間将塑，已是汗流浹背脉顿。一陣腳步聲響...
開封第一講書人閱讀 32,918評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國(guó)打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留点寥，地道東北人艾疟。一個(gè)月前我還...
沈念sama閱讀 47,962評(píng)論 2贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像敢辩，于是被迫代替她去往敵國(guó)和親蔽莱。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,781評(píng)論 2贊 354

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

單鏈表的結(jié)構(gòu)體定義與聲明

關(guān)于C語(yǔ)言的struct

單鏈表的初始化

單鏈表的插入與遍歷操作

單鏈表的刪除某個(gè)元素的操作

獲取單鏈表中的指定位置的元素

查找某數(shù)在單鏈表中的位置

用頭插法實(shí)現(xiàn)單鏈表整表創(chuàng)建

用尾插法實(shí)現(xiàn)單鏈表整表創(chuàng)建

完整的程序如下：

推薦閱讀更多精彩內(nèi)容