中南大学算法实验报告

中南大学本科生课程设计(实践)任务书、设计报告（C++语言程序设计）题目多功能集成程序系统学生姓名闵杰指导教师罗芳学院材料科学与工程专业班级材料类1003学生学号**********计算机基础教学实验中心2011 年 6 月 30 日《集合简单计算、信息管理、绘图及多媒体系统设计》C++实践报告关键词：C++程序设计MFC[.exe] 面向对象计算信息管理绘图播放器一、引言1.1实践任务：1、计算程序设计。

如：计算器、一元二次方程的求解、华氏温度和摄氏温度之间的转换、求阶乘等。

2、文本编辑程序设计。

3、绘图程序设计。

如：吹泡泡程序、曲线等图形绘制。

4、信息管理程序设计。

能完成信息的添加、删除和修改等功能。

5、多媒体程序设计。

如：音频播放器、flash动画播放器等。

1.2实践目的：当今社会是信息时代，科技的高速发展要求我们能过熟练掌握并运用新的科学技术。

而信息的获取需要我们能够掌握应用程序的深层代码，运用所掌握的计算机程序知识对数据进行管理。

C++是由C发展而来的，与C兼容。

所以它可以用于面向过程的结构化程序设计，但是它又有自己的特点，它也可以用于面向对象的程序设计，是一种功能强大的混合型的程序设计语言。

通过本次实践，１、可以加深我们对面向对象的认识，巩固C++的基础知识，了解基于对话框的应用程序、文档/视图应用程序的框架结构和运行机制，初步掌握创建ＭＦＣ应用程序的方法、过程。

２、掌握常用的控件的重要属性、主要消息、常用成员函数，并熟练地应用这些控件设计应用程序。

３、掌握绘制图形的方法、定时器的使用，鼠标消息处理函数和键盘消息处理函数的编写、对话框使用和菜单设计的技术。

４、培养我们的独立思考、设计综合程序的能力；同时培养自学能力；训练小论文撰写能力。

因此，计算机程序设计是大多数专业的必修课。

随着软件工程技术的不断发展，面向对象的程序设计方法已成为当今软件开发的主流技术，我们肩负着博采众长的使命，运用好该程序将使我们受益匪浅。

