数据结构实验报告

右边👉是实验报告文档→📖

实验一 顺序表的操作

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
#define ElemType int
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW 3
#define MAXSIZE 100
typedef struct{
    ElemType* elem;
    int length;
}SqList;
Status InitList(SqList &L);//初始化
Status ClearList(SqList &L);//清空
Status ListEmpty(SqList L);//判断是否为空
Status GetElem(SqList L,int i,ElemType& e);//获取表中第i位的元素
Status ListLength(SqList L);//求线性表的长度
Status ListInsert(SqList &L,int i,ElemType e);//在线性表指定位置插入元素
void   ShowList(SqList L);//显示线性表所有元素
Status ListDelete(SqList& L,int i);//删除线性表指定位置元素
Status LocateElem(SqList L,int e);//定位第一个i出现的位置
Status NextElem(SqList L,int cur_e,int& next_e);//求后继
Status PriorElem(SqList L,int cur_e,int& pre_e);//求前驱
int main()
{
    int order;
    SqList L;
    if(InitList(L)){
        cout<<"初始化成功!\n";
    }else cout<<"初始化失败!\n";
    while(true){
        cout << "Menu***********************************\n";
        cout << "1---(清空) 清空线性表\n";             //ClearList(&L)
        cout << "2---(判空) 判断线性表是否为空\n";      //ListEmpty(L)
        cout << "3---(求长) 求线性表长度\n";           //ListLength(L)
        cout << "4---(获取) 获取线性表指定位置元素\n";   //GetElem()
        cout << "5---求前驱\n";                 //PriorElem(L,cur_e,&pre_e)
        cout << "6---求后继\n";                 //NextElem(L,cur_e,&next_e)
        cout << "7---(插入) 在线性表指定位置插入元素\n";  //ListInsert(&L,i,e)
        cout << "8---(删除) 删除线性表指定位置元素\n";    //ListDelete(&L,i)
        cout << "9---显示线性表\n";              //ShowList(L)
        cout << "10--定位\n";                   //LocateElem(L,e)
        cout << "11--求两个集合的交集,并集和差集\n";//
        cout << "    退出，输入一个负数！\n";
        cout << "Menu***********************************\n";
        cout << "请输入操作代码：";
        cin >> order;
        if (order < 0) return 0;
        cout << "\n";
        int i;
        ElemType e,cur_e,pre_e,next_e;
        switch (order) {
            case 1:
                cout << (ClearList(L) ? "清空成功!\n" : "清空失败!\n");
                cout << "线性表长度为:" << ListLength(L) << "\n";
                break;
            case 2:
                cout << (ListEmpty(L) ? "线性表为空\n" : "线性表不为空\n");
                break;
            case 3:
                cout << "线性表长度为:" << ListLength(L) << "\n";
                break;
            case 4:
                cout << "请输入要获取第几位元素:";
                cin >> i;
                if (GetElem(L, i, e))
                    cout << "第" << i << "位元素是:" << e << "\n";
                else cout << "第" << i << "位元素不存在!\n";
                break;
            case 5:
                cout<<"请输入你要求谁的前驱:";
                cin>>cur_e;
                if(PriorElem(L,cur_e,pre_e)) cout<<cur_e<<"的前驱是:"<<pre_e<<"\n";
                else cout<<"该元素不存在或者没有前驱\n";
                break;
            case 6:
                cout<<"请输入你要求谁的后继:";
                cin>>cur_e;
                if(NextElem(L,cur_e,next_e)) cout<<cur_e<<"的后继是:"<<next_e<<"\n";
                else cout<<"该元素不存在或者没有后继\n";
                break;
            case 7:
                cout << "请输入插入位置:";
                cin >> i;
                cout << "请输入插入数据:";
                cin >> e;
                cout << (ListInsert(L, i, e) ? "插入成功!\n" : "插入失败!\n");
                break;
            case 8:
                cout << "请输入你要删除的位置:";
                cin >> i;
                cout << (ListDelete(L, i) ? "删除成功!\n" : "删除失败!\n");
                break;
            case 9:
                ShowList(L);
                break;
            case 10:
                cout<<"请输入你要定位的元素:";
                cin>>e;
                if(LocateElem(L,e)) cout<<e<<"的位置是"<<LocateElem(L,e)<<"\n";
                else cout<<"不存在\n";
                break;
            case 11:
                SqList A,B;
                InitList(A);
                for(int i=0;i<10;i++){
                    ListInsert(A,i+1,i+1);
                }
                cout<<"已经生成了A,";
                ShowList(A);
                InitList(B);
                for(int i=0;i<10;i++){
                    ListInsert(B,i+1,i+6);
                }
                cout<<"已经生成了集合B,";
                ShowList(B);
                cout<<"A和B的交集是:";
                for(int i=0;i<A.length;i++){
                    for(int j=0;j<B.length;j++){
                        if(A.elem[i]==B.elem[j]){
                            cout<<A.elem[i]<<" ";
                            break;
                        }
                    }
                }
                cout<<"\nA和B的并集是:";
                for(int i=0;i<A.length;i++){
                    if(LocateElem(B,A.elem[i])) continue;
                    else cout<<A.elem[i]<<" ";
                }
                for(int i=0;i<B.length;i++){
                    cout<<B.elem[i]<<" ";
                }
                cout<<"\nA和B的差集如下:\n";
                cout<<"    A-B=";
                for(int i=0;i<A.length;i++){
                    if(LocateElem(B,A.elem[i])) continue;
                    else cout<<A.elem[i]<<" ";
                }
                cout<<"\n    B-A=";
                for(int i=0;i<B.length;i++){
                    if(LocateElem(A,B.elem[i])) continue;
                    else cout<<B.elem[i]<<" ";
                }
                cout<<"\n";
                break;
            default:
                cout << "输入命令错误！";
                break;
        }
        cout<<"按回车键继续....";
        getchar();getchar();
    }
}
Status InitList(SqList &L){
    L.elem=new ElemType[MAXSIZE];
    if(!L.elem) exit(OVERFLOW);
    L.length=0;
    return OK;
}
Status ClearList(SqList &L){
    L.length=0;
    return OK;
}
Status ListEmpty(SqList L){
    return (!L.length);
}
Status GetElem(SqList L,int i,ElemType& e){
    if(i<=0||i>L.length) return ERROR;
    e=L.elem[i-1];
    return OK;
}
Status ListLength(SqList L){
    return L.length;
}
Status ListInsert(SqList &L,int i,ElemType e){
    if(i<=0||i>L.length+1) return ERROR;
    if(L.length==MAXSIZE) return ERROR;
    for(int j=L.length-1;j>=i-1;j--){
        L.elem[j+1]=L.elem[j];
    }
    L.elem[i-1]=e;
    L.length++;
    return OK;
}
void ShowList(SqList L){
    if(ListEmpty(L)) {
        cout<<"线性表为空!\n";
        return ;
    }else cout<<"线性表元素为:";
    for(int i=0;i<L.length;i++){
        cout<<L.elem[i]<<" ";
    }cout<<"\n";
}
Status ListDelete(SqList& L,int i){
    if(i<=0||i>L.length) return ERROR;
    for(int j=i;j<L.length;j++){
        L.elem[i-1]=L.elem[i];
    }
    L.length--;
    return OK;
}
Status LocateElem(SqList L,int e){
    for(int i=0;i<L.length;i++){
        if(L.elem[i]==e) return i+1;
    }
    return ERROR;
}
Status PriorElem(SqList L,int cur_e,int &pre_e){
    int ret=LocateElem(L,cur_e);
    if(ret&&ret!=1){
        pre_e=L.elem[ret-2];
        return OK;
    }else return ERROR;
}
Status NextElem(SqList L,int cur_e,int &next_e){
    int ret=LocateElem(L,cur_e);
    if(ret&&ret!=L.length){
        next_e=L.elem[ret];
        return OK;
    }else return ERROR;
}

