数据结构与算法例程集合.txt

数据结构和算法的C语言描述集合

    L min1_pos,min2_pos,t,min_pri;
    bt min1_son,min2_son;
    int min1,min2;
    char min1_c,min2_c;
    //=========================================

    //=========================================
    //这些变量用于构造二叉子树
    bt left,right,root;
    //==========================================

    //==========================================
    //这些变量用于将二叉子树信息插入链表
    L made,temp_p;
    //============================================

    while(list_element_amount()>=2)    //若表中还有两个或以上结点，则归并继续
    {
        //选择次数值最小的两个结点

        //============================================================================
        //先寻找第一个小结点
        t=l->next;
        min1=t->amount;        //将第一个结点的次数值赋给min1
        min1_pos=t;            //将第一个结点的位置指针赋给min1_pos
        min1_c=t->ch;        //将第一个结点的字符赋值给min1_c
        min1_son=t->son;    //将第一个结点的二叉指针赋值给min1_son
        min_pri=l;            //min_pri始终指向最小结点的前驱，以方便删除最小结点

        while(t->next!=NULL)
        {
            t=t->next;
            if(min1>t->amount)    //发现更小的结点
            {
                min1=t->amount;        //将当前结点的次数值赋给min1
                min1_pos=t;            //将当前结点的位置指针赋给min1_pos
                min1_c=t->ch;        //将当前结点的字符赋值给min1_c
                min1_son=t->son;    //将当前结点的二叉指针赋值给min1_son
            }
        }//退出本循环时，最小结点的信息找出，将该结点删除

        min_pri=l;
        while(min_pri->next!=min1_pos)
            min_pri=min_pri->next;
        //退出循环时min_pri指向min1_pos的前驱
        min_pri->next=min1_pos->next;        //删除结点min1_pos
        //寻找第一个小结点完成
        //=================================================================

        //=================================================================
        //先寻找第二个小结点
        t=l->next;
        min2=t->amount;        //将第二个结点的次数值赋给min2
        min2_pos=t;            //将第二个结点的位置指针赋给min2_pos
        min2_c=t->ch;
        min2_son=t->son;
        min_pri=l;        //min_pri始终指向最小结点的前驱，以方便删除最小结点

        while(t->next!=NULL)
        {
            t=t->next;
            if(min2>t->amount)    //发现更小的结点
            {
                min2=t->amount;        //将当前结点的次数值赋给min2
                min2_pos=t;            //将当前结点的位置指针赋给min2_pos
                min2_c=t->ch;
                min2_son=t->son;
            }
        }//退出本循环时，最小结点的信息找出，将该结点删除

        min_pri=l;
        while(min_pri->next!=min2_pos)
            min_pri=min_pri->next;
        //退出循环时min_pri指向min1_pos的前驱
        min_pri->next=min2_pos->next;        //删除结点min2_pos
        //寻找第二个小结点完成
        //=================================================================


        //==================================================================
        //两个最小结点找到，由这对结点级成一个二叉子树，将根结点插入链表中
        if(min1_son==NULL)    //该结点无二叉子树指针，则须新分配一个二叉树结点
        {
            left=(bt)malloc(sizeof(tnode));        //产生左孩子
            left->amount=min1;        //次数值复制
            left->ch=min1_c;        //字符复制
            left->left=NULL;
            left->right=NULL;
        }
        else    //该结点为计算产生的结点，它已指向一个二叉子树
            left=min1_son;    //left直接指向已经生成的二叉子树的根结点

        if(min2_son==NULL)    //该结点无二叉子树指针，则须新分配一个二叉树结点
        {
            right=(bt)malloc(sizeof(tnode));        //产生右孩子
            right->amount=min2;        //次数值复制
            right->ch=min2_c;        //字符复制
            right->left=NULL;
            right->right=NULL;
        }
        else
            right=min2_son;    //left直接指向已经生成的二叉子树的根结点

        root=(bt)malloc(sizeof(tnode));
        root->amount=min1+min2;
        root->ch='\0';        //对于计算产生的树结点，字符均为空
        root->left=left;
        root->right=right;
        //二叉子树完成

        //生成一个对应上面已产生二叉子树地址的链表结点
        made=(L)malloc(sizeof(Node));
        made->amount=root->amount;
        made->ch=root->ch;
        made->next=NULL;
        made->son=root;

        //将生成的链表结点插入链表中
        temp_p=l;
        while(temp_p->next!=NULL)
            temp_p=temp_p->next;
        //退出循环时temp_p指向链表最后一个结点
        temp_p->next=made;        //将生成的结点插入链表
    }

    temp_p=l->next;
    return temp_p->son;
}

