我與鏈表的初識

這篇文章絕對對對對對對親民

2020年對于所有人來說應該是充滿故事的一年，我亦如此，這十二個月，經歷了全國人民眾志成城抗疫的那幾個月，體驗了宅在家里上網課的感覺，幾十年以來的高考延期也發生在我的身上，最終在烈日炎炎的七月結束了高考，與高中告別，與穿著校服的那段青蔥歲月告別，9月，我拖著行李來到了NUIST，學上了我高中一直向往的計算機專業，

以上

算是我對我的2020做個短短的總結吧😊

OK，快讓我們的主角鏈表登場吧！
在這里，必須得吐槽一下學校里的C語言老師，鏈表講的都是啥玩意？一上來就增刪改查，就鏈表元素排序？兩節課結束所有內容？我聽的真是一臉懵逼，
課后，我真是掙扎了好久，終于把鏈表弄清了點眉目，本篇文章我會將我所學會做一份總結，希望能給初學鏈表的朋友們一點點啟發和幫助！

為什么要學鏈表？鏈表干嘛的？

這就是鏈表牛逼所在，之前我們儲存資料都是通過陣列，可陣列開辟的是一段連續的空間，如果我們要儲存一個特別大特別大的資料，計算機內極有可能找不到這么大的一塊儲存空間，這時候，鏈表閃亮登場，用鏈表儲存資料，不需要開辟一段連續的空間，在儲存資料時，只需要隨機找到一個空余的空間并賦值，接下來再尋找下一個空余的空間并賦值，就像在一堆珠子中隨機撿一個珠子，把它串在線上，最終形成了一個珍珠串，把它送給女朋友，所以，鏈表就是這樣，把一個個不連續的地址串起來，用以儲存龐大的資料，（說的不對直接罵）

從珍珠串開始，便引入了鏈表最基本的幾個概念，
節點，頭指標，首節點，尾節點

節點就是每個結構體中資料域和指標域構成的整體（不能理解這段中文意思的沒關系，我一開始也不懂，去往下看），簡單理解節點就是珍珠串上的每一顆珍珠，
在我們儲存完資料后，在讀取時必須得找到第一個節點的位置，這樣才能像多米諾骨牌一樣一個一個尋找下一個節點的位置，因此頭指標的作用就是給我們指出第一個節點位置，就好比珍珠串第一個珍珠前繩子打的結，
首節點很簡單，就是第一個珍珠，相對應，尾節點就是最后一個珍珠，

現在，我們看一下鏈表都是怎么構造的

struct node
{
	int a;
	double b;
	struct node *next;
};

是不是有些不知所措，結構體中為什么又定義了一個結構體指標？
記得我之前說的資料域和指標域嗎？在這段代碼中，資料域就是node結構體中的int型別資料a和double型別資料b，而指標域就是結構體中的next指標，next指標指向了下一個struct node型別的地址，是不是有點遞回的意思，

資料域用來儲存資料，指標域指向下一個開辟的地址，以繼續儲存資料，

為了繼續熟悉這個結構，我們來構造一個靜態鏈表

# include <stdio.h>
# include <stdlib.h>
struct student  //構造鏈表
{
	int num;
	double score;
	struct student *next;
};
int main()
{
	struct student a,b,c,*head;

	//對結構體進行賦值
	a.num=1;
	a.score=89.5;
	b.num=2;
	b.score=98;
	c.num=3;
	c.score=85;

	//頭指標指向a所在地址
	head=&a;

	//每個結構體指標指向下一個結構體
	a.next=&b;
	b.next=&c;
	c.next=NULL; //最后一個節點指標域指向空
	//列印鏈表
	do
	{
		printf("%d %.lf\n",head->num,head->score);
		head=head->next;
	}while(head!=NULL);
	return 0;
}

通過靜態鏈表來理解鏈表非常關鍵，初學的朋友一定要細細品味這段代碼

建立一個動態鏈表
相信細品過建立靜態鏈表的同學會發現，要是我要儲存未知個數個資料，靜態鏈表明顯沒用了呀！還不如做個陣列呢！
因此，我們來建立一個動態鏈表，
首先，你們需要會malloc()函式，不會的給大家推篇博客學習一下再來吧請點我q(≧▽≦q)
通過malloc()函式我們就可以開辟一段符合每段節點長度的儲存空間，再上一個節點的指標域指向該空間的首地址，以新建一個節點
下面贈上代碼，請細品

# include <stdio.h>
# include <stdlib.h>

//宏定義
# define NODE struct node  //用NODE代替struct node 減少下面每次構造一個結構體指標都要打這么多字的麻煩 
# define LEN sizeof(NODE)  //用LEN代替每個節點的長度

NODE* creatlist(void);     //建立動態鏈表
void printlist(NODE*);     //列印鏈表

NODE
{
	int num;
	NODE * next;
};

NODE* creatlist()
{
	NODE *pN,*temp;
	NODE *head=NULL,*tail=NULL;
	int n=0;
	temp=pN=(NODE *)malloc(LEN);    //開辟空間
	printf("\n請給每個節點賦值，以0作為結束\n");
	scanf("%d",&pN->num); 
	while(pN->num!=0)
	{
		n++;
		if(n==1)
			head=pN;
		else
			temp->next=pN;
		temp=pN;
		pN=(NODE*)malloc(LEN);
		scanf("%d",&pN->num); 
	}
	temp->next=tail;
	return head;
}