实验二 单链表的操作

#include<iostream>
#define ElemType int
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
    ElemType data;
    LNode* next;
}LNode,*LinkList;
Status InitList(LinkList &L);//单链表的初始化
void CreateList_H(LinkList &L,int n);//前插法创建单链表
void CreateList_R(LinkList &L,int n);//后插法创建单链表
LNode* LocateElem(LinkList L,ElemType e);//定位单链表中的元素位置
Status ListInsert(LinkList &L,int i,ElemType e);//插入元素
Status ListDelete(LinkList &L,int i);//删除元素
void ShowList(LinkList L);//显示链表内容
void Merge(LinkList A,LinkList B,LinkList &C);//合并两个单链表
using namespace std;
int main()
{
    LinkList L;
    while(true){
        cout<<"1710121058李博\n";
        cout<<"0----初始化创建空的单链表\n";
        cout<<"1----前插法创建单链表插入n个元素\n";
        cout<<"2----后插法创建单链表插入n个元素\n";
        cout<<"3----查找单链表\n";
        cout<<"4----插入单链表\n";
        cout<<"5----删除单链表\n";
        cout<<"6----两个有序单链表的归并运算\n";
        cout<<"7----显示单链表所有元素\n";
        cout<<"输入负数退出\n";
        int order,i,e,n;
        cout<<"请输入你要执行的操作:";
        cin>>order;
        if(order<0) break;
        switch(order){
            case 0:
                if(InitList(L)) cout<<"初始化成功!\n";
                else cout<<"初始化失败!\n";
                break;
            case 1:
                cout<<"请输入你要建的链表长度n和n个内容:";
                cin>>n;
                CreateList_H(L,n);
                break;
            case 2:
                cout<<"请输入你要建的链表长度n和n个内容:";
                cin>>n;
                CreateList_R(L,n);
                break;
            case 3:
                cout<<"请输入你需要查找的元素:";
                cin>>e;
                if(LocateElem(L,e)) cout<<"元素"<<e<<"的位置在"<<LocateElem(L,e)<<"\n";
                else cout<<"该元素不在链表中!\n";
                break;
            case 4:
                cout<<"请输入你要插入的位置和插入的元素(空格隔开):";
                cin>>i>>e;
                ListInsert(L,i,e);
                break;
            case 5:
                cout<<"请输入你要删除元素的位置:";
                cin>>i;
                cout<<(ListDelete(L,i)?"删除成功!\n":"删除失败!\n");
                break;
            case 6:
                LinkList A,B,C;
                cout<<"首先建立两个有序的单链表A和B\n";
                cout<<"请输入A的长度n和n个内容:";
                cin>>n;
                CreateList_R(A,n);
                cout<<"请输入B的长度n和n个内容:";
                cin>>n;
                CreateList_R(B,n);
                cout<<"已经建立好单链表A和B\n";
                cout<<"建立好的表分别如下:\n";
                InitList(C);
                cout<<"A"; ShowList(A);
                cout<<"B"; ShowList(B);
                Merge(A,B,C);
                cout<<"合并以后的";
                ShowList(C);
                break;
            case 7:
                ShowList(L);
                break;
            default:
                cout<<"输入指令错误!\n";
                break;
        }
        cout<<"按回车键继续...\n";
        getchar();
        getchar();
    }

    return 0;
}
Status InitList(LinkList &L){
    L=new LNode;
    L->next=NULL;
    return OK;
}
void CreateList_H(LinkList &L,int n){//逆序位输入n个元素的值,建立带表头结点的单链表
    L=new LNode;
    L->next=NULL;
    for(int i=0;i<n;i++){
        LNode* p=new LNode;
        cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}
void CreateList_R(LinkList &L,int n){//正位序输入n个元素的值,建立带表头节点的单链表
    L=new LNode;
    LNode* r=L;
    for(int i=0;i<n;i++){
        LNode* p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
LNode *LocateElem(LinkList L,ElemType e){
    LNode* p=L->next;
    while(p&&p->data!=e){
        p=p->next;
    }
    return p;
}
Status ListInsert(LinkList &L,int i,ElemType e){
    LNode* p=L;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||j>i-1) return ERROR;
    LNode* s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}
Status ListDelete(LinkList &L,int i){
    LNode* p=L;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1) return ERROR;
    LNode* q=p->next;
    p->next=q->next;
    delete(q);
    return OK;
}
void ShowList(LinkList L){
    LNode* p=L;
    if(p->next==NULL){
        cout<<"链表为空\n";
        return ;
    }
    cout<<"链表内容为:";
    while(p->next){
        p=p->next;
        cout<<p->data<<" ";
    }
    cout<<endl;
}
void Merge(LinkList A,LinkList B,LinkList &C){
    LNode* pa=A->next;
    LNode* pb=B->next;
    C=A;
    LNode* pc=C;
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    } 
    pc->next=pa?pa:pb;  
}