void encoding()        //根据建立的哈夫曼树编码
{
    stack code,top,temp,readcode;
    bt r;
    huff temp_huff,hp;
    char huff[100]="";        //用于存储当前字符的哈夫曼编码串
    int i,j,n=0;

    hlist=(hnode*)malloc(sizeof(hnode));
    hlist->ch='\0';
    for(i=0;i<100;i++)
        hlist->code[i]='\0';
    hlist->next=NULL;
    hp=hlist;    

    //建立空栈
    code=(stack)malloc(sizeof(snode));
    code->amount=0;
    code->ch='\0';
    code->next=NULL;
    code->son=NULL;        //栈的头结点指向树的根结点
    top=code;

    r=root;
    temp=(stack)malloc(sizeof(snode));    //给哈夫曼树的根结点分配栈结点
    temp->amount=r->amount;
    temp->ch='0';
    temp->next=top;
    temp->son=r;
    top=temp;
    
    while(r!=NULL)    //当前结点存在
    {
        if(r->left!=NULL&&r->left->amount!=-1)    //当前结点有左孩子
        {
            r=r->left;        //r转向左孩子
            r->amount=-1;

            temp=(stack)malloc(sizeof(snode));    //给左孩子分配栈结点
            temp->amount=r->amount;
            temp->ch='0';
            temp->next=top;
            temp->son=r;
            top=temp;
        }
        else if(r->right!=NULL&&r->right->amount!=-1)        //当前结点有右孩子
        {
            r=r->right;        //r转向右孩子
            r->amount=-1;

            temp=(stack)malloc(sizeof(snode));    //给右孩子分配栈结点
            temp->amount=r->amount;
            temp->ch='1';
            temp->next=top;
            temp->son=r;
            top=temp;
        }
        else    //无未访问的孩子结点
        {
            
            if(r->left==NULL&&r->right==NULL)    //当前结点为叶子结点
            {
                for(i=0;i<100;i++)    //对哈夫曼编码数组初始化
                    huff[i]='\0';

                //先输出该叶子结点的编码
                printf("字符%c,编码为:",r->ch);
                readcode=top;
                i=0;

                while(readcode!=code)
                {
                    huff[i++]=readcode->ch;        //将栈元素倒置入哈夫曼编码数组中
                    readcode=readcode->next;
                }
                
                temp_huff=(hnode*)malloc(sizeof(hnode));    //为当前字符及其编码创建结点
                temp_huff->ch=r->ch;        //存储编码的原字符
                for(j=0;j<100;j++)        //初始化编码串数组
                    temp_huff->code[j]='\0';

                j=0;

                for(i=i-2;i>=0;i--)                //依次读出哈夫曼编码数组中的编码串
                {
                    printf("%c",huff[i]);
                    temp_huff->code[j++]=huff[i];
                }
                temp_huff->next=NULL;
                hp->next=temp_huff;
                hp=temp_huff;

                printf("\t\t");
                if(++n%2==0)
                    printf("\n");
            }

            if(top->next!=code)        //若栈非空
            {
                top=top->next;
                r=top->son;
            }
            else
                break;
        }
    }
}


void describe_tree()    //交互式显示哈夫曼树
{
    bt t;
    stack s,top,temp;
    int choice;

    s=(stack)malloc(sizeof(snode));
    s->amount=0;
    s->ch='\0';
    s->next=NULL;
    s->son=NULL;
    top=s;
    
    t=root;//t指向哈夫曼树的根结点

    temp=(stack)malloc(sizeof(snode));    //分配新栈结点
    temp->amount=t->amount;        
    temp->ch=t->ch;
    temp->next=top;        //结点入栈
    temp->son=t;    //将当前二叉树结点指针给栈顶结点
    top=temp;        //修改栈顶指针

    printf("输入1往左子树，输入2往右子树，输入3返回父结点，输入4退出程序，其它输入无效\n");
    scanf("%d",&choice);
    getchar();
    
    while(choice==1||choice==2||choice==3)
    {
        if(choice==1)        //往左子树
        {
            if(t->left!=NULL)
            {
                t=t->left;
                temp=(stack)malloc(sizeof(snode));    //分配新栈结点
                //新结点入栈
                temp->amount=t->amount;        
                temp->ch=t->ch;
                temp->next=top;        //结点入栈
                temp->son=t;    //将当前二叉树结点指针给栈顶结点
                top=temp;        //修改栈顶指针
                printf("%c,%d\n",t->ch,t->amount);
            }
            else    //左子树不存在，当前结点已经是叶子结点
                printf("无左孩子！\n");    
        }
        else if(choice==2)    //往右子树
        {
            if(t->right!=NULL)
            {
                t=t->right;
                temp=(stack)malloc(sizeof(snode));    //分配新栈结点
                //新结点入栈
                temp->amount=t->amount;
                temp->ch=t->ch;
                temp->next=top;        //结点入栈
                temp->son=t;    //将当前二叉树结点指针给栈顶结点
                top=temp;        //修改栈顶指针
                printf("%c,%d\n",t->ch,t->amount);
            }
            else    //右子树不存在，当前结点已经是叶子结点
                printf("无右孩子！\n");
        }
        else if(choice==3)    //返回父结点
        {
            if(top->next!=s)    //栈非空
            {
                top=top->next;
                t=top->son;
                printf("%c,%d\n",t->ch,t->amount);
            }
            else
                printf("已经在根结点了！\n");
        }
        //else if(choice==4)    //退出程序
        //    exit(0);

        scanf("%d",&choice);
        getchar();
    }
}


