数据结构上机题（二）（C++语言）

说在前面的话

以下这几份代码看着不太像我写的，也记不起从哪儿搜集的……也挂上来，造福一下学弟学妹们。

以前写过的所有数据结构上机题代码已经上传到码云，点击查看

---

简易文本编辑器

#ifndef TEXTEDITOR_H_INCLUDED
#define TEXTEDITOR_H_INCLUDED

#include<iostream>
#include<list>
#include<fstream>
#include<algorithm>

using namespace std;

class TextEditor
{
private:
    int cursor;         //光标所在行
    int line;           //总行数
    int offset;         //光标所在行的偏移量
    int total;          //总字数
    int letters;        //字母总数
    int quots;          //其它字符总数
    int nums;           //数字总数
    int spaces;         //空格总数
    string textName;    //文档名字
    list<string> article;       //用来存储文本信息的链表
public:
    TextEditor();
    ~TextEditor();
    const string & getName() const;
    void setName(const string &name);
    int  getCursor(int *,int *) const;
    int moveCursor(int);
    int setCursor(int ,int);
    int addText(const string &);
    int insertText(string);
    int findTextInAll(const string &,int *,int *);
    int deleteText(const string &);
    int deleteText(int ,int,int);
    int saveFile();
    void wordState(int *,int *,int *,int *,int *) const;
    list<string>::iterator getIndex(int x);
    friend ostream & operator<<(ostream &,TextEditor &);
    friend istream & operator>>(istream &,TextEditor &);
};

TextEditor:: TextEditor()
{
    textName = "Untitled";
    cursor = 1;
    line = 1;
    offset = 0;
    total = 0;
    spaces = 0;
    quots = 0;
    letters = 0;
    nums = 0;
}

TextEditor::~TextEditor()
{

}

list<string>::iterator TextEditor::getIndex(int x)      //获取行数
{
    if(x < 0)
        x = 0;
    if(x > line)
        x= line;
    list<string>::iterator it;
    int l = 0;
    for(it = article.begin(); it != article.end(); it++)
    {
        l++;
        if(l == x)
            break;
    }
    return  it;
}

const string & TextEditor::getName() const
{
    return textName;
}

void TextEditor::setName(const string &name)
{
    if(name.length() != 0)
    {
        textName = name;
    }
}

int TextEditor::getCursor(int *pLine = NULL, int *pOffset = NULL) const    //获取光标位置
{
    *pLine = cursor;
    *pOffset = offset;
    return 1;
}

int TextEditor::moveCursor(int offset)
{
    list<string>::iterator it = getIndex(cursor);       //获取现在光标位置
    this->offset += offset;
    while( it->length()<this->offset && it != article.end())
    {
        this->offset -= it->length();
        cursor++;
        it++;
    }
    return 1;
}

int TextEditor::setCursor(int line ,int offset)
{
    if(line>article.size())
        line = article.size();
    this->cursor = line;
    if(offset<0)
        offset = 0;
    if(offset>getIndex(line)->length())
        offset = getIndex(line)->length();
    this->offset = offset;
    return 1;
}

