學(xué)習(xí)啦 > 學(xué)習(xí)英語(yǔ) > 專業(yè)英語(yǔ) > 計(jì)算機(jī)英語(yǔ) > c語(yǔ)言鏈表的用法

c語(yǔ)言鏈表的用法

時(shí)間： 長(zhǎng)思709由 分享

c語(yǔ)言鏈表的用法

　　鏈表是數(shù)據(jù)結(jié)構(gòu)中比較基礎(chǔ)也是比較重要的類型之一，那么有了數(shù)組，為什么我們還需要鏈表呢！或者說(shuō)設(shè)計(jì)鏈表這種數(shù)據(jù)結(jié)構(gòu)的初衷在哪里？下面小編就為大家介紹下c語(yǔ)言鏈表的用法。
　　c語(yǔ)言枚舉的用法如下：
        這是因?yàn)?，在我們使用?shù)組的時(shí)候，需要預(yù)先設(shè)定目標(biāo)群體的個(gè)數(shù)，也即數(shù)組容量的大小，然而實(shí)時(shí)情況下我們目標(biāo)的個(gè)數(shù)我們是不確定的，因此我們總是要把數(shù)組的容量設(shè)置的很大，這樣以來(lái)就浪費(fèi)了很多的空間。另外，數(shù)組在進(jìn)行插入操作和刪除操作的時(shí)候，在插入或者刪除制定元素之后，我們往往需要進(jìn)行循環(huán)移位，這增加了我們的線性開(kāi)銷。
