约瑟夫环实验报告xin.docx

约瑟夫环实验报告xin.docx

《约瑟夫环实验报告xin.docx》由会员分享，可在线阅读，更多相关《约瑟夫环实验报告xin.docx（18页珍藏版）》请在冰点文库上搜索。

约瑟夫环实验报告xin

约瑟夫环实验报告

专业班号：

软件工程二班姓名：

邵欣学号：

2220082123

实验日期：

2009.12.26指导老师：

蒋波

一、问题描述

约瑟夫问题的一种描述是：

编号为1，2，......，n的n个人按顺时针方向围坐一环，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺指针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

二、实验要求

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

三、测试数据

m的初值为20；n=7,7个人的密码依次为：

3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序应为：

6，1，4，7，2，3，5）。

四、程序实现

#include

#include

typedefstructLNode

{

intpas;//每个人持有的密码

intpsw;//这个人的编号

structLNode*next;//指向下一个节点

}LNode,*LinkList;

voidmain（）

{voidListDelete_L（LinkListL,intkey,intn）;//依次输出几个人的序号和密码

LinkListcreatList_L（intn）;//构建约瑟夫环

LinkLists;

intn,m;

printf（"请输入总人数N:

\n"）;

scanf（"%d",&n）;

printf（"请输入报数上限值M:

\n"）;

scanf（"%d",&m）;

s=creatList_L（n）;

printf（"这几个人的出列顺序和手持密码为：

\n"）;

printf（"出列顺序手持密码\n"）;

ListDelete_L（s,m,n）;

}

LinkListcreatList_L（intn）

{

LinkListp,q;

LinkListhead;

inti=1;intkey;

head=（LinkList）malloc（sizeof（LNode））;

p=head;

for（i=1;i<=n;i++）{

printf（"请输入第%d个人的手持密码:

",i）;

scanf（"%d",&key）;

q=p;

p=（LinkList）malloc（sizeof（LNode））;

p->psw=i;p->pas=key;

q->next=p;

}

p->next=head->next;

free（head）;

head=p->next;

return（head）;

}

voidListDelete_L（LinkListL,intkey,intn）

{

LinkListp,s;

intj=1;

while（n>0）{

p=L;

for（j=1;jnext;}

printf（"%3d%8d\n",p->psw,p->pas）;

key=p->pas;

s->next=p->next;

L=p->next;

free（p）;

n--;

}

}

五、实验结果

赫夫曼树的实验报告

专业班号：

软件工程二班姓名：

邵欣学号：

2220082123

实验日期：

2009.12.26指导老师：

蒋波

一、问题描述

假设有n个权值{w1，w2，w3，……wn}，构造一棵具有n个叶子节点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树或哈夫曼树

二、实验要求

用w存放n个字符的权值（均>0），构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC。

三、程序实现

#include

#include

#include

#include

#include

usingnamespacestd;

typedefstruct

{

charletter;

intweight;

intparent;

intlchild;

intrchild;

}HTNode,*HuffmanTree;//动态分配数组存储HuffmanTree

typedefchar**HuffmanCode;//动态分配数组存储HuffmanTree编码表

typedefstruct

{

HuffmanTreeHT;

HuffmanCodeHC;

intlen;

char*c;

}Huf;

voidmain（）

