本篇文章介紹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 語言 數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
