帶頭結(jié)點的鏈表的基本操作(超詳細(xì))
鏈表是一種動態(tài)分配空間的存儲結(jié)構(gòu),能更有效地利用存儲空間,通過對單鏈表基本操作的代碼實現(xiàn),我深刻領(lǐng)悟到以“指針”指示元素的后繼,在插入或刪除元素時不需要移動元素。但是與此同時,由于鏈表是“順序存取”的結(jié)構(gòu),給隨機存取元素和在表尾插入等操作帶來不便。,所以接下來我將學(xué)習(xí)尾指針表示的單鏈表,雙向鏈表以及循環(huán)鏈表等。
前言
本文參考王卓老師的數(shù)據(jù)結(jié)構(gòu)視頻和嚴(yán)蔚敏老師的《數(shù)據(jù)結(jié)構(gòu)》
一、鏈表的定義
用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。
結(jié)點 = 數(shù)據(jù)元素+指針(指后繼元素存儲位置)
二、鏈表的 C 語言描述
代碼如下(示例):
//帶頭結(jié)點的單鏈表 typedef struct LNode { int data; struct LNode* next; }Lnode,*LinkList;
三、鏈表中基本操作的實現(xiàn)
3.1構(gòu)造一個帶頭結(jié)點的空鏈表
c++中用new來動態(tài)的開辟空間,而c中則是用malloc來開辟空間
我使用new來動態(tài)開辟空間
注意:參數(shù)是引用型的
代碼如下(示例):
void InitList(LinkList& L) { L = new Lnode;//L=(LinkList)malloc(sizeof(LNode)) L->next = NULL; }
3.2取第i個數(shù)據(jù)元素
結(jié)束條件:鏈表走到空或者i的大小不對,比1小
則while語句判斷條件為:while(p&&j<i) p表示當(dāng)前節(jié)點不為空,j<i表示傳進來的i是正確的,并且到該點
當(dāng)此時p為空或者j>i,則返回0,表示未找到
否則把此時節(jié)點的data傳給引用型參數(shù)data,并返回1
代碼如下(示例):
int GetElem_L(LinkList L, int i, int& data) { int j = 1; Lnode* p; p = L->next; while (p && j < i) { p = p->next; j++; } if (!p || j > i) return 0; data = p->data; return 1; }
3.3在鏈表中查找值為e的元素
時間效率分析:查找次數(shù)與位置有關(guān),O(n)
注意,可以按照具體情況來寫函數(shù)的返回值類型
比如,返回值類型可以是節(jié)點的地址,也可以是節(jié)點的位置
3.3.1返回值類型是節(jié)點的地址
代碼如下(示例):
Lnode* LocationElem(LinkList L, int e) { Lnode* p = L->next; while (p && p->data != e) { p = p->next; } return p; }
3.3.2返回值類型是節(jié)點的位置(序號)
代碼如下(示例):
int LocateElem_L(LinkList L, int e) { int j = 1; Lnode* p = L->next; while (p && p->data != e) { p = p->next; j++; } if (p) return j; else return 0; }
3.4在第i位插入數(shù)據(jù)元素
修改指針的時間O(1),但是不知道插在哪里,所以需要查找,查找時間O(n)
代碼如下(示例):
void ListInsert_L(LinkList& L, int i, int e) { int j = 0; Lnode* p = L; while (p && j < i - 1)//即找到i-1的位置 { p = p->next; j++; } if (!p || j > i - 1) { printf("i值錯誤,i小于1或大于表長\n"); return; } Lnode* s = new Lnode; s->data = e; s->next = NULL; s->next = p->next; p->next = s;//注意兩行不能調(diào)換位置,否則s指向自己,錯誤 printf("插入成功\n"); }
3.5刪除第i個數(shù)據(jù)元素
修改指針的時間O(1),但是不知道刪除位置,所以需要查找,查找時間O(n)
代碼如下(示例):
void ListDelete(LinkList& L, int i, int& e) { Lnode* p = L,*q; int j = 0; while (p->next && j < i - 1)//找到i-1的節(jié)點 { p = p->next; j++; } if (!(p->next) || j > i - 1) { printf("未找到要刪除的節(jié)點\n"); return; } q = p->next; e = q->data; p->next = q->next; delete q;//釋放空間 printf("成功刪除\n"); }
3.6 前插建立具有n的元素鏈表
時間復(fù)雜度:O(n)
逆序輸入
確保結(jié)果與想要的是一致的(與尾插結(jié)果一致)
代碼如下(示例):
void CreateList_F(LinkList& L, int t[],int n) { //創(chuàng)建n個節(jié)點 L = new Lnode; L->next = NULL; for(int i=n-1;i>=0;i--) { Lnode* p =new Lnode; p->data=t[i]; p->next = L->next; L->next = p; } }
3.7尾插建立具有n的元素鏈表
正序輸入
時間復(fù)雜度:O(n)
代碼如下(示例):
void CreateList_L(LinkList& L,int a[],int n) { //尾指針指向尾節(jié)點 L = new Lnode; L->next = NULL; Lnode* r = L;//尾指針,開始也指向頭節(jié)點 for (int i = 0; i < n; i++) { Lnode* p = new Lnode; p->data=a[i]; p->next = NULL; r->next = p; r = p;//把尾指針更新到新節(jié)點的位置 } }
3.8線性表置空
從首元節(jié)點開始刪除,保存了頭指針和頭節(jié)點
頭節(jié)點的next賦值為空
代碼如下(示例):
void CleanList(LinkList& L) { Lnode* p = L->next; Lnode* q; while (p) { q = p->next; delete p; p = q; } L->next = NULL; }
3.9銷毀鏈表
所有節(jié)點,包括頭節(jié)點也刪掉
代碼如下(示例):
void DestoryList(LinkList& L) { Lnode* p; while (L) { p = L; L = L->next; delete p; } }
3.10判斷鏈表是否為空
頭節(jié)點和頭指針還在算空表,返回1
當(dāng)頭節(jié)點的next值不為空,即起碼有個首元節(jié)點,則不算空表,返回0
代碼如下(示例):
int isEmpty(LinkList L) { if (L->next == NULL) return 1; return 0; }
3.11求鏈表的表長
用一個int型的length來計算,在循環(huán)中,當(dāng)tmp未走到空的時候,每次都加1
代碼如下(示例):
int ListLength(LinkList L) { Lnode* tmp = L->next; int length = 0; while (tmp != NULL) { length++; tmp = tmp->next; } return length; }
3.12遍歷鏈表
當(dāng)鏈表未走到空的時候,依次把所有節(jié)點的數(shù)據(jù)都輸出
代碼如下(示例):
void ListTraverse(LinkList L) { Lnode *tmp=L->next; int i=0; while(tmp!=NULL) { cout<<"第"<<i+1<<"個元素的數(shù)據(jù):"<<tmp->data<<endl; i++; tmp=tmp->next; } }
四、鏈表代碼實現(xiàn)
代碼如下(示例):
#include <iostream> using namespace std; const int N=101; //帶頭結(jié)點的單鏈表 typedef struct LNode { int data; struct LNode* next; }Lnode,*LinkList; //鏈表初始化 //構(gòu)造一個帶頭結(jié)點的空鏈表 void InitList(LinkList& L) { L = new Lnode;//L=(LinkList)malloc(sizeof(LNode)) L->next = NULL; } //判斷鏈表是否為空 //頭節(jié)點和頭指針還在(空表) int isEmpty(LinkList L) { if (L->next == NULL) return 1; return 0; } //銷毀鏈表 //所有節(jié)點,包括頭節(jié)點也刪掉 void DestoryList(LinkList& L) { Lnode* p; while (L) { p = L; L = L->next; delete p; } } //清空單鏈表 //清空元素,從首元節(jié)點開始刪除 void CleanList(LinkList& L) { Lnode* p = L->next; Lnode* q; while (p) { q = p->next; delete p; p = q; } L->next = NULL; } //求鏈表的表長 int ListLength(LinkList L) { Lnode* tmp = L->next; int length = 0; while (tmp != NULL) { length++; tmp = tmp->next; } return length; } //求第i個元素的值 int GetElem_L(LinkList L, int i, int& data) { int j = 1; Lnode* p; p = L->next; while (p && j < i) { p = p->next; j++; } if (!p || j > i) return 0; data = p->data; return 1; } //按值查找 返回地址 //時間效率分析:查找次數(shù)與位置有關(guān),O(n) Lnode* LocationElem(LinkList L, int e) { Lnode* p = L->next; while (p && p->data != e) { p = p->next; } return p; } //按值查找,返回位置序號 int LocateElem_L(LinkList L, int e) { int j = 1; Lnode* p = L->next; while (p && p->data != e) { p = p->next; j++; } if (p) return j; else return 0; } //在第i個元素之前插入值為e的節(jié)點 //修改指針的時間O(1),但是不知道插在哪里,所以需要查找,查找時間O(n) void ListInsert_L(LinkList& L, int i, int e) { int j = 0; Lnode* p = L; while (p && j < i - 1)//即找到i-1的位置 { p = p->next; j++; } if (!p || j > i - 1) { printf("i值錯誤,i小于1或大于表長\n"); return; } Lnode* s = new Lnode; s->data = e; s->next = NULL; s->next = p->next; p->next = s;//注意兩行不能調(diào)換位置,否則s指向自己,錯誤 printf("插入成功\n"); } //刪除 刪除第i個節(jié)點 //修改指針的時間O(1),但是不知道刪除位置,所以需要查找,查找時間O(n) void ListDelete(LinkList& L, int i, int& e) { Lnode* p = L,*q; int j = 0; while (p->next && j < i - 1)//找到i-1的節(jié)點 { p = p->next; j++; } if (!(p->next) || j > i - 1) { printf("未找到要刪除的節(jié)點\n"); return; } q = p->next; e = q->data; p->next = q->next; delete q;//釋放空間 printf("成功刪除\n"); } //頭插法建立單鏈表 時間復(fù)雜度:O(n) 逆序輸入 void CreateList_F(LinkList& L, int t[],int n) { //創(chuàng)建n個節(jié)點 L = new Lnode; L->next = NULL; for(int i=n-1;i>=0;i--) { Lnode* p =new Lnode; p->data=t[i]; p->next = L->next; L->next = p; } } //尾插法 正序輸入 時間復(fù)雜度:O(n) void CreateList_L(LinkList& L,int a[],int n) { //尾指針指向尾節(jié)點 L = new Lnode; L->next = NULL; Lnode* r = L;//尾指針,開始也指向頭節(jié)點 for (int i = 0; i < n; i++) { Lnode* p = new Lnode; p->data=a[i]; p->next = NULL; r->next = p; r = p;//把尾指針更新到新節(jié)點的位置 } } //遍歷 void ListTraverse(LinkList L) { Lnode *tmp=L->next; int i=0; while(tmp!=NULL) { cout<<"第"<<i+1<<"個元素的數(shù)據(jù):"<<tmp->data<<endl; i++; tmp=tmp->next; } } void menu() { cout<<"*******************************************"<<endl; cout<<"1.構(gòu)造一個帶頭結(jié)點的空鏈表 "<<endl; cout<<"2.建立具有n的元素鏈表"<<endl; cout<<"3.取第i個數(shù)據(jù)元素"<<endl; cout<<"4.在鏈表中查找值為e的元素"<<endl; cout<<"5.在第i位插入數(shù)據(jù)元素"<<endl; cout<<"6.刪除第i個數(shù)據(jù)元素"<<endl; cout<<"7.求鏈表的表長"<<endl; cout<<"8.判斷鏈表是否為空"<<endl; cout<<"9.清空鏈表"<<endl; cout<<"10.銷毀鏈表"<<endl; cout<<"11.遍歷鏈表"<<endl; cout<<"12.退出"<<endl; cout<<"*******************************************"<<endl; } int main() { int choice; LinkList L; int i2,e2,e,i1,e1; int t,n,x1; int x,data; while(1) { menu(); cout<<"請輸入你的選擇"<<endl; cin>>choice; switch(choice) { case 1: InitList(L); cout<<"成功初始化"<<endl; break; case 2: cout<<"請選擇你想要創(chuàng)建鏈表的方法"<<endl; cout<<"1.是頭插法\t2.是尾插法"<<endl; cin>>t; if(t==1) { int a1[N]; cout<<"請輸入需要多少個節(jié)點"<<endl; cin>>n; for(int i=0;i<n;i++) { cout<<"請輸入第"<<i+1<<"個節(jié)點的數(shù)據(jù)"<<endl; cin>>a1[i]; } CreateList_F(L,a1,n); } else { int a2[N]; cout<<"請輸入需要多少個節(jié)點"<<endl; cin>>n; for(int i=0;i<n;i++) { cout<<"請輸入第"<<i+1<<"個節(jié)點的數(shù)據(jù)"<<endl; cin>>a2[i]; } CreateList_L(L,a2,n); } break; case 3: cout<<"輸入要查找的位置"<<endl; cin>>x; GetElem_L(L,x,data); cout<<"第"<<x+1<<"個元素的值為:"<<data<<endl; break; case 4: cout<<"輸入值"<<endl; cin>>e; x1=LocateElem_L(L,e); cout<<"位置為:"<<x1<<endl; break; case 5: cout<<"請輸入要插入哪里跟節(jié)點的數(shù)據(jù)"<<endl; cin>>i1>>e1; ListInsert_L(L,i1,e1); break; case 6: cout<<"請輸入要刪除哪個節(jié)點"<<endl; cin>>i2; ListDelete(L,i2,e2); cout<<"刪除成功,原來的節(jié)點的數(shù)據(jù)為"<<e2<<endl; break; case 7: cout<<"長度為"<<ListLength(L)<<endl; break; case 8: if(isEmpty(L)) cout<<"鏈表為空"<<endl; else cout<<"鏈表不為空"<<endl; break; case 9: CleanList(L); cout<<"清空成功"<<endl; break; case 10: DestoryList(L); cout<<"銷毀成功"<<endl; break; case 11: ListTraverse(L); break; case 12: cout<<"成功退出"<<endl; exit(0); default: cout<<"請重新輸入"<<endl; break; } } }
五、測試結(jié)果
測試樣例:創(chuàng)建4個節(jié)點 數(shù)據(jù)分別為1、2、3、4 其余測試基于以上4個節(jié)點
圖一
圖二
圖三
圖四
圖五
圖六
圖七
圖八
圖九
圖十
圖11
圖十二
六、總結(jié)
鏈表是一種動態(tài)分配空間的存儲結(jié)構(gòu),能更有效地利用存儲空間,通過對單鏈表基本操作的代碼實現(xiàn),我深刻領(lǐng)悟到以“指針”指示元素的后繼,在插入或刪除元素時不需要移動元素。但是與此同時,由于鏈表是“順序存取”的結(jié)構(gòu),給隨機存取元素和在表尾插入等操作帶來不便。,所以接下來我將學(xué)習(xí)尾指針表示的單鏈表,雙向鏈表以及循環(huán)鏈表等。
帶有頭結(jié)點的鏈表的基本操作
#ifndef _LIST_h_ #define _LIST_h_ //鏈表中的數(shù)據(jù)結(jié)構(gòu) typedef struct Link_data { int a; int b; }Node_data; //鏈表節(jié)點結(jié)構(gòu) typedef struct Link_node { Node_data data; struct Link_node *pNext; }Node; Node* CreateList(void); Node* FindNodeByGlobalIndex(Node *pHead, int iGlobalIndex); Node* Insert2ListTail(Node *pHead, Node_data *pAutoInfo); int RemoveList(Node *pHead); void PrintList(Node *pHead); int DeleteList (Node *pHead,int x); void ReverseList(Node *pHead); void SortList(Node *pHead); #endif
#include <string.h> #include <malloc.h> #include<stdio.h> #include"list.h" /************************************************* Function : CreateList Description : 創(chuàng)建鏈表頭節(jié)點 Return : 鏈表的頭指針 *************************************************/ Node* CreateList(void) { Node *pHead = NULL; //申請的頭指針 pHead = (Node *)malloc(sizeof(Node)); //判斷是否申請成功 if (NULL == pHead) { return NULL; } //針對具體結(jié)構(gòu)進行初始化 pHead->data.a = 0; pHead->data.b = 0; pHead->pNext = NULL; return pHead; } /************************************************* Function : FindNodeByGlobalIndex Description : 根據(jù)指定參數(shù),查找某個節(jié)點 Input : pHead 鏈表的頭節(jié)點指針 要查找的學(xué)生ID Return : 正確:返回指定節(jié)點的指針 失敗:返回空指針 *************************************************/ Node* FindNodeByGlobalIndex(Node *pHead, int iGlobalIndex) { Node *pNode = NULL; if ((NULL == pHead) || (iGlobalIndex < 0)) { return NULL; } pNode = pHead->pNext; while ((NULL != pNode)) { if (pNode->data.a == iGlobalIndex) { break; } pNode = pNode->pNext; } return pNode; } /************************************************* Function : Insert2ListTail Description : 向鏈表中尾部插入某個節(jié)點 Input : pHead 鏈表的頭節(jié)點指針 pStudentInfo 學(xué)生信息 Return : 正確:返回頭節(jié)點指針 失敗:返回空指針 *************************************************/ Node* Insert2ListTail(Node *pHead, Node_data *pAutoInfo) { Node* pNode = NULL; Node* pNewNode = NULL; if ((NULL == pHead) || (NULL == pAutoInfo)) { return NULL; } pNode = pHead; while (pNode->pNext != NULL) { pNode = pNode->pNext; } pNewNode = (Node *)malloc(sizeof(Node)); if (NULL == pNewNode) { return NULL; } pNode->pNext = pNewNode; pNewNode->pNext = NULL; memcpy(&(pNewNode->data), pAutoInfo, sizeof(Node_data )); return pHead; } /************************************************* Function : RemoveList Description : 刪除整個鏈表 Input : pHead 鏈表的頭節(jié)點指針 Return : 正確: 1 失敗: 0 *************************************************/ int RemoveList(Node *pHead) { Node *pNode = NULL; Node *pb = NULL; if (NULL == pHead) { return 0; } pNode = pHead; pb = pNode->pNext; if (NULL == pb) { free(pNode); } else { while (NULL != pb) { free(pNode); pNode = pb; pb = pb->pNext; } free(pNode); } pNode = NULL; return 1; } /************************************************* Function : PrintList Description : 打印整個鏈表 Input : pHead 鏈表的頭節(jié)點指針 Return : *************************************************/ void PrintList(Node *pHead) { Node *pNode = NULL; if (NULL == pHead) { return ; } pNode = pHead->pNext; while ((NULL != pNode)) { printf("\r\n a is %d b is %d",pNode->data.a,pNode->data.b); pNode = pNode->pNext; } return ; } /************************************************* Function : DeleteList Description : 刪除鏈表的一個結(jié)點,刪除條件該節(jié)點的a值與x相同 Input : Return : *************************************************/ int DeleteList (Node *pHead,int x) { Node *pNode = NULL; Node *pre = NULL; if (NULL == pHead ) { return 0; } pNode = pHead->pNext; pre = pHead; while(pNode) { if(pNode->data.a == x)//刪除條件 { pre->pNext = pNode->pNext; free(pNode); return 1; } else { pre = pNode; } pNode = pNode->pNext; } return 0; } /************************************************* Function : ReverseList Description : 鏈表反轉(zhuǎn) Input : Return : *************************************************/ void ReverseList(Node *pHead) { Node* p = pHead->pNext; Node* q = p->pNext; Node* t = NULL; if(NULL == pHead || NULL == pHead->pNext) { return; } while(NULL != q) { t = q->pNext; q->pNext = p; p = q; q = t; } pHead->pNext->pNext = NULL; pHead->pNext = p; } /************************************************* Function : SortList Description : 按a值排序 Input : Return : *************************************************/ void SortList(Node *pHead) { Node* pi = pHead->pNext; Node* pj = pi->pNext; Link_data temp; memset(&temp,0,sizeof(Link_data)); if(NULL == pHead || NULL == pHead->pNext) { return; } for(;pi != NULL;pi=pi->pNext) { for(pj = pi->pNext;pj != NULL;pj=pj->pNext) { if(pj->data.a < pi->data.a) { temp = pj->data; pj->data = pi->data; pi->data = temp; } } } }
#include<stdio.h> #include<string.h> #include"list.h" Node * g_LinkHead = NULL; int main() { Node_data data1; Node_data data2; Node_data data4; Node *data3 = NULL; memset(&data1, 0, sizeof(Node_data)); memset(&data2, 0, sizeof(Node_data)); memset(&data4, 0, sizeof(Node_data)); data1.a=3; data1.b=3; data2.a=2; data2.b=4; data4.a=5; data4.b=6; g_LinkHead=CreateList(); Insert2ListTail(g_LinkHead,&data1); Insert2ListTail(g_LinkHead,&data2); Insert2ListTail(g_LinkHead,&data4); PrintList(g_LinkHead); //data3 = FindNodeByGlobalIndex(g_LinkHead, 2); //printf("\r\n data3.a %d data3.b %d",data3->data.a,data3->data.b); printf("\n\n"); //(void) ReverseList(g_LinkHead); (void) SortList(g_LinkHead); PrintList(g_LinkHead); /*if(DeleteList (g_LinkHead,4)) { PrintList(g_LinkHead); } PrintList(g_LinkHead);*/ /*if(RemoveList(g_LinkHead)) { g_LinkHead = NULL; } PrintList(g_LinkHead);*/ return 0; }
到此這篇關(guān)于帶頭結(jié)點的鏈表的基本操作(超詳細(xì))的文章就介紹到這了,更多相關(guān)帶頭結(jié)點的鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++學(xué)習(xí)之智能指針中的unique_ptr與shared_ptr
吃獨食的unique_ptr與樂于分享的shared_ptr是C++中常見的兩個智能指針,本文主要為大家介紹了這兩個指針的使用以及智能指針使用的原因,希望對大家有所幫助2023-05-05vscode工程中c_cpp_properties.json文件作用詳細(xì)說明
c_cpp_properties.json是Visual Studio Code的一個配置文件,用于定義C/C++編譯器的路徑、默認(rèn)包含路徑和預(yù)處理器定義,這篇文章主要給大家介紹了關(guān)于vscode工程中c_cpp_properties.json文件作用詳細(xì)說明的相關(guān)資料,需要的朋友可以參考下2024-08-08用C++實現(xiàn),將一句話里的單詞進行倒置的方法詳解
本篇文章是對用C++實現(xiàn),將一句話里的單詞進行倒置的方法進行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05