中南⼤学数据结构实验报告1（线性表）实验⼀线性表的操作算法⼀、实验⽬的：1了解线性表的逻辑结构和存储结构，以及定义在逻辑结构上的各种基本运算2分别以数组和链表为存储结构，实现线性表的插⼊，删除，查找，排序，合并等操作⼆、实验内容：⽤C/C++语⾔编写程序，分别以数组和链表为存储结构，完成以下功能：1输⼊数据，创建⼀个线性表2可在线性表的任意位置插⼊新结点3可删除线性表的任意⼀个结点4可在线性表中查找结点5将线性表从⼩⾄⼤排序6将两个线性表合并三、详细设计：顺序表#includeusing namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct { //结构体ElemType *elem;int length;int listsize;}SqList;SqList Lx;Status InitList_Sq(SqList &L) //分配空间{ L.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,ElemType e) //插⼊新元素{ int *q,*p;ElemType *newbase; if(i<1 || i>L.length+1) return ERROR;if(L.length>=L.listsize){ newbase=new ElemType[L.listsize+LISTINCREMENT];if(!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for (p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;return OK;}Status Listlength(SqList L) //长度{ int *p=L.elem; //判断线形表是否存在while(p){ return (L.length); }}Status GetElem(SqList L, int i,ElemType &e) //取元素{ if(i<1 || i>L.length)return ERROR;else{ e=L.elem[i-1];return e;}}void MergeList(SqList La,SqList Lb,SqList &Lc) //合并{ ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ ListInsert(Lc,++k,ai);++i; }else{ ListInsert(Lc,++k,bj);++j; }}while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void show(SqList L,int i) //显⽰{ int j;ElemType k;cout<<"顺序表显⽰如下:"<for(j=0;j{ k=L.elem[j];cout<"; }if(j==i-1 && i>0){ k=L.elem[j]; cout<cout<}void create(SqList &L,int n) //输⼊元素{ int e; for(int i=0;i{ cin>>e;L.elem[i]=e;L.length=i+1; }}Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除{ ElemType *p, *q; if(i<1 || i>L.length) return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p) *(p-1)=*p;--L.length;return OK;}Status Listxiugei(SqList &L,int i,ElemType &e) //修改{ if(i<1 || i>L.length) return ERROR;else{ L.elem[i-1]=e;return OK; }}void shuru(SqList &L1) //顺序表的创建{ int a;InitList_Sq(L1);cout<<"请输⼊顺序表的长度：";cin>>a;cout<<"请输⼊顺序表的元素(共"<create(L1,a);show(L1,a);}void shanchu(SqList &L1) //删除顺序表⾥的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输⼊有误，请重新输⼊"<cout<<"请选择所要删除元素的位置:";cin>>j; }ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<show(L1,a-1);}void charu(SqList &L1) //插⼊元素到顺序表⾥{ int a; int j; ElemType e1; a=L1.length;cout<<"请选择所要插⼊元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输⼊有误，请重新输⼊"<cout<<"请选择所要插⼊元素的位置:";cin>>j; }cout<<"要插⼊的元素:";cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<show(L1,a+1);}void hebing(SqList &L3) //合并两个顺序表{ SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输⼊第⼀个有序表的长度："; cin>>a;cout<<"请输⼊第⼀个有序表的元素(共"<create(L1,a);show(L1,a);cout<<"请输⼊第⼆个有序表的长度："; cin>>b;cout<<"请输⼊第⼆个有序表的元素(共"<create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下："; show(L3,a+b);}void main() //主菜单{ int choice;for(;;){ cout<<"顺序表的基本操作"<cout<<"1.顺序表的创建"<cout<<"2.顺序表的显⽰"<cout<<"3.顺序表的长度"<cout<<"4.插⼊元素到顺序表⾥"<cout<<"5.删除顺序表⾥的元素"<cout<<"6.合并两个顺序表"<cout<<"7.退出系统"<cout<<"请选择：";cin>>choice;switch(choice){ case 1: shuru(Lx);break;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度:"<case 4: charu(Lx);break;case 5: shanchu(Lx);break;case 6: hebing(Lx);break;case 7: cout<<"退出系统!"<default : cout<<"输⼊有误，请重新选择"< }}链表#includeusing namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode //存储结构{ ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n) //尾插法创建单链表{ LinkList p;L=new LNode;L->next=NULL; //建⽴⼀个带头结点的单链表LinkList q=L; //使q指向表尾for(int i=1;i<=n;i++){ p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; }}Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素{ LinkList p=L->next;int j=1;while(p&&j{ p=p->next;++j; }if(!p||j>i) return error; //第i个元素不存在e=p->data;return ok;}Status LinkInsert(LinkList &L,int i,ElemType e) //插⼊{ LinkList p=L;int j=0;while(p&&j{ p=p->next;++j; } //寻找第i-1个结点 if(!p||j>i-1)return error; //i⼩于1或者⼤于表长加1 LinkList s=new LNode; //⽣成新结点s->data=e;s->next=p->next; //插⼊L中p->next=s;return ok;}Status ListDelete(LinkList &L,int i,ElemType &e) // 删除{ LinkList p=L;LinkList q;int j=0;while(p->next&&j{ //寻找第i个结点，并令p指向其前驱 p=p->next;++j; }if(!(p->next)||j>i-1) return error; //删除位置不合理q=p->next;p->next=q->next; //删除并释放结点e=q->data;delete(q);return ok;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) { //合并两个顺序链表LinkList pa,pc,pb; pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; }else{ pc->next=pb;pc=pb;pb=pb->next; }}pc->next=pa?pa:pb;delete(Lb);}void show(LinkList L) //显⽰{ LinkList p;p=L->next;while(p){ cout<data<<"-->";p=p->next; }cout<}int Length(LinkList L,int i) //表长{ i=0;LinkList p=L->next;while(p){ ++i;p=p->next; }return i;}void xiugai(LinkList L) //修改{ int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输⼊要修改的元素位置(0 cin>>i;GetElem(L,i,e);cout<<"该位置的元素:"<cout<<"修改后的元素值:";cin>>k;while(p&&j{ p=p->next;++j; }m=p->data;p->data=k;cout<<"修改后的单链表显⽰如下:"< show(L);}void hebing() //合并两个单链表{ int a,b;LinkList La,Lb,Lc;cout<<"请输⼊第⼀个有序链表的长度:"<cin>>a;cout<<"请输⼊第⼀个有序链表的元素共（"< CreateList(La,a);show(La);cout<<"请输⼊第⼆个有序链表的长度:"< cin>>b;cout<<"请输⼊第⼆个有序链表的元素共（"< CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下："<show(Lc);}void main() //主函数{ int select;int x;ElemType y;LinkList list;for(;;){ cout<<"单链表的基本操作"<cout<<"1.单链表的创建"<cout<<"2.单链表的显⽰"<cout<<"3.单链表的长度"<cout<<"4.插⼊元素到单链表⾥"<cout<<"5.删除单链表⾥的元素"<cout<<"6.合并两个单链表"<cout<<"7.退出系统"<cout<<"请选择:";cin>>select;switch(select){ case 1:cout<<"请输⼊单链表的长度:"< cin>>x;cout<<"请输⼊"<CreateList(list,x);break;case 2: cout<<"单链表显⽰如下:"<show(list);break;case 3: int s;cout<<"单链表的长度为:"<break;case 4: cout<<"请选择要插⼊的位置:"; cin>>x; while(x<0||x>Length(list,s)){ cout<<"输⼊有误，请重新输⼊"<cout<<"请选择所要插⼊元素的位置:"; cin>>x; }cout<<"要插⼊的元素值:";cin>>y;LinkInsert( list,x,y);cout<<"插⼊后单链表显⽰如下:"<show(list);break;case 5: cout<<"请选择要删除的位置:"; cin>>x; while(x<0||x>Length(list,s)){ cout<<"输⼊有误，请重新输⼊"<cout<<"请选择所要删除元素的位置:"; cin>>x; }ListDelete(list,x,y);cout<<"要删除的元素值:"<cout<<"删除后的单链表显⽰如下:"<show(list);break;case 6: hebing();break;case 7: exit(0);break;default : cout<<"输⼊有误，请重新输⼊"< break;}}}四、实验结果：顺序表链表。

计算机体系结构课程设计学院：信息科学与工程学院专业班级：指导老师：学号：姓名：目录实验 1 对指令操作码进行霍夫曼编码 (3)一、实验目的 (3)二、实验内容 (3)三、设计思路 (4)四、关键代码 (4)五、实验截图 (5)六、源代码 (5)实验 2 使用LRU 方法更新Cache (8)一、实验目的 (8)二、实验内容 (8)三、设计思路 (9)四、程序截图 (9)五、实验代码 (9)实验总结 (16)参考文献 (16)实验1 对指令操作码进行霍夫曼编码一、实验目的了解和掌握指令编码的基本要求和基本原理二、实验内容1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。

