学习啦 > 学习英语 > 专业英语 > 计算机英语 > c语言链表的用法

c语言链表的用法

时间: 长思709 分享

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!\n");
  return NULL;
  }
  else
  {
  p=tmp;
  printf("please input the first node's message!\n");
  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",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!\n");
  return NULL;
  }
  else
  {
  printf("please input the delete Node's value:\n");
  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<stdio.h>
  #include<string.h>
  #include<stdlib.h>
  #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                 \n");
  printf("       ******* 1 add a person        *******\n");
  printf("       ******* 2 show the phone list *******\n");
  printf("       ******* 3 find  from phone list *******\n");
  printf("       ******* 4 delete from phone list *******\n\n\n");
  printf("Please input the cmd number:\n");
  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!\n");
  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!\n");
  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!\n");
  }
  else
  {
  printf("please input the name:\n");
  gets(name);
  printf("please input the number:\n");
  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!\n");
  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:\n");
  while(show!=NULL)
  {
  printf("Name:%s  Number:%s\n",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:\n");
  gets(name);
  Position node=FindPersonByName(list,name);
  if(node!=NULL)
  printf("find success! name-> %s number-> %s\n",node->name,node->number);
  else
  printf("find failed!\n");
  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\n");
  return ;
  }
  char name[N];
  printf("please input the name:\n");
  gets(name);
  DeletePersonByName(list,name);
  }
515221