Chinaunix首页 | 论坛 | 博客

oops

首页　| 　博文目录　| 　关于我

王贤才

  • 博客访问： 1045493
  • 博文数量： 573
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 66
  • 用 户 组： 普通用户
  • 注册时间： 2016-06-28 16:21
文章分类

全部博文（573）

文章存档

2018年（3）

2016年（48）

2015年（522）

我的朋友
最近访客
推荐博文
相关博文
查找

分类： C/C++

2015-12-02 15:00:14


点击(此处)折叠或打开

  1. #include <string.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <math.h>

  6. #define EQ(a,b) (!strcmp((a),(b))) /*字符串a和b相等*/
  7. #define LT(a,b) (strcmp((a),(b)) < 0) /*字符串a小于字符串b*/
  8. #define LQ(a,b) (strcmp((a),(b)) <= 0) /*字符串a小于等于字符串b*/

  10. #define SZ_STRING 16

  12. typedef char STRING[SZ_STRING];

  14. /*顺序表中元素的类型*/
  15. typedef struct elemtype
  16. {
  17.     STRING key;
  18.     STRING value;
  19. }ELEMTYPE;

  21. /*静态查找表之顺序表：顺序存储结构(顺序表中元素的存放是无序的)*/
  22. typedef struct sunxutable
  23. {
  24.     ELEMTYPE * elem; /*数据元素的基址，0号单元留空*/
  25.     int length; /*表长度*/
  26. }SUNXUTABLE;

  28. typedef SUNXUTABLE * SunXuTablePtr;

  30. /*次优二叉树结点结构体*/
  31. typedef struct secondoptinaltreenode
  32. {
  33.     STRING key; /*结点键值*/
  34.     STRING value; /*结点值*/
  35.     int weight; /*结点权值*/
  36.     struct secondoptinaltreenode * leftchild; /*左孩子*/
  37.     struct secondoptinaltreenode * rightchild; /*右孩子*/
  38. }SECONDOPTINALTREENODE;

  40. typedef SECONDOPTINALTREENODE * SecOptTreeNodePtr;

  42. /*由次优二叉树结点元素组成的有序表*/
  43. typedef struct ordertable
  44. {
  45.     SecOptTreeNodePtr node; /*次优二叉树结点元素的基址，0号单元留空*/
  46.     int length; /*有序表的长度*/
  47. }ORDERTABLE;

  49. typedef ORDERTABLE * OrderTablePtr;

  51. int InitSxTable(SunXuTablePtr * sxtableptr);
  52. int DestroySunXuTable(SunXuTablePtr sxtableptr);
  53. int Search_Seq(SunXuTablePtr sxtableptr, STRING key);
  54. int Search_Bin(SunXuTablePtr sxtableptr, STRING key);
  55. int PrintSxTable(SunXuTablePtr sxtableptr);

  57. int InitOrderTable(OrderTablePtr * ordertableptr);
  58. int PrintOrderTable(OrderTablePtr ordertableptr, int * sw);
  59. int FindSW(OrderTablePtr ordertableptr, int sw[], int length);
  60. void CreateSecondOptimalTree(SecOptTreeNodePtr * secopttreenodeptr, OrderTablePtr ordertableptr, int * sw, int low, int high);
  61. void PrintSecondOptimalTreeNode1(SecOptTreeNodePtr secopttreenodeptr, int * sw);
  62. void PrintSecondOptimalTreeNode2(SecOptTreeNodePtr secopttreenodeptr, int * sw);
  63. void PrintSecondOptimalTreeNode3(SecOptTreeNodePtr secopttreenodeptr, int * sw);

  65. int main(int argc, char * * argv)
  66. {
  67.     freopen("chazhao.txt", "w", stdout);
  68.     printf("查找的各种算法！(顺序查找，折半查找，次优查找)\n");
  69.     
  70.     SunXuTablePtr sxtableptr = NULL;
  71.     InitSxTable(&sxtableptr); /*初始化顺序表*/
  72.     
  73.     printf("\n=======================================================\n\n");
  74.     printf("顺序查找：适用于表中数据无序的情况！\n");
  75.     printf("顺序表中所有数据如下：\n");
  76.     
  77.     PrintSxTable(sxtableptr);
  78.     
  79.     int search_index = -1;
  80.     char key[16];
  81.     memset(key, 0, sizeof(key));
  82.     strcpy(key, "C");
  83.     search_index = Search_Seq(sxtableptr, key);
  84.     printf("顺序查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
  85.     memset(key, 0, sizeof(key));
  86.     strcpy(key, "I");
  87.     search_index = Search_Seq(sxtableptr, key);
  88.     printf("顺序查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
  89.     memset(key, 0, sizeof(key));
  90.     strcpy(key, "M");
  91.     search_index = Search_Seq(sxtableptr, key);
  92.     printf("顺序查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
  93.     
  94.     printf("\n=======================================================\n\n");
  95.     printf("折半查找：适用于表中数据有序并且查找概率相等的情况！\n");
  96.     printf("有序表中所有数据如下：\n");
  97.     PrintSxTable(sxtableptr);
  98.     
  99.     memset(key, 0, sizeof(key));
  100.     strcpy(key, "D");
  101.     search_index = Search_Bin(sxtableptr, key);
  102.     printf("折半查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
  103.     memset(key, 0, sizeof(key));
  104.     strcpy(key, "I");
  105.     search_index = Search_Bin(sxtableptr, key);
  106.     printf("折半查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
  107.     memset(key, 0, sizeof(key));
  108.     strcpy(key, "N");
  109.     search_index = Search_Bin(sxtableptr, key);
  110.     printf("折半查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
  111.     
  112.     printf("\n=======================================================\n\n");
  113.     printf("次优查找树折半查找：适用于表中数据有序并且查找概率不相等的情况！\n");
  114.     
  115.     OrderTablePtr ordertableptr = NULL;
  116.     InitOrderTable(&ordertableptr); /*初始化有序表*/
  117.     
  118.     int sw[10]={0}; /*有序表中所有数据的累计权值和(0号留空，初值为0)*/
  119.     printf("求有序表中各个数据元素的累计权值和：\n");
  120.     FindSW(ordertableptr, sw, 10);
  121.     printf("为构造次优查找树，准备的有序表中所有数据如下：\n");
  122.     PrintOrderTable(ordertableptr, sw);
  123.     
  124.     SecOptTreeNodePtr secopttreenodeptr = NULL; /*次优查找树根结点*/
  125.     int low = 1; /*0号下标为空，所以从1开始*/
  126.     int high = ordertableptr->length; /*0号为空，9个元素的话，最高下标就是9*/
  127.     printf("创建次优查找树!\n");
  128.     CreateSecondOptimalTree(&secopttreenodeptr, ordertableptr, sw, 1, high);
  129.     
  130.     printf("\n按先序序列打印次优查找树：\n");
  131.     PrintSecondOptimalTreeNode1(secopttreenodeptr, sw);
  132.     printf("\n按中序序列打印次优查找树：\n");
  133.     PrintSecondOptimalTreeNode2(secopttreenodeptr, sw);
  134.     printf("\n按后序序列打印次优查找树：\n");
  135.     PrintSecondOptimalTreeNode3(secopttreenodeptr, sw);

  137.     DestroySunXuTable(sxtableptr);
  138.     /*监视哨在最高下标处的算法*/
  139. }

  141. /*功能：按照有序表中各个元素的weight域，求累计权值和，保存在sw中*/
  142. int FindSW(OrderTablePtr ordertableptr, int * sw, int length)
  143. {
  144.     int i = -1;
  145.     int j = -1;
  146.     /*求累计权值和！*/
  147.     for(i=0; i<length; i++)
  148.     {
  149.         for(j=0; j<=i; j++)
  150.         {
  151.             sw[i] += ordertableptr->node[j].weight;
  152.         }
  153.     }
  154. }

  156. /*功能：打印出整颗二叉树(按照先序遍历序列)*/
  157. void PrintSecondOptimalTreeNode1(SecOptTreeNodePtr secopttreenodeptr, int * sw)
  158. {
  159.     if(secopttreenodeptr == NULL)
  160.     {
  161.         return;
  162.     }
  163.     printf("元素:key=[%s],value=[%s],weight=[%d]\n", secopttreenodeptr->key,secopttreenodeptr->value, secopttreenodeptr->weight);
  164.     PrintSecondOptimalTreeNode1(secopttreenodeptr->leftchild, sw);
  165.     PrintSecondOptimalTreeNode1(secopttreenodeptr->rightchild, sw);
  166. }

  168. /*功能：打印出整颗二叉树(按照中序遍历序列)*/
  169. void PrintSecondOptimalTreeNode2(SecOptTreeNodePtr secopttreenodeptr, int * sw)
  170. {
  171.     if(secopttreenodeptr == NULL)
  172.     {
  173.         return;
  174.     }
  175.     PrintSecondOptimalTreeNode2(secopttreenodeptr->leftchild, sw);
  176.     printf("元素:key=[%s],value=[%s],weight=[%d]\n", secopttreenodeptr->key,secopttreenodeptr->value, secopttreenodeptr->weight);
  177.     PrintSecondOptimalTreeNode2(secopttreenodeptr->rightchild, sw);
  178. }

  180. /*功能：打印出整颗二叉树(按照后序遍历序列)*/
  181. void PrintSecondOptimalTreeNode3(SecOptTreeNodePtr secopttreenodeptr, int * sw)
  182. {
  183.     if(secopttreenodeptr == NULL)
  184.     {
  185.         return;
  186.     }
  187.     PrintSecondOptimalTreeNode3(secopttreenodeptr->leftchild, sw);
  188.     PrintSecondOptimalTreeNode3(secopttreenodeptr->rightchild, sw);
  189.     printf("元素:key=[%s],value=[%s],weight=[%d]\n", secopttreenodeptr->key,secopttreenodeptr->value, secopttreenodeptr->weight);
  190. }

  192. /***************************************************************
  193.  *函数名：CreateSecondOptimalTree()
  194.  *功能：创建次优查找树(采用二叉链式存储结构)
  195.  *输入参数：
  196.  * ordertableptr : 有序表地址
  197.  * sw ：累计权值和表地址
  198.  * low ：树区间最低下标(初始时:是有序表中的第1号元素，不是第0号)
  199.  * high : 树区间最高下标
  200.  *输出参数：
  201.  * secopttreenodeptr : 创建的次优查找树
  202.  *返回值：空
  203.  *编程思想：
  204.  * 1，在有序表中找出最小的(detaPi)元素所在的下标，作为树根结点。
  205.  * 2，以树根结点为中心点，在顺序表中左右分开:左边是左子树的结点，右边是右子树的结点。
  206.  * 3，在左右子树中继续1,2步，可以递归实现
  207. ****************************************************************/
  208. void CreateSecondOptimalTree(SecOptTreeNodePtr * secopttreenodeptr, OrderTablePtr ordertableptr, int * sw, int low, int high)
  209. {
  210.     if((ordertableptr == NULL)||(sw == NULL)||(low > high))
  211.         return;
  212.     /*找树根结点元素:先找最小(detaPi)的值(detaPi:是第i个元素左右两边权值和之差的绝对值)*/
  213.     int minPi = abs(sw[high]); /*最小的(detaPi)*/
  214.     int minPi_index = -1; /*最小的(detaPi)元素所在的下标*/
  215.     int i = 0;
  216.     for(i=low; i<=high; i++)
  217.     {
  218.         /*abs((sw[high] - sw[i]) - (sw[i-1] - sw[low-1])) : |右边的权值和 - 左边的权值和|*/
  219.         if(abs((sw[high] - sw[i]) - (sw[i-1] - sw[low-1])) < minPi) /*找最小(detaPi)*/
  220.         {
  221.             minPi = abs(sw[high] + sw[low-1] - sw[i] -sw[i-1]);
  222.             minPi_index = i; /*记录最小(detaPi)元素的下标值*/
  223.         }
  224.     }
  225.     /*minPi_index记录的下标就是树跟结点*/
  226.     *secopttreenodeptr = (SecOptTreeNodePtr)malloc(sizeof(SECONDOPTINALTREENODE));
  227.     if(*secopttreenodeptr == NULL)
  228.     {
  229.         printf("CreateSecondOptimalTree mallo err!\n");
  230.         return;
  231.     }
  232.     memset(*secopttreenodeptr, 0, sizeof(SECONDOPTINALTREENODE));
  233.     memcpy(*secopttreenodeptr, &(ordertableptr->node[minPi_index]), sizeof(SECONDOPTINALTREENODE)); /*生成根结点*/
  234.     
  235.     int newlow; /*孩子树区间最低下标*/
  236.     int newhigh; /*孩子树区间最高下标*/
  237.     if(minPi_index == low) /*左子树为空*/
  238.     {
  239.         (*secopttreenodeptr)->leftchild = NULL;
  240.     }
  241.     else /*创建左子树*/
  242.     {
  243.         newlow = low;
  244.         newhigh = minPi_index - 1;
  245.         CreateSecondOptimalTree(&((*secopttreenodeptr)->leftchild), ordertableptr, sw, newlow, newhigh);
  246.     }
  247.     if(minPi_index == high) /*右子树为空*/
  248.     {
  249.         (*secopttreenodeptr)->rightchild = NULL;
  250.     }
  251.     else /*创建右子树*/
  252.     {
  253.         newlow = minPi_index + 1;
  254.         newhigh = high;
  255.         CreateSecondOptimalTree(&((*secopttreenodeptr)->rightchild), ordertableptr, sw, newlow, newhigh);
  256.     }
  257. }

  259. /*功能：打印有序表中的所有元素*/
  260. int PrintOrderTable(OrderTablePtr ordertableptr, int * sw)
  261. {
  262.     if(ordertableptr == NULL)
  263.          return -1;
  264.     int i = 0;
  265.     for(i=0; i<ordertableptr->length+1; i++)
  266.     {
  267.         printf("元素下标[%d],key=[%s],value=[%s],weight=[%d],sw=[%d]\n", i, ordertableptr->node[i].key, ordertableptr->node[i].value, ordertableptr->node[i].weight, sw[i]);
  268.     }
  269.     return 0;
  270. }

  272. /***************************************************************
  273.  *函数名称：InitOrderTable()
  274.  *功能：初始化次优二叉树的有序表(顺序存储结构)
  275.  *输出参数：
  276.  * ordertableptr : 有序表指针的地址
  277.  *返回值：
  278. ****************************************************************/
  279.  int InitOrderTable(OrderTablePtr * ordertableptr)
  280.  {
  281.      int weightvalue[128]={1, 1, 2, 5, 3, 4, 4, 3, 5};

  283.     *ordertableptr = (ORDERTABLE*)malloc(sizeof(ORDERTABLE));
  284.     if(*ordertableptr == NULL)
  285.         return -1;
  286.     memset((*ordertableptr), 0, sizeof(ORDERTABLE));
  287.     (*ordertableptr)->length = 9;
  288.     (*ordertableptr)->node = (SECONDOPTINALTREENODE *) malloc(((*ordertableptr)->length+1) * sizeof(SECONDOPTINALTREENODE)); /*0号单元留空*/
  289.     if((*ordertableptr)->node == NULL)
  290.         return -1;
  291.     memset((*ordertableptr)->node, 0, (*ordertableptr)->length * sizeof(SECONDOPTINALTREENODE));
  292.     /*初始化顺序表的元素*/
  293.     strcpy((*ordertableptr)->node[0].key, "");
  294.     strcpy((*ordertableptr)->node[0].value, "");
  295.     (*ordertableptr)->node[0].weight = 0;
  296.     (*ordertableptr)->node[0].leftchild = NULL;
  297.     (*ordertableptr)->node[0].rightchild = NULL;
  298.     strcpy((*ordertableptr)->node[1].key, "A");
  299.     strcpy((*ordertableptr)->node[1].value, "AAA");
  300.     (*ordertableptr)->node[1].weight = weightvalue[0];
  301.     (*ordertableptr)->node[1].leftchild = NULL;
  302.     (*ordertableptr)->node[1].rightchild = NULL;
  303.     strcpy((*ordertableptr)->node[2].key, "B");
  304.     strcpy((*ordertableptr)->node[2].value, "BBB");
  305.     (*ordertableptr)->node[2].weight = weightvalue[1];
  306.     (*ordertableptr)->node[2].leftchild = NULL;
  307.     (*ordertableptr)->node[2].rightchild = NULL;
  308.     strcpy((*ordertableptr)->node[3].key, "C");
  309.     strcpy((*ordertableptr)->node[3].value, "CCC");
  310.     (*ordertableptr)->node[3].weight = weightvalue[2];
  311.     (*ordertableptr)->node[3].leftchild = NULL;
  312.     (*ordertableptr)->node[3].rightchild = NULL;
  313.     strcpy((*ordertableptr)->node[4].key, "D");
  314.     strcpy((*ordertableptr)->node[4].value, "DDD");
  315.     (*ordertableptr)->node[4].weight = weightvalue[3];
  316.     (*ordertableptr)->node[4].leftchild = NULL;
  317.     (*ordertableptr)->node[4].rightchild = NULL;
  318.     strcpy((*ordertableptr)->node[5].key, "E");
  319.     strcpy((*ordertableptr)->node[5].value, "EEE");
  320.     (*ordertableptr)->node[5].weight = weightvalue[4];
  321.     (*ordertableptr)->node[5].leftchild = NULL;
  322.     (*ordertableptr)->node[5].rightchild = NULL;
  323.     strcpy((*ordertableptr)->node[6].key, "F");
  324.     strcpy((*ordertableptr)->node[6].value, "FFF");
  325.     (*ordertableptr)->node[6].weight = weightvalue[5];
  326.     (*ordertableptr)->node[6].leftchild = NULL;
  327.     (*ordertableptr)->node[6].rightchild = NULL;
  328.     strcpy((*ordertableptr)->node[7].key, "G");
  329.     strcpy((*ordertableptr)->node[7].value, "GGG");
  330.     (*ordertableptr)->node[7].weight = weightvalue[6];
  331.     (*ordertableptr)->node[7].leftchild = NULL;
  332.     (*ordertableptr)->node[7].rightchild = NULL;
  333.     strcpy((*ordertableptr)->node[8].key, "H");
  334.     strcpy((*ordertableptr)->node[8].value, "HHH");
  335.     (*ordertableptr)->node[8].weight = weightvalue[7];
  336.     (*ordertableptr)->node[8].leftchild = NULL;
  337.     (*ordertableptr)->node[8].rightchild = NULL;
  338.     /*注意：如果长度只分配9的话，node[9]其实已经越界了，在数组的外面了
  339.     再操作mallo()的话，可能会覆盖这个空间*/
  340.     strcpy((*ordertableptr)->node[9].key, "I");
  341.     strcpy((*ordertableptr)->node[9].value, "III");    
  342.     (*ordertableptr)->node[9].weight = weightvalue[8];
  343.     (*ordertableptr)->node[9].leftchild = NULL;
  344.     (*ordertableptr)->node[9].rightchild = NULL;
  345.     
  346.     return 0;
  347.  }
  348.  
  349. /***************************************************************
  350.  *函数名：DestroySunXuTable()
  351.  *函数功能：销毁顺序表
  352.  *函数参数：
  353.  * sxtableptr ：顺序表指针
  354. ****************************************************************/
  355. int DestroySunXuTable(SunXuTablePtr sxtableptr)
  356. {
  357.     if(sxtableptr == NULL)
  358.         return -1;
  359.     if(sxtableptr->elem != NULL)
  360.     {
  361.         free(sxtableptr->elem);
  362.         sxtableptr->elem = NULL;
  363.     }
  364.     if(sxtableptr != NULL)
  365.     {
  366.         free(sxtableptr);
  367.         sxtableptr = NULL;
  368.     }
  369.     return 0;
  370. }

  372. /***************************************************************
  373.  *函数名：Search_Bin()
  374.  *功能：折半查找：在有序表中折半查找其指定的关键字的元素
  375.  *输入参数：
  376.  * sxtable ：顺序表
  377.  * key ：待查找的关键字
  378.  *返回值：
  379.  * 若找到： 则返回该元素在表中的位置
  380.  * 若未找到：则返回0
  381. ****************************************************************/
  382. int Search_Bin(SunXuTablePtr sxtableptr, STRING key)
  383. {
  384.      if((key == NULL)||(sxtableptr == NULL))
  385.          return 0;
  386.      int low = 1; /*设置区间初值*/
  387.      int high = sxtableptr->length;
  388.      int mid = 0;
  389.      
  390.      while(low <= high)
  391.      {
  392.          mid = (low + high)/2;
  393.          if(EQ(key, sxtableptr->elem[mid].key)) /*找到待查找元素,可以直接返回了*/
  394.              return mid;
  395.          else if(LT(key, sxtableptr->elem[mid].key))    /*继续在前半区间查找*/
  396.              high = mid - 1;
  397.          else low = mid + 1; /*继续在后半区间查找*/
  398.      }
  399.      
  400.     return 0; /*找不到时，返回0*/         
  401. }

  403. /*功能：打印顺序表中的所有元素*/
  404. int PrintSxTable(SunXuTablePtr sxtableptr)
  405. {
  406.     if(sxtableptr == NULL)
  407.          return -1;
  408.     int i = 0;
  409.     for(i=0; i<sxtableptr->length+1; i++)
  410.     {
  411.         printf("元素下标[%d],key=[%s],value=[%s]\n", i, sxtableptr->elem[i].key, sxtableptr->elem[i].value);
  412.     }
  413.     return 0;
  414. }

  416. /*功能：初始化顺序表(顺序存储结构)*/
  417. int InitSxTable(SunXuTablePtr * sxtableptr)
  418. {
  419.     /*顺序表中元素的存放是无序的,为了试验有序表的折半查找，
  420.     这里人为的让数据元素是有序的，免去了排序的操作
  421.     所以也可以当有序表使用，并且，并不影响顺序查找的测试*/
  422.     *sxtableptr = (SUNXUTABLE*)malloc(sizeof(SUNXUTABLE));
  423.     if(*sxtableptr == NULL)
  424.         return -1;
  425.     memset((*sxtableptr), 0, sizeof(SUNXUTABLE));
  426.     (*sxtableptr)->length = 9;
  427.     (*sxtableptr)->elem = (ELEMTYPE *) malloc((*sxtableptr)->length * sizeof(ELEMTYPE));
  428.     if((*sxtableptr)->elem == NULL)
  429.         return -1;
  430.     memset((*sxtableptr)->elem, 0, (*sxtableptr)->length * sizeof(ELEMTYPE));
  431.     /*初始化顺序表的元素*/
  432.     strcpy((*sxtableptr)->elem[1].key, "A");
  433.     strcpy((*sxtableptr)->elem[1].value, "AAA");
  434.     strcpy((*sxtableptr)->elem[2].key, "B");
  435.     strcpy((*sxtableptr)->elem[2].value, "BBB");
  436.     strcpy((*sxtableptr)->elem[3].key, "C");
  437.     strcpy((*sxtableptr)->elem[3].value, "CCC");
  438.     strcpy((*sxtableptr)->elem[4].key, "D");
  439.     strcpy((*sxtableptr)->elem[4].value, "DDD");
  440.     strcpy((*sxtableptr)->elem[5].key, "E");
  441.     strcpy((*sxtableptr)->elem[5].value, "EEE");
  442.     strcpy((*sxtableptr)->elem[6].key, "F");
  443.     strcpy((*sxtableptr)->elem[6].value, "FFF");
  444.     strcpy((*sxtableptr)->elem[7].key, "G");
  445.     strcpy((*sxtableptr)->elem[7].value, "GGG");
  446.     strcpy((*sxtableptr)->elem[8].key, "H");
  447.     strcpy((*sxtableptr)->elem[8].value, "HHH");
  448.     strcpy((*sxtableptr)->elem[9].key, "I");
  449.     strcpy((*sxtableptr)->elem[9].value, "III");    
  450.     
  451.     return 0;
  452. }

  454. /***************************************************************
  455.  *函数名：Search_Seq()
  456.  *功能：顺序查找：在顺序表中顺序查找其指定的关键字的元素
  457.  *输入参数：
  458.  * sxtable ：顺序表
  459.  * key ：待查找的关键字
  460.  *返回值：
  461.  * 若找到： 则返回该元素在表中的位置
  462.  * 若未找到：则返回0
  463. ****************************************************************/
  464. int Search_Seq(SunXuTablePtr sxtableptr, STRING key)
  465. {
  466.      if((key == NULL)||(sxtableptr == NULL))
  467.          return 0;
  468.      strcpy(sxtableptr->elem[0].key, key); /*哨兵*/
  469.      /*对0号元素elem[0]赋值key，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。
  470.      elem[0]起到监视哨的作用，这仅仅是程序设计技巧上的改进*/
  471.      int i = 0;
  472.      for(i=sxtableptr->length; !EQ(sxtableptr->elem[i].key, key); i--); /*从后往前走*/
  473.     
  474.     return i; /*找不到时，会一直找到第一个，肯定相等，此时i=0*/         
  475. }

阅读(561) | 评论(0) | 转发(0) |
0

上一篇：双向循环链表

下一篇：Hash表

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6