單鏈表的創(chuàng)建、刪除、反轉(zhuǎn)、插入、排序操作

文章目錄

• 單鏈表的創(chuàng)建、刪除、反轉(zhuǎn)、插入、排序操作
• • 1.1 鏈表引言
  • 1.2 單鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
  • 1.3 創(chuàng)建鏈表
  • 1.4 打印整個(gè)鏈表
  • 1.5 鏈表插入數(shù)據(jù)
  • 1.6 刪除某一個(gè)節(jié)點(diǎn)
  • 1.7 刪除整個(gè)鏈表
  • 1.8 鏈表的反轉(zhuǎn)
  • 1.9 鏈表的排序

1.1 鏈表引言

? 在初學(xué)鏈表時(shí)很多人會(huì)問(wèn)，什么是鏈表，鏈表怎么實(shí)現(xiàn)，原理是什么？的確帶著問(wèn)題學(xué)習(xí)會(huì)讓你變得更快，鏈表可以簡(jiǎn)單理解為老師領(lǐng)著幼兒園小朋友過(guò)馬路，他們手拉手牽著一起，老師在最前面領(lǐng)著后面的小朋友，老師就是這個(gè)領(lǐng)頭人（鏈表的頭節(jié)點(diǎn)），每一個(gè)小朋友可以看做一個(gè)節(jié)點(diǎn)。

1.2 單鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

? 單鏈表的節(jié)點(diǎn)數(shù)據(jù)根據(jù)自己的需要自行設(shè)置，但是數(shù)據(jù)中必然存在一個(gè)指針，而且指針類型為本數(shù)據(jù)類型，本文為了展示出其相關(guān)操作的原理，因此節(jié)點(diǎn)的數(shù)據(jù)定義相對(duì)簡(jiǎn)單。

/*鏈表的節(jié)點(diǎn)結(jié)構(gòu)定義*/ typedef struct list_node {int data;struct list_node *next; }list_node;

1.3 創(chuàng)建鏈表

? 創(chuàng)建鏈表需要自定義一個(gè)函數(shù)，指定鏈表頭，應(yīng)該創(chuàng)建幾個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)自行輸入所以進(jìn)行如下定義。使用whlie語(yǔ)句進(jìn)行創(chuàng)建幾個(gè)節(jié)點(diǎn)的判斷，并且對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)分配空間，通過(guò)scanf輸入數(shù)據(jù)。當(dāng)知道有幾個(gè)小朋友需要連接老師（頭節(jié)點(diǎn)）時(shí)就很容易知道，老師的下一個(gè)牽手的應(yīng)該是一個(gè)小朋友，而最后一個(gè)小朋友沒(méi)有東西牽著，所以為NULL。

int creat_list(list_node *head,int n) {if(head!=NULL&&n>0){list_node *p=head;int input_data;while(n>0){p->next=(list_node *)malloc(sizeof (list_node));printf("please input data：\n");scanf("%d",&input_data);p->next->data=input_data;p=p->next;n--;head->data++;}p->next=NULL;//鏈表的尾部節(jié)點(diǎn)下個(gè)指向?yàn)榭?#xff0c;理解最后一個(gè)小朋友沒(méi)東西牽著return 0;}else{printf("輸入創(chuàng)建鏈表參數(shù)出錯(cuò)：\n");return -1;} }

1.4 打印整個(gè)鏈表

? 打印鏈表實(shí)現(xiàn)相對(duì)簡(jiǎn)單，相當(dāng)于老師牽著小朋友，讓每個(gè)小朋友進(jìn)行報(bào)數(shù)，當(dāng)?shù)阶詈笠粋€(gè)小朋友時(shí)牽著為空氣，報(bào)數(shù)完畢，所以判斷條件就是當(dāng)下一個(gè)指針指向?yàn)榭盏臅r(shí)候停止遍歷鏈表。

/*打印整個(gè)鏈表*/ void print_list(list_node *head) {if(head!=NULL){printf("sum node %d\n",head->data);list_node *p=head->next;while(p!=NULL){printf("~~~~~~~~~~~%d\n",p->data);p=p->next;}} }

1.5 鏈表插入數(shù)據(jù)

? 鏈表插入的函數(shù)，指定要插入的鏈表的頭節(jié)點(diǎn)，插入的位置，需要插入的數(shù)據(jù)。插入的原理如下圖：假設(shè)在1號(hào)和2號(hào)之間需要插入一個(gè)小朋友，首先應(yīng)該報(bào)數(shù)，當(dāng)一號(hào)報(bào)數(shù)完畢后，我們知道了應(yīng)該在此插入，然后停下操作，先創(chuàng)建一個(gè)節(jié)點(diǎn)空間，然后把小朋友（節(jié)點(diǎn)數(shù)據(jù)）放進(jìn)這個(gè)空間，新插入的小朋友應(yīng)該是一邊被一號(hào)牽著，另一邊牽著2號(hào)。