void codeoutput()    //输出原始字符串的哈夫曼编码串
{
    huff hp;
    //char *s;
    int i;
    c=str;        //c指向原始字符串str的首位置
    printf("\n\n原始字符串为:%s\n哈夫曼编码为:",c);
    code_sum=0;
    //在编码链表中找寻与c匹配的编码串
    while(*c!='\0')        //字符串未读完
    {
        hp=hlist->next;        //hp指向编码链表的第一个字符编码组
        
        while(hp->ch!=*c&&hp->next!=NULL)    //尚未找到匹配字符且后面还有字符
            hp=hp->next;
        //退出循环的原因可能是找到了匹配字符，也可能是链表读完，需要进一步判断
        if(hp->ch==*c)    //找到匹配字符
        {
            i=0;
            while(hp->code[i]!='\0')
                printf("%c",hp->code[i++]);            
        }
        code_sum+=i;
        C++;
    }
    printf("\n\n");
}

void analyze()    //编码性能分析
{
    int n=0;
    printf("\t\t\t性能分析中...\n\n");
    while(pow(2,n)<char_num)    //计算等长编码情况下需要的编码位数
        n++;
    printf("等长码需要 %d 位,编码总长 %d 位,本次哈夫曼编码总长 %d , 压缩比 %g\n",n,n*char_amount,code_sum,(float)code_sum/(n*char_amount));

}

main()
{
    int choice;
    //初始化，操作包括建立空链表和键盘输入字符串
    initial();

    //将接收的字符串依次读入链表中，并统计出现的次数
    pull_in_list();

    //建立最优二叉树
    root=create();

    //交互式显示哈夫曼树
    if(root!=NULL)
    {
        printf("\n哈夫曼树构造完成，是否查看哈夫曼树，输入1查看，其它输入跳过");
        scanf("%d",&choice);
        getchar();

        if(choice==1)
            describe_tree();
    }
    else
    {
        printf("哈夫曼树未建立，查看字符串中是否只含一种字符，或者重试\n");
        exit();
    }

    //要挟据建立的最优二叉树进行编码
    encoding();

    //将原始字符串的哈夫曼编码串输出
    codeoutput();

    //编码性能分析
    analyze();

    printf("\n\n\t\t\tAll Copyright Are Presevered By cobby\n\n输入任何键退出\n");
    scanf("%d",&choice);
}




六、排序
/* 冒泡排序 */

#include<stdlib.h>
#include<stdio.h>

main()
{
    int i,j,temp,a[30000];
    long TIME=0;
    rand();

    for(i=0;i<30000;i++)
    {
        a[i]=rand();
        printf("%d\t",a[i]);
    }

    for(i=29999;i>=0;i--)
        for(j=0;j<=i;j++)
            if(a[j+1]<a[j])
            {
                TIME++;
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }

    for(i=0;i<=29999;i++)
        printf("%d\t",a[i]);
    printf("\n%d\n",TIME);
}


/*  直接选择排序法 */

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//#include<time.h>

main()
{
    int i,j,value,pos,temp,a[30000];
    long TIME=0;
    
    rand();
    for(i=0;i<30000;i++) /* make up the rand numbers*/
    {
        a[i]=rand();
        printf("%d\t",a[i]);
    }

    for(i=0;i<30000;i++)        /* sort */
    {
        value=a[i];
        pos=i;
        for(j=i+1;j<30000;j++)
        {
            TIME++;
            if(value>a[j])
            {
                value=a[j];
                pos=j;
            }
        }
        temp=a[i];
        a[i]=a[pos];
        a[pos]=temp;
    }
    for(i=0;i<30000;i++)
        printf("%d\t",a[i]);
    printf("\n\n%ld\n",TIME);
}