算法导论课设(5个)

1、课程实验报告课程名称 算法导论 题 目 堆排序 计数排序 贪心算法 散列表 动态规划 （院）系 理 学 院 专业 _信息与计算科学 班级 1202班 _ 学号 26 02 22_ 学生姓名 孙银东 黄君 叶勇_ _ 导师姓名 阳卫锋 _ 完成日期 _2014年11月20日_ _题目一 堆排序班级: 信科1202 姓名: 孙银东 黄君 叶勇一、实验目的：掌握堆的创建，学会利用堆进行排序。 二、实验内容：对数组利用堆进行排序。三、实验要求：1） 写出算法的伪代码和C程序代码2） 记录每一步数组的中元素的变化程序代码参考#include #define Length 10 int compare(i

2、nt a,int b) /用于比较值的大小 if(ab) return 0; else if(ab) return 1; else return -1; void swap(int &a,int &b)/自定义的交换函数，目的是交换函数值 int tmp; tmp = a; a = b; b = tmp; void heapify(int A,int idx,int max) /保持堆的性质 int largest; int left_child = 2*idx+1; int right_child= 2*idx+2; if(left_childmax & compare(Aidx,Aleft

3、_child)=1) largest = left_child; else largest = idx; if(right_child=0;i-) heapify(A,i,Length); int main() int ALength = 2,60,3,234,1,0,23,56,-23; buildheap(A); int i,j; for(i=Length-1;i=0;-i) swap(A0,Ai); heapify(A,0,i); for(j=0;jLength;j+) printf(%dn,Aj); return 0; 四、结果分析堆排序设计结果：五、总结对数组利用堆进行排序，要求我们

4、对前期所学知识了解透彻，这样可以很快得到结论题目二 计数排序一、实验目的：学习使用计数排序。 二、实验内容：对数组利用计数排序进行排序。三、实验要求：1） 写出算法的伪代码和C程序代码2） 记录每一步数据结构（比如数组）中元素的变化程序代码参考#include int main()using namespace std;int const len=10;int i,j,count;i=j=count=0;int array_oldlen;for(i=0;i10;i+) scanf(%d,&array_oldi);int array_newlen;for(i=0;ilen;i+) for(j=0

5、;jarray_oldj) count+; array_newcount=array_oldi; count=0; coutThe result :endl;for(i=0;ilen;i+) coutarray_newi ;coutendl;system(pause);return 0; 四、结果分析计数排序设计结果：（1）输入十个数字（2）输出结果五、总结将数学中的排序问题弄懂，就能很快解决计数排序问题题目三 贪心算法程序设计一、实验目的：掌握贪心算法。 二、实验内容：设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然 数的乘积最大。 对于给定的正整数n，编程计算最

6、优分解方案。三、实验要求：利用贪心算法思想写出算法的伪代码和C程序代码。程序代码参考#include#includeint tanxin(int n) /贪心算法实现函数 int a100; intk=1,sum=1,s=0; if(nak)k+;ak=ak-1+1;n-=ak;s=k;if(n=ak)ak+;n-;for(int i=0;in;i+)ak-i+; for(int j=1;j=s;j+) sum*=aj; return sum;int main(int argc, char* argv) /主函数测试 int n;printf(请输入要求的数：n);scanf(%d,&n);

7、printf(%dn,tanxin( n);system(pause);return 0;四、结果分析贪心算法设计结果：五 总结要了解贪心算法的核心原理，上机多操作，才能发现不足，得出结果 题目四： 散列表算法程序设计实验目的：1通过本次实验进一步理解散列表的概念；2掌握散列表的创建；3掌握散列表中数据的存储与查找。程序代码：#include#include#include#include #define MAXSIZE 20 /商场商品记录数量 #define MAX_SIZE 20 /商品的最大长度#define HASHSIZE 53 /定义表长 #define SUCCESS 1#de

8、fine UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NAMAX_SIZE;typedef struct/记录NA name;NA tel;NA add;Record;typedef struct/散列表Record *elemHASHSIZE; /数据元素存储基址int count; /当前数据元素个数int size; /当前容量HashTable;Status eq(NA x, NA y)/关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif (strcmp(x, y) =

9、 0)return SUCCESS;else return UNSUCCESS;Status NUM_BER; /记录的个数void getin(Record* a)/键盘输入各商品的信息printf(输入要添加的个数：n);scanf(%d, &NUM_BER);int i;for (i = 0; iNUM_BER; i+)printf(请输入第%d个记录的商品名:n, i + 1);scanf(%s, );printf(请输入%d个记录的商品ID:n, i + 1);scanf(%s, ai.tel);printf(请输入第%d个记录的地址:n, i + 1);scanf(%

10、s, ai.add); /gets(str2);?void ShowInformation(Record* a)/显示输入的商品信息int i;for (i = 0; iNUM_BER; i+)printf(n第%d个商品信息:n 商品：%sn 商品ID：%sn 联系地址：%sn, i + 1, , ai.tel, ai.add);void Cls(Record* a)printf(*);system(cls);long fold(NA s)/商品的折叠处理char *p;long sum = 0;NA ss;strcpy(ss, s);/复制字符串，不改变原字符串的大小写str

11、upr(ss);/将字符串ss转换为大写形式p = ss;while (*p != 0)sum += *p+;printf(nsum=%d, sum);return sum;int Hash1(NA str)/散列函数long n;int m;n = fold(str);/先将商品名进行折叠处理m = n%HASHSIZE; /折叠处理后的数，用除留余数法构造散列函数return m; /并返回模值int Hash2(NA str)/散列函数long n;int m;n = atoi(str);/把字符串转换成整型数.m = n%HASHSIZE; /用除留余数法构造散列函数return m;

12、 /并返回模值Status collision(int p, int &c)/冲突处理函数，采用二次探测再散列法解决冲突int i, q;i = c / 2 + 1;while (i= 0) return q;else i = c / 2 + 1;elseq = (p - i*i) % HASHSIZE;c+;if (q = 0) return q;else i = c / 2 + 1;return UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H, Record* a)/建表，以商品的商品为关键字，建立相应的散列表/若散列地址