与扩展操作码和等长编码进行比较。

2. 问题描述以及问题分析举例说明此问题，例如：P1P2P3P4P5P6P70.450.300.150.050.030.010.01下表所示：对此组指令进行HUFFMAN 编码正如下图所示：最后得到的HUFFMAN 编码如下表所示：P1P2P3P4P5P6P7 010110111011110111110111111最短编码长度为：H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95.要对指令的操作码进行HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行HUFFAM 编码。

此过程的难点构造HUFFMAN 树，进行HUFFAM 编码只要对你所生成的HUFFMAN 树进行中序遍历即可完成编码工作。

三、设计思路观察上图，不难看出构造HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。

2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。

3、在对链表进行排序，链表是否只有一个节点，是则HUFFAN 树构造完毕，否则继续做 2 的操作。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

算法分析与设计实验报告学院：信息科学与工程学院专业班级：物联网工程1301班指导老师：向瑶学号：姓名：目录实验一 ----------------------------------------3 实验目的 -----------------------------------------3 实验内容 -----------------------------------------3实验原理及部分代码---------------------------------3实验结果 ------------------------------------------4 源代码-------------------------------------------4 实验二 ----------------------------------------7 实验目的 -----------------------------------------7 实验内容 -----------------------------------------7实验原理及部分代码---------------------------------7实验结果 ------------------------------------------8 源代码-------------------------------------------8 实验三 ----------------------------------------10 实验目的 -----------------------------------------10 实验内容 -----------------------------------------10实验原理及部分代码---------------------------------10实验结果 ------------------------------------------11 源代码-------------------------------------------11 心得体会 -----------------------------------------14实验一递归与分治一、实验目的1、理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

实验一线性表的操作算法一、实验目的：1了解线性表的逻辑结构和存储结构，以及定义在逻辑结构上的各种基本运算2分别以数组和链表为存储结构，实现线性表的插入，删除，查找，排序，合并等操作二、实验内容：用C/C++语言编写程序，分别以数组和链表为存储结构，完成以下功能：1输入数据，创建一个线性表2可在线性表的任意位置插入新结点3可删除线性表的任意一个结点4可在线性表中查找结点5将线性表从小至大排序6将两个线性表合并三、详细设计：顺序表#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct { //结构体ElemType *elem;int length;int listsize;}SqList;SqList Lx;Status InitList_Sq(SqList &L) //分配空间{ L.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,ElemType e) //插入新元素{ int *q,*p;ElemType *newbase;if(i<1 || i>L.length+1) return ERROR;if(L.length>=L.listsize){ newbase=new ElemType[L.listsize+LISTINCREMENT];if(!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for (p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;return OK;}Status Listlength(SqList L) //长度{ int *p=L.elem; //判断线形表是否存在while(p){ return (L.length); }}Status GetElem(SqList L, int i,ElemType &e) //取元素{ if(i<1 || i>L.length)return ERROR;else{ e=L.elem[i-1];return e;}}void MergeList(SqList La,SqList Lb,SqList &Lc) //合并{ ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ ListInsert(Lc,++k,ai);++i; }else{ ListInsert(Lc,++k,bj);++j; }}while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void show(SqList L,int i) //显示{ int j;ElemType k;cout<<"顺序表显示如下:"<<endl;for(j=0;j<i-1;j++){ k=L.elem[j];cout<<k<<"->"; }if(j==i-1 && i>0){ k=L.elem[j]; cout<<k; }cout<<endl;}void create(SqList &L,int n) //输入元素{ int e;for(int i=0;i<n;i++){ cin>>e;L.elem[i]=e;L.length=i+1; }}Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除{ ElemType *p, *q;if(i<1 || i>L.length) return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p) *(p-1)=*p;--L.length;return OK;}Status Listxiugei(SqList &L,int i,ElemType &e) //修改{ if(i<1 || i>L.length)return ERROR;else{ L.elem[i-1]=e;return OK; }}void shuru(SqList &L1) //顺序表的创建{ int a;InitList_Sq(L1);cout<<"请输入顺序表的长度：";cin>>a;cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);}void shanchu(SqList &L1) //删除顺序表里的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>j; }ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);}void charu(SqList &L1) //插入元素到顺序表里{ int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>j; }cout<<"要插入的元素:";cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);}void hebing(SqList &L3) //合并两个顺序表{ SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输入第一个有序表的长度："; cin>>a;cout<<"请输入第一个有序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);cout<<"请输入第二个有序表的长度："; cin>>b;cout<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下："; show(L3,a+b);}void main() //主菜单{ int choice;for(;;){ cout<<"顺序表的基本操作"<<endl;cout<<"1.顺序表的创建"<<endl;cout<<"2.顺序表的显示"<<endl;cout<<"3.顺序表的长度"<<endl;cout<<"4.插入元素到顺序表里"<<endl;cout<<"5.删除顺序表里的元素"<<endl;cout<<"6.合并两个顺序表"<<endl;cout<<"7.退出系统"<<endl;cout<<"请选择：";cin>>choice;switch(choice){ case 1: shuru(Lx);break;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度:"<<Listlength(Lx)<<endl;break;case 4: charu(Lx);break;case 5: shanchu(Lx);break;case 6: hebing(Lx);break;case 7: cout<<"退出系统!"<<endl;exit(0);break;default : cout<<"输入有误，请重新选择"<<endl;break; }}}链表#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode //存储结构{ ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n) //尾插法创建单链表{ LinkList p;L=new LNode;L->next=NULL; //建立一个带头结点的单链表LinkList q=L; //使q指向表尾for(int i=1;i<=n;i++){ p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; }}Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素{ LinkList p=L->next;int j=1;while(p&&j<i){ p=p->next;++j; }if(!p||j>i) return error; //第i个元素不存在e=p->data;return ok;}Status LinkInsert(LinkList &L,int i,ElemType e) //插入{ LinkList p=L;int j=0;while(p&&j<i-1){ p=p->next;++j; } //寻找第i-1个结点 if(!p||j>i-1)return error; //i小于1或者大于表长加1 LinkList s=new LNode; //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;return ok;}Status ListDelete(LinkList &L,int i,ElemType &e) // 删除{ LinkList p=L;LinkList q;int j=0;while(p->next&&j<i-1){ //寻找第i个结点，并令p指向其前驱 p=p->next;++j; }if(!(p->next)||j>i-1) return error; //删除位置不合理q=p->next;p->next=q->next; //删除并释放结点e=q->data;delete(q);return ok;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) { //合并两个顺序链表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; }else{ pc->next=pb;pc=pb;pb=pb->next; }}pc->next=pa?pa:pb;delete(Lb);}void show(LinkList L) //显示{ LinkList p;p=L->next;while(p){ cout<<p->data<<"-->";p=p->next; }cout<<endl;}int Length(LinkList L,int i) //表长{ i=0;LinkList p=L->next;while(p){ ++i;p=p->next; }return i;}void xiugai(LinkList L) //修改{ int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输入要修改的元素位置(0<i<length):";cin>>i;GetElem(L,i,e);cout<<"该位置的元素:"<<e<<endl;cout<<"修改后的元素值:";cin>>k;while(p&&j<i){ p=p->next;++j; }m=p->data;p->data=k;cout<<"修改后的单链表显示如下:"<<endl;show(L);}void hebing() //合并两个单链表{ int a,b;LinkList La,Lb,Lc;cout<<"请输入第一个有序链表的长度:"<<endl;cin>>a;cout<<"请输入第一个有序链表的元素共（"<<a<<"个）："<<endl;CreateList(La,a);show(La);cout<<"请输入第二个有序链表的长度:"<<endl;cin>>b;cout<<"请输入第二个有序链表的元素共（"<<b<<"个）："<<endl;CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下："<<endl;show(Lc);}void main() //主函数{ int select;int x;ElemType y;LinkList list;for(;;){ cout<<"单链表的基本操作"<<endl;cout<<"1.单链表的创建"<<endl;cout<<"2.单链表的显示"<<endl;cout<<"3.单链表的长度"<<endl;cout<<"4.插入元素到单链表里"<<endl;cout<<"5.删除单链表里的元素"<<endl;cout<<"6.合并两个单链表"<<endl;cout<<"7.退出系统"<<endl;cout<<"请选择:";cin>>select;switch(select){ case 1:cout<<"请输入单链表的长度:"<<endl;cin>>x;cout<<"请输入"<<x<<"个元素"<<endl;CreateList(list,x);break;case 2: cout<<"单链表显示如下:"<<endl;show(list);break;case 3: int s;cout<<"单链表的长度为:"<<Length(list,s)<<endl;break;case 4: cout<<"请选择要插入的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>x; }cout<<"要插入的元素值:";cin>>y;LinkInsert( list,x,y);cout<<"插入后单链表显示如下:"<<endl;show(list);break;case 5: cout<<"请选择要删除的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>x; }ListDelete(list,x,y);cout<<"要删除的元素值:"<<y<<endl;cout<<"删除后的单链表显示如下:"<<endl;show(list);break;case 6: hebing();break;case 7: exit(0);break;default : cout<<"输入有误，请重新输入"<<endl;break;}}}四、实验结果：顺序表链表。

