首页 > 数据库开发 > 链表建立、删除、插入基本操作

链表建立、删除、插入基本操作

在数据结构中,链表无疑是最基本的,也是在大多数IT公司面试笔试中考察最多的;有了扎实的处理链表的基础,对以后学习更复杂的数据结构类型是很有帮助也是很有必要的;因此在闲暇时间中,又再一次重写了对于链表的一些基本操作,也参考了一些资料,在此将代码分享一下,希望对初学者有所帮助。

 

一开始的时候,对于链表的建立,都会这样来写,基本上都会用到两次malloc函数的调用。代码大致上如下所示。

 

[cpp][/cpp] view plaincopyprint?

  1. //创建长度为n的单链表
  2. node *create(int n)
  3. {
  4.     node *head,*precious,*current;
  5.     int cnt;
  6.     int label = 1;
  7.     for(cnt = 0;cnt < n;cnt++)
  8.     {
  9.         if(label == 1)
  10.         {
  11.             precious = (node *)malloc(sizeof(node));
  12.             printf("Input the information just like:name ID gender age \n");
  13.             scanf("%s%s%s%d",precious->name,precious->ID,precious->s,&precious->age);
  14.             precious->link = NULL;
  15.             head = precious;
  16.             label = 0;
  17.         }
  18.         else
  19.         {
  20.             current = (node*)malloc(sizeof(node));
  21.             printf("Input the information just like:name ID gender age \n");
  22.             scanf("%s%s%s%d",current->name,current->ID,current->s,¤t->age);
  23. //          current->link = NULL;
  24.             precious->link = current;
  25.             precious = current;
  26.         }
  27.     }
  28.     precious->link = NULL;
  29.     return head;
  30. }

 

 

后来看了一些资料,简化了很多,下面这种写法值得提倡:

 

[cpp][/cpp] view plaincopyprint?

  1. //建立链表
  2. node *CreatLink(int n)
  3. {
  4.     node *head,*p,*q;
  5.     for(int i=1; i<n+1; i++)
  6.     {
  7.         p = (node*)malloc(sizeof(node));
  8.         printf("input a number:");
  9.         scanf("%d",&p->data);
  10.         if(i == 1) head = p;
  11.         else q->next = p;
  12.         q = p;
  13.         p->next = NULL;
  14.     }
  15.     return head;
  16. }

 

 

然后要提到的就是插入和删除的操作了:有两点要注意:首先不论是插入还是删除第一要做的就是找到要操作的那个位置;其次要把操作的位置分三种情况,即头结点、中间结点、尾结点。

下面的代码参考了一些资料(如程序员面试宝典、谭浩强的书)

插入结点

 

[cpp][/cpp] view plaincopyprint?

  1. node *Insert(node *head,int num)
  2. {
  3.     node *p,*q,*s;
  4.     s = (node*)malloc(sizeof(node));
  5.     printf("input a number:");
  6.     scanf("%d",&s->data);
  7.     p = head;
  8.     //先寻找到相应位置再处理,假设数据已按升序排列
  9.     while(p->data < s->data && p->next != NULL)
  10.     {
  11.         q = p; p = p->next;
  12.     }
  13.     if(p == head) {head = s; p = s->next;}
  14.     else if(p->next == NULL) { p->next = s; s->next = NULL; }
  15.     else { q->next = s; s->next = p; }
  16.     return head;
  17. }

删除结点:(可以将尾结点和中间结点步骤合二为一)

 

 

[cpp][/cpp] view plaincopyprint?

  1. node *Delete(node *head,int num)
  2. {
  3.     node *p,*q;
  4.     p = head;
  5.     //先查找再删除
  6.     while(p->data != num && p->next != NULL)
  7.     {
  8.         q = p; p = p->next;
  9.     }
  10.     if(num == p->data)
  11.     {
  12.         if(p == head) { head = p->next; free(p); }
  13.         else { q->next = p->next; free(p); }
  14.     }
  15.     else
  16.         printf("%d could not been found",num);
  17.     return head;
  18. }

最后简单再介绍一下链表排序,链表排序,重点在排序,对指针的操作少;而排序用到的无非就是几种经典的排序算法,如冒泡、直接、选择等等。通过我个人的经历来看,排序对于面试笔试来说也是个重点,几乎都能被问到。

 

以下是一个用冒泡法写的一个链表排序

 

[cpp][/cpp] view plaincopyprint?

  1. node *Sort(node* head,int length)
  2. {
  3.     node *p;
  4.     for(int i = 1; i < length ; i++)
  5.     {
  6.         p = head;
  7.         for(int j = 0; j < length - i ; j++)
  8.         {
  9.             if(p->data > p->next->data)
  10.             {
  11.                 int tmp = p->data;
  12.                 p->data = p->next->data;
  13.                 p->next->data = tmp;
  14.             }
  15.             p = p->next;
  16.         }
  17.     }
  18.         return head;
  19. }

本文固定链接: http://www.devba.com/index.php/archives/2002.html | 开发吧

报歉!评论已关闭.