int TextEditor::addText(const string & text)
{
    article.push_back(text);
    total += text.length();
    for(int i=0; i<text.length(); i++)
    {
        if(text[i]==' ')
            spaces++;
        else if(text[i]>='0' && text[i]<='9')
            nums++;
        else if(text[i]>='a' && text[i]<='z')
            letters++;
        else if(text[i]>='A' && text[i]<='Z')
            letters++;
        else
            quots++;
    }
    line++;
    return 1;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int TextEditor::insertText(string text)
{
    total += text.length();
    for(int i=0; i<text.length(); i++)
    {
        if(text[i]==' ')
            spaces++;
        else if(text[i]>='0'&&text[i]<='9')
            nums++;
        else if(text[i]>='a'&&text[i]<='z')
            letters++;
        else if(text[i]>='A'&&text[i]<='Z')
            letters++;
        else
            quots++;
    }
    if(article.empty())
    {
        article.push_back(text);
        offset = text.length();
        return 1;
    }
    list<string>::iterator it = getIndex(cursor);

    string temp = it->substr(0,offset);
    temp += text;
    temp += it->substr(offset);
    *it = temp;
    return 1;
}
int TextEditor::findTextInAll(const string & text ,int *line,int *offset)
{
    list<string>::iterator it;
    int l = 0;
    int li = *line;
    int pp = *offset;
    for(it = article.begin(); it != article.end(); it++)
    {
        l++;
        if(*line>l)
            continue;
        if(*line<l)
            *offset = -1;
        if(it->find(text,(*offset)+1) != string::npos)
        {
            *line = l;
            *offset = it->find(text,(*offset)+1);
            return 1;
        }
    }
    if(li == *line && pp == *offset)
        *offset = -1;
    return 1;
}

int TextEditor::deleteText(const string & text)
{
    int line = 1,offset = -1;
    findTextInAll(text, &line, &offset);
    while(1)
    {
        if(offset == -1)
            break;
        cout<<"是否删除第"<<line<<"行位置"<<offset<<"处的数据(Y of N):";
        char c[100];
        cin>>c;
        if(c[0]!='Y' && c[0]!='y')
            continue;
        deleteText(line,offset,text.length());
        findTextInAll(text,&line,&offset);
    }
}
int TextEditor::deleteText(int cursor ,int pos, int length)
{
    list<string>::iterator it = getIndex(cursor);
    total -= length;
    string text = *it;
    for(int i= pos; i<min(it->length(),pos+length); i++)
    {
        if(text[i]==' ')
            spaces--;
        else if(text[i]>='0'&&text[i]<='9')
            nums--;
        else if(text[i]>='a'&&text[i]<='z')
            letters--;
        else if(text[i]>='A'&&text[i]<='Z')
            letters--;
        else
            quots--;
    }
    *it = it->erase(pos,length);
}
void TextEditor::wordState(int *pTotal,int *pLetter,int *pDigit,int *pSpace,int *pQuot) const
{
    *pTotal = total;
    *pLetter = letters;
    *pDigit = nums;
    *pSpace = spaces;
    *pQuot = quots;
}
ostream & operator<<(ostream & out,TextEditor & editor)
{
    int line = 1;
    list<string>::iterator it;
    out<<"***********"<<editor.textName<<".txt*********"<<endl;
    for (it = editor.article.begin(); it != editor.article.end(); it++)
    {
        out<<line++<<":";
        out<<*it<<endl;
    }
    out<<endl;
    return out;
}
istream & operator>>(istream & in,TextEditor &editor)
{
    char s[100];
    getchar();
    gets(s);
    string text(s);
    editor.insertText(text);
    while(1)
    {
        cout<<"继续输入(Y 或 N)：";
        string c;
        in>>c;
        if(c[0]!='Y'&&c[0]!='y')
            break;
        getchar();
        gets(s);
        string ss(s);
        editor.insertText(ss);
    }
    return in;
}
int TextEditor::saveFile()
{
    string name = textName+".txt";
    ofstream out(name.c_str(),ios::out);
    list<string>::iterator it;
    for(it=article.begin(); it!=article.end(); it++)
    {
        out<<*it<<endl;
    }
    out.close();
}
#endif // TEXTEDITOR_H_INCLUDED

void showInstructions()
{
    cout<<"*************简易文本编辑器***************\n";
    cout<<"选择以下数字进行文本编辑"<<endl;
    cout<<"0.获取帮助信息"<<endl;
    cout<<"1.获取文档名字"<<endl;
    cout<<"2.设置文档名字"<<endl;
    cout<<"3.显示全文"<<endl;
    cout<<"4.移动光标位置"<<endl;
    cout<<"5.在光标处添加文字"<<endl;
    cout<<"6.在文档最后添加文字"<<endl;
    cout<<"7.统计文章字数"<<endl;
    cout<<"8.查找文本出现的位置"<<endl;
    cout<<"9.删除文本"<<endl;
    cout<<"10.保存文件"<<endl;
    cout<<"11.退出系统"<<endl;
    cout<<"******************************************"<<endl;
}
void getChoice()
{
    TextEditor editor;
    while(1)
    {
        cout<<"\n";
        cout<<"请选择(0.显示帮助)：";
        int n;
        cin>>n;
        if(n == 11) break;
        switch(n)
        {
        case 0:
        {
            showInstructions();
            break;
        }
        case 1:
        {
            cout<<"文档名称为："<<editor.getName()<<endl;
            break;
        }
        case 2:
        {
            string s;
            cout<<"请输入新的文档名字: ";
            cin>>s;
            editor.setName(s);
            cout<<"设置成功"<<endl;
            break;
        }
        case 3:
        {
            cout<<editor;
            int line,pos;
            editor.getCursor(&line,&pos);
            cout<<"光标目前的行数为："<<line<<" 偏移量为："<<pos<<endl;
            break;
        }
        case 4:
        {
            int line,pos;
            editor.getCursor(&line,&pos);
            cout<<"光标目前的行数为："<<line<<" 偏移量为："<<pos<<endl;
            cout<<"光标要移动的行数:";
            cin>>line;
            cout<<"光标在这一行的位置:";
            cin>>pos;
            editor.setCursor(line,pos);
            break;
        }
        case 5:
        {
            cout<<editor;
            int line,pos;
            editor.getCursor(&line,&pos);
            cout<<"光标目前的行数为："<<line<<" 偏移量为："<<pos<<endl;
            string text;
            cout<<"请输入你要写入的文字(英文)："<<endl;
            cin>>editor;
            break;
        }
        case 6:
        {
            cout<<"请输入要添加的文字："<<endl;
            string text;
            char s[100];
            getchar();
            gets(s);
            text = s;
            editor.addText(text);
            while(1)
            {
                cout<<"继续插入(Y 或 N)：";
                string c;
                cin>>c;
                if(c[0]!='Y'&&c[0]!='y') break;
                getchar();
                gets(s);
                text = s;
                editor.addText(text);
            }
            break;
        }
        case 7:
        {
            int total,space,num,quot,letter;
            editor.wordState(&total,&letter,&num,&space,&quot);
            cout<<"全文总数为："<<total<<endl;
            cout<<"全文字母数为："<<letter<<endl;
            cout<<"全文数字数为："<<num<<endl;
            cout<<"全文标点数为："<<quot<<endl;
            cout<<"全文空格数为："<<space<<endl;
            break;
        }
        case 8:
        {
            cout<<"请输入要查找的文本:"<<endl;
            string text;
            char s[100];
            getchar();
            gets(s);
            text = s;
            int line=1,offset=-1;
            editor.findTextInAll(text,&line,&offset);
            while(1)
            {
                if(offset==-1) break;
                cout<<"文本在第"<<line<<"行的第"<<offset<<"个位置"<<endl;
                editor.findTextInAll(text,&line,&offset);
            }
            break;
        }
        case 9:
        {
            cout<<"1.删除一段文本"<<endl;
            cout<<"2.删除特定位置的文本"<<endl;
            int as;
            cout<<"请输入选择：";
            cin>>as;
            if(as==1)
            {
                cout<<"请输入要删除的文字:"<<endl;
                string text;
                char s[100];
                getchar();
                gets(s);
                text = s;
                editor.deleteText(text);
                cout<<"删除成功"<<endl;
            }
            else if (as ==2)
            {
                cout<<"输入行号：";
                int line,pos,length;
                cin>>line;
                cout<<"\n输入位置：";
                cin>>pos;
                cout<<"\n输入长度：";
                cin>>length;
                editor.deleteText(line,pos,length);
                cout<<"删除成功"<<endl;
            }

            break;
        }
        case 10:
        {
            editor.saveFile();
            cout<<"保存文本成功！"<<endl;
            break;
        }
        default:
            cout<<"输入数字错误"<<endl;
            continue;
        }
    }
}
int main()
{
    showInstructions();
    getChoice();
    system("pause");
    return 0;
}

---

医院设施管理

#include<iostream>
#include<string>
#include<algorithm>
#include<time.h>
#include<stack>
#include<queue>

using namespace std;

//////////////////////////医院设施管理/////////////////////////////////////////
class hosnode//医院节点
{
    friend class hos;
    hosnode* father;//父亲指针；
    hosnode* left_child;//最左的孩子
    hosnode* right_brother;//右兄弟

    string name;//节点名称
    int num;//数量

public:
    hosnode(string name,int num)
    {
        this->name = name;
        this->num = num;
    }
    string getname()
    {
        return name;
    }
    int get_n()
    {
        return num;
    }
};

class hos//结构类（这里为医院结构类）
{
    hosnode* head;

public:
    hos(string name,int n)
    {
        head = new hosnode(name,n);
        head->left_child = NULL;
        head->right_brother = NULL;
        head->father = NULL;
    }
    hosnode *find(string name)
    {
        hosnode* temp = head;
        if(name == temp->name)
            return temp;

        queue<hosnode*> hosqueue;
        hosqueue.push(temp);
        while(!hosqueue.empty())
        {
            temp = hosqueue.front()->left_child;
            hosqueue.pop();         //出队列
            while(temp != NULL)
            {
                hosqueue.push(temp);
                if(name == temp->name)
                    return temp;

                temp = temp->right_brother;
            }
        }
        return 0;

    }
    bool insert(string father,string child,int n)
    {
        hosnode* temp = find(father);
        if(temp->left_child == NULL)
        {
            temp->left_child = new hosnode(child,n);
            temp->left_child->right_brother = NULL;
            temp->left_child->father = temp;
            temp->left_child->left_child = NULL;
        }
        else
        {
            temp = temp->left_child;
            while(temp->right_brother != NULL)
                temp = temp->right_brother;

            temp->right_brother = new hosnode(child,n);
            temp->right_brother->right_brother = NULL;
            temp->right_brother->father=find(father);
            temp->right_brother->left_child = NULL;
        }
        return 1;
    }
    int get_number(string father, string child)//
    {
        hosnode* p1 = find(father);
        hosnode* p2 = find(child);
        int sum = 1;
        while(p2!=NULL && p2!=p1)
        {
            sum *= p2->num;
            p2 = p2->father;
        }
        if(p2 == NULL)
        {
            return 0;
        }
        else
            return sum;
    }
    hosnode * get_this_and_all_childs(string name)
    {
        hosnode * temp=find(name);
        if(temp == NULL)
            return 0;
        else
        {
            cout<<temp->name<<"的所有孩子:";
            temp = temp->left_child;
            if(temp == NULL)
                cout<<"无";
            while(temp != NULL)
            {
                cout<<temp->name<<' '<<temp->get_n()<<" ";
                temp = temp->right_brother;
            }
            cout<<"\n";
            return find(name);
        }

    }
    void show_all()
    {
        hosnode* temp = head;
        get_this_and_all_childs(head->name);
        queue<hosnode*> hosqueue;
        hosqueue.push(temp);
        while(!hosqueue.empty())
        {
            temp = hosqueue.front()->left_child;//出队列
            hosqueue.pop();
            while(temp != NULL)
            {
                hosqueue.push(temp);
                get_this_and_all_childs(temp->name);
                temp = temp->right_brother;
            }
        }
    }

};
/////////////////////////////////////医院设施管理///////////////////////////////////
int main()
{
	hos a("医院",1);
	a.insert("医院","楼层",10);
	a.insert("楼层","配楼",4);
	a.insert("楼层","中央大厅",1);
	a.insert("中央大厅","电视",1);
	a.insert("中央大厅","沙发",2);
	a.insert("配楼","长走廊",2);
	a.insert("配楼","走廊连接",1);
	a.insert("走廊连接","库房",5);
	a.insert("长走廊","病房",21);
	a.insert("病房","卫生间",1);
	a.insert("病房","插座",4);
	a.insert("病房","病床",2);
	a.insert("卫生间","洗脸盆",1);
	a.insert("卫生间","座便器",1);
	a.insert("插座","插口",2);
	a.insert("插座","面板",1);

	cout<<"每个楼层共有"<<a.get_number("楼层","病房")<<"个病房"<<endl;
	cout<<"每个长走廊共有"<<a.get_number("长走廊","病房")<<"个病房"<<endl;
	cout<<"每个病房共有"<<a.get_number("病房","插口")<<"个插口"<<endl;
	cout<<"整个医院共有"<<a.get_number("医院","插口")<<"个插口"<<endl;
	a.get_this_and_all_childs("楼层");

	cout<<"\n\n\n";
	a.show_all();
}

图像压缩

// Huffman2005.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Windows.h"
#include "math.h"
#include <time.h>

//几个全局变量，存放读入图像的位图数据、宽、高、颜色表及每像素所占位数(比特)
//此处定义全局变量主要为了后面的图像数据访问及图像存储作准备
unsigned char *pBmpBuf;//读入图像数据的指针
int bmpWidth;//图像的宽
int bmpHeight;//图像的高
int imgSpace;//图像所需空间
RGBQUAD *pColorTable;//颜色表指针
int biBitCount;//图像类型
char str[100];//文件名称
int Num[300];//各灰度值出现的次数
float Feq[300];//各灰度值出现的频率
unsigned char *lpBuf;//指向图像像素的指针
unsigned char *m_pDib;//存放打开文件的DIB

int NodeNum;    //Huffman树总节点个数
int NodeStart;  //Huffman树起始节点
struct Node         //Huffman树节点
{
    int color;      //记录叶子节点的灰度值（非叶子节点为 -1）
    int lson,rson;  //节点的左右儿子（若没有则为 -1）
    int num;        //节点的数值（编码依据）
    int mark;       //记录节点是否被用过(用过为1，没用过为0)
} node[600];
char CodeStr[300][300]; //记录编码值
int CodeLen[300];       //编码长度
bool ImgInf[8000000];   //图像信息
int InfLen;             //图像信息长度


/***********************************************************************
* 函数名称：
* readBmp()
*
*函数参数：
*  char *bmpName -文件名字及路径
*
*返回值：
*   0为失败,1为成功
*
*说明：给定一个图像文件名及其路径，读图像的位图数据、宽、高、颜色表及每像素
*      位数等数据进内存,存放在相应的全局变量中
***********************************************************************/
bool readBmp(char *bmpName)
{
    //二进制读方式打开指定的图像文件
    FILE *fp=fopen(bmpName,"rb");
    if(fp==0)
    {
        printf("未找到指定文件！\n");
        return 0;
    }


    //跳过位图文件头结构BITMAPFILEHEADER
    fseek(fp, sizeof(BITMAPFILEHEADER),0);


    //定义位图信息头结构变量，读取位图信息头进内存，存放在变量head中
    BITMAPINFOHEADER head;
    fread(&head, sizeof(BITMAPINFOHEADER), 1,fp);

    //获取图像宽、高、每像素所占位数等信息
    bmpWidth = head.biWidth;
    bmpHeight = head.biHeight;
    biBitCount = head.biBitCount;

    //定义变量，计算图像每行像素所占的字节数（必须是4的倍数）
    int lineByte=(bmpWidth * biBitCount/8+3)/4*4;

    //灰度图像有颜色表，且颜色表表项为256
    if(biBitCount==8)
    {
        //申请颜色表所需要的空间，读颜色表进内存
        pColorTable=new RGBQUAD[256];
        fread(pColorTable,sizeof(RGBQUAD),256,fp);
    }

    //申请位图数据所需要的空间，读位图数据进内存
    pBmpBuf=new unsigned char[lineByte * bmpHeight];
    fread(pBmpBuf,1,lineByte * bmpHeight,fp);

    //关闭文件
    fclose(fp);

    return 1;
}

/***********************************************************************

保存信息

***********************************************************************/
//二进制转十进制
int Change2to10(int pos)
{
    int i,j,two = 1;
    j = 0;
    for(i = pos + 7; i >= pos; i --)
    {
        j += two * ImgInf[i];
        two *= 2;
    }
    return j;
}

//保存Huffman编码树
int saveInfo(char *writePath,int lineByte)
{
    int i,j,k;

    FILE *fout;
    fout = fopen(writePath,"w");
    fprintf(fout,"%d %d %d\n",NodeStart,NodeNum,InfLen);//输出起始节点、节点总数、图像所占空间
    for(i = 0; i < NodeNum; i ++)    //输出Huffman树
    {
        fprintf(fout,"%d %d %d\n",node[i].color,node[i].lson,node[i].rson);
    }

    /*for(i = 0;i < InfLen;i ++){
    fprintf(fout,"%d",ImgInf[i]);
    }
    fprintf(fout,"\n");*/

    fclose(fout);

    return 0;
}

//保存文件
bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height,
             int biBitCount, RGBQUAD *pColorTable)
{
    //如果位图数据指针为0,则没有数据传入,函数返回
    if(!imgBuf)
        return 0;

    //颜色表大小,以字节为单位,灰度图像颜色表为1024字节,彩色图像颜色表大小为0
    int colorTablesize=0;
    if(biBitCount==8)
        colorTablesize=1024;

    //待存储图像数据每行字节数为4的倍数
    int lineByte=(width * biBitCount/8+3)/4*4;

    //以二进制写的方式打开文件
    FILE *fp=fopen(bmpName,"wb");
    if(fp==0) return 0;

    //申请位图文件头结构变量，填写文件头信息
    BITMAPFILEHEADER fileHead;
    fileHead.bfType = 0x4D42;//bmp类型

    //bfSize是图像文件4个组成部分之和
    fileHead.bfSize= sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER)
                     + colorTablesize + lineByte*height;
    fileHead.bfReserved1 = 0;
    fileHead.bfReserved2 = 0;

    //bfOffBits是图像文件前三个部分所需空间之和
    fileHead.bfOffBits=54+colorTablesize;

    //写文件头进文件
    fwrite(&fileHead, sizeof(BITMAPFILEHEADER),1, fp);

    //申请位图信息头结构变量，填写信息头信息
    BITMAPINFOHEADER head;
    head.biBitCount=biBitCount;
    head.biClrImportant=0;
    head.biClrUsed=0;
    head.biCompression=0;
    head.biHeight=height;
    head.biPlanes=1;
    head.biSize=40;
    head.biSizeImage=lineByte*height;
    head.biWidth=width;
    head.biXPelsPerMeter=0;
    head.biYPelsPerMeter=0;
    //写位图信息头进内存
    fwrite(&head, sizeof(BITMAPINFOHEADER),1, fp);

    //如果灰度图像,有颜色表,写入文件
    if(biBitCount==8)
        fwrite(pColorTable, sizeof(RGBQUAD),256, fp);

    //写位图数据进文件
    //fwrite(imgBuf, height*lineByte, 1, fp);
    fwrite(imgBuf, InfLen / 8, 1, fp);


    //关闭文件
    fclose(fp);

    return 1;
}


