链表是数据结构中比较基础也是比较重要的类型之一,那么有了数组,为什么我们还需要链表呢!或者说设计链表这种数据结构的初衷在哪里?下面小编就为大家介绍下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=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: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:判断要添加的联系人名称是否已经存在于电话簿中.

  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);

  }

1.《c语言链表 c语言链表的用法有哪些》援引自互联网,旨在传递更多网络信息知识,仅代表作者本人观点,与本网站无关,侵删请联系页脚下方联系方式。

2.《c语言链表 c语言链表的用法有哪些》仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证。

3.文章转载时请保留本站内容来源地址,https://www.lu-xu.com/jiaoyu/76997.html