数据结构实验1 病人看病程序的模拟、最短路径算法、LZ77 压缩算法实验报告

实验1：病人看病模拟程序一．实验目的掌握单链队列存储方式的类型定义，掌握单链队列的基本运算的实现。学会根据应用问题的需要选择合适的数据结构，掌握队列的先进先出运算规则及其在病人看病模拟程序中的应用，理解队列在运算过程中状态的变化。二．实验内容编写一个程序，反映病人到医院看病排队看医生的情况。三．需求分析运行环境：Windows操作环境，VisualC++6.0程序应该达到的功能：在病人排队过程中，主要重复两件事：（1）病人到达就诊室，将病历交给护士，排到等待队列中候诊。（2）护士从等待队列中取出下一位病人的病历，该病人进入入诊室就诊。要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说民如下：排队——输入排队病人的病历号，加入到病人排队队列中。就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除。查看排队——从队首到队尾列出所有的排队病人的病历号。不再排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行。下班——退出运行。四．概要设计数据结构的选择考虑到病人排队候诊的过程中具有先排队就诊的特诊，与队列的先进先出的特征相吻合，因此可以考虑采用队列线性表，其中，队列的存储结构有循环顺序队列和单链队列。考虑到循环顺序队列的插入，删除浪费空间和时间，故采用单链队列，而建立带头结点的单链队列比无头结点的单链队列更简化了插入和删除操作，因此采用带头结点的单链队列。程序的总体结构建立名为“doctor”的项目文件，在该项目的管理下完成本程序开发。在该项目下建立名为“1.cpp”的源程序文件，文件中主要包括main()和SeeDoctor()两个函数，它们的关系如图1(b)所示。eexp3_6.cpp文件图1（a）图1（b）main程序的主要功能在SeeDoctot()函数中实现，main()函数起到调用SeeDoctor()函数的作用。main五．详细设计数据结构的类型定义：SeeDoctor链队结点的类型定义SeeDoctortypedefstructqnode{intdata;structqnode*next;}QNode;链队的整体结构定义qu->qu->rearqu->front123链队的整体结构图示qu->rearqu->rearqu->front^main()函数：voidmain(){ seeDoctor();}SeeDoctor()函数：模拟病人看病的过程。病人排队看医生，所以要用到一个队列，这里设计了一个带头结点的单链表作为队列。六．函数代码#include<stdio.h>#include<malloc.h>typedefstructqnode{intdata;structqnode*next;}QNode;//链队结点类型typedefstruct{QNode*front,*rear;}QuType;//链队类型voidSeeDoctor(){//模拟病人看病的过程intsel,flag=1,find,no;QuType*qu;QNode*p;qu=(QuType*)malloc(sizeof(QuType));//创建空队qu->front=qu->rear=NULL;while(flag==1){//循环执行printf("1:排队2：就诊3:查看排队4:不再排队，余下依次就诊5:下班请选择:");scanf("%d",&sel);switch(sel){case1:printf(">>输入病历号：");do{scanf("%d",&no);find=0;p=qu->front;while(p!=NULL&&!find)if(p->data==no)find=1;elsep=p->next;if(find)printf(">>输入的病历号重复，重新输入:");}while(find==1);p=(QNode*)malloc(sizeof(QNode));//创建结点p->data=no;p->next=NULL;if(qu->rear==NULL)//第一个病人排队qu->front=qu->rear=p;else{qu->rear->next=p;qu->rear=p;//将*p结点入队}break;case2:if(qu->front==NULL)//队空printf(">>没有排队的病人!\n");else{//队不空p=qu->front;printf(">>病人%d就诊\n",p->data);if(qu->rear==p)//只有一个病人排队的情况qu->front=qu->rear=NULL;elsequ->front=p->next;free(p);}break;case3:if(qu->front==NULL)//队空printf(">>没有排队的病人!\n");else{p=qu->front;printf(">>排队病人:");while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}break;case4:if(qu->front==NULL)//队空printf(">>没有排队的病人！\n");else{p=qu->front;printf(">>病人按以下顺序就诊：");while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}flag=0;//退出break;case5:if(qu->front!=NULL)//队不空printf(">>请排队的病人明天就医！\n");flag=0;break;}}}intmain(){SeeDoctor();return0;}七．运行结果八．使用说明在VisualC++6.0环境下，按下述步骤操作即可：“文件”菜单/打开工作区/选择proj3_6.dsw”，确定/“编译”菜单/执行exp3_6.exe。九．心得体会通过编程，熟悉了C语言的上机环境，掌握了C语言的基本结构；通过模拟病人看病过程，掌握队列的基本操作，基本可以完成队列的操作编程。实验4最短路径算法实验目的1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2．掌握图的存储结构以及单源点最短路径算法。实验内容1.理解Dijkstra算法的原理，用Dijkstra算法编程找出从s到t的最短路径。2.编程实现Dijkstra算法，需求分析：首先让用户输入一个带权的有向图，输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。用户输入一对对弧后，我们可以采用数组的形式来进行存储每个顶点之间的权值，最后由用户输入该有向图的源点（即每个最短路径的起点），要求源点必须为刚才输入的各顶点中的某一个，如果用户输入错误，程序要给出错误信息提示并退出程序。然后，我们可以设计一个Graph这样的类，将对关系的各种操作放入其中，然后我们在主函数中调运这个类就可以实现最短路问题的求解了。概要设计：①.构造一个新的类Graph:classGraph{private:intarcs[MAX][MAX],Path[MAX][MAX],D[MAX];intarcnum,vexnum,weight,v0;Typea,b,vexs[MAX];public:voidCreat_Graph();voidShow_ShortestPath();voidShortestPath_DIJ();};②.结构化调用类中方法的主函数：intmain(){ Graph<char>G;G.Creat_Graph();G.ShortestPath_DIJ();G.Show_ShortestPath(); return0;}函数代码/****************************************About:有向图的Dijkstra算法实现*Author:TankyWoo*Blog:www.WuTianQ***************************************/#include<iostream>usingnamespacestd;constintmaxnum=100;constintmaxint=999999;//各数组都从下标1开始intdist[maxnum];//表示当前点到源点的最短路径长度intprev[maxnum];//记录当前点的前一个结点intc[maxnum][maxnum];//记录图的两点间路径长度intn,line;//图的结点数和路径数//n--nnodes//v--thesourcenode//dist[]--thedistancefromtheithnodetothesourcenode//prev[]--thepreviousnodeoftheithnode//c[][]--everytwonodes'distancevoidDijkstra(intn,intv,int*dist,int*prev,intc[maxnum][maxnum]){bools[maxnum];//判断是否已存入该点到S集合中for(inti=1;i<=n;++i){dist[i]=c[v][i];s[i]=0;//初始都未用过该点if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;}dist[v]=0;s[v]=1;//依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中//一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度//注意是从第二个节点开始，第一个为源点for(inti=2;i<=n;++i){inttmp=maxint;intu=v;//找出当前未使用的点j的dist[j]最小值for(intj=1;j<=n;++j)if((!s[j])&&dist[j]<tmp){u=j;//u保存当前邻接点中距离最小的点的号码tmp=dist[j];}s[u]=1;//表示u点已存入S集合中//更新distfor(intj=1;j<=n;++j)if((!s[j])&&c[u][j]<maxint){intnewdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}}//查找从源点v到终点u的路径，并输出voidsearchPath(int*prev,intv,intu){intque[maxnum];inttot=1;que[tot]=u;tot++;inttmp=prev[u];while(tmp!=v){que[tot]=tmp;tot++;tmp=prev[tmp];}que[tot]=v;for(inti=tot;i>=1;--i)if(i!=1)cout<<que[i]<<"->";elsecout<<que[i]<<endl;}intmain(){freopen("input.txt","r",stdin);//各数组都从下标1开始//输入结点数cin>>n;//输入路径数cin>>line;intp,q,len;//输入p,q两点及其路径长度//初始化c[][]为maxintfor(inti=1;i<=n;++i)for(intj=1;j<=n;++j)c[i][j]=maxint;for(inti=1;i<=line;++i){cin>>p>>q>>len;if(len<c[p][q])//有重边{c[p][q]=len;//p指向qc[q][p]=len;//q指向p，这样表示无向图}}for(inti=1;i<=n;++i)dist[i]=maxint;for(inti=1;i<=n;++i){for(intj=1;j<=n;++j)printf("%8d",c[i][j]);printf("\n");}Dijkstra(n,1,dist,prev,c);//最短路径长度cout<<"源点到最后一个顶点的最短路径长度:"<<dist[n]<<endl;//路径cout<<"源点到最后一个顶点的路径为:";searchPath(prev,1,n);}运行结果：算法分析下图为有向图G的带权邻接矩阵，运用Dijkstra算法计算从A到其余各顶点的最短路径以及其长度。ABCDEF┏┓分析可知：A┃∞∞10∞30100┃从A到C的最短路径为：AàC，其长度为10；B┃∞∞5∞∞∞┃从A到E的最短路径为：A->E,其长度为30；C┃∞∞∞50∞∞┃从A到D的最短路径为：AàE->D，其长度为50;D┃∞∞∞∞∞10┃从A到F的最短路径为：AàE->D->F，其长度为60;E┃∞∞∞20∞60┃而从A无法到达B。F┃∞∞∞∞∞∞┃易知：运行结果完全正确。┗┛心得体会熟悉了图的各种存储结构，特别是图的邻接矩阵和邻接表存储结构，掌握图的存储结构以及单源点最短路径算法；理解Dijkstra算法的原理，通过编程实现了Dijkstra算法，学会了用Dijkstra算法编程找出从s到t的最短路径。LZ77压缩算法实验报告一、实验内容：使用C++编程实现LZ77压缩算法的实现。二、实验目的：用LZ77实现文件的压缩。三、实验环境：1、软件环境：VisualC++6.02、编程语言：C++四、实验原理：LZ77算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。五、LZ77算法的基本流程：1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤2，否则进行步骤3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。代码如下：#include<windows.h>#include<stdio.h>#include<memory.h>#include"lz77.h"////////////////////////////////////////////////////////////////////outfileformat://0;flag2;buffer;0;flag2;buffer;...flag1;flag2;bufferlast//flag1-2bytes,sourcebufferblocklength//ifblocksizeis65536,bezero//flag2-2bytes,compressedbufferlength//ifcannotcompress,besamewithflag1//////////////////////////////////////////////////////////////////voidmain(intargc,char*argv[]){/*if(argc!=4){puts("Usage:");printf("Compress:%scsourcefiledestfile\n",argv[0]);printf("Decompress:%sdsourcefiledestfile\n",argv[0]);return;}*/ BYTEsoubuf[65536];BYTEdestbuf[65536+16]; FILE*in;FILE*out; /*in=fopen("input.txt","rb");if(in==NULL){ puts("Can'topensourcefile"); return;}out=fopen("compress.txt","wb");if(out==NULL){ puts("Can'topendestfile"); fclose(in); return;} fseek(in,0,SEEK_END); longsoulen=ftell(in); fseek(in,0,SEEK_SET); CCompressLZ77cc;WORDflag1,flag2;*/ inttemp;printf("compress(0)ordecompress(1)?:"); scanf("%d",&temp);if(temp==0)//compress{ in=fopen("input.txt","rb"); if(in==NULL) { puts("Can'topensourcefile"); return; } out=fopen("compress.txt","wb"); if(out==NULL) { puts("Can'topendestfile"); fclose(in); return; } fseek(in,0,SEEK_END); longsoulen=ftell(in); fseek(in,0,SEEK_SET); CCompressLZ77cc; WORDflag1,flag2;intlast=soulen,act;while(last>0){act=min(65536,last);fread(soubuf,act,1,in);last-=act;if(act==65536)//out65536bytesflag1=0;else//outlastblocksflag1=act;fwrite(&flag1,sizeof(WORD),1,out); intdestlen=cc.Compress((BYTE*)soubuf,act,(BYTE*)destbuf);if(destlen==0)//can'tcompresstheblock{flag2=flag1;fwrite(&flag2,sizeof(WORD),1,out);fwrite(soubuf,act,1,out);}else{flag2=(WORD)destlen;fwrite(&flag2,sizeof(WORD),1,out);fwrite(destbuf,destlen,1,out);}}}elseif(temp==1)//decompress{ in=fopen("compress.txt","rb"); if(in==NULL) { puts("Can'topensourcefile"); return; } out=fopen("decompress.txt","wb"); if(out==NULL) { puts("Can'topendestfile"); fclose(in); return; } fseek(in,0,SEEK_END); longsoulen=ftell(in); fseek(in,0,SEEK_SET); CCompressLZ77cc; WORDflag1,flag2;intlast=soulen,act;while(last>0){fread(&flag1,sizeof(WORD),1,in);fread(&flag2,sizeof(WORD),1,in);last-=2*sizeof(WORD);if(flag1==0)act=65536;elseact=flag1;last-=flag2?(flag2):act; if(flag2==flag1){fread(soubuf,act,1,in);}else{fread(destbuf,flag2,1,in);if(!cc.Decompress((BYTE*)soubuf,act,(BYTE*)destbuf)){puts("Decompresserror");fclose(in);fclose(out);return;}}fwrite((BYTE*)soubuf,act,1,out);}}else{puts("Usage:");printf("Compress:%scsourcefiledestfile\n",argv[0]);printf("Decompress:%sdsourcefiledestfile\n",argv[0]);} fclose(in);fclose(out);}////////////////////////////////LZ77.h////////////////////////////////使用在自己的堆中分配索引节点，不滑动窗口//每次最多压缩65536字节数据//的优化版本#ifndef_WIX_LZ77_COMPRESS_HEADER_001_#define_WIX_LZ77_COMPRESS_HEADER_001_//滑动窗口的字节大小#define_MAX_WINDOW_SIZE 65536classCCompress{public: CCompress(){}; virtual~CCompress(){};public: virtualintCompress(BYTE*src,intsrclen,BYTE*dest)=0; virtualBOOLDecompress(BYTE*src,intsrclen,BYTE*dest)=0;protected: //tools ///////////////////////////////////////////////////////// //CopyBitsInAByte:在一个字节范围内复制位流 //参数含义同CopyBits的参数 //说明： // 此函数由CopyBits调用，不做错误检查，即 // 假定要复制的位都在一个字节范围内 voidCopyBitsInAByte(BYTE*memDest,intnDestPos, BYTE*memSrc,intnSrcPos,intnBits); //////////////////////////////////////////////////////// //CopyBits:复制内存中的位流 // memDest-目标数据区 // nDestPos-目标数据区第一个字节中的起始位 // memSrc-源数据区 // nSrcPos-源数据区第一个字节的中起始位 // nBits-要复制的位数 // 说明： // 起始位的表示约定为从字节的高位至低位（由左至右） // 依次为0，，...,7 // 要复制的两块数据区不能有重合 voidCopyBits(BYTE*memDest,intnDestPos, BYTE*memSrc,intnSrcPos,intnBits); ////////////////////////////////////////////////////////////// //将DWORD值从高位字节到低位字节排列 voidInvertDWord(DWORD*pDW); ///////////////////////////////////////////////////////////// //设置byte的第iBit位为aBit // iBit顺序为高位起从记数（左起） voidSetBit(BYTE*byte,intiBit,BYTEaBit); //////////////////////////////////////////////////////////// //得到字节byte第pos位的值 // pos顺序为高位起从记数（左起） BYTEGetBit(BYTEbyte,intpos); //////////////////////////////////////////////////////////// //将位指针*piByte(字节偏移),*piBit(字节内位偏移)后移num位 voidMovePos(int*piByte,int*piBit,intnum); ///////////////////////////////////////////////////////// //取log2(n)的upper_bound intUpperLog2(intn); ///////////////////////////////////////////////////////// //取log2(n)的lower_bound intLowerLog2(intn);};classCCompressLZ77:publicCCompress{public: CCompressLZ77(); virtual~CCompressLZ77();public: ///////////////////////////////////////////// //压缩一段字节流 //src-源数据区 //srclen-源数据区字节长度,srclen<=65536 //dest-压缩数据区，调用前分配srclen字节内存 //返回值>0压缩数据长度 //返回值=0数据无法压缩 //返回值<0压缩中异常错误 intCompress(BYTE*src,intsrclen,BYTE*dest); ///////////////////////////////////////////// //解压缩一段字节流 //src-接收原始数据的内存区,srclen<=65536 //srclen-源数据区字节长度 //dest-压缩数据区 //返回值-成功与否 BOOLDecompress(BYTE*src,intsrclen,BYTE*dest);protected: BYTE*pWnd; //窗口大小最大为64k，并且不做滑动 //每次最多只压缩64k数据，这样可以方便从文件中间开始解压 //当前窗口的长度 intnWndSize; //对滑动窗口中每一个字节串排序 //排序是为了进行快速术语匹配 //排序的方法是用一个k大小的指针数组 //数组下标依次对应每一个字节串：(0000)(0001)...(0100)(0101)... //每一个指针指向一个链表，链表中的节点为该字节串的每一个出现位置 structSTIDXNODE { WORDoff; //在src中的偏移 WORDoff2; //用于对应的字节串为重复字节的节点 //指从off到off2都对应了该字节串 WORDnext; //在SortHeap中的指针 }; WORDSortTable[65536];//256*256指向SortHeap中下标的指针 //因为窗口不滑动，没有删除节点的操作，所以 //节点可以在SortHeap中连续分配 structSTIDXNODE*SortHeap; intHeapPos; //当前分配位置 //当前输出位置(字节偏移及位偏移) intCurByte,CurBit;protected: //////////////////////////////////////// //输出压缩码 //code-要输出的数 //bits-要输出的位数(对isGamma=TRUE时无效) //isGamma-是否输出为γ编码 void_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma); /////////////////////////////////////////////////////////// //在滑动窗口中查找术语 //nSeekStart-从何处开始匹配 //offset,len-用于接收结果，表示在滑动窗口内的偏移和长度 //返回值-是否查到长度为或以上的匹配字节串 BOOL_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len); /////////////////////////////////////////////////////////// //得到已经匹配了个字节的窗口位置offset //共能匹配多少个字节 inlineint_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset); ////////////////////////////////////////// //将窗口向右滑动n个字节 inlinevoid_ScrollWindow(intn); //向索引中添加一个字节串 inlinevoid_InsertIndexItem(intoff); //初始化索引表，释放上次压缩用的空间 void_InitSortTable();};#endif//_WIX_LZW_COMPRESS_HEADER_001_////////////////////////////////LZ77.CPP//////////////////////////////#include<windows.h>#include<stdio.h>#include<memory.h>#include<crtdbg.h>#include"lz77.h"///////////////////////////////////////////////////////////取log2(n)的upper_boundintCCompress::UpperLog2(intn){inti=0;if(n>0){intm=1;while(1){if(m>=n)returni;m<<=1;i++;}}elsereturn-1;}//UpperLog2////////////////////////////////////////////////////////////////////////////////////////////////////////////////////取log2(n)的lower_boundintCCompress::LowerLog2(intn){inti=0;if(n>0){intm=1;while(1){if(m==n)returni;if(m>n)returni-1;m<<=1;i++;}}elsereturn-1;}//LowerLog2///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////将位指针*piByte(字节偏移),*piBit(字节内位偏移)后移num位voidCCompress::MovePos(int*piByte,int*piBit,intnum){num+=(*piBit);(*piByte)+=num/8;(*piBit)=num%8;}//MovePos//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////得到字节byte第pos位的值//pos顺序为高位起从记数（左起）BYTECCompress::GetBit(BYTEbyte,intpos){intj=1;j<<=7-pos;if(byte&j)return1;elsereturn0;}//GetBit////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////设置byte的第iBit位为aBit//iBit顺序为高位起从记数（左起）voidCCompress::SetBit(BYTE*byte,intiBit,BYTEaBit){if(aBit)(*byte)|=(1<<(7-iBit));else(*byte)&=~(1<<(7-iBit));}//SetBit//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////将DWORD值从高位字节到低位字节排列voidCCompress::InvertDWord(DWORD*pDW){unionUDWORD{DWORDdw;BYTEb[4];};UDWORD*pUDW=(UDWORD*)pDW;BYTEb;b=pUDW->b[0];pUDW->b[0]=pUDW->b[3];pUDW->b[3]=b;b=pUDW->b[1];pUDW->b[1]=pUDW->b[2];pUDW->b[2]=b;}//InvertDWord////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBits:复制内存中的位流//memDest-目标数据区//nDestPos-目标数据区第一个字节中的起始位//memSrc-源数据区//nSrcPos-源数据区第一个字节的中起始位//nBits-要复制的位数//说明：//起始位的表示约定为从字节的高位至低位（由左至右）//依次为0，，...,7//要复制的两块数据区不能有重合voidCCompress::CopyBits(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits){intiByteDest=0,iBitDest;intiByteSrc=0,iBitSrc=nSrcPos;intnBitsToFill,nBitsCanFill;while(nBits>0){//计算要在目标区当前字节填充的位数nBitsToFill=min(nBits,iByteDest?8:8-nDestPos);//目标区当前字节要填充的起始位iBitDest=iByteDest?0:nDestPos;//计算可以一次从源数据区中复制的位数nBitsCanFill=min(nBitsToFill,8-iBitSrc);//字节内复制CopyBitsInAByte(memDest+iByteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsCanFill);//如果还没有复制完nBitsToFill个if(nBitsToFill>nBitsCanFill){iByteSrc++;iBitSrc=0;iBitDest+=nBitsCanFill;CopyBitsInAByte(memDest+iByteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsToFill-nBitsCanFill);iBitSrc+=nBitsToFill-nBitsCanFill;}else{iBitSrc+=nBitsCanFill;if(iBitSrc>=8){iByteSrc++;iBitSrc=0;}}nBits-=nBitsToFill;//已经填充了nBitsToFill位iByteDest++;}}//CopyBits////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBitsInAByte:在一个字节范围内复制位流//参数含义同CopyBits的参数//说明：//此函数由CopyBits调用，不做错误检查，即//假定要复制的位都在一个字节范围内voidCCompress::CopyBitsInAByte(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits){BYTEb1,b2;b1=*memSrc;b1<<=nSrcPos;b1>>=8-nBits;//将不用复制的位清b1<<=8-nBits-nDestPos;//将源和目的字节对齐*memDest|=b1;//复制值为的位b2=0xff;b2<<=8-nDestPos;//将不用复制的位置b1|=b2;b2=0xff;b2>>=nDestPos+nBits;b1|=b2;*memDest&=b1;//复制值为的位}//CopyBitsInAByte///////////////////////////////////////////////////////////------------------------------------------------------------------CCompressLZ77::CCompressLZ77(){SortHeap=newstructSTIDXNODE[_MAX_WINDOW_SIZE];}CCompressLZ77::~CCompressLZ77(){delete[]SortHeap;}//初始化索引表，释放上次压缩用的空间voidCCompressLZ77::_InitSortTable(){memset(SortTable,0,sizeof(WORD)*65536);nWndSize=0;HeapPos=1;}//向索引中添加一个字节串voidCCompressLZ77::_InsertIndexItem(intoff){WORDq;BYTEch1,ch2;ch1=pWnd[off];ch2=pWnd[off+1];if(ch1!=ch2){//新建节点q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}else{//对重复字节串//因为没有虚拟偏移也没有删除操作，只要比较第一个节点//是否和off相连接即可q=SortTable[ch1*256+ch2];if(q!=0&&off==SortHeap[q].off2+1){//节点合并SortHeap[q].off2=off;}else{//新建节点q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].off2=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}}}////////////////////////////////////////////将窗口向右滑动n个字节voidCCompressLZ77::_ScrollWindow(intn){for(inti=0;i<n;i++){nWndSize++;if(nWndSize>1)_InsertIndexItem(nWndSize-2);}}/////////////////////////////////////////////////////////////得到已经匹配了个字节的窗口位置offset//共能匹配多少个字节intCCompressLZ77::_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset){inti=2;//已经匹配了个字节intmaxsame=min(srclen-nSeekStart,nWndSize-offset);while(i<maxsame&&src[nSeekStart+i]==pWnd[offset+i])i++;_ASSERT(nSeekStart+i<=srclen&&offset+i<=nWndSize);returni;}/////////////////////////////////////////////////////////////在滑动窗口中查找术语//nSeekStart-从何处开始匹配//offset,len-用于接收结果，表示在滑动窗口内的偏移和长度//返回值-是否查到长度为或以上的匹配字节串BOOLCCompressLZ77::_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len){intj,m,n;if(nSeekStart<srclen-1){BYTEch1,ch2;ch1=src[nSeekStart];ch2=src[nSeekStart+1];WORDp;p=SortTable[ch1*256+ch2];if(p!=0){m=2;n=SortHeap[p].off;while(p!=0){j=_GetSameLen(src,srclen,nSeekStart,SortHeap[p].off);if(j>m){m=j;n=SortHeap[p].off;}p=SortHeap[p].next;}(*offset)=n;(*len)=m;returnTRUE;}}returnFALSE;}//////////////////////////////////////////输出压缩码//code-要输出的数//bits-要输出的位数(对isGamma=TRUE时无效)//isGamma-是否输出为γ编码voidCCompressLZ77::_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma){if(isGamma){BYTE*pb;DWORDout;//计算输出位数intGammaCode=(int)code-1;intq=LowerLog2(GammaCode);if(q>0){out=0xffff;pb=(BYTE*)&out;//输出q个CopyBits(dest+CurByte,CurBit,pb,0,q);MovePos(&CurByte,&CurBit,q);}//输出一个out=0;pb=(BYTE*)&out;CopyBits(dest+CurByte,CurBit,pb+3,7,1);MovePos(&CurByte,&CurBit,1);if(q>0){//输出余数,q位intsh=1;sh<<=q;out=GammaCode-sh;pb=(BYTE*)&out;InvertDWord(&out);CopyBits(dest+CurByte,CurBit,pb+(32-q)/8,(32-q)%8,q);MovePos(&CurByte,&CurBit,q);}}else{DWORDdw=(DWORD)code;BYTE*pb=(BYTE*)&dw;InvertDWord(&dw);CopyBits(dest+CurByte,CurBit,pb+(32-bits)/8,(32-bits)%8,bits);MovePos(&CurByte,&CurBit,bits);}}///////////////////////////////////////////////压缩一段字节流//src-源数据区//srclen-源数据区字节长度//dest-压缩数据区，调用前分配srclen+5字节内存//返回值>0压缩数据长度//返回值=0数据无法压缩//返回值<0压缩中异常错误intCCompressLZ77::Compress(BYTE*src,intsrclen,BYTE*dest){inti;CurByte=0;CurBit=0;intoff,len;if(srclen>65536)return-1;pWnd=src;_InitSortTable();for(i=0;i<srclen;i++){if(CurByte>=srclen)return0;if(_SeekPhase(src,srclen,i,&off,&len)){//输出匹配术语flag(1bit)+len(γ编码)+offset(最大bit)_OutCode(dest,1,1,FALSE);_OutCode(dest,len,0,TRUE);//在窗口不满k大小时，不需要位存储偏移_OutCode(dest,off,UpperLog2(nW