/*********************

Huffman编码图像解码

*********************/
//读入编码图像
bool readHuffman(char *Name)
{
    int i,j;
    char NameStr[100];
    //读取Huffman编码信息和编码树
    strcpy(NameStr,Name);
    strcat(NameStr,".bpt");
    FILE *fin = fopen(NameStr,"r");
    if(fin == 0)
    {
        printf("未找到指定文件！\n");
        return 0;
    }
    fscanf(fin,"%d %d %d",&NodeStart,&NodeNum,&InfLen);
    //printf("%d %d %d\n",NodeStart,NodeNum,InfLen);
    for(i = 0; i < NodeNum; i ++)
    {
        fscanf(fin,"%d %d %d",&node[i].color,&node[i].lson,&node[i].rson);
        //printf("%d %d %d\n",node[i].color,node[i].lson,node[i].rson);
    }

    //二进制读方式打开指定的图像文件
    strcpy(NameStr,Name);
    strcat(NameStr,".bhd");
    FILE *fp=fopen(NameStr,"rb");
    if(fp==0)
    {
        printf("未找到指定文件！\n");
        return 0;
    }

    //跳过位图文件头结构BITMAPFILEHEADER
    fseek(fp, sizeof(BITMAPFILEHEADER),0);

    //定义位图信息头结构变量，读取位图信息头进内存，存放在变量head中
    BITMAPINFOHEADER head;
    fread(&head, sizeof(BITMAPINFOHEADER), 1,fp);

    //获取图像宽、高、每像素所占位数等信息
    bmpWidth = head.biWidth;
    bmpHeight = head.biHeight;
    biBitCount = head.biBitCount;

    //定义变量，计算图像每行像素所占的字节数（必须是4的倍数）
    int lineByte=(bmpWidth * biBitCount/8+3)/4*4;

    //灰度图像有颜色表，且颜色表表项为256
    if(biBitCount==8)
    {
        //申请颜色表所需要的空间，读颜色表进内存
        pColorTable=new RGBQUAD[256];
        fread(pColorTable,sizeof(RGBQUAD),256,fp);
    }

    //申请位图数据所需要的空间，读位图数据进内存
    pBmpBuf=new unsigned char[lineByte * bmpHeight];
    fread(pBmpBuf,1,InfLen / 8,fp);

    //关闭文件
    fclose(fp);

    return 1;
}

