- 相干保举
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这个直达关键。（实在，这类做法在指针中很是遍及，大局部有前往指针范例的函数中，城市起首界说一个指针变量来保管函数的传入的参数，而不是对参数间接停止操纵）。
?
/*
函数功效：建立一个链表
函数描写：每次输入一个新的整数，即把新增添一个节点寄存该整数，
当输入的整数为-1时，函数竣事。
*/
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，期待找到任务以后在做进一步的法式完美。（尼玛，念书去。。。应届生，找个任务他妈咋这么难呢！?? 任务经历，任务经历，艹，阿谁大牛一出校门就甚么城市。）
?
/**************************************************************************
Programe:
This is a phone list write by list
The programe is just prictise for list
Author: heat nan
Mail:[email protected]
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:判定要增加的接洽人称号是不是已存在于德律风簿中.
Input: List 德律风列表,name 要增加的接洽人的姓名.
Return: 已存在前往1,不存在前往0.
*/
int JudgeNameExist(List list,char* name)
{
if(FindPersonByName(list,name)!=NULL)
return 1;
else
return 0;
}
/*
Function:按照输入的姓名查找接洽人的信息节点
Input: 要输入的德律风列表list,姓名name
Return: 前往查找到的节点
*/
List FindPersonByName(List list,char* name)
{
while(list!=NULL)
{
if(strcmp(list->name,name)==0)
break;
list=list->next;
}
return list;
}
/*
Function:按照姓名增加新的接洽人到接洽人列表
Input: 指向接洽人列表地点的指针， 新用户节点
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: 打印接洽人列表
Input： 接洽人列表
*/
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:按照姓名删除接洽人
Input： 指向接洽人地点的指针，接洽人姓名
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说话链表的用法】相干文章：
C说话链表逆序方式技能08-21
链表的C说话完成方式08-27
C说话的轮回链表和约瑟夫环09-29
C说话assert用法06-24
C说话#include用法10-17
C说话#define的用法08-19
c说话if语句的用法07-23
assert用法（C说话）05-30
C说话assert的用法10-29
链表的C说话完成方式编程进修06-12