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