广工数据结构anyview答案(4)

void CountSort(RcdSqList &L)

/* 采用顺序表存储结构，在函数内自行定义计数数组c */ { int k = L.length ; RcdSqList L1; int c[21]; int i,j;

for(i = 1;i <= L.length ;i++) for(j = 1;j <= L.length;j++) {

if(L.rcd[i].key

for(i = 1;i<=L.length ;i++) {

L1.rcd[c[i]+1].key = L.rcd[i].key; }

for(i = 1;i<=L.length ;i++) {

L.rcd[L.length-i+1].key = L1.rcd[i].key; } } /*

{ int k = L.length ; int c[k]; int i,j;

for(i = 1;i <= L.length ;i++) for(j = 1;j < L.length;j++) {

if(L.rcd[i].key

//用一种办法代替后面两个for循环 } */

//为什么要倒过来放，难道序列是栈？ //运行时间有点久

DS06

/**04********************************************************************/

/**********

【题目】已知某哈希表的装载因子小于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 collision(int &p,int size) {

p =(p+1)%size; }

void PrintKeys(HashTable ht, void(*print)(StrKeyType)) /* 依题意用print输出关键字 */ {

int i,j,p,k;

StrKeyType key; for(i = 65; i < 91;i++) {

k = 0; j = 0;

key[0] = i; p = 0;

while(j < ht.size) {

collision(p,ht.size); k++; j++;

if(26 == k) break;

if(ht.rcd[p].key[0] == key[0]) print(ht.rcd[p].key); }

}

//输出速度太慢了，改为用key第一个字进行比较 }

/**15************************************************* /**********

【题目】假设哈希表长为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); */ {

int i,k,j;

HLink p,q,p1;

H.rcd = (HLink*)malloc(7*sizeof(HLink)); H.size = 7; H.count = 0;

for(i = 0;es[i] >= 'A';i++) {

p = (HNode*)malloc(sizeof(HNode)); p->data = 0;

p->next = NULL; p->data = es[i];

k = Hash( H, p->data) ; if(NULL !=H.rcd[k])

{ // 判断其中是否有相同的HKeyType p1 = H.rcd[k]; while(NULL != p1)

{ //用j作为标记，如果j = 0表示没有相同的，插入p if(p1->data == p->data) j = 1; p1 = p1->next; }

if(j == 0) {

q = H.rcd[k]; p->next = q; H.rcd[k] = p;

} j = 0; } else

H.rcd[k] = p; //为什么H.rcd[k]->next = p;不会报错

H.count++; } }

第7章

/***04*******

【题目】试编写如下定义的递归函数的递归算法: g(m,n) = 0 当m=0,n>=0 g(m,n) = g(m-1,2n)+n 当m>0,n>=0 **********/

int G(int m, int n)

/* 如果 m<0 或 n<0 则返回 -1 */ {

if(m<0||n<0) return -1; if(m==0) return 0;

if(m>0&&n>=0) return G(m-1,2*n)+n; //三种情况

//三个并列，如果条件不是排他的话有可能错 //尽量用if..else }

/***05*******

【题目】试写出求递归函数F(n)的递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 **********/ int F(int n)

/* 如果 n<0 则返回 -1 */ {

if(n<0) return -1; if(n==0) return 1; else

return n*F(n/2); }

/***06*******

【题目】求解平方根 的迭代函数定义如下： sqrt(A,p,e) = p 当|p*p-A|=e

其中，p是A的近似平方根，e是结果允许误差。试写出相 应的递归算法。 **********/

float Sqrt(float A, float p, float e)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库广工数据结构anyview答案(4)在线全文阅读。