中南大学计算机实践报告中南大学计算机实践报告中南大学本科生课程设计(实践)任务书、设计报告（计算机程序设计基础FORTRAN）题目线性方程组求解问题学生姓名指导教师学院专业班级学生学号刘卫国土木工程学院土建类班计算机基础教学实验中心202*年6月29日一、实践目的通过本课程设计，培养程序设计能力以及综合解决实际问题的能力。

通过自己分析问题、寻求算法、编写、调试程序的过程，掌握FORTRAN程序设计与调试方法，提高灵活运用所学知识解决问题的能力。

二、设计任务线性病态方程组问题：1/21/31/4x10.951/31/41/5x0.6721/41/51/6x30.52（1）求方程的解。

（2）将方程右边向量元素b3改为0.53，再求解，并比较b3的变化和解的相对变化。

（3）计算系数矩阵A的条件数并分析结论。

提示：矩阵A的条件数等于A的范数与A的逆矩阵的范数的乘积，即cond(A)AA1。

这样定义的条件数总是大于1的。

条件数越接近于1，矩cond(A)AA1阵的性能越好，反之，矩阵的性能越差。

矩阵A的条件数Amax{aij}1jni1m，其中，aij系矩阵A的元素。

要求：（1）方程的系数矩阵、常数向量均从文件中读入。

（2）定义求解线性方程组Ax=b的子程序，要求该子程序能求解任意线性方程组。

（3）在主程序中调用子程序，并对求解结果进行对比分析。

（4）绘制常数向量修改前后所求得的方程解的数据分布图。

三系统坏境系统开发环境为CONSOLEAPPLICAT三．系统功能及系统详细设计四系统功能及系统详细设计。

系统功能分析针对题目要求，我设计的系统主要为了解决题目中所提出并要求的问题。

