一起來看看C語言線性表的線性鏈表
定義
鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素,每一個結(jié)點包含兩個域:存放數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域,存放其后繼元素地址的域稱為指針域。因此n個元素的線性表通過每個結(jié)點的指針域連接成了一個“鏈條”,稱為鏈表。若此鏈表的每個結(jié)點中只包含一個指針域,則被稱為線性鏈表或單鏈表。
線性表的鏈式存儲結(jié)構(gòu),它不需要用地址連續(xù)的存儲單元來實現(xiàn),因為它不要求邏輯上相鄰的兩個數(shù)據(jù)元素物理位置上也相鄰,它是通過“指針”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。
鏈表是由一個個結(jié)點構(gòu)成的,結(jié)點定義如下:
typedef struct node { DataType data; struct node *next; } Linklist;
線性鏈表的存取必須從表頭指針開始,表頭指針指示線性鏈表中第一個結(jié)點的存儲單位置。由于線性表最后一個數(shù)據(jù)元素沒有直接后繼,則線性鏈表中的最后一個結(jié)點的指針域為“空”(NULL)。
為了使用方便可以在第一個元素的前面增加一個結(jié)點(被稱為頭節(jié)點),該節(jié)點的數(shù)據(jù)域為空,指針域中存儲線性鏈表的第一個元素所在的結(jié)點(表頭結(jié)點)的存儲地址。如果為空表,則指針域為空。
因此空鏈表也分為帶有頭結(jié)點的空鏈表和不帶頭結(jié)點的空鏈表。若有頭結(jié)點,頭結(jié)點的數(shù)據(jù)域為空,指針域為空,則說明該鏈表為空鏈表;若沒有頭結(jié)點,表頭指針為空指針,則說明該鏈表為空鏈表。
1.插入
假設(shè)要在線性表的兩個數(shù)據(jù)元素a和b之間插入一個數(shù)據(jù)元素x,p為指向結(jié)點a的指針。為了插入數(shù)據(jù)元素x,首先要生成一個數(shù)據(jù)域為x的新結(jié)點,s為指向新增節(jié)點的指針,然后使新增節(jié)點的指針域指向b(p->next),結(jié)點a的指針域指向新增節(jié)點(s)。
int InsertLinkList(LinkList *H, int i, DataType x) /*在有頭結(jié)點的線性鏈表H中第i個位置前插入元素x*/ { LinkList *p; LinkList *s; int j = 0; p = H; while (p && j<i-1) { p = p->next; j++; }/*循環(huán)直到p指向第i-1個元素*/ if (!p) return -1;/*i大于表長加1*/ s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = p->next;/*插入數(shù)據(jù)元素x*/ p->next = s; return 1; }
2.建立線性鏈表
1)頭插法
建立線性鏈表應(yīng)從空表開始,每讀入一個數(shù)據(jù)元素則申請一個結(jié)點,然后插在鏈表的頭結(jié)點與第一個結(jié)點之間。記頭結(jié)點為H,申請的結(jié)點為s,按照上述插入算法,操作步驟為:
s->next = H->next; H->next = s;
再加上新建頭結(jié)點、讀入數(shù)據(jù)元素、申請結(jié)點等步驟,可編程如下:
LinkList *CreateLinkList_front() { LinkList *H;/*H表示頭結(jié)點*/ LinkList *s; char x;/*設(shè)數(shù)據(jù)元素的類型為char*/ H = (LinkList *)malloc(sizeof(LinkList));/*為頭結(jié)點申請內(nèi)存空間*/ H->next = NULL; scanf(" %c", &x); while (x!=flag)/*flag為結(jié)束創(chuàng)建過程的標志,如'#'等*/ { s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = H->next; H->next = s; scanf(" %c", &x); } return H; }
因為是在鏈表的頭部插入,讀入數(shù)據(jù)的順序和線性表中的邏輯順序是相反的。
2)尾插法
在表頭插入建立線性鏈表方法簡單,但讀入數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的,若希望次序一致,則用尾插法。因為每次是將新結(jié)點插入到鏈表的尾部,所以需加入一個指針用來始終指向鏈表中的尾結(jié)點,以便能夠?qū)⑿陆Y(jié)點插入到鏈表的尾部。
在前面,我們介紹了插入算法,在這里可以通過調(diào)用插入算法,即定義一個變量int i = 1;,調(diào)用前面的函數(shù)InsertLinkList(H, i, x);,每插入一個數(shù)據(jù)元素,便使i++;,這樣就可一直保持在鏈表的尾部插入。
LinkList *CreateLinkList_rear() { LinkList *H; DataType x;/*設(shè)DataType為數(shù)據(jù)元素的類型*/ int i = 1; H = (LinkList *)malloc(sizeof(LinkList)); H->next = NULL; scanf(&x);/*讀入數(shù)據(jù)元素的值*/ while (x!=flag) { InsertLinkList(H, i, x);/*調(diào)用插入算法*/ i++; scanf(&x); } return H; }
但是這樣使得算法的時間復雜度比頭插法要高出了一個數(shù)量級,因為每次在尾部插入數(shù)據(jù)元素時,都要重新調(diào)用InsertLinkList()函數(shù),使指針重新從表頭指針開始指向尾結(jié)點。
因此我們可以使指針(記為p)一直指向鏈表中的尾結(jié)點,然后讓新結(jié)點(記為s)按照插入算法插入鏈表的尾部。只需修改上述代碼的while循環(huán)即可實現(xiàn):
LinkList *CreateLinkList_rear() { LinkList *H, *p, *s; DataType x;/*設(shè)DataType為數(shù)據(jù)元素的類型*/ H = (LinkList *)malloc(sizeof(LinkList)); H->next = NULL; scanf(&x);/*讀入數(shù)據(jù)元素的值*/ p = H; while (x!=flag) { s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = NULL; p->next = s; p = p->next; scanf(&x); } return H; }
3.刪除
假設(shè)鏈表中有a, b, c3個數(shù)據(jù)元素,要刪除數(shù)據(jù)元素a和數(shù)據(jù)元素c中間的數(shù)據(jù)元素b時,僅需修改數(shù)據(jù)元素a所在的結(jié)點的指針域。假設(shè)指針p指向數(shù)據(jù)元素a,用語句表示就是:
p->next = p->next->next;
添加一個指針變量q,讓q指向數(shù)據(jù)元素b,當改變數(shù)據(jù)元素a所在的結(jié)點的指針域后,即可釋放q的內(nèi)存,即釋放數(shù)據(jù)元素b所占的內(nèi)存。進一步地,調(diào)用函數(shù)時傳入標志變量i,可實現(xiàn)刪除第i個數(shù)據(jù)元素。
int DeleteLinkList(LinkList *H, int i) /*在有頭結(jié)點的線性鏈表H中刪除第i個元素*/ { LinkList *p; LinkList *q; int j = 0; p = H; while (p->next && j<i-1) { p = p->next; j++; }/*循環(huán)直到p指向第i-1個元素*/ if (!(p->next)) return -1;/*刪除節(jié)點不合法*/ q = p->next; p->next = q->next;/*刪除第i個數(shù)據(jù)元素*/ free(q);/*釋放第i個數(shù)據(jù)元素所占內(nèi)存*/ return 1; }
對比插入算法和刪除算法,while循環(huán)的功能同樣是使p指向第i-1個元素,為什么插入算法的循環(huán)條件為p && j<i-1,而刪除算法的循環(huán)條件是p->next && j<i-1?能否將刪除算法的循環(huán)條件也改為p && j<i-1?
這是因為,在鏈表根本沒有i-1個元素的情況下,循環(huán)條件為p && j<i-1的循環(huán)運行結(jié)果為p指向尾結(jié)點的下一個結(jié)點即p=NULL,而循環(huán)條件為p->next && j<i-1的循環(huán)運行結(jié)果為p指向尾結(jié)點即p≠NULL。若將刪除算法的循環(huán)條件也改為p && j<i-1,在鏈表根本沒有i-1個元素的情況下,while循環(huán)后面的語句if (!(p->next))將會造成非法內(nèi)存訪問,因為此時p=NULL,我們無法訪問空指針指向的內(nèi)容。
4.查找
查找結(jié)點使用的算法是線性查找法(順序查找法),即從鏈表的第一個結(jié)點開始,順著指針鏈一個一個比較,相等則查找成功,返回結(jié)點位置;如果比較到最后也沒有相等的,則查找不成功,返回空。
LinkList *SearchLinkList(LinkList *H, DataType x) /*在線性鏈表H中查找值為x的結(jié)點,找到后返回其指針,否則返回空*/ { LinkList *p = H->next;/*p指向線性鏈表的第一個數(shù)據(jù)元素*/ while (p!=NULL && p->data!=x) p = p->next; return p; }
若要返回值為x的結(jié)點在鏈表中的位序,則可使用一個標記變量i,記錄結(jié)點的位序;若找不到則返回-1。修改程序如下:
int SearchLinkList(LinkList *H, DataType x) /*在線性鏈表H中查找值為x的結(jié)點,找到后返回其在鏈表中的位序,否則返回-1*/ { LinkList *p = H->next;/*p指向線性鏈表的第一個數(shù)據(jù)元素*/ int i = 1; while (p!=NULL && p->data!=x) { p = p->next; i++; } if (p != NULL) return i; else return -1; }
5.求線性鏈表的表長
設(shè)H是帶頭結(jié)點的線性鏈表(線性表的長度不包括頭結(jié)點),求線性鏈表的表長的操作與上述查找某結(jié)點在鏈表中的位序相似。
int LinkListLength(LinkList *H) { LinkList *p = H;/*p指向頭結(jié)點*/ int n = 0; while (p->next) { p = p->next; n++; }/*p所指的是第n個結(jié)點*/ return n; }
總結(jié)
本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法
這篇文章主要為大家詳細介紹了C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-01-01cocos2dx實現(xiàn)橡皮擦效果以及判斷是否擦除完畢
這篇文章主要為大家詳細介紹了cocos2dx實現(xiàn)橡皮擦效果以及判斷是否擦除完畢,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-12-12C++ Leetcode實現(xiàn)從英文中重建數(shù)字
本文主要介紹了當給你一個字符串s,其中包含字母順序打亂的用英文單詞表示的若干數(shù)字(0-9)時,如何通過Leetcode按升序返回原始的數(shù)字。感興趣的童鞋可以來看看2021-11-11C++實現(xiàn)LeetCode(156.二叉樹的上下顛倒)
這篇文章主要介紹了C++實現(xiàn)LeetCode(156.二叉樹的上下顛倒),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07