数据结构之链表

3010阅读　0评论2016-05-05　linux_player_c
分类：C/C++

链表的简介

数据结构是编程中对数据处理的一种常见的容器，它们的发明总是从简单到复杂的一个过程，在C语言的编程中我们首先接触了基本数据类型，包括定点数 （char、short、int、long）、浮点数（float、double）、指针类型。接着了解到了数组（相同数据类型的集合），结构体（不同数 据类型的集合）。再往后随着数据规模的增大以及数据之间的复杂关系，又开发出了链表、栈、队列、树（二叉树、字典树、B树等）、图等数结构，使我们对数据 的处理能力进一步加强，所以掌握好数据结构非常的重要，本次博客将会着重介绍相关数据结构的实现。首先让我们从最简单的链表开始数据结构之旅。


链表与数组

首先让我们来介绍下链表与数组之间的有缺点，关于数组我们有以下几种定义方式：


点击(此处)折叠或打开

  1. int array1[] = {12, 23, 34, 45, 56, 67, 78}; //方法1
  2. int array2[100] = {0}; //方法2

  4. int *array3 = NULL;

  6. array3 = (int *)malloc(sizeof(int) * 100); //方法3
  7. if(array3 != NULL){
  8.      fprintf(stderr, "the memory is full!\n");
  9.      exit(1);
  10. }

上述是我们定义数组的三种方式，他们对内存的占用位置是不同的，简单的叙述下:

array2和array3是我们的整型数组，它们存在于进程的栈上（后面会对内存的分布进行详细的介绍），而array3则和其他两个略有不 同，array3被定义为一个int类型的指针，也就是说array3存储的是一个地址，我们在malloc函数调用中其实是在堆内存中分配了 (4bytes * 100 = 400bytes)大小的空间，并且把该内存块的第一个字节的地址存在了array3中，这样相当于array3虽然在栈上，但是它所指向的空间是在堆上 存放的。

不管上述的数组是如何定义的，数组都会满足以下几个特点：

1.数组在物理上还是逻辑上都是连续存储的，其中的元素都是可以通过首地址加偏移量进行定位的。
2.使用数组对元素进行查找，时间复杂度非常低，在O（1）的时间复杂度可以完成查找。
3.使用数组进行插入和删除的时候就不那么乐观了，如果被删除或插入的元素在数组的末位，O（1）的时间复杂度也可以完成。但是绝大多数情况下插入和删除的元素都是在数组的中间进行，这样的话时间复杂度将会上升到O（n）。
4.最关键的一点，一旦数组定义完成后，其大小是不可以更改的。这样就要求使用者能够精确的估计数据规模，但现实环境中很可能会造成数组过大或过小而引发浪费和不足的窘境。

由此我们可以发现数组有着很多的不足，还好我们发明了更加灵活的数据结构，链表应该是其中的一个代表（尽管它也不是那么的完美），链表由相同结构的链表节点构成，关于它们是如何能够链接在一起的，我们需要去关注链表节点的结构：
这里写图片描述

我们可以看到链表节点主要分为两大部分:数据域和链域。数据域是我们最要存储的内容，而链域则代表着一种指针，这个指针指向类型为链表节点，这样每一个节点就可以记录下下一个节点的位置，从而把原本毫不相干的链表节点串接起来。

关于链表节点的结构体定义如下所示：


点击(此处)折叠或打开

  1. #define TRUE (1)
  2. #define FALSE (0)

  4. typedef unsigned char Boolean;

  6. typedef struct List_node
  7. {
  8.     int data; //数据域
  9.     struct List_node *next; //指针域
  10. }List_node;

  12. typedef List_node *List_head

为了方便链表操作的实现我们重定义了Boolean类型作为逻辑上的真或假。

链表的操作也是在.h文件中进行声明的，我们叫这样的声明为接口，如下是单链表的接口声明:


点击(此处)折叠或打开

  1. List_head init_list(void) ; //链表的初始化
  2. void destroy_list(List_head *head) ; //链表的删除
  3. Boolean push_front(List_head head, int value); //头部插入
  4. Boolean push_back(List_head head, int value) ; //尾部插入
  5. Boolean pop_front(List_head head) ; //头部删除
  6. Boolean pop_back(List_head head) ; //尾部删除
  7. Boolean delete_list_node(List_head head,
  8.                                   List_node *node) ; //删除某个指针的值
  9. Boolean find_value_node(List_head head,
  10.                           int value, List_node **node); //找到指定值的地址
  11. void show_list(List_head head) ; //显示链表信息
  12. void sort_list_ascend(List_head head) ; //链表的升序排序
  13. void sort_list_descend(List_head head) ; //链表的降序排序
  14. int list_length(List_head head) ; //链表的长度