子程序则各尽其用，不仅可以作为整体系统的重要部分，还可以使用于通用问题。

如三角分解法，可以解决线性方程组的求解问题。

求范数和矩阵求逆的子程序，可以解决相应的问题。

再如绘图程序，将问题(2)的结果直观化，更直观明显的表现了病态方程的特点与定义。

中南大学自动化专业离散数学实验报告2离散数学作为计算机科学与技术专业的基础课程之一，对于培养学生的逻辑思维和抽象思维能力具有重要意义。

本次实验是关于离散数学中的图论部份，通过实际操作和计算来理解和应用图的相关概念和算法。

实验一开始，我们首先学习了图的基本概念和术语，例如顶点、边、路径、回路等。

然后，我们学习了图的表示方法，包括邻接矩阵和邻接表。

通过实际操作，我们发现邻接矩阵适合表示稠密图，而邻接表适合表示稀疏图。

这种不同的表示方法对于图的遍历和搜索算法有着重要的影响。

接下来，我们进行了图的遍历实验。

通过深度优先搜索和广度优先搜索算法，我们可以遍历图中的所有节点，并找到特定节点之间的路径。

深度优先搜索算法通过递归的方式进行，它会首先访问一个节点的所有邻接节点，然后再递归地访问这些邻接节点的邻接节点。

广度优先搜索算法则是通过队列的方式进行，它会首先访问一个节点的所有邻接节点，然后将这些邻接节点按照访问的顺序加入队列中，再逐个出队进行访问。

通过实验，我们发现深度优先搜索算法更适适合于寻觅路径，而广度优先搜索算法更适适合于寻觅最短路径。

在实验的后半部份，我们学习了最小生成树和最短路径算法。

最小生成树算法用于找到一个连通图的最小生成树，其中包含了连接图中所有节点的最短路径。

我们学习了Prim算法和Kruskal算法，它们分别基于贪心算法和并查集来实现。

通过实验，我们发现Prim算法适适合于稠密图，而Kruskal算法适适合于稀疏图。

最短路径算法用于找到两个节点之间的最短路径，我们学习了Dijkstra算法和Floyd算法。

Dijkstra算法通过贪心策略逐步更新节点之间的最短路径，而Floyd算法则通过动态规划的方式计算所有节点之间的最短路径。

通过实验，我们发现Dijkstra算法适适合于稀疏图，而Floyd算法适适合于稠密图。

总结起来，本次实验让我们深入了解了离散数学中的图论部份，并通过实际操作和计算来应用图的相关概念和算法。

算法分析与设计实验报告学院：信息科学与工程学院专业班级：物联网工程1301班指导老师：向瑶学号：姓名：目录实验一 ----------------------------------------3 实验目的 -----------------------------------------3 实验内容 -----------------------------------------3实验原理及部分代码---------------------------------3实验结果 ------------------------------------------4 源代码-------------------------------------------4实验二 ----------------------------------------7 实验目的 -----------------------------------------7 实验内容 -----------------------------------------7实验原理及部分代码---------------------------------7实验结果 ------------------------------------------8 源代码-------------------------------------------8实验三 ----------------------------------------10实验目的 -----------------------------------------10实验内容 -----------------------------------------10实验原理及部分代码---------------------------------10实验结果 ------------------------------------------11源代码-------------------------------------------11心得体会 -----------------------------------------14实验一递归与分治一、实验目的1、理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

实验七1.需求分析本实验目的是使读者，掌握常用排序方法的基本思想，通过实验加深理解各种排序算法，通过实验掌握各种排序方法的时间复杂度分析，了解各种排序方法的优缺点及适用范围。

1．排序算法的实现（设计性实验）问题描述排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。

它的功能是将一个数据元素的任意序列重新排列成一个按键有序的序列。

学习和研究各种排序方法是计算机工作者的一项重要工作课题。

基本要求随机产生n个整数（依次为n赋值100、200、300、1 000和2 000），将其存于数组A[1..n]中。

对主要算法（顺序查找、插入排序、归并排序、堆排序和快速排序）进行实验比较，计算出平均比较次数c n、平均移动次数m n及执行时间t n。

c n和m n由程序自动计算，t n由系统时间计算。

对实验结果数据进行对比分析。

测试数据由随机数生成器决定。

实现提示(1) 设计一个驱动程序，其任务是，随机输入一组原始数据A[1..n]，对于查找还需准备一个键码值（可以随机产生，也可在A[1..n]中按索引号挑选若干有代表性的数据）。

对每组原始数据，分别调用查找或排序算法过程。

(2) 为了自动计算c n和m n需要在每个算法过程中的适当位置插入计数操作。

手工计算每个算法的执行时间t n时，为了减少计时误差，删除所插入的计数操作，并按n的大小确定一个K，对每个查找或排序算法过程反复调用K次，在调用开始前设置一个计时起点t0，在K次调用执行后可打印信息。

设计时的终点为t1，则(t1t0)/K便是算法的大致执行时间。

选作内容对不同的输入表长做试验，观察含义相同的变量相对于表长的变化关系，还可以对稳定性做验证。

2．统计成绩（综合性实验）问题描述给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名及各科成绩组成。

对学生的考试成绩进行有关统计，并打印统计表。

基本要求(1) 按总数高低次序，打印出名次表，分数相同的为同一名次。

“人工智能”实验报告专业自动化班级 09级学号姓名日期：2011.12目录一、实验八自动规划实验群 (3)二、实验一生产式系统实验群 (6)三、实验二搜索策略实验群 (7)四、实验七神经网络 (9)五、实验心得和体会 (10)实验八自动规划实验群姓名班级指导老师日期2011.12实验目的熟悉和掌握自动规划的基本原理,方法和主要技术。