实验三 栈和队列的操作

#include<iostream>
#define MAXSIZE 100
#define SElemType int
#define QElemType int
typedef int Status;
#define OK 1
#define OVERFLOW -2
#define ERROR 0
using namespace std;
///--------------栈操作部分--------------///
typedef struct{
    SElemType *base;
    SElemType *top;
    int stackSize;
}SqStack;
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

Status InitStack(SqStack &S){
    S.base=new SElemType[MAXSIZE];
    if(!S.base) exit(OVERFLOW);
    S.top=S.base;
    S.stackSize=MAXSIZE;
    return OK;
}
Status InitStack(LinkStack &S){
    S=NULL;
    return OK;
}
SElemType GetTop(SqStack S){
    if(S.base!=S.top){
        cout<<"栈顶元素为:"<<*(S.top-1)<<"\n";
    }else{
        cout<<"栈为空\n";
    }
    return OK;
}
SElemType GetTop(LinkStack S,SElemType &e){
    if(S!=NULL){
        e=S->data;
        return OK;
    }else{
        return ERROR;
    }
}
Status Push(SqStack &S,SElemType e){
    if(S.top-S.base==S.stackSize) {
        cout<<"栈已满，入栈失败!\n";
        return ERROR;
    }
    *S.top++=e;
    cout<<"入栈成功!\n";
    return OK;
}
Status Push(LinkStack S,SElemType e){
    StackNode* p=new StackNode;
    p->data=e;
    p->next=S;
    S=p;
    return OK;
}
Status Pop(SqStack &S,SElemType &e){
    if(S.top==S.base){
        cout<<"栈为空，出栈失败!\n";
        return ERROR;
    }
    e=*--S.top;
    cout<<"出栈元素为:"<<e<<".\n";
    return OK;
}
Status Pop(LinkStack S,SElemType &e){
    if(S==NULL){
        cout<<"栈为空，出栈失败!\n";
        return ERROR;
    }
    e=S->data;
    StackNode* p=new StackNode;
    p=S;
    S=S->next;
    delete p;
    cout<<"出栈元素为:"<<e<<"\n";
    return OK;
}
///-----------队列部分--------------///
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Status InitQueue(SqQueue &Q){
    Q.base=new QElemType[MAXSIZE];
    if(!Q.base) return OVERFLOW;
    Q.front=Q.rear=0;
    return OK;
}

