Chinaunix首页 | 论坛 | 博客
  • 博客访问: 575701
  • 博文数量: 108
  • 博客积分: 46
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文(108)

文章存档

2014年(13)

2013年(90)

2012年(6)

分类: LINUX

2013-04-07 15:20:28

原文地址:哈希链表的基本操作 作者:zooyo


  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define HASHSIZE 5

  4. typedef struct __Node {
  5.     int val;
  6.     struct __Node *next;
  7. }Node;

  8. int hash(int value) {
  9.     return value % HASHSIZE;
  10. }

  11. void Init_hash(Node **chain) {
  12.     int i;
  13.     for(i=0; i<HASHSIZE; i++) {
  14.         chain[i] = NULL;//初始化每个槽位
  15.     }
  16. }

  17. int Traverse(Node *slot, int value) {
  18.     Node *pNode = slot;
  19.     while(pNode != NULL) {
  20.         if(pNode->val == value) return -1;
  21.         pNode = pNode->next;
  22.     }
  23.     return 0;
  24. }

  25. int Insert(Node **chain) {
  26.     int value, key;
  27.     Node *newNode;
  28.     printf("Please input the value you want to insert: ");
  29.     scanf("%d", &value);

  30.     key = hash(value);
  31.     // 遍历链表避免插入相同的值
  32.     if(Traverse(chain[key], value) == 0) {
  33.         // 申请新节点内存
  34.         if ((newNode = (Node *)malloc(sizeof(Node)))
  35.             != NULL) {
  36.             newNode->val = value;
  37.             // 把新节点插入原第一个节点之前
  38.             newNode->next = chain[key];
  39.             chain[key] = newNode;
  40.             return 0;
  41.         }
  42.     } else {
  43.         printf("the value already existsn");
  44.         return -1;
  45.     }
  46. }

  47. int Delete(Node **chain) {
  48.     int value, key, i = 1;
  49.     Node *pCur, *pPrev;
  50.     printf("Please input the value you want to delete: ");
  51.     scanf("%d", &value);
  52.  
  53.     key = hash(value);
  54.     pPrev = chain[key];
  55.     pCur = pPrev;
  56.     while(pCur != NULL) {
  57.         if(pCur->val == value) {
  58.             if(i == 1) //如果匹配删除的值是第一个节点,
  59.                 chain[key] = pCur->next;
  60.             //把上一个节点直接指向当前节点的下一个节点
  61.             pPrev->next = pCur->next;
  62.             free(pCur);
  63.             return 0;
  64.         }
  65.         //如果没查找到value, 操作下一个节点.
  66.         pPrev = pCur;
  67.         pCur = pCur->next;
  68.         i++;
  69.     }
  70.     printf("Can't find the value!n");
  71.     return -1;
  72. }

  73. void Search(Node **chain) {
  74.     int value, key, flag = 0, i = 1;
  75.     Node *pNode;
  76.     printf("Please input the value you want to search: ");
  77.     scanf("%d", &value);

  78.     key = hash(value);
  79.     pNode = chain[key];

  80.     while(pNode != NULL) {
  81.         if(pNode->val == value) {
  82.             printf("Hit, the value in %d chain %d noden", key, i);
  83.             flag = 1;
  84.             break;
  85.         }
  86.         pNode = pNode->next;
  87.         i++; //计数第几个节点
  88.     }
  89.     if(!flag)    printf("Miss, the value has not been foundn");
  90.     printf("n");
  91. }

  92. void Destroy(Node **chain) {
  93.     int i;
  94.     Node *pCur, *pNext;
  95.     for(i=0; i<HASHSIZE; i++) {
  96.         if(chain[i] != NULL) {
  97.             pCur = chain[i];
  98.             do { //保存下个节点的指针
  99.                 pNext = pCur->next;
  100.                 //printf("Destroy val = %dn", pCur->val);
  101.                 free(pCur); // 释放当前节点内存
  102.                 pCur = pNext; //操作下一个节点
  103.             } while(pCur != NULL);
  104.             chain[i] = pCur;
  105.         }
  106.     }
  107. }

  108. void Invert(Node **chain) {
  109.     int i;
  110.     Node *pCur, *pPrev, *pNext;
  111.     for(i=0; i<HASHSIZE; i++) {
  112.         if(chain[i] != NULL) {
  113.             pPrev = chain[i]; //指向第一个节点
  114.             pCur = pPrev->next; //指向第二个节点
  115.             while(pCur != NULL) {
  116.                 pNext = pCur->next; //指向第三个节点
  117.                 pCur->next = pPrev; //让第中间节点指向前面一个节点
  118.                 pPrev = pCur; //上一个节点的指针指向当前节点
  119.                 pCur = pNext; //指向当前节点的指针指向下一个节点
  120.             }
  121.         /*
  122.         让指针反向后第一个节点成为最后一个节点,
  123.         所以把原第一个节点的指针域设置为NULL,
  124.         最后一个节点成为了第一个节点, 把它的地址存入哈希表中.
  125.         */
  126.             chain[i]->next = NULL;
  127.             chain[i] = pPrev;
  128.         }
  129.     }
  130. }

  131. void Print_hash(Node **chain) {
  132.     int i;
  133.     Node *pNode;
  134.     printf("n");
  135.     for(i=0; i<HASHSIZE; i++) {
  136.         printf("%d:", i);
  137.         pNode = chain[i];
  138.         while(pNode != NULL) {
  139.             printf("-->%d", pNode->val);
  140.             pNode = pNode->next;
  141.         }
  142.         printf("n");
  143.     }
  144.     printf("n");
  145. }

  146. int main(void) {
  147.     Node *chain[HASHSIZE];
  148.     Init_hash(chain);
  149.     int value = 1;
  150.     while (value) {
  151.         printf("[1]:Insert ");
  152.         printf("[2]:Delete ");
  153.         printf("[3]:Search ");
  154.         printf("[4]:Destroy ");
  155.         printf("[5]:Invert ");
  156.         printf("[0]:Exit ");
  157.         scanf("%d", &value);
  158.         switch (value) {
  159.             case 0:
  160.                 return 0;
  161.             case 1:
  162.                 Insert(chain);
  163.                 break;
  164.             case 2:
  165.                 Delete(chain);
  166.                 break;
  167.             case 3:
  168.                 Search(chain);
  169.                 continue;
  170.             case 4:
  171.                 Destroy(chain);
  172.                 break;
  173.             case 5:
  174.                 Invert(chain);
  175.                 break;
  176.             default:
  177.                 break;
  178.         }
  179.         Print_hash(chain);
  180.     }

  181.     return 0;
  182. }

阅读(576) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~