实验原理规划是一种问子题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。

简而言之，规划是一个行动过程的描述。

一个总规划可以含有若干个子规划。

实验环境转载相关源文件实验环境转载相关源文件实现过程单步观察实验算法算法结果分析观测结果通过规定规则，确定initial state和goal state，使得移动臂按照规则进行移动。

分别进行clear holding pickup putdown putdowntable等实现对木块的移动。

实现过程先进行逆向推理选择，找出途径后再进行移动。

学生结论对于不同的规则将会出现不同的移动过程。

通过规定不同的动作可实现不通过的移动。

实验一生产式系统实验群姓名指导老师日期2011.12实验目的熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。

推理方法逆向推理建立规则库建立事实库该动物是哺乳动物<- 该动物有毛发.该动物是哺乳动物<- 该动物有奶.该动物是鸟<- 该动物有羽毛.该动物是鸟<- 该动物会飞&会下蛋.该动物是食肉动物<- 该动物吃肉.该动物是食肉动物<- 该动物有犬齿&有爪&眼盯前方.该动物是有蹄类动物<- 该动物是哺乳动物&有蹄. 该动物是有蹄类动物<- 该动物是哺乳动物& 是嚼反刍动物.该动物是金钱豹<- 该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.该动物是虎<- 该动物是哺乳动物&该动物是食肉动物&是黄褐色&身上有黑色条纹.该动物是长颈鹿<- 该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.该动物是斑马<- 该动物是有蹄类动物&身上有黑色条纹.该动物是鸵鸟<- 该动物是鸟&有长脖子&有长腿&不会飞&有黑白二色.该动物是企鹅<- 该动物是鸟&会游泳&不会飞&有黑白二色.该动物是信天翁<- 该动物是鸟&善飞. %------动物识别系统事实集：%会游泳. %--该动物是企鹅%不会飞.%有黑白二色.%该动物是鸟.%-------- %--该动物是鸟%该动物会飞.%会下蛋.%----该动物是金钱豹<- 该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.%该动物有毛发.%是食肉动物.%是黄褐色.%身上有暗斑点.%----该动物是虎<- 该动物是哺乳动物&该动物是食肉动物&是黄褐色&身上有黑色条纹.%该动物是哺乳动物.%是食肉动物.%是黄褐色.%身上有暗斑点.%----该动物是长颈鹿<- 该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.%该动物是有蹄类动物.%有长脖子.%有长腿.%身上有暗斑点.预测结果假设目标为该动物是金钱豹，则结果为true.实验过程及结果(注意观测规则的匹配过程和方法) （1）假设这个动物是金钱豹。

人工智能实验报告学院：专业班级：指导老师：学号：姓名：第一次实验：搜索策略1.节点静态图（Node1为起点，Node0为终点）2.DFS搜索策略：当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

属于盲目搜索。

搜索结果前四步open表和close表的变化3.BFS搜索策略：BFS并不使用经验法则算法。

从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。

依次对出队的结点进行搜索，直至找到目标节点搜索结果前四步open表和close表的变化4.Lowest cost first搜索策略：类似于BFS，但在搜索结点时，并不按照队列的顺序进行搜索，而选取队列中与起始结点距离最近的结点进行搜索。

搜索结果前四步open表和close表的变化5.best first搜索策略：最佳优先搜索通过扩展最有可能到达目标节点的节点，根据指定的规则，探索一个图。

搜索结果前四步open表和close表的变化6.层次深度优先搜索策略：令k=1，进行k层的深度优先搜索，如果没有找到目标，则k+1，进行k+1层的深度优先搜索，以此类推。

搜索结果前四步open表和close表的变化7.A*算法搜索策略：A*[1]（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。

公式表示为：f(n)=g(n)+h(n),其中f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

计算机操作系统实验报告学院：信息科学与工程学院专业班级：信息安全1302班指导老师：郁博文学号：0906130205计算机操作系统1.设计目的1、增强学生对计算机操作系统基本原理、基本理论、基本算法的理解；2、提高和培养学生的动手能力。

2.设计要求1、每人至少选作1题，多做不限；2、每人单独完成，可以讨论，但每人的设计内容不得完全相同，抄袭或有2人/多人设计完全一样者，不能通过；3、设计完成后，应上交课程设计文档，文档格式应是学校课程设计的标准格式，所有学生的封面大小、格式也必须一样；4、同时上交设计的软盘(或以班刻录光盘)。

3.设计题目调度算法的模拟：模拟各种调度算法，并进行调度性能分析。

4.设计过程4.1 设计思路模拟了一个作业调度算法，其中用到了先来先服务算法（FCFS）、短作业优先算法（SJF）、最高响应比优先算法（HRN）三种算法。

如下，分别为三种算法的程序流程图。

4.2 实验过程图1 - 开始界面图2 –输入作业的信息（名字、提交时间、运行时间）图3 –选择算法（FCFS、SJF、HRN）图4、5 – 选择FCFS 算法后输出结果图6、7 – 选择SJF 算法后输出结果图8、9 – 选择HRN 算法后输出结果4.3 调度性能分析1.先来先服务算法（FCFS）优点：能体现公平性；缺点：一旦一个较长的作业进入系统后就会长时间的占用系统的资源，这样如果有优先级较高的短作业需要执行的话需要等待很长时间。

2.短作业优先算法（SJF）优点：比前者改善了平均周转时间和平均带权周转时间，缩短作业的等待时间，提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不到执行，未能一句作业的紧迫程度来划分执行的优先级，难以准确估计作业的执行时间，从而影响调度性能。

