前言
在我們學習C語言基礎的程序中，指標和鏈表一直是新手的兩大攔路虎，在大學的程式語言課程設計中，我們在設計系統時可能會用到鏈表或者結構體陣列，今天，我想為大家梳理一下關于單鏈表的使用，本文章需要讀者先行理解C語言的結構體和結構體中next的使用，
注：我所使用的是vs2019，部分代碼可能在其他編譯器中會報錯，
單鏈表的分類
在我理解中，單鏈表分為兩類，一種是有表頭單鏈表，一種是無表頭單鏈表，本章我先來幫助大家理解有表頭單鏈表，
結構體框架
struct Structure //為了方便大家理解char型別和int型別在使用上的區別，我特地分別設定了兩個變數
{
char num[4];//編號
int score;//分數
char name[10];//姓名
int room;//房間號
struct Structure* next;
};有表頭單鏈表
有表頭單鏈表，顧名思義，就是創建的鏈表中表頭資料為NULL，next直接指向下一結構體，它包含的基礎功能有：添加資訊，查找資訊，洗掉資訊，資訊排序，檔案操作，資訊顯示，檔案操作功能我暫且放在下一章講解，
下面，我來講解使用有表頭單鏈表需要使用到的函式：
一、create（）創建鏈表，后面產生的結構體將放在表頭后面
struct Structure* create()//創建有表頭鏈表(不存資料）
{
struct Structure* head = (struct Structure*)malloc(sizeof(struct Structure));//產生變數
head->next = NULL;//初始化變數
return head;
}我們需要在主函式main中撰寫 struct Structure* head = create(); 這樣一個鏈表的表頭就形成了，
二、newNote（）創建節點，讀取用戶輸入的記錄，生成結構體資料
struct Structure* newNote()//創建節點
{
struct Structure* p = (struct Structure*)malloc(sizeof(struct Structure));
scanf_s("%s%d%s%d", p->num, 4, &p->score, p->name, 10, &p->room);
p->next = NULL;
return p;
}scanf_s代碼解釋: // scanf_s("%s%d%s%d", p->num, 4, &p->score, p->name, 10, &p->room);
1.代碼解讀:num和name均為char型別的陣列變數，在取址時可以不用添加“&”，后面跟著的4,10為可讀取資料的長度，score和room為int型別變數，需添加“&”讀取地址
2.這是vs新版本中為了保證系統的安全，添加了檢驗機制，
3.它與scanf的區別在于，讀取字串時可以確定讀取的長度，當輸入字串長度過長時可以直接對該變數賦值為空，且不影響后續資料的讀取，若輸入資料為123456 78 張三 101，則存盤的資料為：num="" score=78 name="張三" room=101 ，
函式解讀，創建一個結構體，并存盤用戶輸入資料，并將該結構體回傳，
三、insert（）從表頭插入新的資料，可用于添加資訊的功能，
void insert(struct Structure* head)//呼叫創建節點匯入資料并從表頭插入
{
int n;//用于讀取用戶輸入的記錄個數
printf("請輸入你要錄入的學生個數：");
scanf_s("%d", &n);
for (; n < 1; n--)
{
printf("請輸入資料\n");//也可以定義變數i來提示用戶當前輸入的記錄條數
struct Structure* node = newNote();
node->next = head->next;
head->next = node;
}
}將用戶輸入的記錄一個個從表頭插入鏈表中，
四、query（）通過接收用戶的編號來查找鏈表中對應的記錄，但只能回傳第一個編號相同的記錄
Structure* Query(Structure* head, char* num)//查找編號，有則回傳對應結構體，否則回傳空鏈表
{
Structure* p;
p = head;
while (p != NULL)
{
if (strcmp(num, p->num) == 0)
return p;
p = p->next;
}
return NULL;
}本函式中使用了strcmp（）函式，需使用頭檔案#include<string.h>，常用于比較兩個字串的大小，當兩種相同時則回傳數值0，
本函式從表頭開始查找，編號相同則回傳，直到查找到鏈表尾步為止，若無對應編號則回傳空值，
常被query a record查找函式和delete洗掉函式呼叫，
五、query a record（）查找函式，可用于查找資訊功能
void Query_a_record(Structure* head)//接收查找反饋并展示結果
{
char s[4];
Structure* p;
printf("請輸入一個要查找的編號\t");
scanf_s("%s", s, 4);
getchar();
p = Query(head, s);
if (p != NULL)
{
printf("%s %d %s %d", p->num, p->score, p->name, p->room);
system("pause");
}
else
{
printf("找不到對應的編號!\t\t");
system("pause");
}
}呼叫query查找函式，分兩種情況，若查找到記錄則顯示；若回傳值為空則鏈表沒有該編號，
缺點：無法判斷鏈表是否存盤資料
六、delete（）用于洗掉第一個與編號相同的記錄
Telephone* Delete(Telephone* head, char* num)//接收資料，并洗掉編號相同的記錄
{
Telephone* p1, * p2=NULL;
p1 = head;
while ((strcmp(num, p1->num) != 0) && (p1->next != NULL))
{
p2 = p1; p1 = p1->next;
}
if (strcmp(num, p1->num) == 0)
{
if (p1 == head) head = p1->next;
else p2->next = p1->next;
free(p1);
}
return head;
}用于接收來自delete a record洗掉函式傳遞的編號，然后洗掉第一個與之編號相同的記錄
缺點：只能洗掉一個
七、delete a record（）用于洗掉資訊功能，洗掉查詢的記錄
Structure* Delete_a_record(Structure* head)//傳遞要洗掉的記錄編號，并選擇是否洗掉
{
char s[4];
printf("請輸入你要洗掉的編號：\t");
scanf_s("%s", s, 4);
getchar();
if (Query(head, s) != NULL)
{
head = Delete(head, s);
printf("編號為%s的記錄已洗掉", s);
system("pause");
}
else
{
printf("編號為%s的記錄未查詢到", s);
system("pause");
}
return head;
}通過呼叫query查找函式來確定編號是否存在，然后呼叫delete洗掉函式來洗掉記錄，
八、sort（）按編號排序，用于資訊排序，經典的冒泡排序法
void sort(struct Structure* head)//排序
{
int i, j, n = 0;
Structure t, * p = head, * p1, * p2;
while (p != NULL)//統計結構體數量
{
n++;
p = p->next;
}
p2 = head;
for (i = 0; i < n - 1; i++)
{
p1 = p2->next;
p = p2;
for (j = i + 1; j < n; j++)
{
if (strcmp(p1->num, p->num) < 0)
p = p1;
p1 = p1->next;
}
if (p != p2)
{
strcpy(t.num, p2->num);
strcpy(t.name, p2->name);
t.room = p2->room;
t.score = p2->score;
strcpy(p2->num, p->num);
strcpy(p2->name, p->name);
p2->room = p->room;
p2->score = p->score;
strcpy(p->num, t.num);
strcpy(p->name, t.name);
p->room = t.room;
p->score = t.score;
}
p2 = p2->next;
}
printf("升序排列操作已完成！\t");
system("pause");
}t是結構體變數，是交換的載體，而p1，p2是結構體指標，所以在呼叫結構體成員時，t使用"."，p1使用"->"，
九、display（）用于資訊顯示
void Display(Structure* head)//顯示記錄
{
Structure* p = head;
printf("編號\t\t成績\t\t姓名\t\t教室\n");
p = p->next;//跳過表頭
while (p != NULL)
{
printf("%s\t\t%d\t\t%s\t\t%d\n", p->num, p->score, p->name, p->room);
p = p->next;
}
system("pause");
}完整代碼展示
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//為了方便大家理解char型別和int型別在使用上的區別，我特地分別設定了兩個變數
struct Structure
{
char num[4];//編號
int score;//分數
char name[10];//姓名
int room;//房間號
struct Structure* next;
};
//創建有表頭鏈表(不存資料）
struct Structure* create()
{
struct Structure* head = (struct Structure*)malloc(sizeof(struct Structure));//產生變數
head->next = NULL;//初始化變數
return head;
}
//創建節點
struct Structure* newNote()
{
struct Structure* p = (struct Structure*)malloc(sizeof(struct Structure));
scanf_s("%s%d%s%d", p->num, 4, &p->score, p->name, 10, &p->room);
p->next = NULL;
return p;
}
//呼叫創建節點匯入資料并從表頭插入
void insert(struct Structure* head)
{
int n;//用于讀取用戶輸入的記錄個數
printf("請輸入你要錄入的學生個數：");
scanf_s("%d", &n);
for (; n > 0; n--)
{
printf("請輸入資料\n");//也可以定義變數i來提示用戶當前輸入的記錄條數
struct Structure* node = newNote();
node->next = head->next;
head->next = node;
}
}
//查找編號，有則回傳對應結構體，否則回傳空鏈表
Structure* Query(Structure* head, char* num)
{
Structure* p;
p = head;
while (p != NULL)
{
if (strcmp(num, p->num) == 0)
return p;
p = p->next;
}
return NULL;
}
//接收查找反饋并展示結果
void Query_a_record(Structure* head)//接收查找反饋并展示結果
{
char s[4];
Structure* p;
printf("請輸入一個要查找的編號\t");
scanf_s("%s", s, 4);
getchar();
p = Query(head, s);
if (p != NULL)
{
printf("%s %d %s %d", p->num, p->score, p->name, p->room);
system("pause");
}
else
{
printf("找不到對應的編號!\t\t");
system("pause");
}
}
//接收資料，并洗掉編號相同的記錄
Structure* Delete(Structure* head, char* num)
{
Structure* p1, * p2 = NULL;
p1 = head;
while ((strcmp(num, p1->num) != 0) && (p1->next != NULL))
{
p2 = p1; p1 = p1->next;
}
if (strcmp(num, p1->num) == 0)
{
if (p1 == head) head = p1->next;
else p2->next = p1->next;
free(p1);
}
return head;
}
//傳遞要洗掉的記錄編號，并選擇是否洗掉
Structure* Delete_a_record(Structure* head)
{
char s[4];
printf("請輸入你要洗掉的編號：\t");
scanf_s("%s", s, 4);
getchar();
if (Query(head, s) != NULL)
{
head = Delete(head, s);
printf("編號為%s的記錄已洗掉", s);
system("pause");
}
else
{
printf("編號為%s的記錄未查詢到", s);
system("pause");
}
return head;
}
//排序
void sort(struct Structure* head)
{
int i, j, n = 0;
Structure t, * p = head, * p1, * p2;
while (p != NULL)//統計結構體數量
{
n++;
p = p->next;
}
p2 = head;
for (i = 0; i < n - 1; i++)
{
p1 = p2->next;
p = p2;
for (j = i + 1; j < n; j++)
{
if (strcmp(p1->num, p->num) < 0)
p = p1;
p1 = p1->next;
}
if (p != p2)
{
strcpy(t.num, p2->num);
strcpy(t.name, p2->name);
t.room = p2->room;
t.score = p2->score;
strcpy(p2->num, p->num);
strcpy(p2->name, p->name);
p2->room = p->room;
p2->score = p->score;
strcpy(p->num, t.num);
strcpy(p->name, t.name);
p->room = t.room;
p->score = t.score;
}
p2 = p2->next;
}
printf("升序排列操作已完成！\t");
system("pause");
}
//顯示記錄
void Display(Structure* head)
{
Structure* p = head;
printf("編號\t\t成績\t\t姓名\t\t教室\n");
p = p->next;//跳過表頭
while (p != NULL)
{
printf("%s\t\t%d\t\t%s\t\t%d\n", p->num, p->score, p->name, p->room);
p = p->next;
}
system("pause");
}
void Display_Main_Menu()
{
printf("1.添加資訊\n");
printf("2.洗掉資訊\n");
printf("3.查找資訊\n");
printf("4.排序資訊\n");
printf("5.顯示資訊\n");
printf("0.退出系統\n");
}
int main()
{
int choose, b;
struct Structure* head = create();
while (1)
{
Display_Main_Menu();
scanf_s("%d", &choose);
switch (choose)
{
case 1:
insert(head);
system("cls");
break;
case 2:
Delete_a_record(head);
system("cls");
break;
case 3:
Query_a_record(head);
system("cls");
break;
case 4:
sort(head);
system("cls");
break;
case 5:
Display(head);
system("cls");
break;
case 0:
goto loop;
default:
printf("\t請輸入選項0—9!\n");
system("pause");
}
}
loop:
printf("感謝本次使用成績處理系統\n");
system("pause");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/259777.html
標籤：其他
上一篇：B. Replace and Keep Sorted前綴和
下一篇：Mybatis延遲加載策略