无所事事刷anyview的日子（chapter 03~04）

持续更新中……赶紧刷完anyview然后继续学习老本行……

DC03

1、直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**********
【题目】试以顺序表L的L.rcd[L.length+1]作为监视哨，
改写教材3.2节中给出的升序直接插入排序算法。
顺序表的类型RcdSqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
   int length;
} RcdSqList;
**********/
void InsertSort(RcdSqList &L)
{
    int i,j;
    for(i=1;i<L.length;++i)
    if(L.rcd[i+1].key<L.rcd[i].key) {
        L.rcd[L.length+1]=L.rcd[i+1];
        j=i+1;
        do{j--;L.rcd[j+1]=L.rcd[j];
        } while(L.rcd[L.length+1].key<L.rcd[j-1].key);
        L.rcd[j]=L.rcd[L.length+1];
    }
}

DC04

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**********
【题目】假设哈希表长为m，哈希函数为H(x)，用链地址法
处理冲突。试编写输入一组关键字并建造哈希表的算法。
哈希表的类型ChainHashTab定义如下：
#define NUM         7
#define NULLKEY    -1
#define SUCCESS     1
#define UNSUCCESS   0
#define DUPLICATE  -1
typedef char HKeyType;
typedef struct HNode {
   HKeyType  data;
   struct HNode*  next;
}*HLink;
typedef struct {
   HLink  *rcd;   // 指针存储基址，动态分配数组
   int    count;  // 当前表中含有的记录个数
   int    size;  // 哈希表的当前容量
}ChainHashTab;    // 链地址哈希表
int Hash(ChainHashTab H, HKeyType k) { // 哈希函数
  return k % H.size;
}
Status Collision(ChainHashTab H, HLink &p) {
  // 求得下一个探查地址p 
  if (p && p->next) { 
    p = p->next;
    return SUCCESS;
  } else return UNSUCCESS;
}
**********/
int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) 
/* 直接调用下列函数                             */
/* 哈希函数：                                   */
/*    int Hash(ChainHashTab H, HKeyType k);     */
/* 冲突处理函数：                               */
/*    int Collision(ChainHashTab H, HLink &p);  */
{
    HLink p,q;
    int i,pos; 
    for(i=0;i<n;i++) H.rcd[i]->next=NULL;
    for(i=0;i<n;i++) {
        q=(HNode*)malloc(sizeof(HNode));
        q->data=es[i];q->next=NULL; //建立新结点
        pos=Hash(H,es[i]); //查找位置
        p=H.rcd[pos];
        while(p->data!=q->data&&p->next) 
            Collision(H,p);  //确定是否出现过
        if(p->data!=q->data) {  //新元素，插在前面
            q->next=H.rcd[pos];
            H.rcd[pos]=q;
        }
    }
    return OK ;                  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**********
【题目】已知某哈希表的装载因子小于1，哈希函数H(key)
为关键字(标识符)的第一个字母在字母表中的序号，处理
冲突的方法为线性探测开放定址法。试编写一个按第一个
字母的顺序输出哈希表中所有关键字的算法。
哈希表的类型HashTable定义如下：
#define SUCCESS    1
#define UNSUCCESS  0
#define DUPLICATE -1
typedef char StrKeyType[4];
typedef struct {
   StrKeyType key; // 关键字项
   int    tag;     // 标记 0:空；1:有效; -1:已删除
   void  *any;     // 其他信息
} RcdType;
typedef struct {
  RcdType *rcd;    // 存储空间基址
  int      size;   // 哈希表容量
  int      count;  // 表中当前记录个数
} HashTable;
**********/
void PrintKeys(HashTable ht, void(*print)(StrKeyType))
/* 依题意用print输出关键字 */
{       
    int n,i,size; 
    char c;  
    size=11;
    for(c='A';c<='Z';c++) {
        n=(c-'A')%size; 
        i=n;  
        while((n+1)%size!=i) {
            if(ht.rcd[n].key[0]==c&&ht.rcd[n].tag==1)
                print(ht.rcd[n].key);
            n=(n+1)%size;
        }  
    }
}