/*第一個(gè)參數(shù)指定鏈表頭，第二參數(shù)在哪一個(gè)位置之后插入值*/ void insert_data(list_node *head,int data,int n) {if(n<0||head->data<n||head==NULL){printf("插入?yún)?shù)出錯(cuò)\n");}else{list_node *p=head->next;list_node *pre=head;while(n>0)//此處相當(dāng)于先報(bào)數(shù){pre=p;p=p->next;n--;}list_node *new_node=(list_node *)malloc(sizeof (list_node));new_node->data=data;new_node->next=p; //此處對(duì)應(yīng)紅色解釋圖pre->next=new_node;head->data++;} }

1.6 刪除某一個(gè)節(jié)點(diǎn)

? 刪除某一個(gè)節(jié)點(diǎn)，也是需要知道鏈表的表頭，和刪除第幾個(gè)節(jié)點(diǎn)，原理和插入類似，如下圖所示：

void delete_data(list_node *head,int n) {if(n<=0||head==NULL){printf("輸入?yún)?shù)錯(cuò)誤");return;}else{list_node *pre=NULL;list_node *current=head;list_node *next=head->next;while(n>0){pre=current;current=next;next=next->next;n--;}pre->next=next;free(current);} }

1.7 刪除整個(gè)鏈表

? 刪除整個(gè)鏈表可不是直接free表頭就行了，要一個(gè)個(gè)遍歷整個(gè)鏈表，然后記錄前一個(gè)指針的位置進(jìn)行一個(gè)一個(gè)free，原理和刪除一個(gè)類似，這里直接上代碼。

/*對(duì)整個(gè)鏈表進(jìn)行刪除*/ void delete_list(list_node *head) {if(head!=NULL){list_node *pre=NULL;list_node *current=head;list_node *next=head->next;while(current!=NULL){pre=current;current=next;next=next->next;free(pre);}free(current);}else{printf("鏈表已經(jīng)為空\(chéng)n");} }

1.8 鏈表的反轉(zhuǎn)

? 這個(gè)相對(duì)來(lái)說(shuō)難一點(diǎn)，但是理解原理之后還是很容易的，有點(diǎn)類似于排序，但是有點(diǎn)區(qū)別。

反轉(zhuǎn)一步一步的過(guò)程應(yīng)該是這樣，也有其他方法，自己查一下。

head->1->2->3->4->5 --------------------------------------原始鏈表

head->2->1->3->4->5 ---------------------------------------第一步

head->3->2->1->4->5 ---------------------------------------第二步

head->4->3->2->1->5 ---------------------------------------第三步

head->5->4->3->2->1 ---------------------------------------第四步

也就是相當(dāng)于，每次把遍歷到的當(dāng)前數(shù)據(jù)提到最前面。

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

/*鏈表的反轉(zhuǎn)*/ void reversal_list(list_node *head) {if(head!=NULL){list_node *current=head->next;list_node *next=current->next;while(next!=NULL){current->next=next->next;next->next=head->next;head->next=next;next=current->next;}}else{printf("鏈表為空\(chéng)n");} }

1.9 鏈表的排序

? 此次鏈表的排序使用的是選擇排序，相對(duì)簡(jiǎn)單，使用冒泡等也能實(shí)現(xiàn)，簡(jiǎn)單講一下冒泡的原理：

head->1->2->3->4 --------------------------------------原始鏈表

head->4->2->3->1 ---------------------------------------第一步

head->4->3->2->1 ---------------------------------------第二步

就是進(jìn)行先讓第一個(gè)數(shù)和之后的每一個(gè)數(shù)比較，只要遇到比他大的就和第一個(gè)位置交換數(shù)據(jù)，然后第一個(gè)位置就是最大的數(shù)據(jù)，之后讓第二位與之后的每一個(gè)數(shù)據(jù)比較只要比他大的數(shù)就交換位置，…一直這么結(jié)束，排序完成。

/*使用選擇排序*/ void list_sort(list_node *head) {/*頭節(jié)點(diǎn)的data用來(lái)存儲(chǔ)總共有多少節(jié)點(diǎn)*/if(head==NULL)return;int i=0;int k=0;list_node *p=head->next;for(i=0;i<head->data-1;i++){list_node *s=p->next;for(k=i+1;k<head->data;k++){if((s->data)<(p->data)){int tem=p->data;p->data=s->data;s->data=tem;}s=s->next;}p=p->next;} }**持續(xù)更新鏈表的循環(huán)鏈表、雙向鏈表操作**

總結(jié)

以上是生活随笔為你收集整理的单链表的创建、删除、反转、插入、排序操作的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。