{voidSelect（HuffmanTree&HT,ints,int&s1,int&s2）;//寻找两个最小的权值s1,s2;并且当有两个或两个以上权值相等时，按照先生成先使用原则

voidsetHuffmanTree（HuffmanTree&HT,char*str,int*w,intn）;//创建赫夫曼树

HufsetHuffmanCode（HuffmanTree&HT,HuffmanCode&HC,intn,char*s）;//从叶子到根结点逆向求每个字符的赫夫曼编码

HufInitialization（）;//初始化操作，接受输入，调用函数setHuffmanTree，setHuffmanCode创建树并编码

voidEncoding（Hufhuf）;//利用已建好的赫夫曼树对文件中的正文进行编码，然后将结果存入文件codefile.txt中,如果正文中没有要编码的字符，则键盘读入

voidDecoding（Hufhuf）;//利用已建好的赫夫曼树将文件对CodeFile.dat中的代码进行译码，结果存入文件TextFile.dat中

voidPrint（）;//将文件CodeFile每行50个代码显示到终端并将此字符形式的编码写入CodePrin中

voidTreeprinting（Hufhuf）;//输出赫夫曼树节点，权值，双亲，左孩子，右孩子

Hufhuf;

intnum;

charinput;

while

（1）{

cout<<"1:

初始化"<

cout<<"2:

进行编码"<

cout<<"3:

进行译码"<

cout<<"4:

打印代码文件"<

cout<<"5:

打印赫夫曼树"<

cout<<"6:

退出"<

cout<<"请输入你的选择：

";

cin>>input;

if（input=='1'）{

num=1;

}elseif（input=='2'）{

num=2;

}elseif（input=='3'）{

num=3;

}elseif（input=='4'）{

num=4;

}elseif（input=='5'）{

num=5;

}elseif（input=='6'）{

num=6;

}else{

num=7;

}

switch（num）{

case1:

huf=Initialization（）;

printf（"\n\n***初始化结束，按任一键继续***\n"）;

getch（）;break;

case2:

Encoding（huf）;

printf（"\n\n***编码结束，按任一键继续***\n"）;

getch（）;break;

case3:

Decoding（huf）;

printf（"\n\n***译码结束，按任一键继续***\n"）;

getch（）;break;

case4:

Print（）;

printf（"\n\n***打印代码结束，按任一键继续***\n"）;

getch（）;break;

case5:

Treeprinting（huf）;

printf（"\n\n***打印树结束，按任一键继续***\n"）;

getch（）;break;

case6:

printf（"\n\n退出\n\n"）;

return;

default:

printf（"选择有错，请重新选择\n"）;

getch（）;break;

}

}

}

voidSelect（HuffmanTree&HT,ints,int&s1,int&s2）

{

intj,k,i;

j=k=10000;

s1=s2=0;

for（i=1;i<=s;i++）{

if（HT[i].parent==0）{

if（HT[i].weight

k=j;s2=s1;

j=HT[i].weight;

s1=i;

}

elseif（HT[i].weight

k=HT[i].weight;

s2=i;

}

}

}

}

voidsetHuffmanTree（HuffmanTree&HT,char*str,int*w,intn）