设计完链表的接口，我们就需要全力以赴的实现这些接口，就好像我们在设计完产品的配料表和使用说明书之后就需要专心致志的设计具体的产品，所以关于链表接口的具体实现我们放在list.c中实现，如下所示：


点击(此处)折叠或打开

  1. List_head init_list(void) //链表的初始化
  2. {
  3.     List_head head = NULL;

  5.     head = buy_node();

  7.     return head;
  8. }

  10. void destroy_list(List_head *head) //链表的删除
  11. {
  12.      List_node *p = NULL;
  13.      List_node *q = NULL;

  15.      // List_node **
  16.      if(head == NULL || *head == NULL){
  17.         return ;
  18.      }

  20.      p = *head;
  21.      while(p != NULL){
  22.          q = p;
  23.          p = p->next;
  24.          free(q);
  25.      }
  26.      *head = NULL;
  27. }

  29. Boolean push_front(List_head head, int value) //头部插入
  30. {
  31.     List_node *node = NULL;

  33.     if(head == NULL){
  34.         return FALSE;
  35.     }

  37.     //购买节点并进行赋值
  38.     node = buy_node();
  39.     node->data = value;

  41.   // printf("adfadf");
  42.     //头部插入节点
  43.     // NULL->next;
  44.     node->next = head->next;
  45.     head->next = node;

  47.     return TRUE;
  48. }

  50. Boolean push_back(List_head head, int value) //尾部插入
  51. {
  52.     List_node *node = NULL;
  53.     List_node *p_node = NULL;

  55.     if(head == NULL){
  56.         return FALSE;
  57.     }

  59.     node = buy_node();
  60.     node->data = value;

  62.     p_node = head;
  63.     //1.找到末尾
  64.     while(p_node->next != NULL){
  65.         p_node = p_node->next;
  66.     }
  67.     //2.插入到末尾
  68.     p_node->next = node;

  70.     return TRUE;
  71. }

  73. Boolean pop_front(List_head head) //头部删除
  74. {
  75.     List_node *p_node = NULL;

  77.     if(head == NULL || head->next == NULL){
  78.         //链表为空或者没有有效节点，头部删除失败
  79.         return FALSE;
  80.     }

  82.     p_node = head->next;
  83.     head->next = head->next->next;
  84.     free(p_node);

  86.     return TRUE;
  87. }

  89. Boolean pop_back(List_head head) //尾部删除
  90. {
  91.     List_node *p_node = NULL;

  93.     if(head == NULL || head->next == NULL){
  94.         return FALSE;
  95.     }

  97.     p_node = head;
  98.     //找到最后一个节点并且删除
  99.     while(p_node->next->next != NULL){
  100.         p_node = p_node->next;
  101.     }
  102.     free(p_node->next);
  103.     p_node->next = NULL;
  104.     return TRUE;
  105. }


  108. //talk
  109. Boolean delete_list_node(List_head head,
  110.                                   List_node *node) //删除某个指针的值
  111. {
  112.     List_node *p_node = NULL;

  114.     if(head == NULL || head->next == NULL || node == NULL){
  115.         return FALSE;
  116.     }

  118.     p_node = head;

  120.     while(p_node->next != node){
  121.         p_node = p_node->next;
  122.         if(p_node == NULL){ //已经遍历完整个链表也没有找到指定的节点
  123.             break ;
  124.         }
  125.     }
  126.     if(p_node == NULL){ //没找到，返回删除失败
  127.         return FALSE;
  128.     }
  129.     //找到并且删除
  130.     p_node->next = node->next;
  131.     free(node);
  132.     return TRUE;
  133. }

  135. Boolean find_value_node(List_head head,
  136.                           int value, List_node **node) //找到指定值的地址
  137. {
  138.     List_node *p_node = NULL;

  140.     if(head == NULL || head->next == NULL || node == NULL){
  141.          return FALSE;
  142.     }

  144.     p_node = head->next;
  145.     while(p_node != NULL){
  146.         if(p_node->data == value){
  147.             *node = p_node;
  148.             return TRUE;
  149.         }
  150.         p_node = p_node->next;
  151.     }

  153.     return FALSE;
  154. }

  156. void show_list(List_head head) //显示链表信息
  157. {
  158.     List_node *p_node = NULL;

  160.     if(head == NULL){
  161.         return ;
  162.     }

  164.     for(p_node = head->next; p_node != NULL; p_node = p_node->next){
  165.         printf("%d ", p_node->data);
  166.     }
  167.     printf("\n");
  168. }

  170. /*
  171.  * int i = 0;
  172.  * int j = 0;
  173.  *
  174.  * for(i = 0; i < length - 1; ++i){
  175.  *     for(j = i + 1; j < length; ++j){
  176.  *         if(array[i] > array[j]){
  177.  *             swap(&array[i], &array[j], sizeof(array[i]));
  178.  *         }
  179.  *     }
  180.  * }
  181.  *
  182.  * */

  184. #define POINTER_SIZE (sizeof(void *))

  186. #define data_size(p_node) (((char *)((p_node) + 1) - (POINTER_SIZE)) - ((char *)(p_node)))

  188. void sort_list_ascend(List_head head) //链表的升序排序
  189. {
  190.     List_node *p_node = NULL;
  191.     List_node *q_node = NULL;

  193.     //如果链表为空，没有元素或者只有一个元素，不进行排序操作
  194.     if(head == NULL || head->next == NULL
  195.     || head->next->next == NULL){
  196.         return ;
  197.     }

  199.     for(p_node = head->next; p_node != NULL; p_node = p_node->next){
  200.         for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
  201.             if(p_node->data > q_node->data){
  202.                 //只交换数据域
  203.                 swap(p_node, q_node, data_size(p_node));
  204.             }
  205.         }
  206.     }

  208. }
  209. void sort_list_descend(List_head head) ; //链表的降序排序

  211. int list_length(List_head head) //链表的长度
  212. {
  213.     List_node *p_node = NULL;
  214.     int length = 0;

  216.     if(head == NULL){
  217.         return length;
  218.     }
  219.     p_node = head->next;

  221.     while(p_node != NULL){
  222.         length++;
  223.         p_node = p_node->next;
  224.     }
  225.     return length;
  226. }

  228. static void swap(void *a, void *b, int length) //交换函数
  229. {
  230.     void *temp = Malloc(length);

  232.     memcpy(temp, a, length);
  233.     memcpy(a, b, length);
  234.     memcpy(b, temp, length);
  235.     free(temp);
  236. }

  238. static void *Malloc(size_t size) //内存申请
  239. {
  240.     void *result = malloc(size);
  241.     if(result == NULL){
  242.         fprintf(stderr, "the memory is full!\n");
  243.         exit(1);
  244.     }
  245.     return result;
  246. }



  250. static List_node *buy_node(void) //生成一个链表节点
  251. {
  252.     List_node *result = NULL;

  254.     result = (List_node *)Malloc(sizeof(List_node));
  255.     bzero(result, sizeof(List_node));
  256.     // int data;
  257.     // struct List_node *next;

  259.     return result;
  260. }
