级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)； qnum = i; /*每个结点地编号*/ qnext = pnext; /*将结点插入链表*/ pnext = 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=qnext) /*在链表中搜索*/ If(q password = x)Return 0;Return 1;Linklist Delnode(Linklist head) /*在链表中删除第一个结点*/ Node *p;P=headnext;Head next =pnext;Return p;Void insertnode(linklist head,node*p)/在链表头结点后插入一个结点酽锕极額閉镇桧猪訣锥。Pnext=head next;Head next =p;取包：输入密码,在链表L2中依次查找是否有与顾客输入密码相符地结点,找到后取出该结点,将其从链表L2中删除,然后将其插入链表L1中.彈贸摄尔霁毙攬砖卤庑。Linklist pcompare(Linklist head,long int x)/开箱前查看是否有此箱,若有将它从L2中删除,返回指向它地指针 Node *p,*q; For(p =head,q =headnext; q!=NULL;q=qnext)If (q password = x) P next=qnext；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 st3; 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-12i=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(x8) n=2;Else if(xnext=NULL) Printf(“满箱！n”);Elsep=DelNode(head1); /将其从链表L1中删除 P-password=MiMa( ); /生成密码 While(!compare(head2,p-password)/若密码重复,则重新生成 P-password=MiMa( ); Printf（“% 1dn”, 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 structchar 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+) Hti.lchild= Hti.rchild= Hti.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(htk.parent=0 & htk.weigthm1) m2= m1;r=1 m1= htk.weigth; l=k; else (htk.parent=0 & htk.weigthm2) m2= htk.weigth; r=k; htl.parent=i;htr.parent=i;hti.weigth= htl.weigth+ htr.weigth;hti.lchild=l;hti.rchild=r;(2)哈夫曼编码地生成哈夫曼编码地存储结构类型定义为：Typedef structChar bitsN;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=hti.parent;while(f!=0) If(htf.lchild=c) Cd.bits-cd.start=0;Else cd.bits-cd.start=1;c=f;f=htf.parent;Hcdi=cd;Printf(“输出哈夫曼编码：n”);For(i=1;i=n;i+)Printf(“% c:”,hti.data);For(k=hcdi.start;k=n;k+)Printf(“% c:”,hcdi.bitsk);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=hti.lchild; /*走向左孩子结点*/Else I=hti.rchild; /*走向右孩子结点*/If(hti. lchild=0) /*判断是否已经走到叶子结点*/ Putchar(hti.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 bitsn; /*存放哈夫曼编码地字符数组*/ Int start; /*编码地起始位置*/hcode ;Int stat(char *st,int cnt.char str) /*统计字符信息中出现地字符种类数和各字符出现地次数*/ Char*p; Int I,j,num27; For(i=1;i=26；i+) Numi=0; For(p=st;*p!=0；p+) *p=tolower(*p); /*若字符信息中有大写字母,则将其转换成小写字母*/ If(*p=a&*p=z) k=*p-96; numk+；j=0;for(i=1;i=26;i+) if(numi!=0) J+; Strj=i+96； Cntj=numi;Return j;Main Int I,j,k,n,t,x,cnt27; Char st50,sr27,bm200; Htnode hcd2*n-1; /*用于存放树中所有结点*/ Hcode hcdn; /*用于存放字符地哈夫曼编码*/ 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,stj!=0;j+)For(i=1;i=n;i+) If(hti.data=stj)For(k=hcdi.start;k=n;k+)Bmt=hcdi.bitsk;T+；Break；Bmt=0；Printf（”发送完毕！n”）；Break；Case4：paintf（”接受到地编码信息为：”）； Puts（bm）； Printf（”译码后地结果为：”）； Tscode（bm,ht,n）； Printf（”n”）； Break；Case0：exit（0）；