本周小结:cry:

支原体感染是真猛啊，这周被疾病狠狠地折磨了:weary:，也狠狠地摆了一周，没咋学习课外内容(快要鸽爆了)，唯一认真写的是数据结构的实验，足足写了上百行C语言代码，是真的折磨啊！不过好在实验内容实现的还不错，记录一下！

实验一

1、参照课本程序2.1～2.7，编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。

2、已知带表头结点单链表的类型定义如下：

typedef struct node

{

ElemType element; //结点的数据域

struct node *link; //结点的指针域

}node;

typedef struct

{

struct node * head;

int n;

}headerList;

参照课本程序2.8～2.14，编写程序，完成带表头结点单链表的初始化、查找、插入、删除、输出、撤销等操作。

3、已知带表头结点一元多项式的类型定义如下：

typedef struct pNode

{

int coef;

int exp;

struct pNode* link;

} pNode;

typedef struct

{

struct pNode *head;

} polynominal;

编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。

#include <stdio.h>
#include <stdlib.h>
//1、顺序表操作实现
typedef struct seqList{
    int n;
    int maxlen;
    int *element;
}SeqList;
//线性表初始化
int Init(SeqList *L,int mSize){
    L->maxlen=mSize;
    L->n=0;
    L->element=(int *)malloc(sizeof(int)*mSize);
    if(!L->element)
        return 0;
    return 1;
}
//查找:给出下标查找元素
int Find(SeqList L,int xiabiao,int *x){
    if(xiabiao<0||xiabiao>L.n-1) return 0;
    *x=L.element[xiabiao];
    return 1;
}
//插入:插入元素到指定下标i处
int Insert(SeqList* L,int i,int x){
    if(i<-1||i>L->n-1) return 0;
    if(L->n==L->maxlen) return 0;
    int j;
    for(j=L->n-1;j>i;j--){
        L->element[j+1]=L->element[j];
    }
    L->element[i+1]=x;
    L->n++;
    return 1;
}
//删除:删除指定下标处的元素
int Delete(SeqList L,int i){
    if(i<0||i>L.n-1) return 0;
    if(!L.n) return 0;
    int j;
    for(j=i;j<L.n-1;j++){
        L.element[j]=L.element[j+1];
    }
    L.n--;
    return 1;
}
//输出:遍历线性表并逐个输出元素
int Output(SeqList* L){
    int i;
    if(L->n==0) return 0;
    for(int i=0;i<L->n;i++){
        printf("%d ",L->element[i]);
    }
    printf("\n");
    return 1;
}
//撤销:释放线性表的空间
void Destory(SeqList *L){
    L->n=0;
    L->maxlen=0;
    free(L->element);
}