void printlist(NODE* head)
{
	NODE* p=head;
	printf("\n您建立的鏈表為：\n");
	while(p!=NULL)
	{
		printf("%d\n",p->num);
		p=p->next;
	}
}

int main()
{
	NODE* p=creatlist();     //p指向回傳的head地址
	printlist(p);
	return 0;
}

看不明白請多看幾次，可在紙上模擬整個程式的運作程序

學會建立動態鏈表后我們再來學習兩個基本技能：
1.洗掉某個節點

函式片段如下

NODE* delete_node(NODE* head)
{
	NODE*p1,*p2;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想洗掉第幾個節點呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	if(m==1)
	{
		head=head->next;
	}
	else
	{
		m--;
		while(m--)
		{
			p2=p1;
			p1=p1->next;
		}
		p2->next=p1->next;
	}
	return head;
}

完整代碼

# include <stdio.h>
# include <stdlib.h>

# define NODE struct node
# define LEN sizeof(NODE)

NODE* creatlist(void);
void printlist(NODE*);
NODE* delete_node(NODE*);

NODE
{
	int num;
	NODE * next;
};


NODE* creatlist()
{
	NODE *pN,*temp;
	NODE *head=NULL,*tail=NULL;
	int n=0;
	temp=pN=(NODE *)malloc(LEN);
	printf("請給每個節點賦值，以0作為賦值的結束\n");
	scanf("%d",&pN->num); 
	while(pN->num!=0)
	{
		n++;
		if(n==1)
			head=pN;
		else
			temp->next=pN;
		temp=pN;
		pN=(NODE*)malloc(LEN);
		scanf("%d",&pN->num); 
	}
	temp->next=tail;
	return head;
}


void printlist(NODE* head)
{
	printf("\n該鏈表每個節點的值為：\n");
	NODE* p=head;
	while(p!=NULL)
	{
		printf("%d\n",p->num);
		p=p->next;
	}
}


NODE* delete_node(NODE* head)
{
	NODE*p1,*p2;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想洗掉第幾個節點呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	if(m==1)
	{
		head=head->next;
	}
	else
	{
		m--;
		while(m--)
		{
			p2=p1;
			p1=p1->next;
		}
		p2->next=p1->next;
	}
	return head;
}


int main()
{
	NODE* p=creatlist();
	printlist(p);
	p=delete_node(p);
	printf("\n洗掉成功!\n");
	system("pause");
	printlist(p);
	return 0;
}

實作效果

2.插入一個節點

函式片段

NODE* insert_node(NODE* head)
{
	NODE*p1,*p2,*p3;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想在第幾個節點后插入一個節點呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	while(m--)
	{
		p2=p1;
		p1=p1->next;
	}
	p3=(NODE*)malloc(LEN);
	p2->next=p3;
	p3->next=p1;
	printf("\n您想給該節點賦值為？\n");
	scanf("%d",&p3->num);
	return head;
}

完整程式

# include <stdio.h>
# include <stdlib.h>

# define NODE struct node
# define LEN sizeof(NODE)

NODE* creatlist(void);
void printlist(NODE*);
NODE* insert_node(NODE*);

NODE
{
	int num;
	NODE * next;
};


NODE* creatlist()
{
	NODE *pN,*temp;
	NODE *head=NULL,*tail=NULL;
	int n=0;
	temp=pN=(NODE *)malloc(LEN);
	printf("請給每個節點賦值，以0作為賦值的結束\n");
	scanf("%d",&pN->num); 
	while(pN->num!=0)
	{
		n++;
		if(n==1)
			head=pN;
		else
			temp->next=pN;
		temp=pN;
		pN=(NODE*)malloc(LEN);
		scanf("%d",&pN->num); 
	}
	temp->next=tail;
	return head;
}


void printlist(NODE* head)
{
	printf("\n該鏈表每個節點的值為：\n");
	NODE* p=head;
	while(p!=NULL)
	{
		printf("%d\n",p->num);
		p=p->next;
	}
}


NODE* insert_node(NODE* head)
{
	NODE*p1,*p2,*p3;
	if(head==NULL)
	{
		printf("\nThe list is null!\n");
		exit(0);
	}
	int m;
	printf("\n您想在第幾個節點后插入一個節點呢？\n");
	scanf("%d",&m);
	p1=p2=head;
	while(m--)
	{
		p2=p1;
		p1=p1->next;
	}
	p3=(NODE*)malloc(LEN);
	p2->next=p3;
	p3->next=p1;
	printf("\n您想給該節點賦值為？\n");
	scanf("%d",&p3->num);
	return head;
}


int main()
{
	NODE* p=creatlist();
	printlist(p);
	p=insert_node(p);
	printf("\n插入成功！\n");
	system("pause");
	printlist(p);
	return 0;
}

實作效果

2021年的第一篇文章 也是我在CSDN的第一篇文章
初涉江湖，經驗不足，江湖前輩，請多指教！
希望我的這篇文章能給剛學鏈表的你一點幫助！

鏈表還有很多很多操作 以后會堅持寫博客做總結(? ??_??)?