　　正是由于以上的兩種主要原因，鏈表被設(shè)計(jì)出來(lái)用于一般表的操作。為了避免上面描述數(shù)組的兩種弊端，我們希望鏈表有一下的特點(diǎn)
　　1 可以靈活的擴(kuò)展自己的長(zhǎng)度。
　　2 存儲(chǔ)地址不連續(xù)，刪除或者插入操作的時(shí)候不需要循環(huán)移位。
　　要實(shí)現(xiàn)以上兩個(gè)特點(diǎn)，我們需既要保證每個(gè)節(jié)點(diǎn)的獨(dú)立性，又要保存相鄰兩個(gè)節(jié)點(diǎn)的聯(lián)系。
　　為此，鏈表一般被設(shè)計(jì)為下面的形式。
　　Node--->Node---->Node
　　鏈表是由一個(gè)一個(gè)的節(jié)點(diǎn)組成的，可以方便和自由的插入未知個(gè)Node，前一個(gè)節(jié)點(diǎn)中用指針保存著下一個(gè)節(jié)點(diǎn)的位置，這樣以來(lái)便順利的完成了我們對(duì)鏈表的兩點(diǎn)期望，但是唯一的缺點(diǎn)是增加了額外的空間消耗。
　　————————————————————————————————————————————————————————————————————————————
　　鏈表的定義：
　　鏈表的定義一般使用結(jié)構(gòu)體，在看《數(shù)據(jù)結(jié)構(gòu)與算法分析》這本書(shū)的時(shí)候發(fā)現(xiàn)，書(shū)中頻繁的使用typedef的關(guān)鍵字，結(jié)果真的很棒不僅保持的代碼的整潔程度，也讓我們?cè)谙旅娴木幋a過(guò)程中少見(jiàn)了很多煩人的指針（當(dāng)然指針還是一直存在的）。所以這里也借用了書(shū)中的定義方法。
　　struct Node;
　　typedef struct Node* PtrNode;
　　typedef PtrNode Position;
　　typedef PtrNode List;
　　struct Node{
　　int Value;
　　PtrNode Next;
　　};
　　下面接著書(shū)寫(xiě)一個(gè)建立鏈表的函數(shù)，輸入每個(gè)節(jié)點(diǎn)的值，直到這個(gè)值是-1的時(shí)候函數(shù)結(jié)束。
　　在這個(gè)里面，我以前一直搞不明白為什么需要定義三個(gè)Node *，現(xiàn)在終于了解了，最終還是復(fù)習(xí)了指針的內(nèi)容明白的，這里說(shuō)一下指針實(shí)現(xiàn)鏈表對(duì)指針的操作很頻繁，需要比較扎實(shí)的掌握了指針之后，在來(lái)看鏈表會(huì)輕松很多。在下面的一段程序里，我分別定義了head/p/tmp這三個(gè)指向節(jié)點(diǎn)結(jié)構(gòu)體的指針，head的主要作用就像一個(gè)傳銷頭目，他會(huì)主動(dòng)聯(lián)系上一個(gè)下線p，然后他就什么也不干了，p接著去發(fā)展一個(gè)又一個(gè)的下線tmp，結(jié)果一串以head為首的鏈表就出來(lái)了。
　　起先，我總覺(jué)得有了head，為什么還要p，這是因?yàn)槿绻苯邮褂胔ead去指向下一個(gè)節(jié)點(diǎn)，head的位置也是不斷在移動(dòng)的，即它永遠(yuǎn)處于鏈表的尾端，這樣當(dāng)我們返回鏈表的時(shí)候，其實(shí)是空值。所以，我們需要p這個(gè)中轉(zhuǎn)環(huán)節(jié)。（其實(shí)，這種做法在指針中非常普遍，大部分有返回指針類型的函數(shù)中，都會(huì)首先定義一個(gè)指針變量來(lái)保存函數(shù)的傳入的參數(shù)，而不是對(duì)參數(shù)直接進(jìn)行操作）。
　　?
　　/*
　　函數(shù)功能：創(chuàng)建一個(gè)鏈表
　　函數(shù)描述：每次輸入一個(gè)新的整數(shù)，即把新增加一個(gè)節(jié)點(diǎn)存放該整數(shù)，
　　當(dāng)輸入的整數(shù)為-1時(shí)，函數(shù)結(jié)束。
　　*/
　　List create()
　　{
　　int n=0;
　　Position p,head,tmp;
　　head=NULL;
　　tmp=malloc(sizeof(struct Node));
　　if(tmp==NULL)
　　{
　　printf("tmp malloc failed!\n");
　　return NULL;
　　}
　　else
　　{
　　p=tmp;
　　printf("please input the first node's message!\n");
　　scanf("%d",&(tmp->Value));
　　}
　　while(tmp->Value!=-1)
　　{
　　n+=1;
　　if(n==1)
　　{
　　head=p;
　　tmp->Next=NULL;
　　}
　　else
　　{
　　p->Next=tmp;
　　}
　　p=tmp;
　　tmp=malloc(sizeof(struct Node));
　　printf("please input the %d node!\n",n+1);
　　scanf("%d",&(tmp->Value));
　　}
　　p->Next=NULL;
　　free(tmp);  //free函數(shù)free掉的只是申請(qǐng)的空間，但是指針還是依然存在的。
　　tmp=NULL;
　　return head;
　　}
　　接下來(lái)，在寫(xiě)一個(gè)刪除鏈表節(jié)點(diǎn)的函數(shù)，輸入一個(gè)整數(shù)然后遍歷鏈表節(jié)點(diǎn)，當(dāng)鏈表節(jié)點(diǎn)的值與該整數(shù)相等的時(shí)候，即把該節(jié)點(diǎn)刪除。
　　在完成這個(gè)函數(shù)首先一定要把這個(gè)過(guò)程思考清楚，不可否認(rèn)我之前是一個(gè)上來(lái)就敲代碼的人，看了《劍指offer》感覺(jué)這種習(xí)慣是程序員的大忌，甚至還想寫(xiě)一篇博客，名字都想好了《程序員的自我修養(yǎng)之思考在前，代碼在后》。其實(shí)想想也是，我們寫(xiě)程序的目的是為了解決問(wèn)題，而不是為了簡(jiǎn)單的寫(xiě)程序，純粹的讓程序跑起來(lái)大概只會(huì)在上學(xué)那會(huì)存在吧！真實(shí)的程序開(kāi)發(fā)中需要考慮幾乎所有 能想到的實(shí)際問(wèn)題，所以無(wú)論程序再下，一要學(xué)會(huì)先思考清楚，再下筆寫(xiě)程序。
　　關(guān)于這個(gè)函數(shù),我們要想到的是：
　　1 如果鏈表為空，我們?cè)撛趺醋?，?dāng)然是直接返回。
　　2 如果要?jiǎng)h除的元素為頭節(jié)點(diǎn)該怎么辦？
　　3 如果要?jiǎng)h除的元素為尾節(jié)點(diǎn)該怎么辦？
　　當(dāng)注意到以上三個(gè)部分，我們的程序就可能避免掉了輸入鏈表為空，程序直接崩潰的現(xiàn)象，也可以避免刪除元素值為頭節(jié)點(diǎn)時(shí)刪不掉的尷尬。我們的程序就有了一定的魯棒性。
　　下面著重考慮鏈表的刪除的實(shí)現(xiàn)：
　　list： ???? Node_a->Node_b->Node_c->Node_d;
　　?????????????? list ?????? tmp???????? p
　　?
　　?? -------> ?????? ? ? ? tmp->Next=p->Next;
　　?
　　?
　　list:?????? Node_a->Node_b----------->Node_d
　　????????????????????????????????????? free(p)
　　假設(shè)我們要?jiǎng)h除的節(jié)點(diǎn)為上圖的Node_c;假設(shè)我們能夠找到Node_c的前一個(gè)位置tmp和被刪除節(jié)點(diǎn)位置p的話;這個(gè)時(shí)候我們只需要執(zhí)行tmp->Next=p->Next即可。
　　只要完成上面的分析以及考慮到各種情況，我們完成下面的代碼就水到渠成了。
　　/*
　　函數(shù)功能：刪除鏈表中指定值的節(jié)點(diǎn)（如果存在多個(gè)，只刪除第一個(gè)）
　　本例中輸入一個(gè)整數(shù)，刪除鏈表節(jié)點(diǎn)值為這個(gè)整數(shù)的節(jié)點(diǎn)。
　　*/
　　List DeleteNode(List list)
　　{
　　Position p,tmp;
　　int value;
　　if(list==NULL)
　　{
　　printf("The list is null,function return!\n");
　　return NULL;
　　}
　　else
　　{
　　printf("please input the delete Node's value:\n");
　　scanf("%d",&value);
　　}
　　p=list;
　　if(p->Value==value)
　　{
　　list=p->Next;
　　free(p);
　　p=NULL;
　　return list;
　　}
　　while(p!=NULL&&p->Value!=value)
　　{
　　tmp=p;
　　p=p->Next;
　　}
　　if(p->Value==value)
　　{
　　if(p->Next!=NULL){
　　tmp->Next=p->Next;
　　}
　　else
　　{
　　tmp->Next=NULL;
　　}
　　free(p);
　　p=NULL;
　　}
　　return list;
　　}
　　?關(guān)于鏈表的使用場(chǎng)景分析:
　　鏈表在程序開(kāi)發(fā)中用到的頻率還是非常高的，所以在高級(jí)語(yǔ)言中往往會(huì)對(duì)鏈表進(jìn)行一些實(shí)現(xiàn)，比如STL中l(wèi)ist以及Java中也有類似的東西。在目前的服務(wù)器端開(kāi)發(fā)，主要運(yùn)用鏈表來(lái)接收一些從數(shù)據(jù)中取出來(lái)的數(shù)據(jù)進(jìn)行處理。
　　即使你不知道鏈表的底層實(shí)現(xiàn)，仍然可以成功的運(yùn)用STL里面的現(xiàn)成的東西。但是作為一個(gè)學(xué)習(xí)者，我覺(jué)得會(huì)使用和從底層掌握仍然是兩個(gè)不同的概念，linux之父說(shuō)：“talk is less，show you code”。
　　以下的程序，用鏈表模擬了一個(gè)電話通訊錄的功能，包括添加聯(lián)系人，查找聯(lián)系人，以及刪除聯(lián)系人。
　　PS：關(guān)于魯棒性，程序中最大的危險(xiǎn)是使用了gets這個(gè)函數(shù)，目前先保留使用gets，等待找到工作之后在做進(jìn)一步的程序完善。（尼瑪，讀書(shū)去。。。應(yīng)屆生，找個(gè)工作他媽咋這么難呢！?? 工作經(jīng)驗(yàn)，工作經(jīng)驗(yàn)，艸，那個(gè)大牛一出校門就什么都會(huì)。）
　　?
　　/**************************************************************************
　　Programe:
　　This is a phone list write by list
　　The programe is just prictise for list
　　Author: heat nan
　　Mail:964465194@qq.com
　　Data:2015/07/27
　　**************************************************************************/
　　#include<stdio.h>
　　#include<string.h>
　　#include<stdlib.h>
　　#define N 25
　　#define M 15
　　struct node;
　　typedef struct node* p_node;
　　typedef p_node List;
　　typedef p_node Position;
　　typedef struct node** PList;
　　struct node{
　　char name[N];
　　char number[M];
　　Position next;
　　};
　　int JudgeNameExist(List list,char* name);
　　void AddPerson(PList list);
　　void PrintList(List list);
　　List FindPerson(List list);
　　List FindPersonByName(List list,char* name);
　　int AddPersonByName(PList list,List node);
　　int DeletePersonByName(PList list,char* name);
　　void DeletePerson(PList list);
　　int main()
　　{
　　List list=NULL;
　　Position p;
　　char cmd[100];
　　while(1)
　　{
　　printf("                    MAIN                 \n");
　　printf("       ******* 1 add a person        *******\n");
　　printf("       ******* 2 show the phone list *******\n");
　　printf("       ******* 3 find  from phone list *******\n");
　　printf("       ******* 4 delete from phone list *******\n\n\n");
　　printf("Please input the cmd number:\n");
　　gets(cmd);
　　switch(cmd[0])
　　{
　　case '1':
　　AddPerson(&list);
　　break;
　　case '2':
　　PrintList(list);
　　break;
　　case '3':
　　FindPerson(list);
　　break;
　　case '4':
　　DeletePerson(&list);
　　break;
　　default:
　　printf("wrong cmd!\n");
　　break;
　　}
　　}
　　return 0;
　　}
　　/*
　　Function:判斷要添加的聯(lián)系人名稱是否已經(jīng)存在于電話簿中.
　　Input:   List 電話列表,name 要添加的聯(lián)系人的姓名.
　　Return:  已經(jīng)存在返回1,不存在返回0.
　　*/
　　int JudgeNameExist(List list,char* name)
　　{
　　if(FindPersonByName(list,name)!=NULL)
　　return 1;
　　else
　　return 0;
　　}
　　/*
　　Function:根據(jù)輸入的姓名查找聯(lián)系人的信息節(jié)點(diǎn)
　　Input:   要輸入的電話列表list,姓名name
　　Return:  返回查找到的節(jié)點(diǎn)
　　*/
　　List FindPersonByName(List list,char* name)
　　{
　　while(list!=NULL)
　　{
　　if(strcmp(list->name,name)==0)
　　break;
　　list=list->next;
　　}
　　return list;
　　}
　　/*
　　Function:根據(jù)姓名添加新的聯(lián)系人到聯(lián)系人列表
　　Input:   指向聯(lián)系人列表地址的指針， 新用戶節(jié)點(diǎn)
　　Return:  添加成功返回1，添加失敗返回0
　　*/
　　int AddPersonByName(PList list,List node)
　　{
　　if(node==NULL)
　　{
　　printf("the node is NULL!\n");
　　return 0;
　　}
　　if(*list==NULL)
　　{
　　*list=node;
　　return 1;
　　}
　　List pHead=*list;
　　while(pHead->next!=NULL)
　　pHead=pHead->next;
　　pHead->next=node;
　　return 1;
　　}
　　void AddPerson(PList list)
　　{
　　Position tmp;
　　Position p_head;
　　tmp=(struct node*)malloc(sizeof(struct node));
　　char name[N];
　　char number[M];
　　if(tmp==NULL)
　　{
　　printf("malloc the tmp node failed in function add person!\n");
　　}
　　else
　　{
　　printf("please input the name:\n");
　　gets(name);
　　printf("please input the number:\n");
　　gets(number);
　　strcpy(tmp->name,name);
　　strcpy(tmp->number,number);
　　tmp->next=NULL;
　　}
　　if(JudgeNameExist(*list,name)==1)
　　{
　　free(tmp);
　　printf("the name have already exist!\n");
　　return;
　　}
　　AddPersonByName(list,tmp);
　　}
　　/*
　　Function: 打印聯(lián)系人列表
　　Input：   聯(lián)系人列表
　　*/
　　void PrintList(List list)
　　{
　　Position show;
　　show=list;
　　if(show==NULL)
　　{
　　return ;
　　}
　　printf("Now,we print the phone list:\n");
　　while(show!=NULL)
　　{
　　printf("Name:%s  Number:%s\n",show->name,show->number);
　　show=show->next;
　　}
　　}
　　List FindPerson(List list)
　　{
　　char name[N];
　　Position pHead=list;
　　printf("please input the name you will find:\n");
　　gets(name);
　　Position node=FindPersonByName(list,name);
　　if(node!=NULL)
　　printf("find success! name-> %s number-> %s\n",node->name,node->number);
　　else
　　printf("find failed!\n");
　　return node;
　　}
　　/*
　　Function:根據(jù)姓名刪除聯(lián)系人
　　Input：  指向聯(lián)系人地址的指針，聯(lián)系人姓名
　　Output： 刪除成功返回1，失敗返回0
　　*/
　　int DeletePersonByName(PList list,char* name)
　　{
　　if(*list==NULL||name==NULL)
　　return 0;
　　List pHead=*list;
　　if(strcmp(pHead->name,name)==0)
　　{
　　*list=pHead->next;
　　free(pHead);
　　pHead->next==NULL;
　　return 0;
　　}
　　List tmp=pHead->next;
　　while(tmp!=NULL)
　　{
　　if(strcmp(tmp->name,name)==0)
　　{
　　pHead->next=tmp->next;
　　free(tmp);
　　tmp->next=NULL;
　　return 1;
　　}
　　pHead=tmp;
　　tmp=tmp->next;
　　}
　　return 0;
　　}
　　void DeletePerson(PList list)
　　{
　　List pHead=*list;
　　if(pHead==NULL)
　　{
　　printf("there is no person you can delet\n");
　　return ;
　　}
　　char name[N];
　　printf("please input the name:\n");
　　gets(name);
　　DeletePersonByName(list,name);
　　}
515221