链表是数据结构中比较基础也是比较重要的类型之一,那么有了数组,为什么我们还需要链表呢!或者说设计链表这种数据结构的初衷在哪里?下面小编就为大家介绍下c语言链表的用法。
链表的定义:
链表的定义一般使用结构体,在看《数据结构与算法分析》这本书的时候发现,书中频繁的使用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=mallocsizeofstruct Node;
iftmp==NULL
printf"tmp malloc failed!";
return NULL;
else
p=tmp;
printf"please input the first node's message!";
scanf"%d",&tmp->Value;
whiletmp->Value!=-1
n+=1;
ifn==1
head=p;
tmp->Next=NULL;
else
p->Next=tmp;
p=tmp;
tmp=mallocsizeofstruct Node;
printf"please input the %d node!",n+1;
scanf"%d",&tmp->Value;
p->Next=NULL;
freetmp; //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
????????????????????????????????????? freep
假设我们要删除的节点为上图的Node_c;假设我们能够找到Node_c的前一个位置tmp和被删除节点位置p的话;这个时候我们只需要执行tmp->Next=p->Next即可。
只要完成上面的分析以及考虑到各种情况,我们完成下面的代码就水到渠成了。
/*
函数功能:删除链表中指定值的节点(如果存在多个,只删除第一个)
本例中输入一个整数,删除链表节点值为这个整数的节点。
*/
List DeleteNodeList list
Position p,tmp;
int value;
iflist==NULL
printf"The list is null,function return!";
return NULL;
else
printf"please input the Node's value:";
scanf"%d",&value;
p=list;
ifp->Value==value
list=p->Next;
freep;
p=NULL;
return list;
whilep!=NULL&&p->Value!=value
tmp=p;
p=p->Next;
ifp->Value==value
ifp->Next!=NULL
tmp->Next=p->Next;
else
tmp->Next=NULL;
freep;
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: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 JudgeNameExistList list,char* name;
void AddPersonPList list;
void PrintListList list;
List FindPersonList list;
List FindPersonByNameList list,char* name;
int AddPersonByNamePList list,List node;
int DeletePersonByNamePList list,char* name;
void DeletePersonPList list;
int main
List list=NULL;
Position p;
char cmd[100];
while1
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:";
getscmd;
switchcmd[0]
case '1':
AddPerson&list;
break;
case '2':
PrintListlist;
break;
case '3':
FindPersonlist;
break;
case '4':
DeletePerson&list;
break;
default:
printf"wrong cmd!";
break;
return 0;
/*
Function:判断要添加的联系人名称是否已经存在于电话簿中.
Input: List 电话列表,name 要添加的联系人的姓名.
Return: 已经存在返回1,不存在返回0.
*/
int JudgeNameExistList list,char* name
ifFindPersonByNamelist,name!=NULL
return 1;
else
return 0;
/*
Function:根据输入的姓名查找联系人的信息节点
Input: 要输入的电话列表list,姓名name
Return: 返回查找到的节点
*/
List FindPersonByNameList list,char* name
whilelist!=NULL
ifstrcmplist->name,name==0
break;
list=list->next;
return list;
/*
Function:根据姓名添加新的联系人到联系人列表
Input: 指向联系人列表地址的指针, 新用户节点
Return: 添加成功返回1,添加失败返回0
*/
int AddPersonByNamePList list,List node
ifnode==NULL
printf"the node is NULL!";
return 0;
if*list==NULL
*list=node;
return 1;
List pHead=*list;
whilepHead->next!=NULL
pHead=pHead->next;
pHead->next=node;
return 1;
void AddPersonPList list
Position tmp;
Position p_head;
tmp=struct node*mallocsizeofstruct node;
char name[N];
char number[M];
iftmp==NULL
printf"malloc the tmp node failed in function add person!";
else
printf"please input the name:";
getsname;
printf"please input the number:";
getsnumber;
strcpytmp->name,name;
strcpytmp->number,number;
tmp->next=NULL;
ifJudgeNameExist*list,name==1
freetmp;
printf"the name have already exist!";
return;
AddPersonByNamelist,tmp;
/*
Function: 打印联系人列表
Input: 联系人列表
*/
void PrintListList list
Position show;
show=list;
ifshow==NULL
return ;
printf"Now,we print the phone list:";
whileshow!=NULL
printf"Name:%s Number:%s",show->name,show->number;
show=show->next;
List FindPersonList list
char name[N];
Position pHead=list;
printf"please input the name you will find:";
getsname;
Position node=FindPersonByNamelist,name;
ifnode!=NULL
printf"find success! name-> %s number-> %s",node->name,node->number;
else
printf"find failed!";
return node;
/*
Function:根据姓名删除联系人
Input: 指向联系人地址的指针,联系人姓名
Output: 删除成功返回1,失败返回0
*/
int DeletePersonByNamePList list,char* name
if*list==NULL||name==NULL
return 0;
List pHead=*list;
ifstrcmppHead->name,name==0
*list=pHead->next;
freepHead;
pHead->next==NULL;
return 0;
List tmp=pHead->next;
whiletmp!=NULL
ifstrcmptmp->name,name==0
pHead->next=tmp->next;
freetmp;
tmp->next=NULL;
return 1;
pHead=tmp;
tmp=tmp->next;
return 0;
void DeletePersonPList list
List pHead=*list;
ifpHead==NULL
printf"there is no person you can delet";
return ;
char name[N];
printf"please input the name:";
getsname;
DeletePersonByNamelist,name;