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

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

#include<malloc.h>
#define MAX 8

typedef structd
{
    char c[MAX];    //循环队列是顺序队列的一种，它的核心就是一个数组
    int front;        //整形变量，作为头指针用
    int rear;        //整形变量，作为尾指针用
}queue;

main()
{
    queue *q;
    char ch;
    int i,choice;
    
    q=(queue*)malloc(sizeof(queue));    //生成一个空循环队列
    for(i=0;i<MAX;i++)
        q->c[i]='\0';
    q->front=0;
    q->rear=0;

    printf("输入要入队的元素:\n");
    scanf("%c",&ch);
    getchar();
    while(ch!='!')
    {
        if((q->rear+1)%MAX==q->front)    //若队列已满
        {
            printf("队列已满，无法入队\n");
            break;
        }
        else
        {
            q->c[q->rear]=ch;    //rear指向当前可入队的数组元素位置
        
            q->rear=(q->rear+1)%MAX;            //修改尾指针，向后移动一个位置
            //注意，不能简单使用q->rear++，不然会导致队列溢出
        }
        scanf("%c",&ch);
        getchar();
    }

    printf("头指针指向元素为%d\t尾指针指向元素为%d\n",q->front,q->rear);

    for(i=q->front;i<q->rear;i=(i+1)%MAX)        //能够用for循环，说明了顺序队列和链式队列的区别
        printf("%c-->",q->c[i]);
    printf("\n");

    //以上建立了一个循环队列
    printf("输入1入队，输入2出队:\n");
    scanf("%d",&choice);
    getchar();

    while(choice==1||choice==2)
    {
        if(choice==1)
        {
            printf("输入要入队的元素\n");
            scanf("%c",&ch);
            getchar();
            if((q->rear+1)%MAX==q->front)    //若队列已满
            {
                printf("队列已满，无法入队\n");
                break;
            }
            else
            {
                q->c[q->rear]=ch;    //rear指向当前可入队的数组元素位置
                q->rear=(q->rear+1)%MAX;            //修改尾指针，向后移动一个位置
                //注意，不能简单使用q->rear++，不然会导致队列溢出
            }
        }
        else if(choice==2)
        {
            if((q->front+1)%MAX!=q->rear)    //队非空
            {
                q->c[q->front]='\0';    //删除元素
                q->front=(q->front+1)%MAX;    //修改队头指针
            }
            else
            {
                printf("队已清空\n");
                break;
            }
        }

        if(q->rear>q->front)    //尾指针在头指针的右边
        {
            for(i=q->front;i<q->rear;i=(i+1)%MAX)        //能够用for循环，说明了顺序队列和链式队列的区别
                printf("%c<--",q->c[i]);
            printf("\n");
        }
        else        //尾指针在头指针的左边
        {
            for(i=q->front;i<(q->rear+MAX);i++)        //能够用for循环，说明了顺序队列和链式队列的区别
                printf("%c<--",q->c[i%MAX]);
            printf("\n");
        }
        printf("头指针指向元素为%d\t尾指针指向元素为%d\n",q->front,q->rear);

        printf("输入1入队，输入2出队:\n");
        scanf("%d",&choice);
        getchar();
    }
}

四、串及其操作
//串的朴素匹配

#include<stdio.h>

main()
{
    char str1[100],str2[100],*p;
    int i=0,j=0,len_str1=0,len_str2=0,num=0;
    printf("输入母串:\n");
    scanf("%s",str1);
    getchar();

    printf("%输入子串:\n");
    scanf("%s",str2);
    getchar();

    p=str1;
    while(*p!='\0')        //获取母串长度
    {
        len_str1++;
        p++;
    }

    p=str2;        //获取子串长度
    while(*p!='\0')
    {
        len_str2++;
        p++;
    }
    
    for(i=0;i<len_str1;i++)    //i为母串下标
    {
        for(j=0;j<len_str2;j++)        //j为子串下标
        {
            num++;
            if(str1[i+j]!=str2[j])
                break;        //若当前字符不匹配，则指针向母串下一个字符移动
        }
        if(j==len_str2)
        {
            printf("子串在母串中的位置为%d\n",i+1);
            //break;        //若子串在母串中多次出现，则全部找到其位置。若恢复break语句则只找出最前的一个匹配子串
        }
    }        
    printf("母串长度为%d,子串长度为%d\n核心语句执行次数为%d\n",len_str1,len_str2,num);
}




五、树（二叉树）及其操作
//二叉排序树

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

typedef struct tnode
{
    int num;
    struct tnode *Lchild,*Rchild;
}Tnode,*Btree;

typedef struct snode
{
    int num;
    Btree r;
    struct snode *next;
}Snode,*stack;

Btree root;

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

    s=(stack)malloc(sizeof(Snode));
    s->num=0;
    s->next=NULL;
    s->r=NULL;
    top=s;
    
    t=root;//t指向哈夫曼树的根结点

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

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

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

void inorder(Btree r)        //中序递归遍历
{
    if(r!=NULL)
    {
        inorder(r->Lchild);
        printf(" %d <",r->num);
        inorder(r->Rchild);
    }
}

