單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。順序表是在計算機內存中以數組的形式保存的線性表，采用順序存儲結構的線性表簡稱為“ 順序表”。單鏈表和順序表盡管都是表，但是有著大不相同的數據結構。

鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。而線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系，采用順序存儲結構的線性表通常稱為順序表。從整體考慮, 順序表要預分配存儲空間, 如果預先分配得過大, 將造成浪費, 若分配得過小, 又將發生上溢;單鏈表不需要預先分配空間, 只要內存內存空間沒有耗盡, 單鏈表中的結點個數就沒有限制。下面我們從源碼進行分析：

1.順序表的完整代碼

#include <stdio.h>

// 定義一個結構體類型

typedef struct {

    char name[10];

    int age;

} DataType;

// 順序表的結構體定義

// 線性表的大小, 也就是最多存儲多少個數據元素

const int maxSize = 100;

typedef struct {

    // 所存放的數據類型為int, 最多存放100個元素的數組

    DataType data[maxSize];

    // 當前所存放的數據元素的個數

    int length;

} SeqList;

/**

 線性表的插入

 @param pList 類型為SeqList的結構體指針

 @param x 要插入的類型為DataType類型的數據元素

 @param i 要插入的位置

*/

void insertSeqList(SeqList * pList, DataType x, int i) {

    // 判斷線性表是否已滿

    if (pList->length == maxSize) {

        printf("表已滿 \n");

        return;

    }

    // 檢查插入位置是否合法

    if (i < 1 || i > (pList->length) + 1) {

        printf("插入位置不合法 \n");

        return;

    }

    // 進行插入操作

    // 從表的最后一個位置依次進行后移

    for (int j = pList->length; j >= i; j--) {

        pList->data[j] = pList->data[j-1];

    }

    // 后移完成之后, 對空出的位置進行賦值

    pList->data[i - 1] = x;

    // 表的長度加1

    pList->length++;

}

/**

 線性表的刪除

 @param pList 類型為SeqList結構體的指針

 @param i 要刪除的位置

 */

void deleteSeqList(SeqList * pList, int i) {

    // 檢查刪除位置是否合法

    if (i < 1 || i > pList -> length) {

        printf("刪除位置不合法");

        return;

    }

    // 進行刪除操作, 依次左移

    for (int j = i; j < pList->length; j++) {

        pList->data[j - 1] = pList->data[j];

    }

    // 表的長度減1

    pList->length--;

}

/**

 線性表的定位

 @param pList 類型為SeqList結構體的指針

 @param name 要查找的姓名

 @return 查找到的元素的位置

 */

int locateSeqList(SeqList * pList, char name[]) {

    int i = 0;

    // 在順序表中查找值為name的結點

    while (i < pList->length && pList->data[i].name == name) {

        i++;

    }

    // 若找到值為name的結點, 則返回結點的序號

    if (i < pList->length) {

        return i + 1;

    } else { // 未找到值為name的結點, 返回0

        return 0;

    }

}

int main(int argc, const char * argv[]) {

    // insert code here...

    // 創建一個結構體實例, 并進行初始化

    DataType dt1 = {"alex", 18};

    DataType dt2 = {"kevin", 16};

    DataType dt3 = {"jack", 21};

    // 創建一個空的線性表

    SeqList list = {};

    // 創建一個指針指向這個線性表

    SeqList * pList = &list;

    printf("插入前表的長度: %d \n", list.length);

    // 插入操作

    insertSeqList(pList, dt1, 1);

    insertSeqList(pList, dt2, 1);

    insertSeqList(pList, dt3, 1);

    printf("插入后表的長度: %d \n", list.length);

    // 刪除操作

    deleteSeqList(pList, 2);

    printf("插入后表的長度: %d \n", list.length);

    // 定位

    int loc = locateSeqList(pList, "alex");

    printf("alex在第%d位 \n", loc);

    return 0;

}

2.單鏈表的完整代碼

#include <stdio.h>

#include <stdlib.h>

// 聲明一個結構體類型

typedef struct {

    char name[12];

    int age;

} DataType;

// 聲明一個單鏈表類型

typedef struct node {

    DataType data; // 數據域

    struct node * next; // 指針域

} Node, * LinkList;

/**

 初始化一個單鏈表

 @return 初始化好的單鏈表

 */