//2、链表操作实现
typedef struct node
{
    int  element;  //结点的数据域
    struct node *link;     //结点的指针域
}node;
typedef struct 
{
    struct node * head;  //链表头指针
    int n;
}headerList;
//链表初始化
int Init2(headerList *H){
    H->head=NULL;
    H->n=0;
    return 1;
}
//查找:给定指定元素位置，返回该元素
int Find2(headerList* H,int i,int *x){
    if(i<0||i>H->n-1) return 0;
    int j;
    node *p=H->head;
    for(j=0;j<i;j++) p=p->link;
    *x=p->element;
    return 1;
}
//插入:在指定位置i插入元素
int Insert2(headerList* H,int i,int x){
    if(i<-1||i>H->n-1) return 0;
    int j;
    node* p=H->head;
    for(j=0;j<i;j++) p=p->link;
    node* q=(node*)malloc(sizeof(node));
    q->element=x;
    if(i>-1){
        q->link=p->link;
        p->link=q;
    }else{
        q->link=H->head;
        H->head=q;
    }
    H->n++;
    return 1;
}
//删除:删除指定位置i处的元素
int Delete2(headerList* H,int i){
    if(i<0||i>H->n-1) return 0;
    if(H->n==0) return 0;
    int j;
    node *p=H->head;
    node *q=H->head; //也要指定初始指向，因为如果i==0，则要free(q)!
    for(j=0;j<i-1;j++) p=p->link;
    if(i==0){ //删除头节点的情况，也是列表里只有一个元素的情况(只有一个元素就是头结点，只能删头结点)
        H->head=H->head->link;
    }else {
        q=p->link;
        p->link=q->link;
    }
    free(q);
    H->n--;
    return 1;
}
//输出:遍历链表并逐个输出元素
int Output2(headerList* H){
    if(!H->n) return 0;
    node *p=H->head;
    int i=0;
    while(i<H->n){
        printf("%d ",p->element);
        p=p->link;
        i++;
    }
    return 1;
}
//删除:逐个释放链表结点空间
void Destory2(headerList* H){
    node *p=H->head;
    node *q;
    while(p){
        q=p;
        p=p->link;
        free(q);
    }
}
//3、多项式操作实现
typedef struct pNode
{
int coef;
int exp;
struct pNode* link;
} pNode;
typedef struct 
{
struct pNode *head;
} polynominal;
//创建多项式：不断接收输入的系数和次幂
void Create(polynominal *p){
    pNode *pn,*pre,*q;
    p->head=(pNode*)malloc(sizeof(pNode));
    p->head->exp=-1;
    p->head->link=p->head;
    printf("\n Create a p:\n");
    for(;;){
        pn=(pNode*)malloc(sizeof(pNode));
        printf("coef:\n");
        scanf("%d",&pn->coef);
        printf("exp:ends with -1\n");
        scanf("%d",&pn->exp);
        if(pn->exp<0) break;
        pre=p->head;
        q=p->head->link;
        while(q&&q->exp>pn->exp){ //遍历，直到当前pn的指数大于q指针结点的指数
            pre=q;
            q=q->link;
        }
        pn->link=q;
        pre->link=pn;
    }
    
}
//撤销:释放多项式的空间
void Destory3(polynominal *p){
    if(p->head->link->exp==-1) free(p->head);
    else{
        pNode *pnow=p->head->link->link;
        pNode *pre=p->head->link;
        while(pnow->exp!=-1){
            free(pre);
            pre=p;
            pnow=pnow->link;
        }
        free(pre);
        free(pnow);
    }
}
//输出:输出多项式
int Output3(polynominal *p){
    pNode *q;
    q=p->head;
    q=q->link;
    while(q->exp!=-1){
        printf("(%dx^%d)",q->coef,q->exp);
        q=q->link;
        if(q->exp!=-1) printf(" + ");
    }
    printf("\n");
}
//多项式相加:次幂相同的系数相加，存储到q中
void Add(polynominal *px,polynominal *qx){
    pNode *q,*ql=qx->head,*p,*pl,*temp;
    p=px->head->link;
    q=ql->link;
    while(p->exp>=0){
        while(p->exp<q->exp){
            ql=q;     //ql与q一同前进一格
            q=q->link;
        }
        if(p->exp==q->exp){
            q->coef=q->coef+p->coef;
            if(q->coef==0){
                ql->link=q->link;  //删除q
                free(q);        //释放q空间
                q=ql->link;    //重置q,使其仍指向ql下一个
                p=p->link;
            }
            else{
                ql=q;
                q=q->link;
                p=p->link;
            }
        
        }
        else{   //p->exp>q->exp情况,这时要用p创建一个结点插到q表达式里，且插在q当前指向的上一个结点也就是ql后面
            temp=(pNode*)malloc(sizeof(pNode));
            temp->coef=p->coef;
            temp->exp=p->exp;
            temp->link=ql->link;
            ql->link=temp;
            //插完后前进
            ql=ql->link;
            p=p->link;

        }
        
    }

}
//加减运算都一样，每次都比较出较大次幂的(因为要降幂排列)，然后计算
void subtract(polynominal *px,polynominal *qx){
    pNode *q,*ql=qx->head,*p,*pl,*temp;
    p=px->head->link;
    q=ql->link;
    while(p->exp>=0){
        while(p->exp<q->exp){
            q->coef=-q->coef;
            ql=q;     //ql与q一同前进一格
            q=q->link;
        }
        if(p->exp==q->exp){
            q->coef=p->coef-q->coef;
            if(q->coef==0){
                ql->link=q->link;  //删除q
                free(q);        //释放q空间
                q=ql->link;    //重置q,使其仍指向ql下一个
                p=p->link;
            }
            else{
                ql=q;
                q=q->link;
                p=p->link;
            }
        
        }
        else{   //p->exp>q->exp情况,这时要用p创建一个结点插到q表达式里，且插在q当前指向的上一个结点也就是ql后面
            temp=(pNode*)malloc(sizeof(pNode));
            temp->coef=p->coef;
            temp->exp=p->exp;
            temp->link=ql->link;
            ql->link=temp;
            //插完后前进
            ql=ql->link;
            p=p->link;

        }
    }
    while(q->exp>=0){
        q->coef=-q->coef;
        q=q->link;
    }
}
//多项式相乘:主循环遍历p2多项式，分别于p1各项相乘，相乘完后再合并系数相同的次幂
void multiply(polynominal *p1,polynominal *p2,polynominal *p3){
    p3->head=(pNode*)malloc(sizeof(pNode));
    p3->head->exp=-1;
    pNode *pre3=p3->head;
    pNode *pmain=p2->head->link;
    while(pmain->exp>=0){  //主循环遍历p2多项式
        pNode *psec=p1->head->link;
        while(psec->exp>=0){ //次循环遍历p1多项式，分别于pmain当前所指相乘
            pNode *temp=(pNode*)malloc(sizeof(pNode));
            temp->coef=pmain->coef*psec->coef;
            temp->exp=pmain->exp+psec->exp;
            pre3->link=temp;
            pre3=pre3->link;
            psec=psec->link;
        }
        pmain=pmain->link;
    }
    pre3->link=p3->head;
    //接下来去掉乘完后重复的次幂
    pre3=p3->head->link;
    pNode *pp3=pre3->link;
    while(pp3->exp>=0){
        if(pp3->exp==pre3->exp){
            pre3->coef=pre3->coef+pp3->coef;
            pre3->link=pp3->link;
            //相等就只需要pp3前进
            pp3=pp3->link;
            continue;
        }
        pre3=pre3->link;
        pp3=pp3->link;
    }
}