{if（n<=1）return;

HuffmanTreep;//使用结构体中的内容

intm,i,s1,s2;//s1,s2是权值最小的两个结点的序号

m=2*n-1;

HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;//0号单元未用

for（p=HT+1,i=1;i<=n;++i,++p,++w）{

p->letter=str[i];p->weight=w[i];

（*p）.parent=0;p->lchild=0;p->rchild=0;

}

for（;i<=m;++i,++p）{

p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;

}

for（i=n+1;i<=m;++i）//建赫夫曼树

{

Select（HT,i-1,s1,s2）;

HT[s1].parent=i;HT[s2].parent=i;

HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

FILE*huftree;//将哈夫曼树写入到文件hufTree.dat中

huftree=fopen（"hufTree.txt","rt"）;

if（huftree==NULL）

{

huftree=fopen（"hufTree.txt","wt"）;

for（i=1;i<=m;i++）

fprintf（huftree,"%d%d%d%d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild）;

rewind（huftree）;

}

}

HufsetHuffmanCode（HuffmanTree&HT,HuffmanCode&HC,intn,char*s）

{

Hufhuf;

huf.c=（char*）malloc（（n+1）*sizeof（char））;

for（intj=1;j<=n;j++）{

huf.c[j]=s[j];

}

intstart=1;char*cd;intf,c,i;

HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;//分配n个字符编码的头指针向量

cd=（char*）malloc（n*sizeof（char））;//分配求编码的工作区间

cd[n-1]='\0';//编码结束符

for（i=1;i<=n;++i）//逐个字符求赫夫曼编码

{

start=n-1;//编码结束符位置

for（c=i,f=HT[i].parent;f!

=0;c=f,f=HT[f].parent）//从叶子到根逆向求编码

if（HT[f].lchild==c）cd[--start]='0';

elsecd[--start]='1';

HC[i]=（char*）malloc（（n-start）*sizeof（char））;//为第i个字符编码分配空间

strcpy（HC[i],&cd[start]）;//从cd复制编码（串）到HC

}

//将HC,HT,n分别存储到结构体Huf中

huf.HC=HC;

huf.HT=HT;

huf.len=n;

free（cd）;//释放工作空间

returnhuf;

}

HufInitialization（）

{

printf（"\n\n开始初始化\n\n"）;

HuffmanTreeHT;

HuffmanCodeHC;

charc[50];

intw[50];

intn;

cout<<"请输入字符的个数：

"<

cin>>n;

cout<<"请输入所有字符：

"<

gets（c）;

for（inti=1;i<=n;i++）{

cout<<"请输入第"<

"<

cin>>w[i];

}

for（intj=n-1;j>=0;j--）

{

c[j+1]=c[j];

}

setHuffmanTree（HT,c,w,n）;

Hufhuf=setHuffmanCode（HT,HC,n,c）;

returnhuf;

}

voidEncoding（Hufhuf）

{

inti=0,j=0,n;

charch[10000];

FILE*code,*tbt;

n=huf.len;

tbt=fopen（"ToBeTran.txt","rt"）;

printf（"\n\n***编码***\n\n"）;

if（tbt==NULL）

{

printf（"不存在文件ToBeTran.txt"）;

printf（"\n请输入要进行编码的报文:

"）;

gets（ch）;

printf（"\n"）;

code=fopen（"CodeFile.txt","wt+"）;

}

else

{

fscanf（tbt,"%s",&ch）;

fclose（tbt）;

code=fopen（"CodeFile.txt","wt+"）;

}

while（ch[j]）

{

for（i=1;i<=n;i++）

if（ch[j]==huf.HT[i].letter）

{

fprintf（code,"%s",huf.HC[i]）;

break;

}

j++;

}

rewind（code）;

fclose（code）;

printf（"已进行编码，且存到文件CodeFile.txt中！

"）;

}

voidDecoding（Hufhuf）

{

HuffmanTreep;

inti,n,j=0;

chard[10000];

FILE*code;

n=huf.len;

code=fopen（"CodeFile.txt","rt"）;

printf（"\n\n***译码***\n\n"）;

if（code==NULL）

{

printf（"没有找到CodeFile.txt文件，先进行编码\n"）;

printf（"输入赫夫曼码进行译码:

"）;

scanf（"%s",&d）;

}

else

{

fscanf（code,"%s",d）;

fclose（code）;

}

code=fopen（"TextFile.txt","wt+"）;

while（d[j]）

{

p=&huf.HT[2*n-1];

while（p->lchild||p->rchild）

{

if（d[j]=='0'）

{

i=p->lchild;

p=&huf.HT[i];

}

else

{

i=p->rchild;

p=&huf.HT[i];

}

j++;

}

printf（"%c",huf.c[i]）;

fprintf（code,"%c",huf.c[i]）;

}

fclose（code）;

printf（"\n\n已进行译码，结果保存到文件TextFile.txt中"）;

}

voidPrint（）

{

charch;

FILE*code,*codeprin;

code=fopen（"CodeFile.txt","r"）;

codeprin=fopen（"CodePrin.txt","w"）;

printf（"文件CodeFile中的编码是：

\n\n"）;

for（inti=1;（ch=fgetc（code））!

=EOF;i++）

{

if（i>=50）{

printf（"\n"）;

fputc（'\n',codeprin）;

i=1;

}

putchar（ch）;

fputc（ch,codeprin）;

}

fclose（codeprin）;

fclose（code）;

printf（"\n\n且已经写入到文件CodePrin.txt中\n"）;

}

voidTreeprinting（Hufhuf）

{

intj,n;

FILE*tree;

tree=fopen（"TreePrint.txt","w"）;

n=huf.len;

printf（"\n\n***打印赫夫曼树***\n\n"）;

printf（"结点weightparentlchildrchild"）;

fprintf（tree,"结点weightparentlchildrchild"）;

for（j=1;j<=n;j++）{

printf（"\n%4d（%c）%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild,huf.HT[j].rchild）;

fprintf（tree,"\n%4d（%c）%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild,huf.HT[j].rchild）;

}

for（inth=n+1;h<=2*n-1;h++）{

printf（"\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild,huf.HT[h].rchild）;

fprintf（tree,"\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild,huf.HT[h].rchild）;

}

fclose（tree）;

}