main()
{
    int array[100],n=0,i,choice;
    Btree p,q;

    for(i=0;i<100;i++)
        array[i]=0;

    printf("输入若干个整数,结束用\"0\"表示\n");
    scanf("%d",&array[n++]);
    getchar();
    while(array[n-1]!=0)
        scanf("%d",&array[n++]);

    n=0;
    if(array[n]!=0)
    {
        root=(Btree)malloc(sizeof(Tnode));        //建立二叉排序树的根结点
        root->num=array[n];
        root->Lchild=NULL;
        root->Rchild=NULL;
        n++;
    }
    else
        exit(0);

    while(array[n]!=0)
    {
        p=(Btree)malloc(sizeof(Tnode));        //依次给每个整数分配结点
        p->num=array[n];
        p->Lchild=NULL;
        p->Rchild=NULL;

        //分配完结点后，要插入到二叉树中合适的位置
        q=root;        //q初始化到根结点
        while(q!=NULL)
        {
            if(q->num<p->num)    //若新结点的值大于根结点的值，则往右子树
            {
                if(q->Rchild!=NULL)        //当前结点有右孩子，则指针移向右孩子继续比较
                    q=q->Rchild;
                else        //当前结点没有右孩子，则新结点为当前结点的右孩子
                {
                    q->Rchild=p;
                    break;
                }
            }
            else
            {
                if(q->Lchild!=NULL)        //当前结点有左孩子，则指针移向左孩子继续比较
                    q=q->Lchild;
                else        //当前结点没有左孩子，则新结点为当前结点的左孩子
                {
                    q->Lchild=p;
                    break;
                }
            }
        }
        n++;
    }
    
    
    //建立二叉排序树完毕
    //对其进行中序遍历
    
    printf("\n哈夫曼树构造完成，是否查看哈夫曼树，输入1查看，其它输入跳过");
    scanf("%d",&choice);
    getchar();
    if(choice==1)
        describe_tree();
    
    inorder(root);
    printf("\n");
}





哈夫曼算法程序太大，一个贴放不下，下面两个贴均为哈夫曼编码程序.

//2005/4/28
//All Copyright Are Reserved By cobby
//哈夫曼编码

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define NULL 0

typedef struct huff_code_node    //存储编码的链表
{
    char ch;    //编码对应的字符
    char code[100];        //字符对应的哈夫曼码
    struct huff_code_node *next;    
}hnode,*huff;

typedef struct tree_Node    //二叉树结点
{
    char ch;    //字符内容
    int amount;    //字符在字符串中出现的次数
    struct tree_Node *left,*right;    //指向左子树与右子树
}tnode,*bt;

typedef struct list_node        //链表结点
{
    char ch;    //存储字符串中的字符
    int amount;    //字符在字符串中出现的次数
    tnode *son;    //链表结点带有二叉子树的根结点指针
    struct list_node *next;    //指向链表中下一个结点
}Node,*L;

typedef struct stack_node
{
    char ch;    //存储字符
    int amount;        //出现次数
    bt son;        //指向二叉树的某结点
    struct stack_node *next;
}snode,*stack;


char t[200],*str,*c;    //用于存储和处理输入的字符串
bt root=NULL;        //哈夫曼树
L l,p,q,new_node;    //链表结点
huff hlist;        //计算得到的编码表
int char_num;    //输入的不同字符数量
int char_amount;    //输入的所有字符数量
int code_sum;        //哈夫曼编码总长


void initial()        //初始化操作
{
    l=(Node*)malloc(sizeof(Node));        //建立空链表
    l->ch='\0';
    l->amount=0;
    l->son=NULL;
    l->next=NULL;

    str=t;    //将字符串指针指向字符串的第一个位置
    //键盘输入字符串
    printf("输入字符串进行哈夫曼编码:\n");
    scanf("%s",str);
    getchar();    
}

void pull_in_list()
{
    int exist;    //表示当前字符是否存在于链表中，0为不存在，1为已存在
    int n;    //计算输入不同字符的数量，计算后赋值给全局变量char_num
    int m;    //计算输入所有字符的数量，计算后赋值给全局变量char_amount
    
    c=str;    //c指向第一个字符
    
    while(*c!='\0')        //若字符串未读完
    {
        exist=0;
        p=l;    //p指向链表头结点
        //寻找该字符是否已经在链表中
        while(p->next!=NULL)    //若链表非空
        {
            p=p->next;
            if(p->ch==*c)    //若当前字符已经在链表中
            {
                exist=1;
                p->amount++;    //字符出现次数加1
                break;
            }
        }

        if(exist==0)    //若当前字符不存在于链表中，则分配一个结点入表
        {
            new_node=(Node*)malloc(sizeof(Node));
            new_node->ch=*c;
            new_node->amount=1;
            new_node->next=NULL;
            new_node->son=NULL;
            p->next=new_node;
            p=new_node;
        }
        C++;    //读下一个字符
    }

    printf("统计结果:\n");
    p=l;
    n=0;
    m=0;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
        m+=p->amount;
        printf("%c——%d\n",p->ch,p->amount);
    }
    char_num=n;
    char_amount=m;
    printf("一共有%d种字符输入，字符总数%d\n",char_num,char_amount);
}

int list_element_amount()        //计算链表中结点的数量（不包括头结点）
{
    L temp;        //定义临时指针
    int n=0;        //结点数量
    temp=l;
    while(temp->next!=NULL)    //后面还有结点
    {
        n++;
        temp=temp->next;
    }
    return n;
}

bt create()    //建立最优二叉树
{
    //=========================================
    //这些变量用于寻找最小结点