帶頭結點單鏈表與不帶頭結點單鏈表的區(qū)別
鏈表作為一種基本數(shù)據(jù)結構,常用的鏈表分為帶結點和不帶頭結點。從線性表的定義可以知道,線性表允許在任意位置進行插入和刪除。所有的鏈表都有一個頭指針head,帶頭結點的鏈表中head的數(shù)據(jù)項為空,而不帶頭的鏈表直接在頭結點存入數(shù)據(jù),那么當從頭插入數(shù)據(jù)時,head需要時刻變化。
接下來具體分析:
1.帶頭結點的鏈表的插入,使用一個臨時變量p等于插入之前的結點(不管具體插入位置),之后不論要插入的結點x是插到鏈表頭還是插入到鏈表其他位置都是如下語句:
x->next=p->next; p->next=x;
2.不帶頭結點的鏈表的插入,若要插入到鏈表的開頭:
x->next=head; head=x; ?//這里不再是head->next=x;
若插到鏈表的其他位置:
p=插入之前的結點 x->next=p->next; p->next=x;
3.帶頭結點的刪除:
p是刪除結點之前結點
x是要刪除結點
p->next=x->next;
free(x);
同樣不存在刪除位置的差異。
4.不帶頭結點的刪除:
刪除第一個結點:head=head->next;這時需要改變鏈表的頭結點。
刪除其他結點時,head的值不會變。
綜上所述,帶頭結點的單鏈表,不論刪除和插入的位置如何,不需要修改head的值,不帶頭結點的單鏈表當頭插和頭刪需要修改head的值。所以一般單鏈表一般帶有頭結點。
下面是其它的補充
下面的代碼中,傳遞鏈表時,傳的是頭指針。如果是帶頭結點的鏈表,傳遞鏈表時,可以傳頭結點,具體可以看看 C語言實現(xiàn)-線性表的鏈式存儲(單鏈表)
帶頭結點單鏈表 和 不帶頭結點單鏈表的區(qū)別:
帶頭結點單鏈表,在進行插入、刪除操作時,不需要改變鏈表頭指針。
不帶頭結點的單鏈表,在進行插入、刪除操作時,可能會涉及到鏈表頭指針的修改(所以鏈表作為參數(shù)傳遞時,傳遞的是頭指針的引用,具體可看代碼④中head_insert方法中的指針變量帶了&取地址符,而代碼⑤中的沒有。因為帶頭結點單鏈表進行頭插操作不需要修改頭指針,而不帶頭結點的單鏈表進行頭插操作時需要修改頭指針)
具體的代碼也有些許差異,可對比 代碼④ 和 代碼⑤
帶頭結點單鏈表 和 不帶頭結點的init()初始化都修改了頭指針,所以指針變量帶了&取地址符
不帶頭結點的操作
① ② ③ ④ 四組代碼本質(zhì)是一樣的。只是我本人對地址、指針、引用、指針變量概念不是很理解,所以才寫了這四組代碼進行對比,方便自己以后復習理解。讀者可以跳過① ② ③,直接看④的代碼即可
代碼①
#include <stdio.h> #include <malloc.h> typedef struct LNode { int data; struct LNode *next; }; void init(LNode **L) { *L = NULL; } void head_insert(LNode **L, int x) { LNode *newP = (LNode *)malloc(sizeof(LNode)); newP->data = x; newP->next = *L; *L = newP; } LNode *get(LNode *L, int k) { if (k < 1) { printf("查找位置非法!"); return NULL; } int i = 1; if (L != NULL && i <= k) { L = L->next; i++; } if (i == k) { return L; } printf("查找位置非法!"); return NULL; } void print(LNode *L) { printf("\n"); while (L) { printf("%4d ", L->data); L = L->next; } printf("\n"); } int main() { LNode *L; init(&L); head_insert(&L, 15); head_insert(&L, 25); head_insert(&L, 35); print(L); printf("\n%4d \n", get(L, 2)->data); return 0; }
代碼②
#include <stdio.h> #include <malloc.h> typedef struct LNode { int data; struct LNode *next; }; void init(LNode *&L) { L = NULL; } void head_insert(LNode *&L, int x) { LNode *newP = (LNode *)malloc(sizeof(LNode)); newP->data = x; newP->next = L; L = newP; } LNode *get(LNode *L, int k) { if (k < 1) { printf("查找位置非法!"); return NULL; } int i = 1; if (L != NULL && i <= k) { L = L->next; i++; } if (i == k) { return L; } printf("查找位置非法!"); return NULL; } void print(LNode *L) { printf("\n"); while (L) { printf("%4d ", L->data); L = L->next; } printf("\n"); } int main() { LNode *L; init(L); head_insert(L, 15); head_insert(L, 25); head_insert(L, 35); print(L); printf("\n%4d \n", get(L, 2)->data); return 0; }
代碼③
#include <stdio.h> #include <malloc.h> typedef struct LNode { int data; struct LNode *next; }*LinkList; void init(LinkList *L) { *L = NULL; } void head_insert(LinkList *L, int x) { LinkList newP = (LinkList)malloc(sizeof(LNode)); newP->data = x; newP->next = *L; *L = newP; } LinkList get(LinkList L, int k) { if (k < 1) { printf("查找位置非法!"); return NULL; } int i = 1; if (L != NULL && i <= k) { L = L->next; i++; } if (i == k) { return L; } printf("查找位置非法!"); return NULL; } void print(LinkList L) { printf("\n"); while (L) { printf("%4d ", L->data); L = L->next; } printf("\n"); } int main() { LinkList L; init(&L); head_insert(&L, 15); head_insert(&L, 25); head_insert(&L, 35); print(L); printf("\n%4d \n", get(L, 2)->data); return 0; }
代碼④
#include <stdio.h> #include <malloc.h> //結構體 typedef struct LNode { int data; struct LNode *next; } *LinkList; //初始化 void init(LinkList &L) { L = NULL; } //頭插 void head_insert(LinkList &L, int x) { LinkList newP = (LinkList)malloc(sizeof(LNode)); newP->data = x; newP->next = L; L = newP; } //按位序查找 LinkList get(LinkList L, int k) { if (k < 1) { printf("查找位置非法!"); return NULL; } int i = 1; if (L != NULL && i <= k) { L = L->next; i++; } if (i == k) { return L; } printf("查找位置非法!"); return NULL; } //遍歷輸出 void print(LinkList L) { printf("\n"); while (L) { printf("%4d ", L->data); L = L->next; } printf("\n"); } int main() { LinkList L; init(L); head_insert(L, 15); head_insert(L, 25); head_insert(L, 35); print(L); printf("\n%4d \n", get(L, 2)->data); return 0; }
帶頭結點的操作
代碼⑤
#include <stdio.h> #include <malloc.h> //結構體 typedef struct LNode { int data; struct LNode *next; } *LinkList; //初始化 void init(LinkList &L) { LinkList newp = (LinkList)malloc(sizeof(LNode)); newp->next = NULL; L = newp; } //頭插 void head_insert(LinkList L, int x) { LinkList newp = (LinkList)malloc(sizeof(LNode)); newp->data = x; newp->next = L->next; L->next = newp; } //按位序查找 LinkList get(LinkList L, int k) { if (k < 1) { printf("查找位置非法!"); return NULL; } int i = 1; LinkList p = L->next; if (p != NULL && i <= k) { p = p->next; i++; } if (i == k) { return p; } printf("查找位置非法!"); return NULL; } //遍歷輸出 void print(LinkList L) { printf("\n"); LinkList p = L->next; while (p) { printf("%4d ", p->data); p = p->next; } printf("\n"); } int main() { LinkList L; init(L); head_insert(L, 15); head_insert(L, 25); head_insert(L, 35); print(L); printf("\n%4d \n", get(L, 2)->data); return 0; }
到此這篇關于帶頭結點單鏈表與不帶頭結點單鏈表的區(qū)別的文章就介紹到這了,更多相關帶頭與不帶頭結點單鏈表區(qū)別內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
C語言使用ffmpeg實現(xiàn)單線程異步的視頻播放器
這篇文章主要為大家詳細介紹了C語言如何使用ffmpeg實現(xiàn)單線程異步的視頻播放器功能,文中的示例代碼講解詳細,感興趣的小伙伴可以嘗試一下2022-12-12C++實現(xiàn)LeetCode(100.判斷相同樹)
這篇文章主要介紹了C++實現(xiàn)LeetCode(100.判斷相同樹),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07應用程序操作NorFlash示例代碼分享(norflash接口使用方法)
相對于操作NandFlash,操作NorFlash相對簡單,因為基本不需要考慮壞塊,NorFlash也沒有OOB區(qū)域,也跟ECC沒有關系。讀寫擦除相對容易,下面看個例子吧2013-12-12C++歸并法+快速排序?qū)崿F(xiàn)鏈表排序的方法
這篇文章主要介紹了C++歸并法+快速排序?qū)崿F(xiàn)鏈表排序的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-04-04VS2010+Opencv+MFC讀取圖像和視頻顯示在Picture控件
這篇文章主要為大家詳細介紹了VS2010+Opencv+MFC讀取圖像和視頻顯示在Picture控件,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-08-08