2021-09-22

《資料結構嚴蔚敏第二版》2.52，單向鏈表的鏈式表示與實作

（來了來了兄弟們，小手點一下右上角，來一波博主養成關注）
接第一篇博客，線性表包括順序實作和鏈式實作，兩者的底層存盤區別體現在順序表是開辟連續地址空間存盤，而鏈表則不用連續地址空間存盤，哪兒有空位往哪兒插入資料，對存盤空間要求不高， ----這是我的大白話（以下是書上正兒八經的解釋）
鏈表和順序表空間性能的比較：
存盤空間：
由于順序表的存盤空間必須預先分配，容易造成存盤空間浪費或者空間溢位（簡單來說就是自己所需要使用的空間比我們擁有的記憶體大記憶體不夠使用所造成的記憶體溢位）
鏈表不需要預先分配空間，只要記憶體允許 ，鏈表元素個數就不受限制，
存盤密度：
順序表的存盤方式可以知道，一個結點只存資料，所以存盤密度是1，而鏈表的存盤方式為資料加指標，鏈表的不同，則資料和指標也不同，比如單鏈表一個結點只有一個指標，而雙向鏈表一個結點有兩個指標，那么鏈表的存盤密度是必然小于1的，
就選擇使用線性表方法來說，如果表的長度變化不大，則選擇使用順序表，反之，則選擇鏈表，

單向鏈表的操作實作：

首先創建鏈表第一步預設結點型別：

typedef struct List{
	int data;    //資料域
	struct list* next;    //指標域
}node;      //node為節點名，每一個節點都是List結構體

初始化：
1.頭節點初始化：

llist *CreatHead()
{
	list *p=(list*)malloc(sizeof(list));//給頭節點開辟地址空間，一個就OK勒 
	p->next=NULL;//頭節點可以選擇不用初始化資料域，只用把頭結點的指標置空就Ok勒 
	return p;//回傳頭節點，這樣我們就可以通過頭結點的指標找到整個鏈表辣 
} 

2.我們初始化整個鏈表，就整五個節點吧，太多了看著迷糊：

頭插法：

void CreatList(list* p)
{
	for(int i=0;i<5;i++)//就整五個 
	{
		list *n=(list*)malloc(sizeof(list));//開辟一個新鮮的存盤空間給新的節點
		//節點創建好了，那么我們就考慮下一步初始化這個節點的資料域，整簡單點，節點的資料置為節點的次序
		n->data=i;
		//接下來就是用新節點的指標域將新的節點和頭節點鏈接起來
		n->next=p->next;
		p->next=n;
		//簡簡單單兩句話鏈接起來
		}
 } 

3.拉進主函式，列印出來看看啥樣：

#include<stdio.h>
#include<stdlib.h>
typedef struct list{
	int data;
	list* next;
}node; 
list *CreatHead()
{
	list *p=(list*)malloc(sizeof(list));//給頭節點開辟地址空間，一個就OK勒 
	p->next=NULL;//頭節點可以選擇不用初始化資料域，只用把頭結點的指標置空就Ok勒 
	return p;//回傳頭節點，這樣我們就可以通過頭結點的指標找到整個鏈表辣 
} 
void CreatList(list* p)
{
	for(int i=0;i<5;i++)//就整五個 
	{
		list *n=(list*)malloc(sizeof(list));//開辟一個新鮮的存盤空間給新的節點
		//節點創建好了，那么我們就考慮下一步初始化這個節點的資料域，整簡單點，節點的資料置為節點的次序
		n->data=i;
		//接下來就是用新節點的指標域將新的節點和頭節點鏈接起來
		n->next=p->next;
		p->next=n;
		//簡簡單單兩句話鏈接起來
		 
		 
	}
 } 
 PrintfList(list * p) 
 {
 	printf("鏈表資料如下：\n");
 	while(p->next!=NULL)
 	{
	    p=p->next;
 		printf("%d ",p->data);
	 }
	 printf("\n"); 
 }
 int main()
 {
 	list* p=CreatHead();//接收頭節點
 	CreatList(p);//傳入頭節點初始化整條鏈表
 	PrintfList(p);//簡簡單單列印一下；
  } 

貼上運行結果:

兄弟們看到有什么異樣沒有？是的沒錯，本來我們是按0 1 2 3 4 的順序把資料裝進鏈表里的，為什么列印出來就是反的啊，這是為什么呀？
俺來分析一下代碼塊：
n->next=p->next;
p->next=n;
首先鏈表還未鏈接的時候只有一個頭節點，頭結點的指標置空了，第一個節點來了；那么我們n->next=p->next;的意思就是把新節點的指標指向頭節點的指向即為NULL，p->next=n;頭結點的指標再指向第一個節點
如圖所示：