void HuffmanDecode()
{
    //获取编码信息
    int i,j,tmp;
    int lineByte=(bmpWidth * biBitCount/8+3)/4*4;
    for(i = 0; i < InfLen / 8; i ++)
    {
        j = i * 8 + 7;
        tmp = *(pBmpBuf + i);
        while(tmp > 0)
        {
            ImgInf[j] = tmp % 2;
            tmp /= 2;
            j --;
        }
    }
    /*for(i = 0;i < InfLen;i ++)
    printf("%d",ImgInf[i]);
    printf("\n");*/

    //解码
    int p = NodeStart;  //遍历指针位置
    j = 0;
    i = 0;
    do
    {
        if(node[p].color >= 0)
        {
            *(pBmpBuf + j) = node[p].color;
            //printf("%d ",*(pBmpBuf + j));
            j ++;
            p = NodeStart;
        }
        if(ImgInf[i] == 1)
            p = node[p].lson;
        else if(ImgInf[i] == 0)
            p = node[p].rson;
        i ++;
    }
    while(i <= InfLen);
    //printf("\nj: %d\n",j);
}


/*********************

Huffman编码

*********************/
//Huffman编码初始化
void HuffmanCodeInit()
{
    int i;
    for(i = 0; i <256; i ++) //灰度值记录清零
        Num[i] = 0;
    //初始化哈夫曼树
    for(i = 0; i < 600; i ++)
    {
        node[i].color = -1;
        node[i].lson  = node[i].rson = -1;
        node[i].num   = -1;
        node[i].mark  = 0;
    }
    NodeNum = 0;
}