Status InitQueue(LinkQueue &Q){
    Q.front=Q.rear=new QNode;
    Q.front->next=NULL;
    return OK;
}

Status GetHead(SqQueue Q){
    if(Q.front==Q.rear){
        cout<<"队列为空\n";
        return ERROR;
    }else{
        cout<<"队头元素为:"<<Q.base[Q.front]<<"\n";
        return OK;
    }

}
QElemType GetHead(LinkQueue Q){
    if(Q.front==Q.rear){
        cout<<"队列为空\n";
        return ERROR;
    }else{
        cout<<"队头元素为:"<<Q.front->next->data<<"\n";
        return OK;
    }
}

Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXSIZE==Q.front){
        cout<<"队列已满\n";
        return ERROR;
    }
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXSIZE;
    cout<<"入队成功\n";
    return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e){
    QueuePtr p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    cout<<"入队成功\n";
    return OK;
}

Status DeQueue(SqQueue &Q){
    if(Q.front==Q.rear){
        cout<<"队列为空\n";
        return ERROR;
    }
    Q.front=(Q.front+1)%MAXSIZE;
    cout<<"出队成功\n";
    return OK;
}
Status DeQueue(LinkQueue &Q){
    if(Q.front==Q.rear){
        cout<<"队列为空\n";
        return ERROR;
    }
    QueuePtr p=Q.front->next;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    delete p;
    cout<<"出队成功\n";
    return OK;
}
int main(){
    SqStack S1;
    LinkStack S2;
    SElemType Se;

    SqQueue Q1;
    LinkQueue Q2;
    QElemType Qe;

    while(true){
        int order;
        cout<<"1:建栈（顺序表）\n";
        cout<<"2:取栈顶元素（顺序表）\n";
        cout<<"3:入栈（顺序表）\n";
        cout<<"4:出栈（顺序表）\n";
        cout<<"5:建栈（链表）\n";
        cout<<"6:取栈顶元素（链表）\n";
        cout<<"7:入栈（链表）\n";
        cout<<"8:出栈（链表）\n";

        cout<<"9:建队列（顺序表）\n";
        cout<<"10:取队头元素（顺序表）\n";
        cout<<"11:入队（顺序表）\n";
        cout<<"12:出队（顺序表）\n";
        cout<<"13:建队列（链表）\n";
        cout<<"14:取队头元素（链表）\n";
        cout<<"15:入队（链表）\n";
        cout<<"16:出队（链表）\n";
        cout<<"输入负数---退出\n";
        cin>>order;
        if(order<0) break;
        switch (order)
        {
            case 1:
                InitStack(S1);
                break;
            case 2:
                GetTop(S1);
                break;
            case 3:
                cout<<"输入你想入栈的元素:";
                cin>>Se;
                Push(S1,Se);
                break;
            case 4:
                Pop(S1,Se);
                break;
            case 5:
                InitStack(S2);
                break;
            case 6:
                if(GetTop(S2,Se)){
                    cout<<"栈顶元素为:"<<Se<<"\n";
                }else{
                    cout<<"栈为空!\n";
                }
                break;
            case 7:
                cout<<"输入你想入栈的元素:";
                cin>>Se;
                Push(S2,Se);
                break;
            case 8:
                Pop(S2,Se);
                break;
            case 9:
                InitQueue(Q1);
                break;
            case 10:
                GetHead(Q1);
                break;
            case 11:
                cout<<"输入你想入队的元素:";
                cin>>Qe;
                EnQueue(Q1,Qe);
                break;
            case 12:
                DeQueue(Q1);
                break;
            case 13:
                InitQueue(Q2);
                break;
            case 14:
                GetHead(Q2);
                break;
            case 15:
                cout<<"输入你想入队的元素:";
                cin>>Qe;
                EnQueue(Q2,Qe);
                break;
            case 16:
                DeQueue(Q2);
                break;
            default:
                cout<<"输入指令有误，请重新输入\n";
                break;
        }
    }
    return 0;
}

