河北工业大学数据结构.doc

河北工业大学数据结构课程实验实 验 报 告题目： Joseph问题求解算法的设计与实现 专业： 计算机 班级： 计8888 姓名：wangdachui 完成日期： 2015/1/10 一、试验内容 编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。2、 试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。三、流程图输入总人数创建并初始化n个节点输入第一个报的数keyn=0 Y 报数过程 N输出出列者的编号及密码 结束 n-四、源程序代码#include#includestruct list int num,code; struct list *next; ; void main() printf(Joseph问题求解算法的设计与实现n n);int i,j,m=1;int key; / 密码.int n; /人数 .list *p,*s,*head;head=(list *)malloc(sizeof(list); /为头结点分配空间.p=head; printf(输入人的总个数:); scanf(%d,&n); for(i=1;inext=p; p-num=i; p-code=key; p-next=head-next; p=head;head=head-next;free(p);p=head; printf(nn输入第一个报的数:n); scanf(%d,&key);printf(n出列顺序为:n);for(;n0;n-)p=head;for(j=1;jnext; /报数过程i=p-num; key=p-code; printf(第%d号成员出列n,i); s-next=p-next; head=p-next; /重新定义head,下次循环的开始结点.free(p);/ 释放已出列的结点. 五、调试过程 m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。6、 结果分析河北工业大学数据结构课程实验实 验 报 告题目： 实验二 停车场管理 专业： 计算机 班级： 计7777 姓名：doubi 完成日期： 2015/1/10 一、试验内容 设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已经停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出场为它让路，待该辆车开出大门外，其他车辆再按次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用二、试验目的（1）深入了解栈和队列的特性，掌握栈和队列的存储方法。 （2）掌握栈和队列的基本操作，如初始化、入栈（队列）、出栈（队列）等，并能在实际问题背景下灵活运用。 输入数据3、 流程图 判断 车离开 m=e|m=E 车到Qn?Y存在便道存在停车场 N车的位置 便道离开车场最后一位后面车后退付费离开 Y 结束便道内车进场4、 源程序代码#includevoid main() struct chechangint hm1,sk1;a5; /停车场struct biandaoint hm2,sk2;b5; /便道struct tuichuint hm3,sk3;c4; /存放从停车场内退出的车 int p=0,q=0,x=0,n,y,t,r,i,j,g,h,z;char m;printf(输入停车场容量和每分钟收费n);scanf(%d%d,&n,&y);printf(输入数据:n);for(;)scanf(%c,&m);/判断输入数据if(m=e|m=E) break;scanf(%d%d,&t,&r); /t表示车牌号，r表示时间/车到达if(m=a|m=A)if(pn) /n表示停车场容量，p表示场内车的数量ap.hm1=t;ap.sk1=r;printf(车停在停车厂内%d号位置.n,p+1);p+;/车停在便道内elsebq.hm2=t;bq.sk2=r;printf(车停在便道上%d号位置.n,q+1);q+;/车离开if(m=d|m=D)h=p;for(i=0;ii;j-)cx.hm3=aj.hm1;cx.sk3=aj.sk1;x+;printf(%d号车在停车厂内停留了%d分钟,应交纳%d元钱.n,t,r-ai.sk1,y*(r-ai.sk1);for(j=i;x-1=0;x-,j+) /退出的车再进入停车场内aj.hm1=cx-1.hm3;aj.sk1=cx-1.sk3;if(q!=0) /便道内的车进入停车场ap.hm1=b0.hm2;ap.sk1=r;p+;for(j=0;jq-1;j+)bj.hm2=bj+1.hm2;bj.sk2=bj+1.sk2;q-;break; /判断车是否停在便道上for(i=0;iq;i+,z=q) if(bi.hm2=t) printf(该车停留在便道内,不收费.n); for(j=i;jq-1;j+) bj.hm2=bj+1.hm2; bj.sk2=bj+1.sk2; q-; break; if(g=h&i=z) printf(无该车.n); 五、调试过程 设n=2，输入数据为：（A，1，5）， （A，2，10）， （D，1，5）， （A，3，20）， （A，4，25）， （A，5，30）， （D，2，35）， （D，4，40）， （E，0，0）。其中：A表示到达（Arrival），D表示离去（Departure），E表示输入结束（End）。六、结果分析河北工业大学数据结构课程实验实 验 报 告题目：基于哈夫曼编码的通信系统的设计与实现 专业： 计算机 班级： 888 姓名：帅哥 完成日期： 2015/1/10 实验三 基于哈夫曼（Huffmen）编码的通信系统的设计与实现一、试验内容 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。二、试验目的（1）掌握二叉树的存储结构及其相关操作。（2）掌握构造哈夫曼树的基本思想，及其编码/译码过程。三、流程图开始三、流程图判断输入编码字符及编码长度进行哈弗曼编码输入要传送的信息对接收到的信息进行编码结束开始构造哈弗曼树：第i个结点值I=num？ 否 是第i个根结点 I=2*num-1? 否 是创建哈弗曼树输出字符统计情况I=num？ 否结束 是四、源程序代码#include #include #include char *codechar;int ncodechar,lcodechar; int *arraychar100; char *temp; float *proba; char pass50; int passl; struct node float pro; int num; struct node* p; struct node* lc; struct node* rc; char *res; int length; *hc;char message10010= 一二三四,五六七八,王岐山地,古古怪怪,弹道导弹,自作主张,发古古怪,曾经沧桑,雷天舞也,杯水车薪,铩羽而归,不卑不亢,一石二鸟,定还深圳,定海神针,各门庭若市,黑暗之女,我甲方发,意气风发,老当益壮,宁一摆手,情切意见,不坠青云,找而亡木,安土重迁,不可一世,大海捞针,秋后蚂蚱,饮酒作诗,玩玩小河,众望所归,无可挑剔,不以为意,冉冉升起,大大咧咧,交定金的,等级低价,打击哦啊,宿建德江,本身就是,鼠年大吉,都没看完,的大客车,大男大女,石大酒店,多么多么,多么多的,电脑的事,啊加拿大,名的的的,期咯看过,洋是你的,发怒分意,时间就贷,名发个备,时候的的,马上开始,的那女的,积分是是,神将世界,顺利交付,是不是是,设计师是,是什么是,咯就的唳,是假的发,秘书部是,膜科技是,是你是是,名啊啊是,农场盗匪,不可意识,心你吗马,岁月江海,尸好啊发,哈弗发人,鬼时间发,不耻上问,应接与暇,你好发班,吃吃的额,几何体发,人员人我,偶就个发,三日不绝,金口雨燕,哈弗是额,千万尔好,看逻辑框,耳濡目染,付人额额,觉得萨就,安静了放,德克士哦,阿婆日怒,阿呆和费,安徽人人,瑞尔富发,垃圾坑啊,恶如日俄,;int zifushengcheng()int i,j=0,k=0,yushu,x; int *b100; for(i=0;i100;i+) bi=(int *)malloc(sizeof(int)*lcodechar); for(j=0;jlcodechar;j+) bij=0; for(i=0;i=0;j-,k+) arraycharik=bij; j=0; k=0; for(i=0;i100;i+) for(j=ncodechar;jlcodechar;j+) arraycharij=rand()%ncodechar; /*for(i=0;i100;i+) for(j=0;jlcodechar;j+) printf(%d ,arraycharij); printf( ); for(j=0;jlcodechar;j+) printf(%c,codechararraycharij); printf(n); */return 1;int probability()int i,j,k;for(i=0;i100;i+)for(j=0;jlcodechar;j+)for(k=0;kncodechar;k+)if(arraycharij=k)probak+;printf(随机生成的字符编码概率:n);for(i=0;ipro;a-pro=b-pro;b-pro=t;Exchangenum(&a-num,&b-num);Exchangepoint(&a-p,&b-p);Exchangepoint(&a-lc,&b-lc);Exchangepoint(&a-rc,&b-rc);return 1;int produce(struct node*a,int *b)int i;a-length=(*b);a-res=(char *)malloc(sizeof(char)*(*b);for(i=0;iresi=tempi;if(a-lc!=NULL&a-rc!=NULL)temp(*b)=0;(*b)+;produce(a-lc),b); temp(*b)=1;(*b)+;produce(a-rc),b);(*b)-;return 1;int huffman() /哈夫曼主程序int i,j,k,l=0;for(i=0;i(ncodechar*2-1);i+)hci.lc=NULL;hci.rc=NULL;hci.p=NULL;hci.num=i;if(incodechar)=probai;continue; =0; for(i=0;incodechar-1;i+) for(j=i*2;j(ncodechar+i);j+) for(k=j+1;k(ncodechar+i);k+) if(&!=0) Exchange(&hck,&hcj); hci+=hci*2.pro+hci*2+1.pro; hci+ncodechar.lc=&hci*2; hci+ncodechar.rc=&hci*2+1; hci*2.p=&hci+ncodechar; hci*2+1.p=&hci+ncodechar; printf(n构造的哈夫曼树:); for(i=0;inum); printf( rc:); if(hci.rc=NULL) printf( ); else printf(%d,hci.rc-num);printf( p:);if(hci.p=NULL)printf( );elseprintf(%d,hci.p-num);produce(&hcncodechar*2-2,&l);printf(n生成的哈夫曼编码是:n);for(i=0;incodechar*2-1;i+)printf(nchar:%cnum:%dlength:%dcode:,codecharhci.num,hci.num,hci.length);for(j=0;jhci.length;j+)printf(%c,hci.resj);return 1;int sent()int i,j,k,x;printf(n*发送方*n);for(i=0;i100;i+)printf(%d:,i+1);for(j=0;j20;j+)printf(%c,messageij);printf( 相应的字符编码:);for(k=0;klcodechar;k+)printf(%c,codechararraycharik);printf(n);printf(输入你的信息号:);scanf(%d,&x);printf(你选择发送的信息是:);for(j=0;j20;j+)printf(%c,messagex-1j);printf(n相应的字符编码是:);for(i=0;ilcodechar;i+)printf(%c,codechararraycharx-1i);printf(n根据哈夫曼树得到的哈夫曼编码是:);for(i=0;ilcodechar;i+)for(j=0;jncodechar*2-1;j+)if(arraycharx-1i=hcj.num)for(k=0;khcj.length;k+)printf(%c,hcj.resk);passpassl=hcj.resk;passl+;return 1;int receive()int i,j,k=0,m;int *get=(int *)malloc(sizeof( int )*lcodechar);printf(n*接收方*n接收到的哈夫曼编码是:);for(i=0;ipassl;i+)printf(%c,passi);i=0;while(i!=lcodechar)for(j=0;(jncodechar*2-1);j+)for(m=0;mhcj.length;m+,k+)if(hcj.resm!=passk)break;if(m=hcj.length)geti=hcj.num;i+;break;k=k-m;printf(n根据哈夫曼树转换出的字符编码为:n);for(i=0;ilcodechar;i+)printf(%c,codechargeti);for(i=0;i100;i+)for(j=0;jlcodechar;j+)if(getj!=arraycharij)break;if(j=lcodechar)printf(n字符编码转换后得到的信息是:n);for(k=0;k20;k+)printf(%c,messageik);break;printf(n接收结束，谢谢使用!);return 1;int main()int i;char t;printf(初始化通讯系统:n输入编码字符集大小n,字符编码长度m(以n m格式来输入):); scanf(%d %d,&ncodechar,&lcodechar); codechar=(char *)malloc(sizeof(char)*ncodechar); proba=(float *)malloc(sizeof(float)*ncodechar);for(i=0;incodechar;i+) probai=0; for(i=0;i100;i+)arraychari=(int *)malloc(sizeof(int )*lcodechar);hc=(struct node*)malloc(sizeof(struct node)*(ncodechar*2-1); temp=(char *)malloc(sizeof(char)*(ncodechar); printf(请输入编码字符(以A B C D的格式来输入):n); for(i=0;incodechar;i+)scanf(%c,&t);if(t=n|t= )i-;continue;codechari=t;zifushengcheng();probability();huffman();sent();receive();return 1;五、调试过程（1）建立有100句中文的信息集合，每个句子称为一条信息。（2）输入编码参数： 从终端输入编码字符集大小n，字符编码长度m（设n为4，m为8）； 从终端输入编码字符（设为A，B，C，D）；（3）生成每条信息的字符编码，构造字符编码集合；（4）计算每个字符在字符编码集合中出现的概率；（5）根据字符概率构造哈夫曼树，求出每个字符的二进制编码。六、结果分析实 验 报 告题目：基于二叉排序树的商品信息查询算法的设计与实现专业： 计算机 班级： 计741 姓名：沈老爷子万岁！ 完成日期： 2015/1/10 实验四 基于二叉排序树的商品信息查询算法的设计与实现一、试验内容 设计并实现基于二叉排序树的商品信息查询算法。完成信息的查询、插入、删除、查询频度的统计等功能。二、试验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法开始三、流程图输入aC=Y建立头结点a=A平衡化调用插入函数，插入一个节点平衡化找到位置，插入输入名称插入函数a=B输出信息查找商品输入名称进入查询函数a=C储存相关信息到数组ca=D平衡化删除节点输入名称查找商品进入删除函数删除失败输出数组ca=Ea=F结束四、源程序代码#include#include#include#define LH +1#define EH 0#define RH -1#define LNAME 5 #define BUYM 3 #define BUYI 2 int Init(); /这里是各种函数int InitTree(BSTree *DT) ;void DestroyTree(BSTree *DT) ;int InsertAVL(BSTree *T,char *e,int *taller,int x);void LeftBalance(BSTree *T);void RightBalance(BSTree * T);void L_Rotate(BSTree *p);void R_Rotate(BSTree *p);int CharInput(char *a);int Compare(char *a,char *b);void print(char *a);int Input();int SearchTemp(char *e);void TempSearch();int Insertbytemp(char *a);BSTree GoodSearch(BSTree T,char *e);void Travelprint(BSTree DT,void(*Visit)(char *a);void RightProcess(BSTree *p,int *taller);void LeftProcess(BSTree *p,int *taller);int DeleteAVL(BSTree *p,char *e,int *taller);void Delete2(BSTree q,BSTree *r,int *taller);int Insertchar(char *a,char *b);typedef struct goodstruct good* lchild;char itemLNAME;int count;int bf;struct good* rchild;*BSTree;typedef struct tempgchar itemLNAME;int count;struct tempg *next;struct tempg *headt;BSTree dt;struct tempg *tnow=NULL;struct tempg *tg;int main()headt=(struct tempg*)malloc(sizeof(struct tempg);headt-next=NULL;Init();Input();DestroyTree(&dt);return 1;int InitTree(BSTree *DT) *DT=NULL;return 1;void DestroyTree(BSTree *DT) if(*DT) / 非空树 if(*DT)-lchild) / 有左孩子 DestroyTree(&(*DT)-lchild); / 销毁左孩子子树 if(*DT)-rchild) / 有右孩子 DestroyTree(&(*DT)-rchild); / 销毁右孩子子树 free(*DT); / 释放根结点 *DT=NULL; / 空指针赋0 int Init()int k;int state;InitTree(&dt);printf(基于二叉排序树的商品信息查询算法的设计与实现n);printf(请您输入商品名字，结束输入end:n);while(1)char tempLNAME;CharInput(temp);if(temp0=e&temp1=n&temp2=d)printf(录入结束!n);return 1;state=InsertAVL(&dt,temp,&k,0);if(state=1)printf(录入成功!n);Travelprint(dt, print);printf(n);else if(state=0)printf(已有此商品，请重新录入n);int InsertAVL(BSTree *T,char *e,int *taller,int x)if(!*T)*T=(BSTree)malloc(sizeof(struct good);Insertchar(*T)-item,e);/字符串赋值函数(*T)-lchild=(*T)-rchild=NULL;(*T)-bf=EH;(*T)-count=x;*taller=1;elseif(Compare(e,(*T)-item)=0)*taller=0;return 0;else if(Compare(e,(*T)-item)=-1)if(!InsertAVL(&(*T)-lchild,e,taller,x)return 0;if(*taller)switch(*T)-bf)case LH:LeftBalance(T);*taller=0;break;case EH:(*T)-bf=LH;*taller=1;break;case RH:(*T)-bf=EH;*taller=0;elseif(!InsertAVL(&(*T)-rchild,e,taller,x)return 0;if(*taller)switch(*T)-bf)case LH:(*T)-bf=EH;*taller=0;break;case EH:(*T)-bf=RH;*taller=1;break;case RH:RightBalance(T);*taller=0;return 1;void LeftBalance(BSTree *T)BSTree lc,rd;lc=(*T)-lchild; / lc指向*T的左子树根结点 switch(lc-bf) / 检查T的左子树的平衡度，并作相应平衡处理 case LH: / 新结点插入在*T的左孩子的左子树上，要作单右旋处理 (*T)-bf=lc-bf=EH;R_Rotate(T);break;case RH: / 新结点插入在*T的左孩子的右子树上，要作双旋处理 rd=lc-rchild; / rd指向*T的左孩子的右子树根 switch(rd-bf) / 修改*T及其左孩子的平衡因子 case LH:(*T)-bf=RH;lc-bf=EH;break;case EH: (*T)-bf=lc-bf=EH;break;case RH:(*T)-bf=EH;lc-bf=LH;rd-bf=EH;L_Rotate(&(*T)-l