帶頭結(jié)點的鏈表的基本操作(超詳細(xì))
鏈表是一種動態(tài)分配空間的存儲結(jié)構(gòu),能更有效地利用存儲空間,通過對單鏈表基本操作的代碼實現(xiàn),我深刻領(lǐng)悟到以“指針”指示元素的后繼,在插入或刪除元素時不需要移動元素。但是與此同時,由于鏈表是“順序存取”的結(jié)構(gòu),給隨機(jī)存取元素和在表尾插入等操作帶來不便。,所以接下來我將學(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表示傳進(jìn)來的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),給隨機(jī)存取元素和在表尾插入等操作帶來不便。,所以接下來我將學(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)進(jìn)行初始化
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-05
vscode工程中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),將一句話里的單詞進(jìn)行倒置的方法詳解
本篇文章是對用C++實現(xiàn),將一句話里的單詞進(jìn)行倒置的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05

