C語言_鏈表總結(jié)
本篇文章介紹C語言鏈表相關(guān)知識點(diǎn)，涉及鏈表的創(chuàng)建、單向鏈表、循環(huán)鏈表、雙向鏈表、單向循環(huán)鏈表，鏈表常見問題總結(jié)等，還列出了結(jié)構(gòu)體數(shù)組與鏈表的練習(xí)題，將在下篇文章貼出完整代碼。
1. 鏈表
1.1 結(jié)構(gòu)體對比
數(shù)組特性: 內(nèi)存空間連續(xù)、只能存放相同類型的數(shù)據(jù)
結(jié)構(gòu)體特性: 內(nèi)存空間連續(xù)、可以存放不同類型的數(shù)據(jù)
#include
struct MyStruct
{
int a;
char b;
};
int main()
{
struct MyStruct *p;
struct MyStruct data={12,'A'};
data.a=123;
data.b='B';
p=&data;
printf("%d\n",p->a);
printf("%c\n",p->b);
return 0;
}
數(shù)組學(xué)生管理系統(tǒng)作業(yè)：
作業(yè): 學(xué)生管理系統(tǒng)
需求: (每一個(gè)功能都是使用函數(shù)進(jìn)行封裝)
1.實(shí)現(xiàn)從鍵盤上錄入學(xué)生信息。 (姓名、性別、學(xué)號、成績、電話號碼)
2.將結(jié)構(gòu)體里的學(xué)生信息全部打印出來。
3.實(shí)現(xiàn)根據(jù)學(xué)生的姓名或者學(xué)號查找學(xué)生，查找到之后打印出學(xué)生的具體信息。
4.根據(jù)學(xué)生的成績對學(xué)生信息進(jìn)行排序。
5.根據(jù)學(xué)號刪除學(xué)生信息。
1.2 單向鏈表的創(chuàng)建與運(yùn)用
鏈表: 單鏈表、雙鏈表 區(qū)分: 循環(huán)和不循環(huán)鏈表
鏈表的特性: 一種數(shù)據(jù)結(jié)構(gòu)的運(yùn)行—>結(jié)構(gòu)體。
學(xué)習(xí)結(jié)構(gòu)體數(shù)組(編寫學(xué)生管理系統(tǒng)): 學(xué)生的人數(shù)問題不好確定。
鏈表本身就是一個(gè)結(jié)構(gòu)體。
單向鏈表的創(chuàng)建與運(yùn)用:
#include
#include
#include
//定義結(jié)構(gòu)體
struct MyListStruct
{
int a;
struct MyListStruct *next; //結(jié)構(gòu)體指針。存放下一個(gè)節(jié)點(diǎn)的地址
};
//定義鏈表頭
struct MyListStruct *ListHead=NULL;
//函數(shù)聲明
struct MyListStruct *CreateListHead(struct MyListStruct *head);
void PintListInfo(struct MyListStruct *head);
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);
void DeleteListNode(struct MyListStruct *head,int a);
int main()
{
int i;
struct MyListStruct temp;
int a;
//1. 創(chuàng)建鏈表頭
ListHead=CreateListHead(ListHead);
//2. 添加節(jié)點(diǎn)
for(i=0; i<5; i++)
{
printf("輸入新節(jié)點(diǎn)數(shù)據(jù):");
scanf("%d",&temp.a);
AddListNode(ListHead,temp);
}
//3. 打印所有節(jié)點(diǎn)數(shù)據(jù)
PintListInfo(ListHead);
//4. 刪除節(jié)點(diǎn)數(shù)據(jù)
printf("輸入刪除的節(jié)點(diǎn)數(shù)據(jù)值:");
scanf("%d",&a);
DeleteListNode(ListHead,a);
//5. 打印所有節(jié)點(diǎn)數(shù)據(jù)
PintListInfo(ListHead);
return 0;
}
/*
函數(shù)功能: 創(chuàng)建鏈表頭
返回值 : 鏈表頭指針
*/
struct MyListStruct *CreateListHead(struct MyListStruct *head)
{
if(head==NULL)
{
head=malloc(sizeof(struct MyListStruct));
head->next=NULL;
}
return head; //返回鏈表頭
}
/*
函數(shù)功能: 添加鏈表節(jié)點(diǎn)
說明: 鏈表頭一般不存放數(shù)據(jù)
*/
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode)
{
struct MyListStruct *p=head; //保存頭地址
struct MyListStruct *new_p=NULL; //新的節(jié)點(diǎn)
/*1. 尋找鏈表尾*/
while(p->next!=NULL)
{
p=p->next; //移動到下一個(gè)地址
}
/*2. 創(chuàng)建新節(jié)點(diǎn)*/
new_p=malloc(sizeof(struct MyListStruct));
if(new_p==NULL)
{
printf("新節(jié)點(diǎn)內(nèi)存申請失敗!\n");
return;
}
/*3. 新節(jié)點(diǎn)賦值*/
memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //內(nèi)存拷貝
new_p->next=NULL; //尾節(jié)點(diǎn)指向空
/*4. 新節(jié)點(diǎn)添加*/
p->next=new_p;
}
/*
函數(shù)功能: 刪除鏈表節(jié)點(diǎn)
*/
void DeleteListNode(struct MyListStruct *head,int a)
{
struct MyListStruct *p=head; //保存頭地址
struct MyListStruct *tmp=NULL;
/*查找數(shù)據(jù)存在的節(jié)點(diǎn)位置*/
while(p->next!=NULL)
{
tmp=p; //保存上一個(gè)節(jié)點(diǎn)的地址
p=p->next;
if(p->a==a) //查找成功
{
tmp->next=p->next; //將要?jiǎng)h除節(jié)點(diǎn)的指針值賦值給刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指針域
//tmp->next=tmp->next->next;
free(p); //直接釋放p節(jié)點(diǎn)空間
//break;
p=head; //重新指向鏈表頭
}
}
}
/*
函數(shù)功能: 遍歷所有鏈表信息
*/
void PintListInfo(struct MyListStruct *head)
{
int cnt=0;
struct MyListStruct *p=head;
printf("\n鏈表遍歷的數(shù)據(jù)如下:\n");
while(p->next!=NULL)
{
p=p->next;
cnt++;
printf("第%d個(gè)節(jié)點(diǎn)的數(shù)據(jù)=%d\n",cnt,p->a);
}
}
作業(yè):
1.看代碼、理解鏈表的創(chuàng)建流程
2.編寫出單向鏈表的基礎(chǔ)運(yùn)用
3.將之前的學(xué)生管理系統(tǒng)使用鏈表方式做出來
鏈表的功能:
(1)創(chuàng)建鏈表頭
(2)在鏈表結(jié)尾添加一個(gè)節(jié)點(diǎn)
(3)刪除指定的一個(gè)鏈表節(jié)點(diǎn)
(4)遍歷鏈表，打印出所有的數(shù)據(jù)。
(5)在鏈表的指定節(jié)點(diǎn)的后面添加一個(gè)節(jié)點(diǎn)。
(6)根據(jù)鏈表節(jié)點(diǎn)里的數(shù)據(jù)對鏈表進(jìn)行排序。
雙向鏈表:
(1)使用逆向+順向兩種遍歷方式刪除鏈表節(jié)點(diǎn)，目的: 提高效率。
類似于二分法查找。
2. 鏈表問題總結(jié)
動態(tài)空間分配:
#include
#include
#include
int main()
{
char *p=malloc(100); //申請動態(tài)空間。
if(p==NULL)
{
return -1;
}
strcpy(p,"1234567890");
printf("%s\n",p);
return 0;
}
#include
#include
#include
int main()
{
char *p1=malloc(100); //申請動態(tài)空間。
printf("%p\n",p1);
char *p2=malloc(100); //申請動態(tài)空間。
printf("%p\n",p2);
char *p3=malloc(100); //申請動態(tài)空間。
printf("%p\n",p3);
char *p4=malloc(100); //申請動態(tài)空間。
printf("%p\n",p4);
return 0;
}
錯(cuò)誤解決:
1.第一個(gè)錯(cuò)誤開始解決
2.常規(guī)錯(cuò)誤: 函數(shù)沒有聲明、分號每加、括號沒有加、=
3.括號沒有對齊。
3. 雙向鏈表和循環(huán)鏈表
3.1 單向循環(huán)鏈表:
#include
#include
#include
//定義結(jié)構(gòu)體
struct MyListStruct
{
int a;
struct MyListStruct *next; //結(jié)構(gòu)體指針。存放下一個(gè)節(jié)點(diǎn)的地址
};
//定義鏈表頭
struct MyListStruct *ListHead=NULL;
//函數(shù)聲明
struct MyListStruct *CreateListHead(struct MyListStruct *head);
void PintListInfo(struct MyListStruct *head);
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);
void DeleteListNode(struct MyListStruct *head,int a);
int main()
{
int i;
struct MyListStruct temp;
int a;
//1. 創(chuàng)建鏈表頭
ListHead=CreateListHead(ListHead);
//2. 添加節(jié)點(diǎn)
for(i=0; i<5; i++)
{
printf("輸入新節(jié)點(diǎn)數(shù)據(jù):");
scanf("%d",&temp.a);
AddListNode(ListHead,temp);
}
//3. 打印所有節(jié)點(diǎn)數(shù)據(jù)
PintListInfo(ListHead);
//4. 刪除節(jié)點(diǎn)數(shù)據(jù)
printf("輸入刪除的節(jié)點(diǎn)數(shù)據(jù)值:");
scanf("%d",&a);
DeleteListNode(ListHead,a);
//5. 打印所有節(jié)點(diǎn)數(shù)據(jù)
PintListInfo(ListHead);
return 0;
}
/*
函數(shù)功能: 創(chuàng)建鏈表頭
返回值 : 鏈表頭指針
*/
struct MyListStruct *CreateListHead(struct MyListStruct *head)
{
if(head==NULL)
{
head=malloc(sizeof(struct MyListStruct));
head->next=head;
}
return head; //返回鏈表頭
}
/*
函數(shù)功能: 添加鏈表節(jié)點(diǎn)
說明: 鏈表頭一般不存放數(shù)據(jù)
*/
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode)
{
struct MyListStruct *p=head; //保存頭地址
struct MyListStruct *new_p=NULL; //新的節(jié)點(diǎn)
/*1. 尋找鏈表尾*/
while(p->next!=head)
{
p=p->next; //移動到下一個(gè)地址
}
/*2. 創(chuàng)建新節(jié)點(diǎn)*/
new_p=malloc(sizeof(struct MyListStruct));
if(new_p==NULL)
{
printf("新節(jié)點(diǎn)內(nèi)存申請失敗!\n");
return;
}
/*3. 新節(jié)點(diǎn)賦值*/
memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //內(nèi)存拷貝
new_p->next=head; //尾節(jié)點(diǎn)指向頭
/*4. 新節(jié)點(diǎn)添加*/
p->next=new_p;
}
/*
函數(shù)功能: 刪除鏈表節(jié)點(diǎn)
*/
void DeleteListNode(struct MyListStruct *head,int a)
{
struct MyListStruct *p=head; //保存頭地址
struct MyListStruct *tmp=NULL;
/*查找數(shù)據(jù)存在的節(jié)點(diǎn)位置*/
while(p->next!=head)
{
tmp=p; //保存上一個(gè)節(jié)點(diǎn)的地址
p=p->next;
if(p->a==a) //查找成功
{
tmp->next=p->next; //將要?jiǎng)h除節(jié)點(diǎn)的指針值賦值給刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指針域
//tmp->next=tmp->next->next;
free(p); //直接釋放p節(jié)點(diǎn)空間
//break;
p=head; //重新指向鏈表頭
}
}
}
/*
函數(shù)功能: 遍歷所有鏈表信息
*/
void PintListInfo(struct MyListStruct *head)
{
int cnt=0;
struct MyListStruct *p=head;
printf("\n鏈表遍歷的數(shù)據(jù)如下:\n");
while(p->next!=head)
{
p=p->next;
cnt++;
printf("第%d個(gè)節(jié)點(diǎn)的數(shù)據(jù)=%d\n",cnt,p->a);
}
}
3.2 雙向鏈表
#include
#include
#include
//定義結(jié)構(gòu)體
struct MyListStruct
{
int a;
struct MyListStruct *next; //結(jié)構(gòu)體指針。存放下一個(gè)節(jié)點(diǎn)的地址
struct MyListStruct *old; //結(jié)構(gòu)體指針。存放上一個(gè)節(jié)點(diǎn)的地址
};
//定義鏈表頭
struct MyListStruct *ListHead=NULL;
//函數(shù)聲明
struct MyListStruct *CreateListHead(struct MyListStruct *head);
void PintListInfo(struct MyListStruct *head);
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);
void DeleteListNode(struct MyListStruct *head,int a);
void PintListInfo_old(struct MyListStruct *head);
int main()
{
int i;
struct MyListStruct temp;
int a;
//1. 創(chuàng)建鏈表頭
ListHead=CreateListHead(ListHead);
//2. 添加節(jié)點(diǎn)
for(i=0; i<5; i++)
{
printf("輸入新節(jié)點(diǎn)數(shù)據(jù):");
scanf("%d",&temp.a);
AddListNode(ListHead,temp);
}
//3. 打印所有節(jié)點(diǎn)數(shù)據(jù)
PintListInfo(ListHead);
PintListInfo_old(ListHead);
//4. 刪除節(jié)點(diǎn)數(shù)據(jù)
printf("輸入刪除的節(jié)點(diǎn)數(shù)據(jù)值:");
scanf("%d",&a);
DeleteListNode(ListHead,a);
//5. 打印所有節(jié)點(diǎn)數(shù)據(jù)
PintListInfo(ListHead);
PintListInfo_old(ListHead);
return 0;
}
/*
函數(shù)功能: 創(chuàng)建鏈表頭
返回值 : 鏈表頭指針
*/
struct MyListStruct *CreateListHead(struct MyListStruct *head)
{
if(head==NULL)
{
head=malloc(sizeof(struct MyListStruct));
head->next=NULL; //尾節(jié)點(diǎn)指向空
head->old=head; //上一個(gè)節(jié)點(diǎn)指向頭
}
return head; //返回鏈表頭
}
/*
函數(shù)功能: 添加鏈表節(jié)點(diǎn)
說明: 鏈表頭一般不存放數(shù)據(jù)
*/
void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode)
{
struct MyListStruct *p=head; //保存頭地址
struct MyListStruct *new_p=NULL; //新的節(jié)點(diǎn)
/*1. 尋找鏈表尾*/
while(p->next!=NULL)
{
p=p->next; //移動到下一個(gè)地址
}
/*2. 創(chuàng)建新節(jié)點(diǎn)*/
new_p=malloc(sizeof(struct MyListStruct));
if(new_p==NULL)
{
printf("新節(jié)點(diǎn)內(nèi)存申請失敗!\n");
return;
}
/*3. 新節(jié)點(diǎn)賦值*/
memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //內(nèi)存拷貝
new_p->next=NULL; //尾節(jié)點(diǎn)指向NULL
new_p->old=p; //保存上一個(gè)節(jié)點(diǎn)的地址
/*4. 新節(jié)點(diǎn)添加*/
p->next=new_p;
}
/*
函數(shù)功能: 刪除鏈表節(jié)點(diǎn)
順向刪除。
*/
void DeleteListNode(struct MyListStruct *head,int a)
{
struct MyListStruct *p=head; //保存頭地址
struct MyListStruct *tmp=NULL;
/*查找數(shù)據(jù)存在的節(jié)點(diǎn)位置*/
while(p->next!=NULL)
{
tmp=p; //保存上一個(gè)節(jié)點(diǎn)的地址
p=p->next;
if(p->a==a) //查找成功
{
tmp->next=p->next; //將要?jiǎng)h除節(jié)點(diǎn)的指針值賦值給刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指針域
//tmp->next=tmp->next->next;
p->next->old=tmp; //保存上一個(gè)節(jié)點(diǎn)的地址
free(p); //直接釋放p節(jié)點(diǎn)空間
//break;
p=head; //重新指向鏈表頭
}
}
}
/*
函數(shù)功能: 遍歷所有鏈表信息
從頭到尾遍歷
*/
void PintListInfo(struct MyListStruct *head)
{
int cnt=0;
struct MyListStruct *p=head;
printf("\n(順向)鏈表遍歷的數(shù)據(jù)如下:\n");
while(p->next!=NULL)
{
p=p->next;
cnt++;
printf("第%d個(gè)節(jié)點(diǎn)的數(shù)據(jù)=%d\n",cnt,p->a);
}
}
/*
函數(shù)功能: 遍歷所有鏈表信息
從尾到頭遍歷
*/
void PintListInfo_old(struct MyListStruct *head)
{
int cnt=0;
struct MyListStruct *p=head;
printf("\n(逆向)鏈表遍歷的數(shù)據(jù)如下:\n");
/*1. 找到鏈表尾*/
while(p->next!=NULL)
{
p=p->next;
}
/*2. 通過鏈表尾遍歷鏈表的數(shù)據(jù)*/
while(p!=head)
{
cnt++;
printf("第%d個(gè)節(jié)點(diǎn)的數(shù)據(jù)=%d\n",cnt,p->a);
p=p->old; //訪問上一個(gè)節(jié)點(diǎn)
}
}
聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。
舉報(bào)投訴
-
C語言
+關(guān)注
關(guān)注
180文章
7604瀏覽量
136683 -
結(jié)構(gòu)體
+關(guān)注
關(guān)注
1文章
130瀏覽量
10840 -
鏈表
+關(guān)注
關(guān)注
0文章
80瀏覽量
10558
發(fā)布評論請先 登錄
相關(guān)推薦
C語言-鏈表(單向鏈表、雙向鏈表)
在前面章節(jié)已經(jīng)學(xué)習(xí)了數(shù)組的使用，數(shù)組的空間是連續(xù)空間，數(shù)組的大小恒定的，在很多動態(tài)數(shù)據(jù)存儲的應(yīng)用場景下，使用不方便；而這篇文章介紹的鏈表結(jié)構(gòu)，支持動態(tài)增加節(jié)點(diǎn)，釋放節(jié)點(diǎn)，比較適合存儲動態(tài)數(shù)據(jù)的應(yīng)用場景，而且鏈表的空間是存儲在堆上面的，可以動態(tài)分配，釋放
源碼|學(xué)生信息管理系統(tǒng)（C語言單鏈表實(shí)現(xiàn)）
源碼|學(xué)生信息管理系統(tǒng)（C語言單鏈表實(shí)現(xiàn)）
發(fā)表于 11-03 10:24
?512次閱讀
C語言實(shí)現(xiàn)靜態(tài)鏈表的建立
在這么卷的時(shí)代，我覺得硬件工程師還是 要掌握基本的C語言編寫能力，鏈表在學(xué)生階段是一個(gè)比較難的知識點(diǎn)，可能有些同學(xué)上完一個(gè)大學(xué)都不會鏈表的編寫，但是在未來工作中，
發(fā)表于 01-13 15:08
?737次閱讀
C語言算法題：反轉(zhuǎn)一個(gè)單向鏈表
鏈表是編程學(xué)習(xí)的一個(gè)難點(diǎn)。其實(shí)，在C語言編程以及單片機(jī)裸機(jī)開發(fā)中，鏈表運(yùn)用并不多。但是如果想提升嵌入式技能水平或收入水平，可以考慮深入嵌入式系統(tǒng)層面（如參與操作系統(tǒng)設(shè)計(jì)、深入學(xué)習(xí)新的操
發(fā)表于 06-21 11:07
?840次閱讀
C語言玩轉(zhuǎn)鏈表
C語言是必學(xué)的一個(gè)課程，不管你是單片機(jī)還是嵌入式物聯(lián)網(wǎng)，都是基礎(chǔ)，所以還是要好好學(xué)習(xí)的今天推薦的資料是關(guān)于C語言鏈表的資料我自己看了一下主要
發(fā)表于 11-13 13:50
C語言中鏈表的作用是什么？
對C語言中指針用的很少，鏈表、文件操作幾乎沒用過，所以也不能理解到底有什么作用。各位有經(jīng)常在做程序時(shí)會用到這些嗎。
發(fā)表于 11-06 06:23
C語言實(shí)現(xiàn)單鏈表舉例
所謂鏈表，就是用一組任意的存儲單元存儲線性表元素的一種數(shù)據(jù)結(jié)構(gòu)。鏈表又分為單鏈表、雙向鏈表和循環(huán)鏈表等。我們先講講單
發(fā)表于 07-11 16:40
?87次下載
工商網(wǎng)監(jiān)
評論