C语言数据结构-algo9-3.c

blake

1. /* algo9-3.c 静态查找表(静态树表)的操作 */
   
2. #include"c1.h"
   
3. #define N 9 /* 数据元素个数 */
   
4. typedef char KeyType; /* 设关键字域为字符型 */
   
5. typedef struct /* 数据元素类型 */
   
6. {
   
7.    KeyType key;
   
8.    int weight;
   
9. }ElemType;
   
10. ElemType r[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3},
    
11.                 {'F',4},{'G',4},{'H',3},{'I',5}}; /* 数据元素(以教科书例9-1为例),全局变量 */
    
12. int sw[N+1]; /* 累计权值，全局变量 */
    
13. #include"c9.h"
    
14. #include"c9-1.h"
    
15. #include"bo9-1.c"
    
16. 
    
17. typedef ElemType TElemType;
    
18. #include"c6-2.h"
    
19. Status SecondOptimal(BiTree *T, ElemType R[],int sw[],int low,int high)
    
20. { /* 由有序表R[low..high]及其累计权值表sw(其中sw[0]==0)递归构造 */
    
21.    /* 次优查找树T。算法9.3 */
    
22.    int i,j;
    
23.    double min,dw;
    
24.    i=low;
    
25.    min=fabs(sw[high]-sw[low]);
    
26.    dw=sw[high]+sw[low-1];
    
27.    for(j=low+1;j<=high;++j) /* 选择最小的△Pi值 */
    
28.      if(fabs(dw-sw[j]-sw[j-1])<min)
    
29.      {
    
30.        i=j;
    
31.        min=fabs(dw-sw[j]-sw[j-1]);
    
32.      }
    
33.    *T=(BiTree)malloc(sizeof(BiTNode));
    
34.    if(!*T)
    
35.      return ERROR;
    
36.    (*T)->data=R[i]; /* 生成结点 */
    
37.    if(i==low)
    
38.      (*T)->lchild=NULL; /* 左子树空 */
    
39.    else
    
40.      SecondOptimal(&(*T)->lchild,R,sw,low,i-1); /* 构造左子树 */
    
41.    if(i==high)
    
42.      (*T)->rchild=NULL; /* 右子树空 */
    
43.    else
    
44.      SecondOptimal(&(*T)->rchild,R,sw,i+1,high); /* 构造右子树 */
    
45.    return OK;
    
46. }
    
47. 
    
48. void FindSW(int sw[],SSTable ST)
    
49. { /* 按照有序表ST中各数据元素的Weight域求累计权值表sw */
    
50.    int i;
    
51.    sw[0]=0;
    
52.    for(i=1;i<=ST.length;i++)
    
53.      sw[i]=sw[i-1]+ST.elem[i].weight;
    
54. }
    
55. 
    
56. typedef BiTree SOSTree; /* 次优查找树采用二叉链表的存储结构 */
    
57. Status CreateSOSTree(SOSTree *T,SSTable ST)
    
58. { /* 由有序表ST构造一棵次优查找树T。ST的数据元素含有权域weight。算法9.4 */
    
59.    if(ST.length==0)
    
60.      *T=NULL;
    
61.    else
    
62.    {
    
63.      FindSW(sw,ST); /* 按照有序表ST中各数据元素的Weight域求累计权值表sw */
    
64.      SecondOptimal(T,ST.elem,sw,1,ST.length);
    
65.    }
    
66.    return OK;
    
67. }
    
68. 
    
69. Status Search_SOSTree(SOSTree *T,KeyType key)
    
70. { /* 在次优查找树T中查找关键字等于key的元素。找到则返回OK，否则返回FALSE */
    
71.    while(*T) /* T非空 */
    
72.      if((*T)->data.key==key)
    
73.        return OK;
    
74.      else if((*T)->data.key>key)
    
75.        *T=(*T)->lchild;
    
76.      else
    
77.        *T=(*T)->rchild;
    
78.    return FALSE; /* 顺序表中不存在待查元素 */
    
79. }
    
80. 
    
81. void print(ElemType c) /* Traverse()调用的函数 */
    
82. {
    
83.    printf("(%c %d) ",c.key,c.weight);
    
84. }
    
85. 
    
86. void main()
    
87. {
    
88.    SSTable st;
    
89.    SOSTree t;
    
90.    Status i;
    
91.    KeyType s;
    
92.    Creat_Ord(&st,N); /* 由全局数组产生非降序静态查找表st */
    
93.    Traverse(st,print);
    
94.    CreateSOSTree(&t,st); /* 由有序表构造一棵次优查找树 */
    
95.    printf("\n请输入待查找的字符: ");
    
96.    scanf("%c",&s);
    
97.    i=Search_SOSTree(&t,s);
    
98.    if(i)
    
99.      printf("%c的权值是%d\n",s,t->data.weight);
    
100.    else
     
101.      printf("表中不存在此字符\n");
     
102. }
     
103. 

复制代码