- 相關(guān)推薦
c語言鏈表的用法有哪些
鏈表是數(shù)據(jù)結(jié)構(gòu)中比較基礎(chǔ)也是比較重要的類型之一，那么有了數(shù)組，為什么我們還需要鏈表呢！或者說設(shè)計鏈表這種數(shù)據(jù)結(jié)構(gòu)的初衷在哪里？下面小編就為大家介紹下c語言鏈表的用法。
鏈表的定義：
鏈表的定義一般使用結(jié)構(gòu)體，在看《數(shù)據(jù)結(jié)構(gòu)與算法分析》這本書的時候發(fā)現(xiàn)，書中頻繁的使用typedef的關(guān)鍵字，結(jié)果真的很棒不僅保持的代碼的整潔程度，也讓我們在下面的編碼過程中少見了很多煩人的指針（當(dāng)然指針還是一直存在的）。所以這里也借用了書中的定義方法。
struct Node;
typedef struct Node* PtrNode;
typedef PtrNode Position;
typedef PtrNode List;
struct Node{
int Value;
PtrNode Next;
};
下面接著書寫一個建立鏈表的函數(shù)，輸入每個節(jié)點的值，直到這個值是-1的時候函數(shù)結(jié)束。
在這個里面，我以前一直搞不明白為什么需要定義三個Node *，現(xiàn)在終于了解了，最終還是復(fù)習(xí)了指針的內(nèi)容明白的，這里說一下指針實現(xiàn)鏈表對指針的操作很頻繁，需要比較扎實的掌握了指針之后，在來看鏈表會輕松很多。在下面的一段程序里，我分別定義了head/p/tmp這三個指向節(jié)點結(jié)構(gòu)體的指針，head的主要作用就像一個傳銷頭目，他會主動聯(lián)系上一個下線p，然后他就什么也不干了，p接著去發(fā)展一個又一個的下線tmp，結(jié)果一串以head為首的鏈表就出來了。
起先，我總覺得有了head，為什么還要p，這是因為如果直接使用head去指向下一個節(jié)點，head的位置也是不斷在移動的，即它永遠(yuǎn)處于鏈表的尾端，這樣當(dāng)我們返回鏈表的時候，其實是空值。所以，我們需要p這個中轉(zhuǎn)環(huán)節(jié)。（其實，這種做法在指針中非常普遍，大部分有返回指針類型的函數(shù)中，都會首先定義一個指針變量來保存函數(shù)的傳入的參數(shù)，而不是對參數(shù)直接進(jìn)行操作）。
/*
函數(shù)功能：創(chuàng)建一個鏈表
函數(shù)描述：每次輸入一個新的整數(shù)，即把新增加一個節(jié)點存放該整數(shù)，
當(dāng)輸入的整數(shù)為-1時，函數(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! ");
return NULL;
}
else
{
p=tmp;
printf("please input the first node's message! ");
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+1);
scanf("%d",&(tmp->Value));
}
p->Next=NULL;
free(tmp); //free函數(shù)free掉的只是申請的空間，但是指針還是依然存在的。
tmp=NULL;
return head;
}
接下來，在寫一個刪除鏈表節(jié)點的函數(shù)，輸入一個整數(shù)然后遍歷鏈表節(jié)點，當(dāng)鏈表節(jié)點的值與該整數(shù)相等的時候，即把該節(jié)點刪除。
在完成這個函數(shù)首先一定要把這個過程思考清楚，不可否認(rèn)我之前是一個上來就敲代碼的人，看了《劍指offer》感覺這種習(xí)慣是程序員的大忌，甚至還想寫一篇博客，名字都想好了《程序員的自我修養(yǎng)之思考在前，代碼在后》。其實想想也是，我們寫程序的目的是為了解決問題，而不是為了簡單的寫程序，純粹的讓程序跑起來大概只會在上學(xué)那會存在吧！真實的程序開發(fā)中需要考慮幾乎所有 能想到的實際問題，所以無論程序再下，一要學(xué)會先思考清楚，再下筆寫程序。
關(guān)于這個函數(shù),我們要想到的是：
1 如果鏈表為空，我們該怎么做，當(dāng)然是直接返回。
2 如果要刪除的元素為頭節(jié)點該怎么辦？
3 如果要刪除的元素為尾節(jié)點該怎么辦？
當(dāng)注意到以上三個部分，我們的程序就可能避免掉了輸入鏈表為空，程序直接崩潰的現(xiàn)象，也可以避免刪除元素值為頭節(jié)點時刪不掉的尷尬。我們的程序就有了一定的魯棒性。
下面著重考慮鏈表的刪除的實現(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é)點為上圖的Node_c;假設(shè)我們能夠找到Node_c的前一個位置tmp和被刪除節(jié)點位置p的話;這個時候我們只需要執(zhí)行tmp->Next=p->Next即可。
只要完成上面的分析以及考慮到各種情況，我們完成下面的代碼就水到渠成了。
/*
函數(shù)功能：刪除鏈表中指定值的節(jié)點（如果存在多個，只刪除第一個）
本例中輸入一個整數(shù)，刪除鏈表節(jié)點值為這個整數(shù)的節(jié)點。
*/
List DeleteNode(List list)
{
Position p,tmp;
int value;
if(list==NULL)
{
printf("The list is null,function return! ");
return NULL;
}
else
{
printf("please input the Node's value: ");
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)于鏈表的使用場景分析:
鏈表在程序開發(fā)中用到的頻率還是非常高的，所以在高級語言中往往會對鏈表進(jìn)行一些實現(xiàn)，比如STL中l(wèi)ist以及Java中也有類似的東西。在目前的服務(wù)器端開發(fā)，主要運用鏈表來接收一些從數(shù)據(jù)中取出來的數(shù)據(jù)進(jìn)行處理。
即使你不知道鏈表的底層實現(xiàn)，仍然可以成功的運用STL里面的現(xiàn)成的東西。但是作為一個學(xué)習(xí)者，我覺得會使用和從底層掌握仍然是兩個不同的概念，linux之父說：“talk is less，show you code”。
以下的程序，用鏈表模擬了一個電話通訊錄的功能，包括添加聯(lián)系人，查找聯(lián)系人，以及刪除聯(lián)系人。
PS：關(guān)于魯棒性，程序中最大的危險是使用了gets這個函數(shù)，目前先保留使用gets，等待找到工作之后在做進(jìn)一步的程序完善。（尼瑪，讀書去。。。應(yīng)屆生，找個工作他媽咋這么難呢！?? 工作經(jīng)驗，工作經(jīng)驗，艸，那個大牛一出校門就什么都會。）
/**************************************************************************
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
#include
#include
#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 ");
printf(" ******* 1 add a person ******* ");
printf(" ******* 2 show the phone list ******* ");
printf(" ******* 3 find from phone list ******* ");
printf(" ******* 4 from phone list ******* ");
printf("Please input the cmd number: ");
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! ");
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é)點
Input: 要輸入的電話列表list,姓名name
Return: 返回查找到的節(jié)點
*/
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é)點
Return: 添加成功返回1，添加失敗返回0
*/
int AddPersonByName(PList list,List node)
{
if(node==NULL)
{
printf("the node is NULL! ");
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! ");
}
else
{
printf("please input the name: ");
gets(name);
printf("please input the number: ");
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! ");
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: ");
while(show!=NULL)
{
printf("Name:%s Number:%s ",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: ");
gets(name);
Position node=FindPersonByName(list,name);
if(node!=NULL)
printf("find success! name-> %s number-> %s ",node->name,node->number);
else
printf("find failed! ");
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 ");
return ;
}
char name[N];
printf("please input the name: ");
gets(name);
DeletePersonByName(list,name);
}
【c語言鏈表的用法有哪些】相關(guān)文章：
C語言assert的用法有哪些07-17
c語言if語句的用法有哪些08-23
C語言中sscanf的用法有哪些09-25
c語言中indexof用法有哪些06-27
C語言鏈表逆序方法技巧08-21
鏈表的C語言實現(xiàn)方法08-27
C語言的循環(huán)鏈表和約瑟夫環(huán)09-29
C語言的缺點有哪些09-16
C語言的特點有哪些09-10
C語言的應(yīng)用有哪些08-05