c語言連結清單的用法
連結清單是資料結構中比較基礎也是比較重要的類型之一，那麼有了數組，為什麼我們還需要連結清單呢！或者說設計連結清單這種資料結構的初衷在哪裡？下面小編就為大家介紹下c語言連結清單的用法。
c語言枚舉的用法如下：
這是因為，在我們使用數組的時候，需要預先設定目标群體的個數，也即數組容量的大小，然而實時情況下我們目标的個數我們是不确定的，是以我們總是要把數組的容量設定的很大，這樣以來就浪費了很多的空間。另外，數組在進行插入操作和删除操作的時候，在插入或者删除制定元素之後，我們往往需要進行循環移位，這增加了我們的線性開銷。
正是由于以上的兩種主要原因，連結清單被設計出來用于一般表的操作。為了避免上面描述數組的兩種弊端，我們希望連結清單有一下的特點
1 可以靈活的擴充自己的長度。
2 存儲位址不連續，删除或者插入操作的時候不需要循環移位。
要實作以上兩個特點，我們需既要保證每個節點的獨立性，又要儲存相鄰兩個節點的聯系。
為此，連結清單一般被設計為下面的形式。
Node--->Node---->Node
連結清單是由一個一個的節點組成的，可以友善和自由的插入未知個Node，前一個節點中用指針儲存着下一個節點的位置，這樣以來便順利的完成了我們對連結清單的兩點期望，但是唯一的缺點是增加了額外的空間消耗。
————————————————————————————————————————————————————————————————————————————
連結清單的定義：
連結清單的定義一般使用結構體，在看《資料結構與算法分析》這本書的時候發現，書中頻繁的使用typedef的關鍵字，結果真的很棒不僅保持的代碼的整潔程度，也讓我們在下面的編碼過程中少見了很多煩人的指針(當然指針還是一直存在的)。是以這裡也借用了書中的定義方法。
struct Node;
typedef struct Node* PtrNode;
typedef PtrNode Position;
typedef PtrNode List;
struct Node{
int Value;
PtrNode Next;
};
下面接着書寫一個建立連結清單的函數，輸入每個節點的值，直到這個值是-1的時候函數結束。
在這個裡面，我以前一直搞不明白為什麼需要定義三個Node *，現在終于了解了，最終還是複習了指針的内容明白的，這裡說一下指針實作連結清單對指針的操作很頻繁，需要比較紮實的掌握了指針之後，在來看連結清單會輕松很多。在下面的一段程式裡，我分别定義了head/p/tmp這三個指向節點結構體的指針，head的主要作用就像一個傳銷頭目，他會主動聯系上一個下線p，然後他就什麼也不幹了，p接着去發展一個又一個的下線tmp，結果一串以head為首的連結清單就出來了。
起先，我總覺得有了head，為什麼還要p，這是因為如果直接使用head去指向下一個節點，head的.位置也是不斷在移動的，即它永遠處于連結清單的尾端，這樣當我們傳回連結清單的時候，其實是空值。是以，我們需要p這個中轉環節。(其實，這種做法在指針中非常普遍，大部分有傳回指針類型的函數中，都會首先定義一個指針變量來儲存函數的傳入的參數，而不是對參數直接進行操作)。
?
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函數free掉的隻是申請的空間，但是指針還是依然存在的。
tmp=NULL;
return head;
}
接下來，在寫一個删除連結清單節點的函數，輸入一個整數然後周遊連結清單節點，當連結清單節點的值與該整數相等的時候，即把該節點删除。
在完成這個函數首先一定要把這個過程思考清楚，不可否認我之前是一個上來就敲代碼的人，看了《劍指offer》感覺這種習慣是程式員的大忌，甚至還想寫一篇部落格，名字都想好了《程式員的自我修養之思考在前，代碼在後》。其實想想也是，我們寫程式的目的是為了解決問題，而不是為了簡單的寫程式，純粹的讓程式跑起來大概隻會在上學那會存在吧！真實的程式開發中需要考慮幾乎所有 能想到的實際問題，是以無論程式再下，一要學會先思考清楚，再下筆寫程式。
關于這個函數,我們要想到的是：
1 如果連結清單為空，我們該怎麼做，當然是直接傳回。
2 如果要删除的元素為頭節點該怎麼辦？
3 如果要删除的元素為尾節點該怎麼辦？
當注意到以上三個部分，我們的程式就可能避免掉了輸傳入連結表為空，程式直接崩潰的現象，也可以避免删除元素值為頭節點時删不掉的尴尬。我們的程式就有了一定的魯棒性。
下面着重考慮連結清單的删除的實作：
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)
假設我們要删除的節點為上圖的Node_c;假設我們能夠找到Node_c的前一個位置tmp和被删除節點位置p的話;這個時候我們隻需要執行tmp->Next=p->Next即可。
隻要完成上面的分析以及考慮到各種情況，我們完成下面的代碼就水到渠成了。
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;
}
?關于連結清單的使用場景分析:
連結清單在程式開發中用到的頻率還是非常高的，是以在進階語言中往往會對連結清單進行一些實作，比如STL中list以及Java中也有類似的東西。在目前的伺服器端開發，主要運用連結清單來接收一些從資料中取出來的資料進行處理。
即使你不知道連結清單的底層實作，仍然可以成功的運用STL裡面的現成的東西。但是作為一個學習者，我覺得會使用和從底層掌握仍然是兩個不同的概念，linux之父說：“talk is less，show you code”。
以下的程式，用連結清單模拟了一個電話通訊錄的功能，包括添加聯系人，查找聯系人，以及删除聯系人。
PS：關于魯棒性，程式中最大的危險是使用了gets這個函數，目前先保留使用gets，等待找到工作之後在做進一步的程式完善。(尼瑪，讀書去。。。應屆生，找個工作他媽咋這麼難呢！?? 工作經驗，工作經驗，艹，那個大牛一出校門就什麼都會。)
?
#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;
}
int JudgeNameExist(List list,char* name)
{
if(FindPersonByName(list,name)!=NULL)
return 1;
else
return 0;
}
List FindPersonByName(List list,char* name)
{
while(list!=NULL)
{
if(strcmp(list->name,name)==0)
break;
list=list->next;
}
return list;
}
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);
}
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;
}
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語言連結清單的用法】相關文章：