3.最高响应比优先算法（HRN）优点：这种算法是对FCFS方式和SJF方式的一种综合平衡。

FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。

CENTRAL SOUTH UNIVERSITY编译原理实验报告学生姓名专业班级学号学院信息科学与工程学院指导教师张修如实验时间 2015年5月实验一计算FIRSTVT集一、实验目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC /JA V A/C#/.NET 。

二、实验内容设计一个由正规文法生成FIRSTVT集的算法动态模拟，实现以下功能：1．输入一个文法G；2．输出由文法G构造FIRSTVT集的算法；3．输出FIRSTVT集。

三、实验要求1．思想的正确性，采用合适的数据存储结构等；2．程序实现的正确性，程序整体结构合理、编程风格规范等；3．程序功能的完善程度，包括功能的基本实现、基本完善、完全实现；4．工作认真、独立完成实验。

四、实验步骤1．问题理解和分析：充分地分析和理解问题本身，弄清要求做什么；2．确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；3．详细设计和编码：确定算法的主要流程，再进行编程；4．程序调试和运行：掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感；5．完成实验报告。

五、程序设计5.1基本算法构造集合FIRSTVT(P)的算法按FIRSTVT(P)的定义，可以用如下两条归则来构造：(1)若有产生式P→a…或→Qa…，则a∈FIRSTVT(P)(2)若a∈FIRSTVT(Q)，且有产生式P→Q…，则a∈FIRSTVT(P)构造算法：建立一个二维布尔数组F[P,a]，使得F[P,a]为真的条件适当且仅当a∈FIRSTVT(P)；再用一个栈STACK，把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放到栈中；算法如下：(1)将布尔矩阵各元素置假；栈置空；(2)按照归则(1)查看产生式，对于P→a…或P→Qa..，置相应F[P,a]为真，符号对(P,a)入栈；(3)按规则(2)，对栈施加如下操作：弹出栈定符号对记作(Q,a)，查看所有产生式是否有形如P→Q…产生式，若有，且a∈FIRSTVT(P)，则将F[P,a]置为真，并把(P,a)入栈；(4)重复(3)，直到栈空为止。

中南大学《计算机网络》实验报告学生姓名学号专业班级指导教师桂劲松学院信息科学与工程学院完成时间 2011年１月模拟路由算法的实现一、实验内容1.模拟距离向量路由算法的路由表交换过程，演示每轮交换后路由表的变化。

2．实现链路状态路由算法中的最短路径算法。

二、实验目的及要求本实验是计算机网络课程的实践性锻炼环节。

通过实验,帮助学生更好地掌握网络通信协议的实现技术，锻炼学生应用高级编程语言完成通信编程的能力，使学生加深对网络协议本质的理解，巩固课堂所学的理论知识。

要求实验者利用路由选择算法模拟软件提供的通信功能，模拟链路状态路由选择算法的初始化、路由信息扩散过程和路由计算方法;掌握链路状态算法的路由信息扩散过程;掌握链路状态算法的路由计算方法。

三、实验原理编程语言： JＡＶA编程工具: MｙEclipsｅ实验实现方式：单机模拟实现核心方法:dijkｓtra算法计算最短路径分析：布置好各个模拟路由，以及路由的路程权值如何获取。

接着就是核心算法的实现,如何计算任意两个路由之间的最短路径问题。

用到的是dijkｓtra算法。

Ｄijkｓtra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径，首先，它求出从起点到最接近起点的顶点之间的最短路径,然后求出第二近的,一次类推,推而广之,再第i次迭代开始之前，算法已经确定了ｉ-1条连接起点和离起点最近顶点之间的最短路径。

这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一颗子树Ti,因为所有边的权值都是非负数,可以从与Tｉ的顶点相邻的顶点中找到下一个和起点最接近的顶点。

和Ti的顶点相邻的顶点的集合称为“边缘顶点”,以他们为候选对象，Diｊkｓtra算法可以从中选出一个最接近起点的顶点。

为了确定第I个最接近的顶点，对于每一个边缘顶点u,该算法求出它到最近的树中顶点v的距离以及从起点到v得最短路径长度dv的和，再从中选出具有最小和的顶点。

此次实验主要是运用路由算法来处理路由当中的一些问题，利用Ｄｉjkstra 算法处理最短路径的问题，在实验中这点已经得到了充分地体现。

算法设计与分析基础——实验报告姓名：学号：0909122824班级：信安1202实验一分治—最近点对一．问题ProblemHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.InputThe input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.二．分析思路题目是给n个点的坐标，求距离最近的一对点之间距离的一半。

“离散数学”实验报告(实验2AC)专业班级学号姓名日期：目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现进程（算法描述） (3)A题型 (3)C题型 (4)五、实验数据及结果分析 (7)A题型 (7)B题型 (9)六、源程序清单 (11)A题型 (11)B题型 (12)七、其他收成及体会 (18)一、实验目的把握关系的概念与性质，大体的关系运算，关系的各类闭包的求法。

明白得等价类的概念，把握等价类的求解方式。

二、实验内容1. 求有限集上给定关系的自反、对称和传递闭包。

（有两种求解方式，只做一种为A，两种都做为B）2. 求有限集上等价关系的数量。

（有两种求解方式，只做一种为A，两种都做为B）3. 求解商集，输入集合和等价关系，求相应的商集。

（C）三、实验环境C或C＋＋语言编程环境实现。

四、实验原理和实现进程（算法描述）A题型求有限集上等价关系的数量。