13、冲突，进行冲突处理benGetTime();int i, p = -1, c, pp;for (i = 0; ielempp != NULL) pp = collision(p, c);if (ppelempp = &(ai); /求得散列地址，将信息存入H-count+;printf(第%d个记录冲突次数为%d。n, i + 1, c);/需要显示冲突次数时输出printf(n建表完成!n此散列表容量为%d,当前表内存储的记录个数为%d.n, HASHSIZE, H-count);benGetTime();void SearchHash1(HashTable* H, int &c)/在记录里

14、查找商品关键字，若查找成功，显示信息/c用来记录冲突次数,查找成功时显示冲突次数benGetTime();NA str;printf(n请输入要查找记录的商品：n);scanf(%s, str);int p, pp;p = Hash1(str);pp = p;while (H-elempp != NULL) & (eq(str, H-elempp-name) = -1)pp = collision(p, c);if (H-elempp != NULL&eq(str, H-elempp-name) = 1)printf(n查找成功！n查找过程冲突次数为%d以下是您需要要查找的信息：nn, c);

15、printf(商品：%sn商品ID：%sn联系地址：%sn, H-elempp-name, H-elempp-tel, H-elempp-add);else printf(n此商品不存在，查找不成功!n);benGetTime();void benGetTime()SYSTEMTIME sys;GetLocalTime(&sys);printf(%4d/%02d/%02d %02d:%02d:%02d.%03d n, sys.wYear, sys.wMonth, sys.wDay, sys.wHour, sys.wMinute, sys.wSecond, sys.wMilliseconds);

16、void CreateHash2(HashTable* H, Record* a)/建表，以商品ID为关键字，建立相应的散列表/若散列地址冲突，进行冲突处理benGetTime();int i, p = -1, c, pp;for (i = 0; ielempp != NULL) pp = collision(p, c);if (ppelempp = &(ai); /求得散列地址，将信息存入H-count+;printf(第%d个记录冲突次数为%d。n, i + 1, c);/需要显示冲突次数时输出printf(n建表完成!n此散列表容量为%d,当前表内存储的记录个数为%d.n, HASHSI

17、ZE, H-count);benGetTime();void SearchHash2(HashTable* H, int &c)/在记录里查找商品ID关键字，若查找成功，显示信息/c用来记录冲突次数,查找成功时显示冲突次数benGetTime();NA tele;printf(n请输入要查找记录的商品ID：n);scanf(%s, tele);int p, pp;p = Hash2(tele);pp = p;while (H-elempp != NULL) & (eq(tele, H-elempp-tel) = -1)pp = collision(p, c);if (H-elempp != N

18、ULL&eq(tele, H-elempp-tel) = 1)printf(n查找成功！n查找过程冲突次数为%d以下是您需要要查找的信息：nn, c);printf(商品：%sn商品ID：%sn联系地址：%sn, H-elempp-name, H-elempp-tel, H-elempp-add);else printf(n此商品不存在，查找不成功!n);benGetTime();void Save()FILE *fp;if (fp = fopen(c:test.txt, w) = NULL)printf(nERROR opening customet file);fclose(fp);int

19、 main(int argc, char* argv)int c, flag = 1;HashTable *H;H = (HashTable*)malloc(LEN);for (int i = 0; i elemi = NULL;H-size = HASHSIZE;H-count = 0;Record aMAXSIZE;while (1)printf(n );printf(n 欢迎使用商品查找系统 );printf(n );printf(n 散列表的设计与实现 );printf(n 【1】. 添加商品信息 );printf(n 【2】. 读取所有商品信息 );printf(n 【3】. 以商品

20、名建立散列表(散列法解决冲突) );printf(n 【4】. 以商品ID建立散列表(散列法解决冲突) );printf(n 【5】. 查找并显示给定商品的记录 );printf(n 【6】. 查找并显示给定ID的记录 );printf(n 【7】. 清屏 );printf(n 【8】. 保存 );printf(n 【9】. 退出程序 );printf(n 提示： );printf(n .进行5操作前 请先输出3 );printf(n .进行6操作前 请先输出4 );printf(n );printf(n);printf(请输入一个任务选项);printf(n);int num;scanf(%

21、d, &num);switch (num)case 1:getin(a);break;case 2:ShowInformation(a);break;case 3:CreateHash1(H, a); /* 以商品建立散列表 */break;case 4:CreateHash2(H, a); /* 以商品ID建立散列表 */break;case 5:c = 0;SearchHash1(H, c);break;case 6:c = 0;SearchHash2(H, c);break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf(你输错了，请重新输入!);printf(n);system(pause);return 0;运行结果 实验五 动态规划程序设计一、实验目的：掌握动态规划算法。 二、实验内容：对维数为序列（5，10，3，12，5，50，6）的各矩阵。找出其矩阵链乘的一个最优加全括号。三、实验要求：利用动态规划思想写出算法的伪代码和C程序代码程序参考代码#includ