本文實例講述了C語言單鏈表實現方法。分享給大家供大家參考，具體如下：
slist.h
#ifndef __SLIST_H__#define __SLIST_H__#include<cstdio>#include<malloc.h>#include<assert.h>typedef int ElemType;typedef struct Node { //定義單鏈表中的結點信息 ElemType data; //結點的數據域 struct Node *next; //結點的指針域}Node,*PNode;typedef struct List { //定義單鏈表的鏈表信息 PNode first; //first指向單鏈表中的第一個結點 PNode last; //last指向單鏈表中的最后一個結點 size_t size; //記錄單鏈表中的結點個數}List;void InitList(List *list);//初始化單鏈表void push_back(List *list, ElemType x);//在單鏈表的末尾插入元素void push_front(List *list, ElemType x);//在單鏈表的頭部插入元素void show_list(List *list);//打印單鏈表void pop_back(List *list);//刪除單鏈表的最后一個元素void pop_front(List *list);//刪除單鏈表的第一個元素void insert_val(List *list, ElemType val);//將數據元素插入到單鏈表中（要求此時單鏈表中的數據元素順序排列）Node* find(List *list, ElemType x);//查找單鏈表中數據值為x的結點int length(List *list);//求單鏈表的長度void delete_val(List *list, ElemType x);//按值刪除單鏈表中的某個數據元素void sort(List *list);//對單鏈表進行排序void reverse(List *list);//逆置單鏈表void clear(List *list);//清除單鏈表void destroy(List *list);//摧毀單鏈表#endif //__SLIST_H__slist.cpp
#include"slist.h"void InitList(List *list) { list->first = list->last = (Node*)malloc(sizeof(Node)); //頭結點 assert(list->first != NULL); list->first->next = NULL; list->size = 0;}void push_back(List *list, ElemType x) { //step 1：創建一個新的結點 Node *s = (Node*)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = NULL; //step 2：將新結點插入單鏈表的表尾 list->last->next = s; list->last = s; //step 3：更新單鏈表的長度 list->size++;}void push_front(List *list, ElemType x) { //step 1：創建一個新的結點 Node *s = (Node*)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = NULL; //step 2：將新結點插入單鏈表的表頭 s->next = list->first->next; list->first->next = s; //step 3：判斷插入的結點是否是單鏈表的第一個結點，若是更新鏈表的尾指針 if (list->size == 0) list->last = s; //step 4：更新單鏈表的長度 list->size++;}void show_list(List *list) { //step 1：指針p指向單鏈表的第一個結點 Node *p = list->first->next; //step 2：循環打印結點的信息 while (p != NULL) { printf("%d->", p->data); p = p->next; } printf("Nul./n");}void pop_back(List *list) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：定義指針p使其指向目標結點的前一個結點 Node *p = list->first;//從頭結點開始 while (p->next != list->last) p = p->next; //step 3：刪除目標結點 free(list->last); list->last = p; list->last->next = NULL; //step 4：更新單鏈表的長度 list->size--;}void pop_front(List *list) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：定義指針p使其指向目標結點的前一個結點 Node *p = list->first->next; //step 3：刪除目標結點 list->first->next = p->next; free(p); //step 4：判斷刪除的結點是否是單鏈表的最后一個結點，若是則更新單鏈表的尾指針 if (list->size == 1) list->last = list->first; //step 4：更新單鏈表的長度 list->size--;}void insert_val(List *list, ElemType x) { //step 1：創建一個新的結點 Node *s = (Node*)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = NULL; //step 2：定義指針p使其指向待插入位置的前一個結點 Node *p = list->first;//從頭結點開始 while (p->next != NULL && p->next->data < s->data) p = p->next; //step 3：判斷結點的待插入位置是否是表尾，若是則更新單鏈表的尾指針 if (p->next == NULL) list->last = s; //step 4：插入結點 s->next = p->next; p->next = s; //step 5：更新單鏈表長度 list->size++;}Node* find(List *list, ElemType x) { //step 1：指針p指向單鏈表的第一個結點 Node *p = list->first->next; //step 2：按照循環順序查找鏈表結點 while (p != NULL && p->data != x) p = p->next; return p;}int length(List *list) { return list->size;}void delete_val(List *list, ElemType x) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：確定結點在單鏈表中的位置，并判斷其是否存在于單鏈表中 Node *p = find(list, x); if (p == NULL) { printf("要刪除的數據不存在！/n"); return; } //step 3：判斷結點位置是否是表尾 if (p == list->last)//是表尾 pop_back(list); else {//不是表尾 Node *q = p->next; p->data = q->data; p->next = q->next; free(q); list->size--; }}void sort(List *list) { //step 1：判斷單鏈表中的結點數是否為0或1 if (list->size == 0 || list->size == 1) return; //step 2：將單鏈表中第一個結點之后的鏈表部分截出，方便重新按順序插入鏈表之中 Node *s = list->first->next; // 指針s指向單鏈表的第一個節點 Node *p = s->next;//q指向s后面的結點 list->last = s;//單鏈表的尾指針指向單鏈表的第一個結點 list->last->next = NULL;//截斷鏈表 //step 3：將截出的鏈表中的結點根據其數據域大小重新插入到原來鏈表中 while (p != NULL) { s = p; p = p->next; Node *q = list->first; while (q->next != NULL && q->next->data < s->data) q = q->next; if (q->next == NULL)//判斷q此時指向的是否是單鏈表的最后一個結點，若是則更新鏈表的尾指針 list->last = s; //將結點重新插入鏈表 s->next = q->next; q->next = s; }}void reverse(List *list) { //step 1：判斷單鏈表中的結點數是否為0或1 if (list->size == 0 || list->size == 1) return; //step 2：將單鏈表中第一個結點之后的鏈表部分截出，然后將截出的鏈表中的結點按頭插法重新插入到原鏈表中 Node *p = list->first->next; Node *q = p->next; list->last = p; list->last->next = NULL; while (q != NULL) { p = q; q = q->next; p->next = list->first->next; list->first->next = p; }}void clear(List *list) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：釋放單鏈表中的每一個結點 Node *p = list->first->next; while (p != NULL) { list->first->next = p->next; free(p); p = list->first->next; } //step 3：頭指針和尾指針重新都指向頭結點 list->last = list->first; //step 4：更新鏈表長度 list->size = 0;}void destroy(List *list) { //step 1：清空單鏈表 clear(list); //step 2：釋放頭結點 free(list->first); //step 3：頭指針和尾指針都賦值為空 list->first = list->last = NULL;}main.cpp
#include"slist.h"void main() { List mylist; InitList(&mylist); ElemType item; Node *p = NULL; int select = 1; while (select) { printf("*******************************************/n"); printf("*[1] push_back [2] push_front */n"); printf("*[3] show_list [4] pop_back */n"); printf("*[5] pop_front [6] insert_val */n"); printf("*[7] find [8] length */n"); printf("*[9] delete_val [10] sort */n"); printf("*[11] reverse [12] clear */n"); printf("*[13*] destroy [0] quit_system */n"); printf("*******************************************/n"); printf("請選擇：>>"); scanf("%d", &select); if (select == 0) break; switch (select) { case 1: printf("請輸入要插入的數據（-1結束）:>"); while (scanf("%d", &item), item != -1) { push_back(&mylist, item); } break; case 2: printf("請輸入要插入的數據（-1結束）:>"); while (scanf("%d", &item), item != -1) { push_front(&mylist, item); } break; case 3: show_list(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: printf("請輸入要插入的數據:>"); scanf("%d", &item); insert_val(&mylist, item); break; case 7: printf("請輸入要查找的數據:>"); scanf("%d", &item); p = find(&mylist, item); if (p == NULL) printf("要查找的數據在單鏈表中不存在！/n"); break; case 8: printf("單鏈表的長度為%d/n", length(&mylist)); break; case 9: printf("請輸入要刪除的值:>"); scanf("%d", &item); delete_val(&mylist, item); break; case 10: sort(&mylist); break; case 11: reverse(&mylist); break; case 12: clear(&mylist); break; //case 13: //destroy(&mylist); //break; default: printf("選擇錯誤,請重新選擇！/n"); break; } } destroy(&mylist); //程序結束，摧毀鏈表}附：單鏈表優化版本
slist.h
#ifndef __SLIST_H__#define __SLIST_H__#include<cstdio>#include<malloc.h>#include<assert.h>typedef int ElemType;typedef struct Node { //定義單鏈表中的結點信息 ElemType data; //結點的數據域 struct Node *next; //結點的指針域}Node,*PNode;typedef struct List { //定義單鏈表的鏈表信息 PNode first; //first指向單鏈表中的第一個結點 PNode last; //last指向單鏈表中的最后一個結點 size_t size; //記錄單鏈表中的結點個數}List;void InitList(List *list);//初始化單鏈表void push_back(List *list, ElemType x);//在單鏈表的末尾插入元素void push_front(List *list, ElemType x);//在單鏈表的頭部插入元素void show_list(List *list);//打印單鏈表void pop_back(List *list);//刪除單鏈表的最后一個元素void pop_front(List *list);//刪除單鏈表的第一個元素void insert_val(List *list, ElemType val);//將數據元素插入到單鏈表中（要求此時單鏈表中的數據元素順序排列）Node* find(List *list, ElemType x);//查找單鏈表中數據值為x的結點int length(List *list);//求單鏈表的長度void delete_val(List *list, ElemType x);//按值刪除單鏈表中的某個數據元素void sort(List *list);//對單鏈表進行排序void reverse(List *list);//逆置單鏈表void clear(List *list);//清除單鏈表void destroy(List *list);//摧毀單鏈表//代碼優化Node* CreateNode(ElemType x); //創建一個單鏈表結點Node* begin(List *list); //返回單鏈表的第一個結點Node* end(List *list); //返回單鏈表中最后一個結點的下一個結點void insert(List *list, Node *pos, ElemType x); //在單鏈表的特定位置（pos）插入新的結點#endif //__SLIST_H__slist.cpp
#include"slist.h"void InitList(List *list) { list->first = list->last = (Node*)malloc(sizeof(Node)); //頭結點 assert(list->first != NULL); list->first->next = NULL; list->size = 0;}//push_back的優化void push_back(List *list, ElemType x) { insert(list, end(list), x);}//push_front的優化void push_front(List *list, ElemType x) { insert(list, begin(list), x);}void show_list(List *list) { //step 1：指針p指向單鏈表的第一個結點 Node *p = list->first->next; //step 2：循環打印結點的信息 while (p != NULL) { printf("%d->", p->data); p = p->next; } printf("Nul./n");}void pop_back(List *list) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：定義指針p使其指向目標結點的前一個結點 Node *p = list->first;//從頭結點開始 while (p->next != list->last) p = p->next; //step 3：刪除目標結點 free(list->last); list->last = p; list->last->next = NULL; //step 4：更新單鏈表的長度 list->size--;}void pop_front(List *list) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：定義指針p使其指向目標結點的前一個結點 Node *p = list->first->next; //step 3：刪除目標結點 list->first->next = p->next; free(p); //step 4：判斷刪除的結點是否是單鏈表的最后一個結點，若是則更新單鏈表的尾指針 if (list->size == 1) list->last = list->first; //step 4：更新單鏈表的長度 list->size--;}//insert_val的優化void insert_val(List *list, ElemType x) { //step 1：創建一個新的結點 Node *s = CreateNode(x); //step 2：定義指針p使其指向待插入位置的前一個結點 Node *p = list->first;//從頭結點開始 while (p->next != NULL && p->next->data < s->data) p = p->next; //step 3：判斷結點的待插入位置是否是表尾，若是則更新單鏈表的尾指針 if (p->next == NULL) list->last = s; //step 4：插入結點 s->next = p->next; p->next = s; //step 5：更新單鏈表長度 list->size++;}Node* find(List *list, ElemType x) { //step 1：指針p指向單鏈表的第一個結點 Node *p = list->first->next; //step 2：按照循環順序查找鏈表結點 while (p != NULL && p->data != x) p = p->next; return p;}int length(List *list) { return list->size;}void delete_val(List *list, ElemType x) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：確定結點在單鏈表中的位置，并判斷其是否存在于單鏈表中 Node *p = find(list, x); if (p == NULL) { printf("要刪除的數據不存在！/n"); return; } //step 3：判斷結點位置是否是表尾 if (p == list->last)//是表尾 pop_back(list); else {//不是表尾 Node *q = p->next; p->data = q->data; p->next = q->next; free(q); list->size--; }}void sort(List *list) { //step 1：判斷單鏈表中的結點數是否為0或1 if (list->size == 0 || list->size == 1) return; //step 2：將單鏈表中第一個結點之后的鏈表部分截出，方便重新按順序插入鏈表之中 Node *s = list->first->next; // 指針s指向單鏈表的第一個節點 Node *p = s->next;//q指向s后面的結點 list->last = s;//單鏈表的尾指針指向單鏈表的第一個結點 list->last->next = NULL;//截斷鏈表 //step 3：將截出的鏈表中的結點根據其數據域大小重新插入到原來鏈表中 while (p != NULL) { s = p; p = p->next; Node *q = list->first; while (q->next != NULL && q->next->data < s->data) q = q->next; if (q->next == NULL)//判斷q此時指向的是否是單鏈表的最后一個結點，若是則更新鏈表的尾指針 list->last = s; //將結點重新插入鏈表 s->next = q->next; q->next = s; }}void reverse(List *list) { //step 1：判斷單鏈表中的結點數是否為0或1 if (list->size == 0 || list->size == 1) return; //step 2：將單鏈表中第一個結點之后的鏈表部分截出，然后將截出的鏈表中的結點按頭插法重新插入到原鏈表中 Node *p = list->first->next; Node *q = p->next; list->last = p; list->last->next = NULL; while (q != NULL) { p = q; q = q->next; p->next = list->first->next; list->first->next = p; }}void clear(List *list) { //step 1：判斷單鏈表是否為空 if (list->size == 0) return; //step 2：釋放單鏈表中的每一個結點 Node *p = list->first->next; while (p != NULL) { list->first->next = p->next; free(p); p = list->first->next; } //step 3：頭指針和尾指針重新都指向頭結點 list->last = list->first; //step 4：更新鏈表長度 list->size = 0;}void destroy(List *list) { //step 1：清空單鏈表 clear(list); //step 2：釋放頭結點 free(list->first); //step 3：頭指針和尾指針都賦值為空 list->first = list->last = NULL;}//優化Node* CreateNode(ElemType x) { Node *s = (Node*)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = NULL; return s;}Node* begin(List *list) { return list->first->next;}Node* end(List *list) { return list->last->next;}void insert(List *list, Node *pos, ElemType x) { //step 1：創建一個新的結點 Node *s = CreateNode(x); //step 2：確定帶插入位置 Node *p = list->first; while (p->next != pos) p = p->next; //step 3：插入結點 s->next = p->next; p->next = s; //step 4：判斷結點是否插入到鏈表的表尾，若是則更新單鏈表的表尾指針 if (pos == NULL) list->last = s; //step 5：更新單鏈表長度 list->size++;}main.cpp
#include"slist.h"void main() { List mylist; InitList(&mylist); ElemType item; Node *p = NULL; int select = 1; while (select) { printf("*******************************************/n"); printf("*[1] push_back [2] push_front */n"); printf("*[3] show_list [4] pop_back */n"); printf("*[5] pop_front [6] insert_val */n"); printf("*[7] find [8] length */n"); printf("*[9] delete_val [10] sort */n"); printf("*[11] reverse [12] clear */n"); printf("*[13*] destroy [0] quit_system */n"); printf("*******************************************/n"); printf("請選擇：>>"); scanf("%d", &select); if (select == 0) break; switch (select) { case 1: printf("請輸入要插入的數據（-1結束）:>"); while (scanf("%d", &item), item != -1) { push_back(&mylist, item); } break; case 2: printf("請輸入要插入的數據（-1結束）:>"); while (scanf("%d", &item), item != -1) { push_front(&mylist, item); } break; case 3: show_list(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: printf("請輸入要插入的數據:>"); scanf("%d", &item); insert_val(&mylist, item); break; case 7: printf("請輸入要查找的數據:>"); scanf("%d", &item); p = find(&mylist, item); if (p == NULL) printf("要查找的數據在單鏈表中不存在！/n"); break; case 8: printf("單鏈表的長度為%d/n", length(&mylist)); break; case 9: printf("請輸入要刪除的值:>"); scanf("%d", &item); delete_val(&mylist, item); break; case 10: sort(&mylist); break; case 11: reverse(&mylist); break; case 12: clear(&mylist); break; //case 13: //destroy(&mylist); //break; default: printf("選擇錯誤,請重新選擇！/n"); break; } } destroy(&mylist); //程序結束，摧毀鏈表}希望本文所述對大家C語言程序設計有所幫助。
新聞熱點
疑難解答
