您好,登錄后才能下訂單哦!
這篇文章主要介紹“如何理解C++編程語(yǔ)言實(shí)現(xiàn)單鏈表”,在日常操作中,相信很多人在如何理解C++編程語(yǔ)言實(shí)現(xiàn)單鏈表問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”如何理解C++編程語(yǔ)言實(shí)現(xiàn)單鏈表”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
一、單鏈表簡(jiǎn)單介紹
二、下面我們先實(shí)現(xiàn)單鏈表的初始化。
三、實(shí)現(xiàn)單鏈表的插入與刪除數(shù)據(jù)
首先,我們?cè)倩仡櫼幌戮€性表的兩種存儲(chǔ)方式——順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)
上圖左邊為順序存儲(chǔ),右邊為鏈?zhǔn)酱鎯?chǔ)
之前我們利用數(shù)組來實(shí)現(xiàn)順序表,對(duì)于順序表的優(yōu)點(diǎn)缺點(diǎn),總結(jié)來說就是,查找方便,增刪復(fù)雜。
線性表之順序存儲(chǔ)的優(yōu)缺點(diǎn)
而鏈表特點(diǎn)可以說恰恰相反,增刪方便,查找復(fù)雜。
今天實(shí)現(xiàn)的是鏈表中最簡(jiǎn)單的一種——單鏈表(每個(gè)結(jié)點(diǎn)中只含有一個(gè)指針域)
對(duì)于鏈表我們只知道它每個(gè)結(jié)點(diǎn)的存儲(chǔ)的物理地址是不連續(xù)的,但邏輯上還是符合線性表“一對(duì)一”的特點(diǎn)。因此,我們就需要用“線”(指針)把這些不連續(xù)的結(jié)點(diǎn)按順序連接起來。
鏈表的結(jié)點(diǎn)在內(nèi)存中存儲(chǔ)不連續(xù)
通過指針把每個(gè)結(jié)點(diǎn)按順序連起來
到這里我們可以發(fā)現(xiàn),要想表示鏈表中的結(jié)點(diǎn),光存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)是不夠的,還得有指針。因此,單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下:
數(shù)據(jù)域存儲(chǔ)數(shù)據(jù),指針域存儲(chǔ)指針
//================線性表的單鏈表存儲(chǔ)結(jié)構(gòu)================= typedef struct LNode { ElemType data;//數(shù)據(jù)域 struct LNode *next;//指針域 }LNode;
注意:因?yàn)橹羔樖侵赶蛎總€(gè)結(jié)點(diǎn)的,也就是指向struct LNode
這個(gè)自定義的結(jié)構(gòu)體類型,所以指針的類型就是struct LNode*。
單鏈表的初始化其實(shí)就是創(chuàng)建幾個(gè)結(jié)點(diǎn),然后用指針把他們連接起來。
先創(chuàng)建一個(gè)頭指針,實(shí)際上就是創(chuàng)建一個(gè)頭結(jié)點(diǎn),然后頭指針指向頭結(jié)點(diǎn)就OK
LNode* CreateList_L(int n) {//順位序輸入n個(gè)元素的值,建立帶表頭結(jié)點(diǎn)的單鏈線性表L LNode *p = (LNode*)malloc(sizeof(LNode));//創(chuàng)建頭結(jié)點(diǎn)(p也就是頭指針) LNode *temp = p;//聲明一個(gè)指針指向頭結(jié)點(diǎn),用于遍歷鏈表(不是頭指針,因?yàn)樗皇菚簳r(shí)指向頭結(jié)點(diǎn)) //生成鏈表 for (int i = n; i > 0; --i) { LNode *node = (LNode *)malloc(sizeof(LNode));//創(chuàng)建結(jié)點(diǎn) if (node){//分配地址成功 scanf_s("%c", &(node->data)); node->next = NULL; //建立新結(jié)點(diǎn)與直接前驅(qū)結(jié)點(diǎn)的邏輯關(guān)系 temp->next = node; temp = temp->next; } else {//如果分配地址失敗,則返回錯(cuò)誤信息 printf("結(jié)點(diǎn)創(chuàng)建失??!\n"); } } return p; }
單鏈表插數(shù)據(jù)情況
觀察可知,我們要實(shí)現(xiàn)插入操作,需要的操作是一樣的。
S1:將后繼結(jié)點(diǎn)的指針賦給新結(jié)點(diǎn)的指針域;
S2:將前驅(qū)節(jié)點(diǎn)的指針域改為指向新結(jié)點(diǎn)的指針。
注意:S1和S2不能換順序。
//===============================算法2.9========================== Status ListInsert_L(LNode *L, int i, ElemType e) { //在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素e int j = 0; LNode *p = L; while (p&&j < i - 1) { p = p->next; ++j; }//尋找第i-1個(gè)結(jié)點(diǎn) if (!p || j > i - 1)return ERROR;//i小于1或者大于表長(zhǎng)時(shí) LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的結(jié)點(diǎn) s->data = e; s->next = p->next;//S1 p->next = s;//S2 return OK; }
單鏈表刪除數(shù)據(jù)示意圖
觀察可知,只需要將待刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針域的值換成待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針即可。
//=====================算法2.10================================= Status ListDelete_L(LNode *L, int i, ElemType *e) { //在帶頭結(jié)點(diǎn)的單鏈表L中,刪除第i個(gè)元素,并由e返回其值 LNode *p = L; int j = 0; while (p->next&&j < i - 1) {//尋找第i個(gè)結(jié)點(diǎn),并令p指向其前驅(qū) p = p->next; ++j; } if (!(p->next) || j > i - 1)return ERROR;//刪除位置不合理 LNode *q = p->next; p->next = q->next;//刪除并釋放結(jié)點(diǎn) *e = q->data; free(q); return OK; } 三、參考代碼實(shí)現(xiàn)與截圖 #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define ElemType char typedef int Status; //================線性表的單鏈表存儲(chǔ)結(jié)構(gòu)================== typedef struct LNode { ElemType data;//數(shù)據(jù)域 struct LNode *next;//指針域 }LNode; LNode* CreateList_L(int n) {//順位序輸入n個(gè)元素的值,建立帶表頭結(jié)點(diǎn)的單鏈線性表L LNode *p = (LNode*)malloc(sizeof(LNode));//創(chuàng)建頭結(jié)點(diǎn) LNode *temp = p;//聲明一個(gè)指針指向頭結(jié)點(diǎn),用于遍歷鏈表(不是頭指針) //生成鏈表 for (int i = n; i > 0; --i) { LNode *node = (LNode *)malloc(sizeof(LNode));//創(chuàng)建結(jié)點(diǎn) if (node){//分配地址成功 scanf_s("%c", &(node->data)); node->next = NULL; //建立新結(jié)點(diǎn)與直接前驅(qū)結(jié)點(diǎn)的邏輯關(guān)系 temp->next = node; temp = temp->next; } else {//如果分配地址失敗,則返回錯(cuò)誤信息 printf("結(jié)點(diǎn)創(chuàng)建失??!\n"); } } return p; } //===============================算法2.9========================== Status ListInsert_L(LNode *L, int i, ElemType e) { //在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素e int j = 0; LNode *p = L; while (p&&j < i - 1) { p = p->next; ++j; }//尋找第i-1個(gè)結(jié)點(diǎn) if (!p || j > i - 1)return ERROR;//i小于1或者大于表長(zhǎng)時(shí) LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的結(jié)點(diǎn) s->data = e; s->next = p->next; p->next = s; return OK; } //=====================算法2.10================================= Status ListDelete_L(LNode *L, int i, ElemType *e) { //在帶頭結(jié)點(diǎn)的單鏈表L中,刪除第i個(gè)元素,并由e返回其值 LNode *p = L; int j = 0; while (p->next&&j < i - 1) {//尋找第i個(gè)結(jié)點(diǎn),并令p指向其前驅(qū) p = p->next; ++j; } if (!(p->next) || j > i - 1)return ERROR;//刪除位置不合理 LNode *q = p->next; p->next = q->next;//刪除并釋放結(jié)點(diǎn) *e = q->data; free(q); return OK; } void display(LNode *L) { LNode *temp =L;//將temp指針重新指向頭結(jié)點(diǎn) //只要temp指針指向的結(jié)點(diǎn)的next不是Null,就執(zhí)行輸出語(yǔ)句。 while (temp->next) { temp = temp->next; printf("%c", temp->data); } printf("\n"); } int main() { LNode *L = NULL; L=CreateList_L(5); display(L); ListInsert_L(L, 2, 'Y'); display(L); ElemType e; ListDelete_L(L, 2, &e); display(L); printf("返回值為:%c", e); system("pause"); return 0; }
初始化鏈表為abcdef
,在第2個(gè)位置插入Y,然后刪除Y
到此,關(guān)于“如何理解C++編程語(yǔ)言實(shí)現(xiàn)單鏈表”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。