级ds(超市密码存储箱系统的设计与实现等)实验代码.doc

超市密码存储箱系统地设计与实现
设计方案
（1） 存储结构类型定义
/*密码箱地存储结构类型定义*/
Typedef struct node{
Int num；/*箱子地号码*/
Long int password;/*箱子地密码（满箱有,空箱无）*/
Struct node *next;/*指向下个结点地指针*/
}node ,*linklist;
(2)主要功能函数设计
①建立链表：最初所有地箱子为空,按照序号依次插入链表L1中,链表L2为空.
LinkList Createlist1﹙﹚ /*建立空箱子链表L1,初始时共12个结点*/
{
Int I ;
Linklist head,p,q;
Head=(node * )malloc(sizeof(node)); /*创建头结点*/
Head →next = NULL;
P =head;
For(i = 1;i﹤=12;i++ ) /*依次建立12个结点,并插入链表中*/
{
q=（node *）malloc(sizeof(node))；
q→num = i; /*每个结点地编号*/
q→next = p→next; /*将结点插入链表*/
p→next = q;
p = q;
}
Return head; /*返回链表地头结点*/
}
Linklist Createlist2﹝﹞ /*建立满箱子链表L2,初始时为空*/
{
Linklist head;
Head =(node *)malloc(sizeof(node)); /*创建头结点*/
Head →next =NULL;
Return head; /*返回链表地头结点*/
}
②寻找空箱子：判断链表L1是否为空,若不空,则取出第一个结点（即将其从链表L1中删除）,然后随机产生一个6位密码,并将此密码依次与链表L2中所有结点地密码相比较,若发现有重复,则重新生成一个密码,直到没有重复为止.将密码写入此箱子结点地password域,然后将此节点插入L2链表.矚慫润厲钐瘗睞枥庑赖。
Long int mima﹝﹞ /*密码产生函数*/
{
Long n,m;
Randomize﹝﹞;
M = random(9)+1;
N=(m*100000 +random(1000000))℅1000000； /*产生6位数地密码*/聞創沟燴鐺險爱氇谴净。
Return(n);
}
Int compare(linklist head,long int x) /*比较是否有重复地密码,若有返回0,无则返回1*/残骛楼諍锩瀨濟溆塹籟。
{
Node *q;
For(q =head;q!=NULL;q=q→next) /*在链表中搜索*/
{
If(q →password == x)
Return 0;
}
Return 1;
}
Linklist Delnode(Linklist head) /*在链表中删除第一个结点*/
{
Node *p;
P=head→next;
Head →next =p→next;
Return p;
}
Void insertnode(linklist head,node*p)//在链表头结点后插入一个结点{酽锕极額閉镇桧猪訣锥。
P→next=head →next;
Head →next =p;
}
③取包：输入密码,在链表L2中依次查找是否有与顾客输入密码相符地结点,找到后取出该结点,将其从链表L2中删除,然后将其插入链表L1中.彈贸摄尔霁毙攬砖卤庑。
Linklist pcompare(Linklist head,long int x)
//开箱前查看是否有此箱,若有将它从L2中删除,返回指向它地指针{
Node *p,*q;
For(p =head,q =head→next; q!=NULL;q=q→next)
{
If (q →password == x)
{
P →next=q→next；
Return q; /*返回指向此箱地结点*/
}
else p=q;
}
Return NULL； /*若无此箱则返回空指针*/
(3)实现程序
#include ”graphics.h”
#include ”stdlib.h”
#include ”stdio.h”
#include ”string.h”
# include ”time.h”
Typedef struct node
{
Int num;
Long int password;
Struct node *next;
}node,*linklist; /*在屏幕上画出箱子,共12个,3行四列,箱体为蓝色*/
Void DrawBox( )
{ int x,y,i=1;
Char st[3];
Setcolor(3);
For(x=300;x﹤=500;x+=50)
Line(x,50,x,200);
For(y=50;y<=200;y+=50)
Line(300,y,500,y);
Setfillstyle(SOLID_FILL,1);
For(y=50;y<=150;y+=50)
For(x=300;x﹤=450;x+=50)
{
itoa(i,st,10);
floodfill(x+30,y+30,3);
outtextxy(x+20,y+25,st); //在每个箱子上标上箱子地编号：1-12
i=atoi (st);
i++;
} }
Int dm(int x) //辅助计算机填充坐标地参数
{
Int m;
M=x%4;
If(m==0)m=4;
Return m;
}
Int dn(int x) //辅助计算机填充坐标地参数
{int n;
If(x<=4) n=1;
Elseif(x<8) n=2;
Else if(x<=12) n=3;
Return n;
}
Void fillcolor(int x,inty,int color)
{
Setfillstyle(SOLID_FILL,color);
Floodfill(x,y,3);
Main( )
{
Int i;Char k;Int m,n;Long int t;Char string[8];
Linklist head1,head2,p;
Int graphdriver=DETECT,graphmode;
Initgraph(&graphdriver, &graphmode,”d:\\tc”);
DrawBox( );
Head1=createlist1(　);
Head2=createlist2(　);
Printf(“1- 存包 2- 取包 0- 退出\n”);
While(1)
{k=getch();
If(k==’0’)exit(0);
If(k==’1’)
{if(head1->next==NULL)
Printf(“满箱！\n”);
Else
{p=DelNode(head1); //将其从链表L1中删除
P->password=MiMa( ); //生成密码
While(!compare(head2,p->password))//若密码重复,则重新生成
P->password=MiMa( );
Printf（“% 1d\n”, p->password）;
InsertNode(head2,p); //将其从插入链表L2中
M=dm(p->num);
N=dn(p->num);
Fillcolor(300+m*50-10,50+n*50-10,4); //将此箱子变为红色
｝
｝
If(k==’2’)
{printf(“请输入密码：”)；
Scanf(“% 1d”,&t);
If(head2->next!=NULL)
{p=pcompare(head2,t);
Ip(p==NULL) continue;
InsertNode(head1,p);
M=dm(p->num);
N=dn(p->num);
Fillcolor(300+m*50-10,50+n*50-10,1); //将此箱子变为蓝色
｝｝｝｝

哈夫曼编码/译码系统
案例描述
......
#difine N 50 //叶子结点数,即在信息中最多可出现30种字符
Typedef struct
{char data; //
int weigth;
int Lchild,rchild,parent;
｝HTNode;
Void creatHufmTree(HTNode ht[],int n)
｛int I,k,m1,m2,l,r;
For(i=1;i<=2*n;i++)
Ht[i].lchild= Ht[i].rchild= Ht[i].parent=0;
For(i=n+1;i<=2*n-1;i++)
{ m1=m2=10000;
L=r=0
For(k=1;k<=i-1;k++)
If(ht[k].parent==0 && ht[k].weigth<m1)
{ m2= m1;r=1
m1= ht[k].weigth;
l=k; }
else (ht[k].parent==0 && ht[k].weigth<m2)
{ m2= ht[k].weigth;
r=k;
}
ht[l].parent=i;
ht[r].parent=i;
ht[i].weigth= ht[l].weigth+ ht[r].weigth;
ht[i].lchild=l;
ht[i].rchild=r;
}
}
(2)哈夫曼编码地生成
哈夫曼编码地存储结构类型定义为：
Typedef struct
{
Char bits[N];
Int start;
}Hcode;
Void HufmCode(HTNode ht[];Hcode hcd[],int n)
{
Int i,f,c,k;
Hcode cd;

For(i=1;i<=n;i++)
{
cd.start=n+1;
c=i;
f=ht[i].parent;
while(f!=0)
{
If(ht[f].lchild==c)
Cd.bits[--cd.start]=’0’;
Else
cd.bits[--cd.start]=’1’;
c=f;
f=ht[f].parent;
}
Hcd[i]=cd;
}
Printf(“输出哈夫曼编码：\n”);
For(i=1;i<=n;i++)
{
Printf(“% c:”,ht[i].data);
For(k=hcd[i].start;k<=n;k++)
Printf(“% c:”,hcd[i].bits[k]);
Printf(“\n”);
}
}
(3)对编码信息地翻译
Void tscode(char *bit,htnode ht[],int n) /*哈夫曼树地译码*/謀荞抟箧飆鐸怼类蒋薔。
{
Int I;
I=2*n-1; /*将树根结点地下标赋i,从根结点出发向下搜索*/
While(*bit!=’＼0’) /*若编码没有结束*/
{
If(*bit==’0’)
I=ht[i].lchild; /*走向左孩子结点*/
Else
I=ht[i].rchild; /*走向右孩子结点*/
If(ht[i]. lchild==0) /*判断是否已经走到叶子结点*/
{
Putchar(ht[i].data); /*输出此编码对应地字符*/
I=2*n-1 /*重新回到根节点,准备下一次搜集*/
}
Bit++; /*取编码中地下一个代码*/
}
}
(4)程序实现
#include”stdio.h”
#include”string.h”
#include”conio.h”
#include”stdlib.h”
#define N30 /*最大叶子结点数*/
Typedef struct
{
Char data; /*编码对应地字符*/
Int weight; /*结点地权值*/
Int lchild,rchild,parent; /*左右孩子及双亲地下标*/
}htnode;
Typedef struct
{
Char bits[n]; /*存放哈夫曼编码地字符数组*/
Int start; /*编码地起始位置*/
}hcode ;
Int stat(char *st,int cnt[].char str[])
/*统计字符信息中出现地字符种类数和各字符出现地次数*/
{
Char*p;
Int I,j,num[27];
For(i=1;i﹤=26；i++)
Num[i]=0;
For(p=st;*p!=’﹨0’；p++)
{
*p=tolower(*p); /*若字符信息中有大写字母,则将其转换成小写字母*/
If(*p﹥=’a’&&*p﹤=’z’)

{
k=*p-96;
num[k]++；
}
}
j=0;
for(i=1;i﹤=26;i++)
if(num[i]!=0)
{
J++;
Str[j]=i+96；
Cnt[j]=num[i];
}
Return j;
}
Main﹝﹞
{
Int I,j,k,n,t,x,cnt[27];
Char st[50],sr[27],bm[200];
Htnode hcd[2*n-1]; /*用于存放树中所有结点*/
Hcode hcd[n]; /*用于存放字符地哈夫曼编码*/
While(1)
{
Printf(”1-输入待传送地字符信息 2-编码 3-发送 4-接收并译码 0-退出n﹨”)；厦礴恳蹒骈時盡继價骚。
Scanf（”%d”,&x）;
Switch(x)
{
Case 1:printf(”请输入要发送地字符串信息：”)；
Scanf(”%s”,st)；
Break；
Case 2:n=stat(st,cnt,sr);
Creathufmtree(ht,n,sr,cnt);
Hufmcode(ht,hcd,n);
Break;
Case 3:t=0;
For(j=0,st[j]!=’﹨0’;j++)
{
For(i=1;i﹤=n;i++)
If(ht[i].data==st[j])
{
For(k=hcd[i].start;k﹤=n;k++)
{
Bm[t]=hcd[i].bits[k];
T++；
}
Break；
}
}
Bm[t]=’﹨0’；
Printf（”发送完毕！﹨n”）；
Break；
Case4：paintf（”接受到地编码信息为：”）；
Puts（bm）；
Printf（”译码后地结果为：”）；
Tscode（bm,ht,n）；
Printf（”﹨n”）；
Break；
Case0：exit（0）；
}
}
}