LinkList initiateLinkList() {

    // 頭指針

    LinkList head;

    // 動態創建一個結點, 也就是頭結點, 然后讓頭指針指向這個結點

    head = malloc(sizeof(Node));

    // 頭結點的指針域為NULL

    head->next = NULL;

    // 返回這個單鏈表

    return head;

}

/**

 求表的長度

 @param list 單鏈表

 @return 表的長度

 */

int LengthLinkList(LinkList list) {

    // 用于計數

    int j = 0;

    // p指向頭指針

    LinkList p = list;

    // 當下一個結點不為空時, 計數加1, p指向下一個結點

    while (p->next != NULL) {

        j++;

        p = p->next;

    }

    // 返回表的長度

    return j;

}

/**

 讀表元素

 @param list 單鏈表

 @param i 要讀取的位置

 @return 如果有返回讀取到的元素, 沒有則返回NULL

 */

LinkList getLinkList(LinkList list, int i) {

    // 用于計數

    int j = 1;

    // p指向首結點

    LinkList p = list->next;

    while (j < i && p != NULL) {

        j++;

        p = p->next;

    }

    // 如果j等于i, 則p指向的結點為要找的結點

    if (j == i) {

        return p;

    } else { // 否則沒有要找的結點

        return NULL;

    }

}

/**

 插入

 @param list 單鏈表

 @param x 要插入的數據元素

 @param i 要插入的位置

 */

void insertLinkList(LinkList list, DataType x, int i) {

    LinkList s, p;

    if (i == 1) {

        p = list;

    } else {

        // 找到第 i-1 個數據元素結點

        p = getLinkList(list, i - 1);

    }

    if (p == NULL) {

        // 如果不存在, 返回錯誤信息

        printf("找不到插入的位置");

    } else{

        // 生成新結點并初始化

        s = malloc(sizeof(Node));

        s->data = x;

        // 新結點的指針域指向第i個元素

        s->next = p->next;

        // 第 i-1 個結點的指針域指向新結點

        p->next = s;

    }

}

/**

 刪除

 @param list 單鏈表

 @param i 要刪除結點的位置

 */

void deleteLinkList(LinkList list, int i) {

    LinkList p;

    // 找到待刪結點的直接前驅

    if (i == 1) {

        p = list;

    } else {

        p = getLinkList(list, i-1);

    }

    // 若直接前驅存在, 且待刪結點存在

    if (p != NULL && p->next != NULL) {

        // q指向待刪結點

        LinkList q = p->next;

        // 移出待刪結點

        p->next = q->next;

        // 釋放已經移出的結點

        free(q);

    } else {

        printf("要不到要刪除的結點");

    }

}

/**

 定位

 @param list 單鏈表

 @param name 要查找的結點的名字

 @return 如果查找到了, 則返回結點的位置, 如果沒有, 則返回0

 */

int locateLinkList(LinkList list, char name[]) {

    int j = 0;

    // p指向首結點

    LinkList p = list->next;

    // 查找結點

    while (p != NULL && !(strcmp(p->data.name, name) == 0)) {

        j++;

        p = p->next;

    }

    // 如果有則返回序號, 沒有返回0

    if (p != NULL) {

        return j + 1;

    } else {

        return 0;

    }

}

int main(int argc, const char * argv[]) {

    // insert code here...

    Node list = {};

    LinkList pList = &list;

    DataType dt1 = {"jack", 18};

    DataType dt2 = {"kevin", 20};

    // 插入元素

    insertLinkList(pList, dt1, 1);

    insertLinkList(pList, dt2, 1);

    // 讀表元素

    LinkList p = getLinkList(pList, 2);

    printf("%s \n", p->data.name);

    // 刪除元素

//    deleteLinkList(pList, 2);

//    deleteLinkList(pList, 1);

    // 讀表長

    int length = LengthLinkList(pList);

    printf("表的長度為: %d \n", length);

    // 定位

    int loc = locateLinkList(pList, "kevin");

    printf("在第%d位 \n", loc);

    return 0;

}

本文我們從源碼分析了順序表和單鏈表的不同，以及順序表和單鏈表兩者數據結構和存儲結構的不同點，盡管都和線性表有一定關系，但是還是要區別對待，避免混淆概念。在本站數據結構和算法教程中，對每種常見的數據結構都有著非常透徹的講解，歡迎小伙伴們一起學習探討學習數據結構過程中遇到的問題，實現共同進步！