Chinaunix首页 | 论坛 | 博客
  • 博客访问: 130806
  • 博文数量: 52
  • 博客积分: 85
  • 博客等级: 民兵
  • 技术积分: 250
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-28 09:25
文章分类
文章存档

2013年(4)

2012年(48)

分类:

2012-03-12 13:21:43

原文地址:单链表操作 作者:Mrt-l

 
该例程包含了单链表的声明,创建,顺序插入,反序排列,
查找节点,删除节点的功能,并在 main 函数中一一得到了验证。
  1. /*
  2.  * 实现链表的存储需要下列机制
  3.  * 1、一种定义节点结构点机制,节点结构含有所有的域。
  4.  * 2、一种在需要时创建节点的方法,可由 malloc 函数完成。
  5.  * 3、一种删除不再需要节点的方法,可由 free 函数完成。
  6.  *
  7.  * 该例程包含了单链表的声明,创建,顺序插入,反序排列,查找节点,删除节点的功能,
  8.  * 并在 main 函数中一一得到了验证。
  9.  */

  10. #include<stdlib.h>
  11. #include<stdio.h>
  12. #include<assert.h>

  13. #define FALSE 0
  14. #define TRUE 1
  15. #define IS_FULL(ptr) ((!ptr))

  16. /* Node 为类型名,NODE 为标签名 */

  17. typedef struct NODE {    
  18.     int value;
  19.     struct NODE *link;    
  20. }Node;

  21. /* 创建一个单向节点 */
  22. struct NODE *creat1()
  23. {
  24.     Node *first;
  25.     first = (Node *)malloc(sizeof(Node));
  26.     first->link = NULL;
  27.     first->value = 5;
  28.     return first;    
  29. }

  30. /*
  31.  * 总是在单链表起始端插入一个新值。
  32.  */

  33. int sll_insert1(Node **rootp, int new_value)
  34. {
  35.     Node *current, *new;
  36.     current = *rootp;

  37.     new = (Node *)malloc(sizeof(Node));
  38.     if (new == NULL)
  39.         return FALSE;        
  40.     
  41.     new->link = current;
  42.     *rootp = new;

  43.     return TRUE;
  44. }

  45. /*
  46.  * 总是在单链表末尾插入一个新值。
  47.  */

  48. int sll_insert4(Node **rootp, int new_value)
  49. {
  50.     Node *previous, *current, *new;
  51.     previous = NULL;
  52.     current = *rootp;

  53.     while (current != NULL) {
  54.         previous = current;
  55.         current = current->link;        
  56.     }         

  57.     new = (Node *)malloc(sizeof(Node));
  58.     if (new == NULL)
  59.         return FALSE;        
  60.     
  61.     new->link = current;
  62.     previous->link = new;
  63. }
  64. /*
  65.  * 插入到一个有序的单链表,按从小到大顺序。
  66.  * 第一个参数是一个指向链表根指针的指针,第二个参数是需要插入的新值。
  67.  * 起始位置、中间位置、末尾均可插入值。
  68.  */

  69. int sll_insert2(Node **rootp, int new_value)
  70. {
  71.     Node *previous, *current, *new;
  72.     previous = NULL;
  73.     current = *rootp;/* 获取第一个节点的指针 */

  74.     while (current != NULL && current->value < new_value) {
  75.         previous = current;
  76.         current = current->link;        
  77.     }

  78.     new = (Node*)malloc(sizeof(Node));
  79.     if (new == NULL) {
  80.         return FALSE;
  81.     }
  82.     new->value = new_value;

  83.     new->link = current;
  84.     if (previous == NULL) {/* 插入到起始位置 */        
  85.         *rootp = new;
  86.     }
  87.     else {/* 中间位置或者末尾 */
  88.         previous->link = new;
  89.     }

  90.     return TRUE;
  91. }

  92. /*
  93.  * 插入到一个有序的单链表。
  94.  * 第一个参数是一个指向链表第一个节点link字段的指针,第二个参数是需要插入的新值。
  95.  * 起始位置、中间位置、末尾均可插入值。
  96.  * 要理解好指向当前节点的指针和指向当前节点 link 字段的指针,一个指向的是节点,另一个
  97.  * 指向的是节点里面的值。
  98.  */

  99. int sll_insert3(register Node **linkp, int new_value)
  100. {
  101.     register Node *current, *new;

  102.     current = *linkp;
  103.     while (current != NULL && current->value < new_value) {
  104.         linkp = &current->link;
  105.         current = *linkp;    
  106.     }
  107.     
  108.     /*while ((current = *linkp) != NULL && current->value < new_value) {
  109.         linkp = &current->link;
  110.     }*/

  111.     new = (Node*)malloc(sizeof(Node));
  112.     if (new == NULL) {
  113.         return FALSE;
  114.     }
  115.     new->value = new_value;

  116.     new->link = current;
  117.     *linkp = new;

  118.     return TRUE;
  119. }

  120. /*
  121.  * 计算一个单链表的节点数
  122.  */

  123. int count_node(Node *root)
  124. {    
  125.     int count;

  126.     for (count = 0; root != NULL; root = root->link)
  127.         count += 1;    
  128.         
  129.     return count;    
  130. }

  131. /* 在一个无序单链表中寻找一个特定的值 */
  132. struct NODE *find_value(Node *root, int value)
  133. {    
  134.     while (root != NULL) {
  135.         if (root->value == value)
  136.             return root;

  137.         root = root->link;     
  138.     }

  139.     return NULL;
  140. }

  141. /*
  142.  * 反序排列一个单链表的所有节点。当链表重排之后,返回一个指向新链表的头节点的指针。
  143.  * 不使用额外的内存。
  144.  */

  145. struct NODE *sin_reverse(Node *current)
  146. {
  147.     Node *previous = NULL, *next;    

  148.     /*for (previous = NULL; current != NULL; current = next) {
  149.         next = current->link;
  150.         current->link = previous;
  151.         previous = current;    
  152.     }*/

  153.     /* 三个指针的位置为:previous,current,next */

  154.     while (current != NULL) {
  155.         next = current->link; //保存下一节点指针
  156.         current->link = previous; //将节点的箭头反向
  157.         previous = current; //一个节点的箭头反向后previous向后移动一步
  158.         current = next;     //一个节点的箭头反向后current    向后移动一步
  159.     }

  160.     return previous;
  161. }

  162. /*
  163.  * 从单链表中移除一个节点。
  164.  */

  165. int sin_remove(Node **linkp, Node *delete)
  166. {
  167.     register Node *current;
  168.     current = *linkp;

  169.     assert(delete != NULL);

  170.     while (current != NULL && current != delete) {
  171.         linkp = &current->link;
  172.         current = *linkp;
  173.     }    
  174.     
  175.     if (current == delete) {
  176.         *linkp = current->link; //指向delete后面的节点
  177.         free(current);
  178.         return TRUE;    
  179.     }
  180.     else    return FALSE;
  181. }

  182. int main()
  183. {    
  184.     Node *root, *ptr;
  185.     int count;    

  186.     //test the function sll_insert1
  187.     /*root = creat1();//5
  188.     sll_insert2(&root, 3);
  189.     sll_insert2(&root, 4);        
  190.     printf("the sin_link contains :");
  191.     for (ptr = root; ptr != NULL; ptr = ptr->link) {
  192.             printf("%4d", ptr->value);
  193.     }        
  194.     printf("\n");

  195.     //test the function sll_insert4
  196.     root = creat1();//5
  197.     sll_insert2(&root, 6);
  198.     sll_insert2(&root, 7);        
  199.     printf("the sin_link contains :");
  200.     for (ptr = root; ptr != NULL; ptr = ptr->link) {
  201.             printf("%4d", ptr->value);
  202.     }        
  203.     printf("\n");

  204.     //test the function sll_insert2
  205.     root = creat1();//5
  206.     sll_insert2(&root, 3);
  207.     sll_insert2(&root, 6);
  208.     sll_insert2(&root, 10);    
  209.     printf("the sin_link contains :");
  210.     for (ptr = root; ptr != NULL; ptr = ptr->link) {
  211.             printf("%4d", ptr->value);
  212.     }    
  213.     printf("\n");*/

  214.     //test the function sll_insert3,find_value ,count_node,sin_reverse
  215.     root = creat1();//5
  216.     sll_insert3(&root, 3);
  217.     sll_insert3(&root, 6);
  218.     sll_insert3(&root, 10);

  219.     ptr = find_value(root, 10);
  220.     printf("find_value=%d \n", ptr->value);

  221.     count = count_node(root);
  222.     printf("count_node=%d \n", count);

  223.     ptr = sin_reverse(root);

  224.     printf("the sin_link contains :");
  225.     for (; ptr != NULL; ptr = ptr->link) {
  226.             printf("%4d", ptr->value);
  227.     }    
  228.     printf("\n");    

  229.     exit(0);
  230. }
阅读(754) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~