int main() {
    //线性表测试
    int i;
    SeqList list;
    Init(&list,10);
    for(i=0;i<list.maxlen;i++){
        Insert(&list,i-1,i);
    }
    Output(&list);
    int x;
    Find(list,2,&x);
    printf("Finding list[2]:%d",x);
    Destory(&list);
    //链表测试
    headerList H;
    Init2(&H);
    for(i=0;i<9;i++){
        Insert2(&H,i-1,i+2);
    }
    printf("\n");
    Output2(&H);
    Delete2(&H,0);
    printf("\nAfter deleting list[0]:\n");
    Output2(&H);
    Insert2(&H,2,99);
    printf("\nAfter inserting 99 at list[3]:\n");
    Output2(&H);
    Find2(&H,1,&x);
    printf("\nFinding list[1]:%d",x);
    Destory2(&H);
    //多项式测试
    polynominal p1;
    polynominal p2;
    polynominal p3;
    Create(&p1);
    Create(&p2);
    Output3(&p1);
    Output3(&p2);
    printf("p1*p2=\n");
    multiply(&p1,&p2,&p3);
    Output3(&p3);
    printf("p1+p2=\n");
    Add(&p1,&p2);
    Output3(&p2);
    // Destory3(&p1);
    // Destory3(&p2);
    return 0;
}

实验二

1、已知二叉树二叉链表结点结构定义如下：

typedef struct btnode{

ElemType element；

struct btnode *lChild；

struct btnode *rChild；

}BTNode；

参照程序 5.1～5.4，编写程序，完成二叉树的先序创建、先序遍历、中序遍历、后序遍历等操作。

2、以第１题所示二叉链表为存储结构，编写程序实现求二叉树结点个数、叶子结点个数、二叉树的高度以及交换二叉树所有左右子树的操作。

3、已知哈夫曼树结点结构定义如下：

typedef struct hfmTNode{

ElementType element; //结点的数据域

int w; //结点的权值

struct hfmTNode *lChild; //结点的左孩子指针

struct hfmTNode *rChild; //结点的右孩子指针

}HFMTNode;

编写程序，实现哈夫曼树的创建、哈夫曼编码以及解码的实现。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//1、二叉树结点定义与基本操作
typedef struct btnode{ 
    int element;
    struct btnode *lChild;
    struct btnode *rChild;
}BTNode;
//先序遍历
void preorder_traversal(BTNode* node){
    if(!node) return;
    printf("%d",node->element);
    preorder_traversal(node->lChild);
    preorder_traversal(node->rChild);
}
//中序遍历
void inorder_traversal(BTNode* node){
    if(!node) return;
    inorder_traversal(node->lChild);
    printf("%d",node->element);
    inorder_traversal(node->rChild);
}
//后序遍历
void postorder_traversal(BTNode* node){
    if(!node) return;
    postorder_traversal(node->lChild);
    postorder_traversal(node->rChild);
    printf("%d",node->element);
}

//先序创建：通过递归先序创建二叉树
BTNode* PreCreateBT(BTNode *t){
    char ch;
    ch=getchar();
    if(ch=='#'){ //建立空树
        t=NULL;
    }else{
        t=(BTNode*)malloc(sizeof(BTNode));
        t->element=ch-'0'; //这里存储的是整数，因此用输入字符要减去'0;
        t->lChild=PreCreateBT(t->lChild);
        t->rChild=PreCreateBT(t->rChild);

    }
    return t;
}