//深搜遍历Huffman树获取编码值
char CodeTmp[300];
void dfs(int pos,int len)
{
    //遍历左儿子
    if(node[pos].lson != -1)
    {
        CodeTmp[len] = '1';
        dfs(node[pos].lson,len + 1);
    }
    else
    {
        if(node[pos].color != -1)
        {
            CodeLen[node[pos].color] = len;
            CodeTmp[len] = '\0';
            strcpy(CodeStr[node[pos].color],CodeTmp);
        }
    }

    //遍历右儿子
    if(node[pos].lson != -1)
    {
        CodeTmp[len] = '0';
        dfs(node[pos].rson,len + 1);
    }
    else
    {
        if(node[pos].color != -1)
        {
            CodeLen[node[pos].color] = len;
            CodeTmp[len] = '\0';
            strcpy(CodeStr[node[pos].color],CodeTmp);
        }
    }
}

//寻找值最小的节点
int MinNode()
{
    int i,j = -1;
    for(i = 0; i < NodeNum; i ++)
        if(!node[i].mark)
            if(j == -1 || node[i].num < node[j].num)
                j = i;
    if(j != -1)
    {
        NodeStart = j;
        node[j].mark = 1;
    }
    return j;
}

//编码主函数
void HuffmanCode()
{
    int i,j,k,a,b;

    for(i = 0; i < 256; i ++)
    {
        //创建初始节点
        Feq[i] = (float)Num[i] / (float)(bmpHeight * bmpWidth);//计算灰度值频率
        if(Num[i] > 0)
        {
            node[NodeNum].color = i;
            node[NodeNum].num = Num[i];
            node[NodeNum].lson = node[NodeNum].rson = -1;   //叶子节点无左右儿子
            NodeNum ++;
        }
    }

    while(1)
    {
        //找到两个值最小的节点，合并成为新的节点
        a = MinNode();
        if(a == -1)
            break;
        b = MinNode();
        if(b == -1)
            break;

        //构建新节点
        node[NodeNum].color = -1;
        node[NodeNum].num = node[a].num + node[b].num;
        node[NodeNum].lson = a;
        node[NodeNum].rson = b;
        NodeNum ++;
        //node[a].mark = node[b].mark = 1;
    }

    //根据建好的Huffman树编码(深搜实现)
    dfs(NodeStart,0);

    //屏幕输出编码
    int sum = 0;
//  printf("Huffman编码信息如下：\n");
    for(i = 0; i < 256; i ++)
        if(Num[i] > 0)
        {
            sum += CodeLen[i] * Num[i];
//          printf("灰度值：%3d  频率: %f  码长: %2d  编码: %s\n",i,Feq[i],CodeLen[i],CodeStr[i]);
        }
//      printf("原始总码长：%d\n",bmpWidth * bmpHeight * 8);
//      printf("Huffman编码总码长：%d\n",sum);
//      printf("压缩比：%.3f : 1\n",(float)(bmpWidth * bmpHeight * 8) / (float)sum);

    //记录图像信息
    InfLen = 0;
    int lineByte=(bmpWidth * biBitCount/8+3)/4*4;
    for(i = 0; i < bmpHeight; i ++)
        for(j = 0; j < bmpWidth; j ++)
        {
            lpBuf = (unsigned char *)pBmpBuf + lineByte * i + j;
            for(k = 0; k < CodeLen[*(lpBuf)]; k ++)
            {
                ImgInf[InfLen ++] = (int)(CodeStr[*(lpBuf)][k] - '0');
            }
        }

    //再编码数据
    j = 0;
    for(i = 0; i < InfLen;)
    {
        *(pBmpBuf + j) = Change2to10(i);
        i += 8;
        j ++;
    }
}