实验四 二叉树和哈夫曼编码

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
#include<climits>
using namespace std;
#define TElemType char
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T){//先序递归建树
    char ch;cin>>ch;
    if(ch=='#') T=NULL;
    else{
        T=new BiTNode;
        T->data=ch;
        CreatBiTree(T->lchild);
        CreatBiTree(T->rchild);
    }
}
void PreOrderTraverse(BiTree T){//先序递归遍历
    if(T){
        cout<<T->data<<" ";
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void InOrderTraverse(BiTree T){//中序递归遍历
    if(T){
        InOrderTraverse(T->lchild);
        cout<<T->data<<" ";
        InOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T){//后序递归遍历
    if(T){
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<T->data<<" ";
    }
}
void LevelOrderTraverse(BiTree T){
    queue<BiTNode*>qu;
    if(T) qu.push(T);
    while(!qu.empty()){
        BiTNode *cur=qu.front();
        qu.pop();
        cout<<cur->data<<" ";
        if(cur->lchild) qu.push(cur->lchild);
        if(cur->rchild) qu.push(cur->rchild);
    }
}
int Depth(BiTree T){
    if(T==NULL) return 0;
    return max(Depth(T->lchild)+1,Depth(T->rchild)+1);
}
int LeafNodeCount(BiTree T,int cnt){
    queue<BiTNode*>qu;//这个最好自己实现一个队列，很简单，我下一个的队列是自己直接在函数里面实现了一个。
    if(T) qu.push(T);
    else cnt++;
    while(!qu.empty()){
        BiTNode* cur=qu.front();
        qu.pop();
        if(cur->lchild) qu.push(cur->lchild);
        if(cur->rchild) qu.push(cur->rchild);
        if(!(cur->lchild||cur->rchild)) cnt++;
    }
    return cnt;
}
int Leaf(BiTree T){
    if(T==NULL) return 0;
    if(T->lchild==NULL&&T->rchild==NULL) return 1;
    return Leaf(T->lchild)+Leaf(T->rchild);
}
void InOrderTraverse2(BiTree T){
    stack<BiTNode*>st;//最好自己实现。
    BiTNode* p=T,q;
    while(p||!st.empty()){
        if(p){
            st.push(p);
            p=p->lchild;
        }else{
            p=(st.top())->rchild;
            cout<<(st.top())->data<<" ";
            st.pop();
        }
    }
}
//-----------------下面是哈夫曼树部分-------------------
typedef struct{
    int weight;                 //结点的权值
    int parent,lchild,rchild;   //结点的双亲，左孩子，右孩子的下标
}HTNode,*HuffmanTree;           //动态分配数组存储哈夫曼树
typedef char **HuffmanCode;     //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int r,int &s1,int &s2){
    int min_weight=INT_MAX;
    for(int i=1;i<=r;i++){
        if(HT[i].weight<=min_weight&&HT[i].parent==0){
            s1=i;
            min_weight=HT[i].weight;
        }
    }
    min_weight=INT_MAX;
    for(int i=1;i<=r;i++){
        if(i==s1) continue;
        if(HT[i].weight<=min_weight&&HT[i].parent==0){
            s2=i;
            min_weight=HT[i].weight;
        }
    }
}
void CreateHuffmanTree(HuffmanTree &HT,int n){
    if(n<=1) return;
    int m=2*n-1;
    HT=new HTNode[m+1];//0号不用
    for(int i=1;i<=m;++i){
        HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
    }
    for(int i=1;i<=n;i++){
        cin>>HT[i].weight;
    }
    for(int i=n+1;i<=m;i++){
        int s1,s2;
        Select(HT,i-1,s1,s2);
        HT[s1].parent=i;HT[s2].parent=i;
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
    HC=new char*[n+1];
    char *cd=new char[n];
    cd[n-1]='\0';
    for(int i=1;i<=n;i++){
        int start=n-1;
        int c=i,f=HT[i].parent;//c is cur
        while(f!=0){
            --start;
            if(HT[f].lchild==c) cd[start]='0';
            else cd[start]='1';
            c=f;
            f=HT[f].parent;
        }
        HC[i]=new char[n-start];
        strcpy(HC[i],&cd[start]);
    }
    delete[] cd;
}
int main(){
    cout<<"李博-1710121058\n";
    BiTree T;
    cout<<"前序遍历建树，请输入节点信息:";
    CreatBiTree(T);
    cout<<endl<<"前序遍历:";
    PreOrderTraverse(T);
    cout<<endl<<"中序递归遍历:";
    InOrderTraverse(T);
    cout<<endl<<"中序非递归遍历:";
    InOrderTraverse2(T);
    cout<<endl<<"后序遍历:";
    PostOrderTraverse(T);
    cout<<endl<<"层序遍历:";
    LevelOrderTraverse(T);
    cout<<endl<<"深度:";
    cout<<Depth(T);
    cout<<endl<<"非递归求叶子个数:";
    cout<<Leaf(T);
    cout<<endl<<"递归求叶子个数:";
    cout<<LeafNodeCount(T,0)<<endl;
    cout<<"下面是哈夫曼树部分--------------------------\n";
    HuffmanTree HT;
    HuffmanCode HC;
    char Hfstring[30];
    cout<<"*****************************************************\n";
    cout<<"***   1,输入HuffmanTree的参数                     ***\n";
    cout<<"***   2,初始化HuffmanTree参数.(含有26字母及空格)   ***\n";
    cout<<"***   3,创建HuffmanTree和编码表.                ***\n";
    cout<<"***   4,输出编码表                             ***\n";
    cout<<"***   5,输入编码,并翻译为字符.                    ***\n";
    cout<<"***   6,输入字符,并实现转码.                       ***\n";
    cout<<"***   7,退出.                                     ***\n";
    cout<<"*****************************************************\n";
    int order,cur;
    string str;
    while(cin>>order&&order!=7){
        switch (order){
            case 1:
            cout<<"请输入参数:";
                //64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1 168
                CreateHuffmanTree(HT,27);
                break;
            case 2:
                CreateHuffmanTree(HT,27);
                break;
            case 3:
                CreatHuffmanCode(HT,HC,27);
                break;
            case 4:
                cout<<"编码表如下:\n";
                for(int i=1;i<=26;i++){
                    cout<<(char)('a'+i-1)<<" : "<<HC[i]<<endl;
                }
                cout<<" "<<" : "<<HC[27]<<endl;
                break;
            case 5:
                cout<<"请输入一段编码:";
                getchar();
                getline(cin,str);
                cur=2*27-1;
                for(int i=0;i<str.length();i++){
                    if(str[i]=='0') cur=HT[cur].lchild;
                    else cur=HT[cur].rchild;
                    if(HT[cur].lchild==0&&HT[cur].rchild==0){
                        if(cur==27) cout<<" ";
                        else cout<<(char)('a'+cur-1);
                        cur=2*27-1;
                    }
                }
                cout<<endl;
                break;
            case 6:
                //i love you
                //01111111010010011100000010111100011100100001
                cout<<"请输入一段字符:";
                getchar();
                getline(cin,str);
                cout<<str.length()<<"len\n";
                for(int i=0;i<str.length();i++){
                    if(isalpha(str[i])) cout<<HC[(str[i]-'a'+1)];
                    else cout<<HC[27];
                }
                cout<<endl;
                break;
            default:
                cout<<"您输入的命令有误.\n";
                break;
        }
    }
    return 0;
}

实验五 图的操作

#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
/********************下面是邻接矩阵********************/
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef int Status;

typedef struct{
    VerTexType vexs[MVNum];     //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum,arcnum;          //图的当前点数和边数
}AMGraph;

int LocateVex(AMGraph G,VerTexType v){
    int idx=-1;//返回-1就是没找到
    for(int i=0;i<G.vexnum;++i){
        if(G.vexs[i]==v) idx=i;
    }
    return idx;
}
Status CreatUDN(AMGraph &G){
    cin>>G.vexnum>>G.arcnum;
    for(int i=0;i<G.vexnum;++i){
        cin>>G.vexs[i];
    }
    for(int i=0;i<G.vexnum;++i){
        for(int j=0;j<G.vexnum;++j){
            G.arcs[i][j]=MaxInt;
        }
    }
    VerTexType v1,v2;
    ArcType w;
    for(int i=0;i<G.arcnum;++i){
        cin>>v1>>v2>>w; 
        int idx1=LocateVex(G,v1),idx2=LocateVex(G,v2);
        if(idx1==-1||idx2==-1){
            cout<<"error!\n";
            return ERROR;
        }
        G.arcs[idx1][idx2]=G.arcs[idx2][idx1]=w;
    }
    return OK;
}
bool visited[MVNum];
void initVis(){
    for(int i=0;i<MVNum;++i){
        visited[i]=false;
    }
}
void DFS(AMGraph G,int v){
    cout<<G.vexs[v]<<" ";
    visited[v]=true;
    for(int i=0;i<G.vexnum;++i){
        if(G.arcs[v][i]!=MaxInt&&!visited[i]) DFS(G,i);
    }
}
#define QElemType int
void BFS(AMGraph G,int v){
    typedef struct{
        QElemType *base;
        int front,rear;
    }SqQueue;
    //初始化SqQueue
    SqQueue Q;
    Q.base=new QElemType[MVNum];
    if(!Q.base) return;
    Q.front=Q.rear=0;//头指针等于尾指针，队列为空

    if((Q.rear+1)%MVNum==Q.front){
        cout<<"队列满了！";
        return ;
    }else{
        Q.base[Q.rear]=v;
        cout<<G.vexs[Q.base[Q.rear]]<<" ";
        visited[Q.base[Q.rear]]=true;
        Q.rear=(Q.rear+1)%MVNum;
    }
    while(Q.rear!=Q.front){
        int e=Q.base[Q.front];
        Q.front=(Q.front+1)%MVNum;//出队
        for(int i=0;i<G.vexnum;++i){
            if(!visited[i]&&G.arcs[e][i]!=MaxInt){//入队
                visited[i]=true;
                if((Q.rear+1)%MVNum==Q.front){
                    cout<<"队列满了！";
                    return ;
                }else{   
                    Q.base[Q.rear]=i;
                    cout<<G.vexs[Q.base[Q.rear]]<<" ";
                    Q.rear=(Q.rear+1)%MVNum;
                }
            }
        }
    }
}
bool S[MVNum];//已求出最短路径的顶点集
int D[MVNum];
int Path[MVNum];
void ShortestPath_DIJ(AMGraph G,int v0){
    //用Dijkstra算法求有向网
    int n=G.vexnum;
    int v;
    for(v=0;v<n;++v){
        S[v]=false;
        D[v]=G.arcs[v0][v];
        if(D[v]<MaxInt) Path[v]=v0;
        else Path[v]=-1;
    }
    S[v0]=true;
    D[v0]=0;

    for(int i=1;i<n;++i){
        int min=MaxInt;
        for(int w=0;w<n;++w){
            if(!S[w]&&D[w]<min){
                v=w;
                min=D[w];
            }
        }
        S[v]=true;
        for(int w=0;w<n;++w){
            if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){
                D[w]=D[v]+G.arcs[v][w];
                Path[w]=v;
            }
        }
    }
}
//****************下面是邻接表建图**********
typedef struct ArcNode{//边结点
    int adjvex;
    struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{//顶点信息
    VerTexType data;
    ArcNode *firstarc;
}VNode,AdjList[MVNum];

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

Status CreatUDG(ALGraph &G){
    cin>>G.vexnum>>G.arcnum;
    for(int i=0;i<G.vexnum;++i){
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    for(int k=0;k<G.arcnum;++k){
        int v1,v2;
        cin>>v1>>v2;
        int idx1,idx2;
        for(int i=0;i<G.vexnum;++i){
            if(G.vertices[i].data==v1){
                idx1=i;
                break;
            }
        }
        for(int i=0;i<G.vexnum;++i){
            if(G.vertices[i].data==v2){
                idx2=i;
                break;
            }
        }
        ArcNode* p1=new ArcNode;
        p1->adjvex=idx2;
        p1->nextarc=G.vertices[idx1].firstarc;
        G.vertices[idx1].firstarc=p1;
        ArcNode* p2=new ArcNode;
        p2->adjvex=idx1;
        p2->nextarc=G.vertices[idx2].firstarc;
        G.vertices[idx2].firstarc=p2;  
    }
    return OK;
}
int main(){ 
    /*测试样例
    5 5
    a b c d e
    a b 1
    a c 2
    b d 3
    c d 4
    d e 5
     */
    AMGraph G;//假设可能不联通
    ALGraph GL;
    CreatUDN(G);//生成无向图
    initVis();//初始化visited数组
    cout<<"DFS: ";
    for(int i=0;i<G.vexnum;++i){
        if(!visited[i]) DFS(G,i);//dfs
    }
    cout<<endl;
    initVis();
    cout<<"BFS: ";
    for(int i=0;i<G.vexnum;++i){
        if(!visited[i]) BFS(G,i);//dfs
    }
    cout<<endl;
    ShortestPath_DIJ(G,0);
    cout<<"源点为0的最短路径如下\n";
    for(int i=1;i<G.vexnum;i++){
        cout<<G.vexs[0]<<" -> "<<G.vexs[i]<<" ,length = "<<D[i]<<"\n";
    }
    return 0;
}

实验六 查找和排序

#include<iostream>
using namespace std;
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define MAXSIZE 100
typedef int KeyType;
typedef struct{
    KeyType key;
}ElemType;
typedef struct{
    ElemType *R;
    int length;
}SSTable;
void initSSTable(SSTable &ST){
    ST.R=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    ST.length=0;
    for(int i=1;i<=100;i++){
        ST.R[i].key=i;
        ST.length++;
    }
}
int Search_Bin(SSTable ST,KeyType key,int &cnt,int &idx){//Sequential Search Table
    int low=1,high=ST.length;
    while(low<=high){
        cnt++;
        int mid=(low+high)/2;
        if(ST.R[mid].key==key){
            idx=mid;
            return OK;
        }
        if(ST.R[mid].key<key) low=mid+1;
        else high=mid-1;
    }
    return ERROR;
}
/////// 二叉排序树部分
typedef struct{
    KeyType key;
}treeElemType;
typedef struct BSTNode{
    treeElemType data;
    BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int InsertBST(BSTree &T,int num){
    if(T){
        if(T->data.key>=num) InsertBST(T->lchild,num);
        else InsertBST(T->rchild,num);
    }else{
        BSTNode* S=new BSTNode;
        S->data.key=num;
        S->lchild=S->rchild=NULL;
        T=S;
    }
    return OK;
}
BSTree SearchBST(BSTree T,KeyType key,int &cnt){
    cnt++;
    if(!T||T->data.key==key) {
        return T;
    }
    else{
        if(T->data.key<key) return SearchBST(T->rchild,key,cnt);
        else return SearchBST(T->lchild,key,cnt);
    }
}
void InOrderTraverse(BSTree T){
    if(T){
        InOrderTraverse(T->lchild);
        cout<<T->data.key<<" ";
        InOrderTraverse(T->rchild);
    }
}
// int flag=true,last=0;//last设为比最小值还小的值
// bool InOrderTraverse1(BSTree T){//中序递归遍历
//     if(T&&flag){
//         InOrderTraverse1(T->lchild);
//         if(T->data.key<=last){
//             flag=false;//不是BST
//         }
//         last=T->data.key;//更新last
//         InOrderTraverse1(T->rchild);
//     }
//     return flag;
// }

//////////////排序算法部分
typedef struct{
    int *elem;
    int length;
}SqList;
int InitList(SqList &L){
    L.elem=new int[MAXSIZE];
    if(!L.elem) exit(OVERFLOW);
    L.length=0;
    cout<<"输入待排序数据个数:";
    int n,num;
    cin>>n;
    cout<<"输入每一个数:";
    for(int i=0;i<n;i++){
        cin>>num;
        L.elem[i+1]=num;
        L.length++;
    }
    return OK;
}
void TraverseList(SqList L){
    cout<<"线性表数据为:";
    for(int i=1;i<=L.length;i++){
        cout<<L.elem[i]<<" ";
    }
    cout<<endl;
}
int Partition(SqList &L,int low,int high){
    L.elem[0]=L.elem[low];      //将子表的第一个记录当作枢轴记录
    while(low<high){
        while(low<high&&L.elem[high]>=L.elem[0]) --high;
        L.elem[low]=L.elem[high];
        while(low<high&&L.elem[low]<=L.elem[0]) ++low;
        L.elem[high]=L.elem[low];
    }
    L.elem[low]=L.elem[0];
    return low;
}
void QSort(SqList &L,int low,int high){
    if(low<high){
        int pivotloc=Partition(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
    }
}
void QuickSort(SqList &L){
    QSort(L,1,L.length);
}


void Merge(int R[],int T[],int low,int mid,int high){
    int i=low,j=mid+1,k=low;
    while(i<=mid&&j<=high){
        if(R[i]<=R[j]) T[k++]=R[i++];
        else T[k++]=R[j++];
    }
    while(i<=mid) T[k++]=R[i++];
    while(j<=high) T[k++]=R[j++];
}
void MSort(int R[],int T[],int low,int high){
    int *S=new int[MAXSIZE];
    if(low==high) T[low]=R[low];
    else{
        int mid=(low+high)/2;
        MSort(R,S,low,mid);
        MSort(R,S,mid+1,high);
        Merge(S,T,low,mid,high);
    }
    delete []S;
}
void MergeSort(SqList &L){
    MSort(L.elem,L.elem,1,L.length);
}
int main(){

    while(true){
        SSTable ST;
        BSTree T;
        SqList L;
        int key,cnt=0,idx=0,order=0,n,num;
        cout<<"**    1710121058-李博    ********************\n";
        cout<<"**    1.初始化顺序表,自动添加[1:100]一百个数据  **\n";
        cout<<"**    2.显示数据表内容  **\n";
        cout<<"**    3.输入你要查找的数并返回在线性表中的查找结果  **\n";
        cout<<"**    4.初始化二叉排序树,并添加数据     **\n";
        cout<<"**    5.显示二叉排序树的数据  **\n";
        cout<<"**    6.输入你要查找的数并返回在二叉排序树中结点的指针  **\n";
        cout<<"**    7.输入待排序数的个数和分别都是几    **\n";
        cout<<"**    8.输出你输入的线性表   **\n";
        cout<<"**    9,快速排序刚才的线性表  **\n";
        cout<<"**    10,归并排序刚才的线性表  **\n";
        cout<<"**    -1,退出  **\n";

        cout<<"****\n";
        cout<<"输入命令:";
        cin>>order;
        if(order==-1) break;
        switch(order){
            case 1:
                initSSTable(ST);//已经初始化进去100个数据[1,2,3,...,100],下标从1开始
                break;
            case 2:
                for(int i=1;i<=ST.length;i++){
                    cout<<ST.R[i].key<<" ";
                }
                cout<<endl;
                break;
            case 3:
                cout<<"请输入你要查找哪个数:";
                cin>>key;
                if(Search_Bin(ST,key,cnt,idx)){//如果没找到则返回ERROR并且idx=0
                    cout<<"查找成功,查找次数:"<<cnt<<",下标:"<<idx<<"\n";
                }else cout<<"查找失败\n";
                break;
            case 4:
                cout<<"你要在二叉排序树插入几个数:";
                cin>>n;
                cout<<"输入你要插入的所有数据";
                for(int i=0;i<n;i++){
                    cin>>num;
                    InsertBST(T,num);
                }
                break;
            case 5:
                //中序遍历输出元素值
                InOrderTraverse(T);
                cout<<endl;
                break;
            case 6:
                cout<<"请输入你要查找哪个数:";
                cin>>key;
                if(SearchBST(T,key,cnt)!=NULL){
                    cout<<"查找成功,查找次数:"<<cnt<<",指针为:"<<T<<"\n";
                }else cout<<"查找失败\n";
                break;
            case 7:
                InitList(L);
                break;
            case 8:
                TraverseList(L);
                break;
            case 9:
                QuickSort(L);
                break;
            case 10:
                MergeSort(L);
                break;
        }
    }
    return 0;
}