上篇博文，介紹了線性表、單鏈表等概念。這篇博文，我們就寫代碼來實現帶頭結點的非循環單鏈表。

1.結點的定義

typedef int element_t;struct node {element_t data; //數據域struct node *next; //指針域 };typedef struct node node_t;

2.初始化

void list_init(node_t *head) {assert(head!=NULL);head->next = NULL; }

head是頭結點的地址，下文同。

3.求鏈表的長度

/* 求鏈表中元素的個數，為空則返回0 */ int list_length(node_t *head) {assert(head!=NULL);int count = 0;while(head->next != NULL){head = head->next;++count;}return count; }

4.判斷鏈表是否為空

/* 判斷鏈表是否為空， 為空返回1，不為空返回0 */ int list_is_empty(node_t *head) {assert(head!=NULL); return(head->next == NULL); }

5.插入結點

/* 把新結點插入到某個結點的后面，此函數主要被其他函數調用 */ void insert_node(node_t *prev, node_t *new_node) {assert(prev!=NULL);assert(new_node!=NULL);new_node->next = prev->next;//圖中第一步prev->next = new_node; //圖中第二步 }

這個函數表示把新結點new_node插入到結點prev的后面。
對于初學者，可能不好理解，請看示意圖：

/* 已知新結點的地址，把新結點插入鏈表頭 */ void list_insert_head(node_t *head, node_t *new_node) {insert_node(head,new_node); }

這種插入方法叫“頭插法”。

/* 返回鏈表最后一個結點的地址，若鏈表為空，則返回頭結點的地址 */ node_t *list_get_last(node_t *head) {assert(head!=NULL);while(head->next!=NULL)head = head->next;return head; } /* 已知新結點的地址，把新結點插入鏈表尾 */ void list_insert_tail(node_t *head,node_t *new_node) {node_t *prev = list_get_last(head);insert_node(prev,new_node); }

這種插入方法叫“尾插法”。

/* 向鏈表表頭插入值為x的結點，成功返回0，失敗返回-1 */ int insert_element_head(node_t *head, element_t x) {assert(head!=NULL);node_t *new_node = (node_t *)malloc(sizeof(node_t));if(new_node==NULL){printf("malloc failed\n");return -1;}new_node->data = x;list_insert_head(head,new_node);return 0;} /* 向鏈表末尾添加值為x的結點，成功返回0，失敗返回-1 */ int insert_element_tail(node_t *head, element_t x) {assert(head!=NULL);node_t *new_node = (node_t *)malloc(sizeof(node_t));if(new_node==NULL){printf("malloc failed\n");return -1;}new_node->data = x;list_insert_tail(head,new_node);return 0;} /* 返回第pos個結點的前一個結點的地址，失敗則返回NULL */ node_t* get_pos_prev_addr(node_t *head, int pos) {assert(head!=NULL);if(list_is_empty(head)){printf("the list is empty, get failed\n");return NULL;}int length = list_length(head);if( (pos<1) || (pos>length) ){printf("pos is out of range\n");return NULL;}int count = 0;node_t *cur = head->next;node_t *prev = head;while(cur != NULL){++count;if(count == pos)return prev;prev = cur;cur = cur->next;} }/* 在pos位置插入新元素x，例如pos=3,則新元素在第3個位置.操作成功返回0，失敗返回負數 */ int insert_element_to_pos(node_t *head, element_t x, int pos) {assert(head!=NULL);int length = list_length(head);if(length==0){printf("the list is empty, insert failed\n");return -1;}if( (pos<1) || (pos >length) ){printf("pos is out of range\n");return -2;}node_t *new_node = (node_t *)malloc(sizeof(node_t));if(new_node==NULL){printf("malloc failed\n");return -3;}new_node->data = x;node_t *prev = get_pos_prev_addr(head,pos);insert_node(prev,new_node);return 0; }

6.鏈表的遍歷和安全遍歷

/* 鏈表的遍歷, todo參數由用戶傳入 */ void list_for_each(node_t *head, void(*todo)(node_t *node)) {assert(head != NULL);assert(todo != NULL);node_t *temp = head->next;while(temp != NULL){todo(temp);temp = temp->next;} }/* 鏈表的安全遍歷 */ void list_for_each_safe(node_t *head, void(*todo)(node_t *node)) {assert(head != NULL);assert(todo != NULL);node_t *cur = head->next;node_t *next;while(cur != NULL){next = cur->next;todo(cur);cur = next;} }

7.鏈表的清空

void list_clear(node_t *head) {void(*todo)(node_t *node) = (void(*)(node_t *))free;list_for_each_safe(head,todo);list_init(head); }

(void(*)(node_t *))free表示把free進行強制類型轉換，轉換成void(*)(node_t *)類型的指針。
此函數執行后，所有結點的空間被釋放，只剩下頭結點，成為一個空鏈表。

8.鏈表的銷毀

void list_destroy(node_t *head) {list_clear(head);free(head); }

此函數執行后，所有結點的空間被釋放，包括頭結點。銷毀后，鏈表就不復存在了。

9.鏈表的創建

鏈表的創建有很多種方法，可以頭插，也可以尾插，這里僅舉一例。

/* 從控制臺創建鏈表，輸入負數則停止。成功則返回頭結點的地址，失敗則返回NULL*/ node_t *list_create(void) {node_t *head = (node_t *)malloc(sizeof(node_t));if(head==NULL){printf("malloc failed\n");return NULL;}list_init(head); // 初始化頭結點int data;printf("please input the number, negative will quite\n");scanf("%d", &data);while(data>=0){node_t *new_node = (node_t *)malloc(sizeof(node_t));if(new_node==NULL){printf("malloc failed\n");list_destroy(head); //釋放空間return NULL;}new_node->data = data;list_insert_head(head,new_node); //這句話也可以換成 list_insert_tail(head,new_node);printf("please input the number, negative will quite\n");scanf("%d", &data);}return head; }

10.返回某個結點的地址或者值

/* 返回第pos個結點的地址（從1開始數），失敗則返回NULL */node_t* get_pos_addr(node_t *head, int pos) {assert(head!=NULL);int length = list_length(head); if(length==0){printf("the list is empty, get failed\n");return NULL;} if( (pos<1) || (pos>length) ){printf("pos is out of range\n");return NULL;}int count = 0;node_t *cur = head->next;while(cur != NULL){++count;if(count == pos){return cur;}cur = cur->next;} }/* 返回第pos個結點的值（由輸出型參數value指示），成功返回值為0，失敗返回值為-1 */ int get_pos_element(node_t *head, int pos, element_t *value) {node_t *p_node = get_pos_addr(head,pos);if(p_node){*value = p_node->data;return 0;}else{return -1; //failed}}

需要強調的是，參數value是輸出型參數，第pos個結點的值由此指針指向。

11.查找

/* 查找具有給定值的第一個元素，成功則返回該結點的地址，失敗返回NULL*/ node_t *find_element_pos(node_t *head, element_t x) {assert(head!=NULL);if(list_is_empty(head))return NULL;node_t *temp = head->next;while(temp!=NULL){if(temp->data == x)return temp;temp = temp->next;}return NULL; } /* 查找具有給定值的第一個元素，成功則返回該結點的前一個結點的地址，失敗返回NULL*/ node_t *find_element_prev_pos(node_t *head, element_t x) {assert(head!=NULL);if(list_is_empty(head))return NULL;node_t *temp = head->next;node_t *prev = head;while(temp!=NULL){if(temp->data == x)return prev;prev = temp;temp = temp->next;}return NULL; }

12.修改結點的值

/* 把第pos個結點的值修改為x,成功則返回0，失敗返回-1 */ int modify_element(node_t *head, int pos, element_t x) {node_t *p_node = get_pos_addr(head,pos);if(p_node){p_node->data = x;return 0;}else{return -1; //failed}}

13.刪除結點

/* 已知某結點的地址為prev，刪除它后面的那個結點, 此函數主要被其他函數調用 */ void delete_post_node(node_t *prev) {assert(prev->next != NULL);node_t *node_del = prev->next;prev->next = node_del->next;free(node_del); } /* 刪除第pos個結點，此結點的值由value指向。刪除成功返回0，失敗返回-1 */ int delete_pos_node(node_t *head, int pos, element_t *value) {int length = list_length(head); if(length==0){printf("the list is empty, get failed\n");return -1;}if( (pos<1) || (pos >length) ){printf("pos is out of range\n");return -2;}node_t *prev = get_pos_prev_addr(head,pos);*value = prev->next->data;delete_post_node(prev);return 0; }/* 刪除表頭結點，此結點的值由value指向。刪除成功返回0，失敗返回-1 */ int delete_from_head(node_t *head, element_t *value) {return delete_pos_node(head,1,value); }/* 刪除表尾結點，此結點的值由value指向。刪除成功返回0，失敗返回-1 */ int delete_from_tail(node_t *head, element_t *value) {int length = list_length(head); return delete_pos_node(head,length,value); }/* 刪除值為x的第一個結點，成功返回0，失敗返回負數 */ int delete_element(node_t *head, element_t x) {assert(head!=NULL);node_t *prev = find_element_prev_pos(head,x);if(prev){delete_post_node(prev);return 0;}else{return -1;} }

【完】

總結

以上是生活随笔為你收集整理的单链表入门（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。