資料結構之線性表的鍊式存儲實作（連結清單）

線性表的鍊式存儲實作

線性表的鍊式存儲實作通常單連結清單. 單連結清單由一系列在記憶體中相連的結點組成, 每個結點均含有資料域和指針域, 資料域存儲資料, 指針域存儲指向下一個結點的指針. 單連結清單的結構如圖:

資料結構之線性表的鍊式存儲實作（連結清單）

單連結清單資料結構中的概念:

結點 node: 結點由資料域和指針域組成, 資料域中可以是任意類型的資料包括結構體甚至其他資料結構, 指針域中是指向連結清單下一個結點的指針.

頭結點 head node: 頭結點也稱表頭啞結點, 資料域無意義, 指針域存儲指向連結清單第一結點的指針, 并将其看作指向目前連結清單的指針, 注意約定頭結點是連結清單的第0個結點, 而非第1個.

頭指針 head pointer: 指向連結清單頭結點的指針, 無頭結點時指向連結清單第一個結點.

位置 position: 一個結點在連結清單中占據一個位置, 頭結點的位置為0.

表長 list length:表中結點的個數(除頭結點)

前驅 previous node: 目前結點的前一個結點.

後繼 next node: 目前結點的下一個結點.

空表 empty list: 隻有頭結點的的連結清單, 表長為0.
存儲結構僞代碼

struct node;
typedef struct node *ptr_to_node;
typedef ptr_to_node list;
typedef ptr_to_node nodeptr; // 指向結點的指針

int is_empty(list l); // 判斷連結清單l是否為空
int is_last(list l, nodeptr node); // 判斷pos所指向的結點是否為最後一個結點
int get_length(list l); // 擷取連結清單長度
int get_position(list l, element_type data); // 擷取資料域為data的結點的位置
nodeptr get_current(list l, int pos); // 擷取指向pos位置的結點的指針
nodeptr get_previous(list l, int pos); // 擷取指向pos位置前一個結點的指針
void init_list(); // 初始化連結清單
nodeptr find_node(list l, element_type data); // 查找資料域為data的結點, 傳回指向其的指針
bool insert_node(list l, int pos, int data); // 在位置pos處插入一個資料域為data的結點
bool delete_node(list l, element_type data); // 删除資料域為data的結點
bool delete_list(list l); // 删除整個連結清單

struct node {
    element_type element;
    nodeptr next;
};

連結清單結構如圖:

實作 is_empty
函數

思路: 頭結點的next指針指向NULL時連結清單為空表.

int is_empty(list l)
{
    return l->next == NULL;
}

實作 is_last
函數

思路: pos結點的next指針指向NULL時, pos指向最後一個結點.

int is_last(list l, nodeptr node)
{
    return node->next == NULL;
}

實作 get_length
函數

思路: 從指向第1個結點的指針開始, 逐個通路結點直到遇到NULL指針.

int get_length(list l)
{
    nodeptr node_ptr = l->next;
    int count = ;
    while(node_ptr != NULL) {
        node_ptr = node_ptr->next;
        count++;
    }
    return count;

實作 get_position
函數

思路: 從從指向第1個結點的指針開始, 逐個通路結點直到資料域為data的結點

int get_position(list l, element_type data)
{
    nodeptr node_ptr = l->next;
    int count = ;
    while(node_ptr->element != data) {
        node_ptr = node_ptr->next;
        count++;
    }
}

實作 get_current
函數

思路: 從第1個位置開始, 逐個通路結點直到pos位置.

nodeptr get_current(list ;, int pos)
{
    if(pos >=  && pos <= get_length()) {
        nodeptr node_ptr = l->next;
        for(int i = ; i < pos; i++) {
            nodeptr = nodeptr->next;
        }
        return node_ptr;
    }
    else {
        error("Wrong position!");
        return NULL;
    }
}

實作 get_previous
函數

思路: 從第1個位置開始, 逐個通路結點直到pos位置的前一個位置.

nodeptr get_previous(list ;, int pos)
{
    if(pos >=  && pos <= get_length()) {
        nodeptr node_ptr = l;
        for(int i = ; i < pos - ; i++) {
            nodeptr = nodeptr->next;
        }
        return node_ptr;
    }
    else {
        error("Wrong position!");
        return NULL;
    }
}

實作 init_list
函數

思路: 配置設定頭結點的記憶體, 并将其指針域指向NULL.

list init_list()
{
    list l = malloc(sizeof(struct node));
    if( l != NULL) {
        l->element = ;
        l->next = NULL;
    }
    return l;
}

實作 find_node
函數

思路: 從連結清單l的第1個結點開始, 将結點的資料域與data比較, 若相同傳回目前節點的指針node_ptr, 若不同将node_ptr後移, 繼續比較直到連結清單末尾.

nodeptr find_node(list l, element_type data)
{
    nodeptr node_ptr = l->next; // 從連結清單第1個結點開始
    while(tmp_node != NULL && node_ptr->element != data)
        node_ptr = node_ptr->next;
    return node_ptr;
}

實作 insert_node
函數

思路:

資料結構之線性表的鍊式存儲實作（連結清單）

step1: 擷取指向插入位置前一個結點的指針previous

step2: 建立要插入的結點, 并設定資料域為data

step3: 設定要插入結點的指針域為previous->next(指向原位置3的結點)

step4: 設定previous的指針域設定為指向要插入的結點

bool insert_element(list l, int pos, element_type data)
{
    if(pos >=  && pos <= get_length(l) + ) {
        nodeptr previous = get_previous(l, pos);
        nodeptr tmp_node = malloc(sizeof(struct node));
        if(tmp_node != NULL) {
            tmp_node->element = data;
            tmp_node->next = previous->next;
            previous->next = tmp_node;
            retur true;
        }
        else {
            error("Out of space!");
            return false;
        }
    }
    else {
        error("Wrong position!");
    }
}

實作 delete_element
函數

思路:

step1: 擷取指向删除位置前一個結點的指針previous

step2: 擷取指向删除位置結點的指針current

step3: 設定删除位置前一個結點的指針域指向删除位置後一個結點

step4: free目前位置結點記憶體

void delete_element(list l, int pos)
{
    if (pos >=  && pos <= get_length(l)) {
        nodeptr previous = get_previous(l, pos);
        nodeptr current = previous->next;
        previous->next = current->next;
        free(current);
        return true;
    }
    else {
        printf("Position is wrong!\n");
        return false;
    }
}

實作 delete_list
函數

step1: 記錄頭指針指向的位置, 并将頭指針指向NULL

step2: 逐個free結點記憶體

void delete_list(list l)
{
    nodeptr recorder = l->next;
        nodeptr tmp_node = NULL;
        l->next = NULL;
        while (recorder != NULL) {
            tmp_node = recorder->next;
            free(recorder);
            recorder = tmp_node;
        }
}

資料結構之線性表的鍊式存儲實作（連結清單）

繼續閱讀

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

基礎算法之二分查找

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

poj3249

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器