集合上的等价关系与该集合的划分之间存在一一对应关系。

一个等价关系对应一个划分，一个划分也对应一个等价关系。

咱们把n个元素的集合划分成k 块的方式数叫第二类Stirling数，表示为S(n,k)。

给定S(n,n) = S(n,1) = 1，有递归关系：S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)集合上所有等价类的个数即为k从1到n，所有S(n,k)之和。

那个问题的算法比较简单，仅需两步就可完成，第一依照上式，概念一个递归函数S（n,k），然后对k从1到n，求取sum=∑S（n，k），sum的值确实是给定n元集合上的等价关系数量，最后将其输出即可。

A题型的流程图如下所示：C题型求解商集，输入集合和等价关系，求相应的商集商集即等价类组成的集合，要求商集，第一需要判定输入的关系是不是为等价关系，不然没有商集。

判定输入的关系是不是为等价关系的算法如下：(1)将输入的关系转换为关系矩阵，那个地址概念了一个函数translate()，转换的方式为：依次查找输入的关系中的二元组的两个元素在集合中的位置，例如<a，b>，假设a在集合A中的位置为i，b在集合A中的位置为j，就令寄存关系矩阵的二维数组M[i][j]=1,如此就将输入的关系R转换为关系矩阵的形式。

“离散数学”实验报告(实验3ABC)专业班级学号姓名日期: 2011.12.19目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现过程（算法描述） (3)1实验原理 (3)2实验过程 (5)五、实验数据及结果分析 (6)六、源程序清单 (10)七、其他收获及体会 (16)一、实验目的理解图论的基本概念, 图的矩阵表示, 图的连通性, 图的遍历, 以及求图的连通支方法。

二、实验内容以偶对的形式输入一个无向简单图的边, 建立该图的邻接矩阵, 判断图是否连通（A）。

并计算任意两个结点间的距离（B）。

对不连通的图输出其各个连通支（C）。

三、实验环境C或C＋＋语言编程环境实现。

四、实验原理和实现过程（算法描述）1.实验原理（1）建立图的邻接矩阵, 判断图是否连通根据图的矩阵表示法建立邻接矩阵A, 并利用矩阵的乘法和加法求出可达矩阵, 从而判断图的连通性。

连通图的定义: 在一个无向图G 中, 若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径), 则称vi和vj是连通的。

如果G 是有向图, 那么连接vi 和vj的路径中所有的边都必须同向。

如果图中任意两点都是连通的, 那么图被称作连通图。

判断连通图的实现：在图中, 从任意点出发在剩余的点中, 找到所有相邻点循环, 直到没有点可以加入为止, 如果有剩余的点就是不连通的, 否则就是连通的。

或者也可用WallShell算法, 由图的邻接矩阵判断图是否连通。

（2）计算任意两个结点间的距离图中两点i, j间的距离通过检验Al中使得aij为1的最小的l值求出。

路径P中所含边的条数称为路径P的长度。

在图G<V,E>中, 从结点Vi到Vj最短路径的长度叫从Vi到Vj的距离, 记为d<Vi, Vj>。

设图的邻接矩阵是A, 则所对应的aij的值表示, 点Vi到点Vj距离为n的路径有aij条。

若aij(1), aij(2), …, aij(n-1), 中至少有一个不为0, 则可断定Vi与Vj可达, 使aij(l)≠0的最小的l即为d(Vi, Vj)。

中南大学c 课程设计实践报告一、教学目标本课程的教学目标是使学生掌握中南大学C课程的核心知识，包括基本概念、原理和应用。

具体目标如下：1.知识目标：学生能够准确理解并掌握C语言的基本语法、数据类型、运算符、控制结构、函数等基本知识。

2.技能目标：学生能够熟练运用C语言进行程序设计，包括编写、调试和运行C程序。

3.情感态度价值观目标：培养学生对计算机科学的兴趣和热情，提高学生的问题解决能力和创新意识。

二、教学内容根据教学目标，本课程的教学内容主要包括以下几个方面：1.C语言的基本语法和数据类型，包括变量、常量、数据类型、运算符等。

2.控制结构，包括条件语句、循环语句等。

3.函数，包括函数的定义、声明、调用和返回值等。

4.指针和数组，包括指针的概念、指针的运算、数组的基本操作等。

5.结构体和文件操作等高级内容。

三、教学方法为了达到教学目标，本课程将采用多种教学方法，包括：1.讲授法：通过教师的讲解和演示，使学生掌握C语言的基本知识和技能。

2.讨论法：通过小组讨论和课堂讨论，激发学生的思考和问题解决能力。

3.案例分析法：通过分析实际案例，使学生了解C语言在实际应用中的作用和意义。

4.实验法：通过编写和调试C程序，培养学生的实际编程能力和问题解决能力。

四、教学资源为了支持教学内容和教学方法的实施，本课程将使用以下教学资源：1.教材：选择一本适合学生水平的C语言教材，作为学生学习的主要参考资料。

2.参考书：提供一些相关的参考书籍，供学生进一步深入学习和参考。

3.多媒体资料：制作一些教学PPT、视频等多媒体资料，帮助学生更好地理解和掌握知识。

4.实验设备：提供计算机实验室，让学生能够进行实际编程和实验操作。

五、教学评估本课程的评估方式包括平时表现、作业和考试等。

具体评估方式如下：1.平时表现：通过学生的课堂参与、提问、回答问题等方式评估学生的学习态度和理解程度。

2.作业：布置适量的作业，包括编程练习和理论题目，以巩固学生对知识的理解和应用能力。