/******************************

主函数

******************************/

int main(int argc, char** argv)
{

    int ord;//命令
    char c;
    int i,j;
    clock_t start,finish;
    int total_time;

//  CString str;

    while(1)
    {
        printf("本程序提供以下功能\n\n\t1.256色灰度BMP图像Huffman编码\n\t2.Huffman编码BMP文件解码\n\t3.退出\n\n请选择需要执行的命令:");
        scanf("%d%c",&ord,&c);

        if(ord == 1)
        {
            printf("\n---256色灰度BMP图像Huffman编码---\n");
            printf("\n请输入要编码图像名称：");
            scanf("%s",str);

            //读入指定BMP文件进内存
            char readPath[100];
            strcpy(readPath,str);
            strcat(readPath,".bmp");
            if(readBmp(readPath))
            {
                //输出图像的信息
                //printf("\n图像信息：\nwidth=%d,height=%d,biBitCount=%d\n",bmpWidth,bmpHeight,biBitCount);

                int lineByte=(bmpWidth * biBitCount/8+3)/4*4;

                if(biBitCount==8)
                {
                    //编码初始化

                    HuffmanCodeInit();

                    //计算每个灰度值出现的次数
                    for(i = 0; i < bmpHeight; i ++)
                        for(j = 0; j < bmpWidth; j ++)
                        {
                            lpBuf = (unsigned char *)pBmpBuf + lineByte * i + j;
                            Num[*(lpBuf)] += 1;
                        }

                    //调用编码
                    start=clock();
                    HuffmanCode();
                    finish=clock();
                    total_time=(finish-start);
                    printf("识别一张耗时：　%d毫秒",total_time);

                    //将图像数据存盘
                    char writePath[100];
                    //保存编码后的bmp
                    strcpy(writePath,str);
                    strcat(writePath,"_Huffman.bhd");
                    saveBmp(writePath, pBmpBuf, bmpWidth, bmpHeight, biBitCount, pColorTable);
                    //保存Huffman编码信息和编码树
                    strcpy(writePath,str);
                    strcat(writePath,"_Huffman.bpt");
                    saveInfo(writePath,lineByte);
                    printf("\n编码完成!编码信息保存在 %s_Huffman 文件中\n\n",str);
                }
                else
                {
                    printf("本程序只支持256色BMP编码！\n");
                }



                //清除缓冲区，pBmpBuf和pColorTable是全局变量，在文件读入时申请的空间
                delete []pBmpBuf;
                if(biBitCount==8)
                    delete []pColorTable;
            }

            printf("\n-----------------------------------------------\n\n\n");
        }
        else if(ord == 2)
        {
            printf("\n---Huffman编码BMP文件解码---\n");
            printf("\n请输入要解码文件名称：");
            scanf("%s",str);

            //编码解码初始化
            HuffmanCodeInit();

            if(readHuffman(str))
            {
                //读取文件
                HuffmanDecode();    //Huffman解码

                //将图像数据存盘
                char writePath[100];
                //保存解码后的bmp
                strcpy(writePath,str);
                strcat(writePath,"_Decode.bmp");
                InfLen = bmpWidth * bmpHeight * 8;
                saveBmp(writePath, pBmpBuf, bmpWidth, bmpHeight, biBitCount, pColorTable);
                system(writePath);

                printf("\n解码完成!保存为 %s_Decode.bmp\n\n",str);
            }
            printf("\n-----------------------------------------------\n\n\n");

        }
        else if(ord == 3)
            break;
    }

    return 0;   /* ANSI C requires main to return int. */
}