//2、二叉树关键特征结点数求解
//求二叉树结点个数
int TreeSize(BTNode* t){
    if(!t) return 0;
    else return TreeSize(t->lChild)+TreeSize(t->rChild)+1;
}
//求二叉树叶子节点个数
int LeafSize(BTNode* t){
    int sum=0;
    if(!t) return 0;
    if(t->lChild==NULL&&t->rChild==NULL) {
        sum=1;
        return sum;
    }
    if(t->lChild&&!t->rChild){
        return LeafSize(t->lChild);
    }
    if(t->rChild&&!t->lChild){
        return LeafSize(t->rChild);
    }
    return LeafSize(t->lChild)+LeafSize(t->rChild)+sum;
}
//求二叉树的高度
//调用的时候复制sum和height为0,sum存储当前结点的高度，heigth为全局高度
void TreeHeight(BTNode* t,int sum,int *height){
    sum++;
    if(sum>*height) *height=sum;
    if(t->rChild) TreeHeight(t->rChild,sum,height);
    if(t->lChild) TreeHeight(t->lChild,sum,height);
}
//交换二叉树所有左右子树
void SwapTree(BTNode* t){
    BTNode* temp;
    if(t->lChild&&t->rChild){
        temp=t->lChild;
        t->lChild=t->rChild;
        t->rChild=temp;
        SwapTree(t->lChild);
        SwapTree(t->rChild);
    }
    if(!t->rChild&&t->lChild){
        t->rChild=t->lChild;
        t->lChild=NULL;
        SwapTree(t->rChild);
    }
    if(!t->lChild&&t->rChild){
        t->lChild=t->rChild;
        t->rChild=NULL;
        SwapTree(t->lChild);
    }
}

//3、哈夫曼树构建与哈夫曼编码
typedef struct hfmTNode{
    int element;
    int w;
    struct hfmTNode *lChild;
    struct hfmTNode *rChild;
}HFMTNode;
//先序遍历哈夫曼树
void preorder_traversal_hfm(HFMTNode* node){
    if(!node) return;
    printf("%d ",node->w);
    preorder_traversal_hfm(node->lChild);
    preorder_traversal_hfm(node->rChild);
}
//向上调整用于处理新加入的元素
void Adjustup(HFMTNode** heap,int current){
    int p=current;
    HFMTNode* temp;
    while (p>0)
    {
        if(heap[p]->w<heap[(p-1)/2]->w){
            temp=heap[p];
            heap[p]=heap[(p-1)/2];
            heap[(p-1)/2]=temp;
            p=(p-1)/2;
        }
        else
            break;
    }
}