然后新的節點再接入頭節點與上一個節點之間，這種插入新節點的方法稱為頭插法，醬紫搞的話，新進來的元素就挨個排后面去了，頭插輸入輸出實作的功能是先進后出，相反的，尾插輸入輸出實作的功能就是先進先出：

尾插法：

void CreatList(list* p)
{
	list *end=p;//整一個尾節點 ，先把尾節點置為頭節點 
	for(int i=0;i<5;i++)//就整五個 
	{
		list *n=(list*)malloc(sizeof(list));//開辟一個新鮮的存盤空間給新的節點
		//節點創建好了，那么我們就考慮下一步初始化這個節點的資料域，整簡單點，節點的資料置為節點的次序
		n->data=i;
		n->next=end->next; 
		end->next=n;
		end=n;//尾節點跟著新節點位置跑 頭節點保持不變就鏈接起來嘍 
	}
 } 

拉進主函式我們看看咋樣：

#include<stdio.h>
#include<stdlib.h>
typedef struct list{
	int data;
	list* next;
}node; 
list *CreatHead()
{
	list *p=(list*)malloc(sizeof(list));//給頭節點開辟地址空間，一個就OK勒 
	p->next=NULL;//頭節點可以選擇不用初始化資料域，只用把頭結點的指標置空就Ok勒 
	return p;//回傳頭節點，這樣我們就可以通過頭結點的指標找到整個鏈表辣 
} 
void CreatList(list* p)
{
	list *end=p;//整一個尾節點 ，先把尾節點置為頭節點 
	for(int i=0;i<5;i++)//就整五個 
	{
		list *n=(list*)malloc(sizeof(list));//開辟一個新鮮的存盤空間給新的節點
		//節點創建好了，那么我們就考慮下一步初始化這個節點的資料域，整簡單點，節點的資料置為節點的次序
		n->data=i;
		n->next=end->next; 
		end->next=n;
		end=n;//尾節點跟著新節點位置跑 頭節點保持不變就鏈接起來嘍 
	}
 } 
 PrintfList(list * p) 
 {
 	printf("鏈表資料如下：\n");
 	while(p->next!=NULL)
 	{
	    p=p->next;
 		printf("%d ",p->data);
	 }
	 printf("\n"); 
 }
 int main()
 {
 	list* p=CreatHead();
 	CreatList(p);

 	PrintfList(p);
  } 

列印結果：

這樣式兒的列印出來就是先進先出嘍，
接下來看看單鏈表的增刪查（改太簡單了，只要查到了節點有手就行，這里就不講改了）

單鏈表增加

這個功能實作，咱們第一步得找到要插入節點的位置，插入節點，OK完活！

 void InsertList(list *p,int add, int element)
{
	int i=0;
	while(p->next!=NULL)
	{
		p=p->next;
		i++;
		if(i==add)//找到位置嘍
		{
			list *newnode=(list*)malloc(sizeof(list));
			newnode->data=element;
			newnode->next=p->next;
			p->next=newnode; 
		}
	}
}

試試在在第二位資料與第三位資料之間插入元素3：

洗掉節點

兩個操作：1.找到要洗掉的節點，更改這個節點的前驅后繼鏈接
2.釋放掉該節點所占的地址空間（為一名合格的程式員，要對存盤空間負責，對不再利用的存盤空間要及時釋放，QAQ）
簡簡單單咱們洗掉第一個節點試試：

void DeleteNode(list *p,1)
{
	list *pre=p;
	list *temp=p; 
	int i=0;
	while(p->next!=NULL)
	{
	   pre=p;
	   p=p->next;  
	   i++;
	   if(i==add)
	   {
	   	pre->next=p->next;
	   	p->next=NULL;
	   	temp=p; 
		} 
	   	}
	   	free(temp);
}

貼上結果：

查找：

肥腸簡單，遍歷鏈表+比對資訊即可：

void querylist(list *p,int q)//q為要洗掉的資料資訊
{
	int i=0;
	while(p->next!=NULL)
	{
		p=p->next;
		i++;
		if(p->data==q)
		{
			printf("查找資料位于第%d位\n",i);
			break;
		 } 
	 } 
}

貼上運行結果：

怎么樣，是不是真的肥腸簡單哇，不會的童鞋，多康康就會了喲，好了，今天就更這些了，明天更新回圈和雙向鏈表的內容，謝謝大家（0.0）.