设计完链表的操作后我们需要对这个功能进行测试，测试代码如下所示：

点击(此处)折叠或打开

  1. int main(int argc, char **argv)
  2. {
  3.     List_head head = NULL;
  4.     int i = 0;

  6.     head = init_list(); //链表的初始化
  7.     for(i = 0; i < 10; ++i){
  8.         push_front(head, rand() % 100);
  9.     }

  11.    // push_back(head, 10);
  12.    // push_back(head, 20);
  13.    // push_back(head, 30);
  14.    // push_back(head, 40);
  15.    // push_back(head, 50);
  16.    // push_back(head, 60);

  18.     show_list(head);

  20.     pop_front(head);
  21.     pop_back(head);

  23.     show_list(head);
  24.    // List_node *find = NULL;

  26.    // Boolean ok = find_value_node(head, 30, &find);

  28.    // if(ok == TRUE){
  29.    // printf("the %d value found\n", find->data);
  30.    // }

  32.     sort_list_ascend(head);
  33.     show_list(head);

  35.     destroy_list(&head); //链表的销毁
  36.     return 0;
  37. }
上述就是我们关于链表的基本操作，虽然非常简单（确实它的功能十分单一，操作不是那么的完善，而且与数据域的类型息息相关），但是清晰的描述出一个链表应该具有的操作。在后续的章节中我们将会介绍更加实用的链表操作，敬请期待。









上一篇：在redhat下使用x11vnc进行桌面共享
下一篇：数据结构之链表面试题