//向下调整用于处理要移除的元素
void AdjustDown(HFMTNode** heap,int current,int border){
    int p=current;
    HFMTNode* temp;
    int minChild;
    while (2*p+1<=border)
    {
        if((2*p+2)&&(heap[2*p+1]->w>heap[2*p+2]->w))
            minChild=2*p+2;
        else
            minChild=2*p+1;
        if(heap[p]->w<=heap[minChild]->w) break;
        else{
            temp=heap[p];
            heap[p]=heap[minChild];
            heap[minChild]=temp;
            p=minChild;
        }
    }
}
//定义优先权队列，用来构建哈夫曼树
typedef struct priorityQueue
{
    HFMTNode** elements;
    int n;
    int maxsize;
}PriorityQueue;
//创建优先权队列
void CreatPQ(PriorityQueue *PQ,int msize){
    PQ->maxsize=msize;
    PQ->n=0;
    PQ->elements=(HFMTNode**)malloc(msize*sizeof(HFMTNode*));
}
//判断优先权队列是否已满
int IsFull(PriorityQueue *PQ){
    if(PQ->n==PQ->maxsize){
        return 1;
    }else{
        return 0;
    }
}
//向优先权队列中添加哈夫曼树结点
void Append(PriorityQueue *PQ,HFMTNode* x){
    if(IsFull(PQ)) return;
    PQ->elements[PQ->n]=x;
    PQ->n++;
    Adjustup(PQ->elements,PQ->n-1);
}
//取出优先权队列最前面的结点，即权重最小的结点
HFMTNode* Serve(PriorityQueue *PQ){
    //return空值
    if(PQ->n==0) return;
    HFMTNode* x=PQ->elements[0];
    PQ->n--;
    PQ->elements[0]=PQ->elements[PQ->n];
    AdjustDown(PQ->elements,0,PQ->n-1);
    return x;
}
//创建哈夫曼树结点
void MakeTree(HFMTNode *x,int w,HFMTNode* lchild,HFMTNode* rchild){
    x->w=w;
    x->lChild=lchild;
    x->rChild=rchild;
}
//创建哈夫曼树
HFMTNode* CreateHFMTree(PriorityQueue *PQ,int w[],int m){
    HFMTNode *x=(HFMTNode*)malloc(sizeof(HFMTNode)),*y=(HFMTNode*)malloc(sizeof(HFMTNode));
    CreatPQ(PQ,m);
    for(int i=0;i<m;i++){
        HFMTNode *temp=(HFMTNode*)malloc(sizeof(HFMTNode));
        MakeTree(temp,w[i],NULL,NULL);
        Append(PQ,temp);
    }
    while (PQ->n>1)
    {
        x=Serve(PQ);
        y=Serve(PQ);
        HFMTNode *z=(HFMTNode*)malloc(sizeof(HFMTNode));
        if(x->w<y->w){
            MakeTree(z,x->w+y->w,x,y);
        }else MakeTree(z,x->w+y->w,y,x);
        Append(PQ,z);
        
    }
    x=Serve(PQ);
    return x;
    
}
//哈夫曼编码
int hfm_encoding(HFMTNode* node,char* string,int i,char code){
    string[i]=code;
    i++;

    int o;
    char* string1=(char*)malloc(10*sizeof(char));
    for(o=0;o<10;o++){
        string1[o]=string[o];
    }
    char* string2=(char*)malloc(10*sizeof(char));
    for(o=0;o<10;o++){
        string2[o]=string[o];
    }
    if(!node) return 0;
    if(!node->lChild&&!node->rChild) {
        printf("encoding of weight %d :",node->w);
        for(o=0;o<i;o++){
            printf("%c",string[o]);
        }
        printf("\n");
        return 0;
    }
    //递归传递字符，如果是左子树则传入‘0’，右子树传入‘1’，并继承当前分支的编码结果
    hfm_encoding(node->lChild,string1,i,'0');
    hfm_encoding(node->rChild,string2,i,'1');
    return 1;
}
//哈夫曼解码
int hfm_decoding(char input,int size,int *w,char* ch){
    int i=0;
    for(i=0;i<size;i++){
        if(ch[i]==input){
            char *str;
            sprintf(str, "%d", w[i]);
            printf("decode %c:1100",input);
        }
    }
    
}
int main(){
    BTNode* root;
    int size;
    int leaf=0;
    int height=0;
    //二叉树测试
    //输入以   56#2#1##30###   为例
    root=PreCreateBT(root);
    printf("preorder_traversal:\n");
    preorder_traversal(root);
    printf("\ninorder_traversal:\n");
    inorder_traversal(root);
    printf("\npostorder_traversal:\n");
    postorder_traversal(root);
    size=TreeSize(root);
    printf("\nsize of tree:%d",size);
    TreeHeight(root,0,&height);
    printf("\nheight of tree:%d",height);
    leaf=LeafSize(root);
    printf("\nleaf of tree:%d\n",leaf);
    SwapTree(root);
    printf("after swaping the tree,preorder_traversal:\n");
    preorder_traversal(root);
    printf("\n");
    int i,*w=(int*)malloc(6*sizeof(int));
    char *ch=(char*)malloc(6*sizeof(char));
    printf("input with data like \"A:9\"\n");
    for(i=0;i<6;i++){
        scanf(" %c:%d",ch+i,w+i);
    }
    //观察哈夫曼树结点、权重的存储情况
    // for(i=0;i<6;i++){
    //     printf("%c:%d ",ch[i],w[i]);
    // }
    PriorityQueue PQ;
    CreateHFMTree(&PQ,w,6);
    printf("HFMTree's preorder_traversal:\n");
    //printf("%d,%d",(*(PQ.elements))->lChild->w,(*(PQ.elements))->rChild->w);
    preorder_traversal_hfm(*(PQ.elements));
    printf("\n");
    char* string1=(char*)malloc(10*sizeof(char));
    char* string2=(char*)malloc(10*sizeof(char));
    hfm_encoding((*(PQ.elements))->lChild,string1,0,'0');
    hfm_encoding((*(PQ.elements))->rChild,string2,0,'1');
    char a;
    scanf("%c",&a);
    scanf("%c",&a);
    hfm_decoding(a,6,w,ch);
}