09級ds(超市密碼存儲箱系統(tǒng)的設(shè)計與實現(xiàn)等)實驗代碼

1、超市密碼存儲箱系統(tǒng)的設(shè)計與實現(xiàn)設(shè)計方案（1） 存儲結(jié)構(gòu)類型定義/*密碼箱的存儲結(jié)構(gòu)類型定義*/Typedef struct node Int num；/*箱子的號碼*/ Long int password;/*箱子的密碼（滿箱有，空箱無）*/ Struct node *next;/*指向下個結(jié)點的指針*/node ,*linklist;(2)主要功能函數(shù)設(shè)計建立鏈表：最初所有的箱子為空，按照序號依次插入鏈表L1中，鏈表L2為空。LinkList Createlist1 /*建立空箱子鏈表L1,初始時共12個結(jié)點*/ Int I ; Linklist head,p,q; Head=(node *

2、 )malloc(sizeof(node); /*創(chuàng)建頭結(jié)點*/ Head next = NULL; P =head; For(i = 1;i=12;i+ ) /*依次建立12個結(jié)點，并插入鏈表中*/ q=（node *）malloc(sizeof(node)； qnum = i; /*每個結(jié)點的編號*/ qnext = pnext; /*將結(jié)點插入鏈表*/ pnext = q; p = q; Return head; /*返回鏈表的頭結(jié)點*/Linklist Createlist2 /*建立滿箱子鏈表L2，初始時為空*/Linklist head;Head =(node *)malloc(s

3、izeof(node); /*創(chuàng)建頭結(jié)點*/Head next =NULL;Return head; /*返回鏈表的頭結(jié)點*/尋找空箱子：判斷鏈表L1是否為空，若不空，則取出第一個結(jié)點（即將其從鏈表L1中刪除），然后隨機(jī)產(chǎn)生一個6位密碼，并將此密碼依次與鏈表L2中所有結(jié)點的密碼相比較，若發(fā)現(xiàn)有重復(fù)，則重新生成一個密碼，直到?jīng)]有重復(fù)為止。將密碼寫入此箱子結(jié)點的password域,然后將此節(jié)點插入L2鏈表。Long int mima /*密碼產(chǎn)生函數(shù)*/Long n,m;Randomize;M = random(9)+1;N=(m*100000 +random(1000000)1000000； /

4、*產(chǎn)生6位數(shù)的密碼*/Return(n);Int compare(linklist head,long int x) /*比較是否有重復(fù)的密碼，若有返回0，無則返回1*/Node *q;For(q =head;q!=NULL;q=qnext) /*在鏈表中搜索*/ If(q password = x)Return 0;Return 1;Linklist Delnode(Linklist head) /*在鏈表中刪除第一個結(jié)點*/ Node *p;P=headnext;Head next =pnext;Return p;Void insertnode(linklist head,node*p)/

5、在鏈表頭結(jié)點后插入一個結(jié)點Pnext=head next;Head next =p;取包：輸入密碼，在鏈表L2中依次查找是否有與顧客輸入密碼相符的結(jié)點，找到后取出該結(jié)點，將其從鏈表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; /*返回指向此箱的結(jié)點*/else p=q

6、;Return NULL； /*若無此箱則返回空指針*/(3)實現(xiàn)程序#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行四列，箱體為藍(lán)色*/Void DrawBox( ) int x,y,i=1; Char st3; Setcolor(3);For(x=300;x

7、=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); /在每個箱子上標(biāo)上箱子的編號：1-12i=atoi (st);i+; Int dm(int x) /輔助計算機(jī)填充坐標(biāo)的參數(shù)Int m;M=x%4;If(m=0)m=4;Return

8、m;Int dn(int x) /輔助計算機(jī)填充坐標(biāo)的參數(shù)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 string8;Linklist head1,head2,p;Int graphdriver=DETECT,graphmode;Initgra

9、ph(&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”);Elsep=DelNode(head1); /將其從鏈表L1中刪除 P->password=MiMa( ); /生成密碼 While(!compare(head2,p->passw

10、ord)/若密碼重復(fù),則重新生成 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); /將此箱子變?yōu)榧t色I(xiàn)f(k=2)printf(“請輸入密碼：”)；Scanf(“% 1d”,&t);If(head2->next!=NULL)p=pcompare(head2,t);Ip(p=NULL) continue;Insert

11、Node(head1,p);M=dm(p->num);N=dn(p->num);Fillcolor(300+m*50-10,50+n*50-10,1); /將此箱子變?yōu)樗{(lán)色哈夫曼編碼/譯碼系統(tǒng)案例描述。#difine N 50 /葉子結(jié)點數(shù)，即在信息中最多可出現(xiàn)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=

12、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.weigth<m1) m2= m1;r=1 m1= htk.weigth; l=k; else (htk.parent=0 && htk.weigth<m2) m2= htk.weigth; r=k; htl.parent=i;htr.parent=i;hti.weigth= htl.weigth+ htr.weigth;

13、hti.lchild=l;hti.rchild=r;(2)哈夫曼編碼的生成哈夫曼編碼的存儲結(jié)構(gòu)類型定義為：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

14、;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; /*將樹根結(jié)點的下標(biāo)賦i，從根結(jié)點出發(fā)向下搜索*/While(*bit!=0) /*若編碼沒有結(jié)束*/If(*bit=0) I=hti.lchild; /*走向左孩子結(jié)點*/Else I=

15、hti.rchild; /*走向右孩子結(jié)點*/If(hti. lchild=0) /*判斷是否已經(jīng)走到葉子結(jié)點*/ Putchar(hti.data); /*輸出此編碼對應(yīng)的字符*/ I=2*n-1 /*重新回到根節(jié)點，準(zhǔn)備下一次搜集*/Bit+; /*取編碼中的下一個代碼*/(4)程序?qū)崿F(xiàn)#include”stdio.h”#include”string.h”#include”conio.h”#include”stdlib.h”#define N30 /*最大葉子結(jié)點數(shù)*/Typedef struct Char data; /*編碼對應(yīng)的字符*/ Int weight; /*結(jié)點的權(quán)值*/ I

16、nt lchild,rchild,parent; /*左右孩子及雙親的下標(biāo)*/htnode;Typedef struct Char bitsn; /*存放哈夫曼編碼的字符數(shù)組*/ Int start; /*編碼的起始位置*/hcode ;Int stat(char *st，int cnt.char str) /*統(tǒng)計字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)*/ Char*p; Int I,j,num27; For(i=1;i=26；i+) Numi=0; For(p=st;*p!=0；p+) *p=tolower(*p); /*若字符信息中有大寫字母，則將其轉(zhuǎn)換成小寫字母*/ If(*p=

17、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; /*用于存放樹中所有結(jié)點*/ Hcode hcdn; /*用于存放字符的哈夫曼編碼*/ While(1)Printf(”1-輸入待傳送的字符信息 2-編碼 3-發(fā)送 4-接收并譯碼 0-退出n”)；Scanf（”%d”,&x）;Switch(x)Case 1:printf(”請輸入要發(fā)送的字符串信息：”)； Scanf(”%s”，st)； Break；Case 2:n=stat(st,cnt,sr); Creathufmtree(ht,n,sr,cnt);