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

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

    printf("一共有几个人围成一圈？\n");
    scanf("%d",&amount);
    getchar();
    printf("从第几个开始计数？\n");
    scanf("%d",&start);
    getchar();
    printf("每几人一次循环？\n");
    scanf("%d",&circle);
    getchar();

    l=(L)malloc(sizeof(node));        //头结点
    l->next=NULL;
    l->num=0;
    q=l;
    n=0;

    while(n++<amount)
    {
        p=(L)malloc(sizeof(node));
        p->next=NULL;
        p->num=n;
        q->next=p;
        q=p;
    }
    q->next=l->next;        //形成循环链表

    //以上完成了单向循环链表的建立
    p=l->next;
    q=l;
    n=1;
    while(n++<start)
    {
        p=p->next;
        q=q->next;
    }
    //退出循环时p,q分别位于指定位置

    //接下去进行周期性结点删除，直到链表只余一个结点为止
    n=1;        //n计算被删除的结点的数量，当n=amount-1时删除结束
    while(n++<amount)
    {
        c=1;    //c作为循环临时变量
        while(C++<circle)
        {
            p=p->next;
            q=q->next;
        }
        //删除当前p指向的结点
        printf("删除结点%d\t",p->num);
        q->next=p->next;
        p=p->next;
    }
    printf("\n最后剩下%d\n",p->num);
}

二、栈及其操作
//All copyright are preserved bycobby
/*建立堆栈*/

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

typedef struct node
{
    char ch;
    struct node *next;
}Snode,*stack;

main()
{
    stack s,top,p;
    char ch;
    
    s=(stack)malloc(sizeof(Snode));
    s->ch='\0';
    s->next=NULL;        /*建立栈底指针*/
    top=s;
    scanf("%c",&ch);
    getchar();
    
    while(ch!='!')
    {
        p=(stack)malloc(sizeof(Snode));
        p->ch=ch;
        p->next=top;
        top=p;
        scanf("%c",&ch);
        getchar();
    }

    while(top->next!=NULL)
    {
        printf("%c-->",top->ch);
        top=top->next;
    }
    printf("\n");
}


//All copyright are preserved bycobby
/*进栈与出栈*/

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

typedef struct node
{
    char ch;
    struct node *next;
}Snode,*stack;

main()
{
    stack s,top,p;
    char ch;
    int choice;
    
    s=(stack)malloc(sizeof(Snode));
    s->ch='!';
    s->next=NULL;        /*建立栈底指针*/
    top=s;
    scanf("%c",&ch);
    getchar();
    
    while(ch!='!')
    {
        p=(stack)malloc(sizeof(Snode));
        p->ch=ch;
        p->next=top;
        top=p;
        scanf("%c",&ch);
        getchar();
    }

    while(p->next!=NULL)    //此处p可用top代替
    {
        printf("%c-->",p->ch);
        p=p->next;
    }
    printf("\n");

    /*以上建立了一个堆栈*/

    printf("进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退出程序\n");
    scanf("%d",&choice);
    getchar();
    while(choice==1||choice==2)    //若不是输入1或2，则不做任何操作
    {
        if(choice==1)
        {
            /*进栈*/
            printf("\n输入要入栈的元素\n");
            scanf("%c",&ch);
            getchar();
            
            p=(stack)malloc(sizeof(Snode));
            p->ch=ch;
            p->next=top;
            top=p;
        }
        else if(choice==2)
        {
            if(top->next!=NULL)
                top=top->next;
            else
            {
                printf("栈已清空\n");
                exit();
            }
            /*出栈*/
        }
        //printf("%c-->",top->ch);
        p=top;
        while(p->next!=NULL)
        {
            printf("%c-->",p->ch);
            p=p->next;
        }
        printf("\n");
        printf("进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退出程序\n");
        scanf("%d",&choice);
        getchar();
    }
}


//All copyright are preserved bycobby
//栈的应用，括号匹配
#include<stdio.h>
#include<malloc.h>
#define NULL 0
typedef struct node
{
    char ch;
    struct node *next;
}snode,*stack;

main()
{
    stack s,top,p;
    char *string,ch[100]="";

    s=(stack)malloc(sizeof(snode));        //建立栈底元素
    s->ch='\0';
    s->next=NULL;
    top=s;

    printf("输入一个含括号的四则运算表达式：\n");
    scanf("%s",ch);
    string=ch;

    while(*string!='\0')
    {
        if(*string=='('||*string=='['||*string=='{')    //遇到左括号，入栈
        {
            p=(stack)malloc(sizeof(snode));
            p->ch=*string;
            p->next=top;
            top=p;
        }
        else if(*string==')'||*string==']'||*string=='}')    //遇到右括号
        {
            if(*string==')')
                if(top->ch=='(')    //括号匹配
                    top=top->next;
                else
                {
                    printf("小括号不匹配");
                    exit(0);
                }
            else if(*string==']')
                if(top->ch=='[')    //括号匹配
                    top=top->next;
                else
                {
                    printf("中括号不匹配");
                    exit(0);
                }
            else
                if(top->ch=='{')    //括号匹配
                    top=top->next;
                else
                {
                    printf("大括号不匹配");
                    exit(0);
                }
        }
        string++;
    }
    if(top->ch!='\0')
        printf("多出左括号%c\n",top->ch);
    
}



三、队及其操作
//All copyright are preserved bycobby
//链队列的建立

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

typedef struct node            //队列结点的基本数据结构，即队列中每个结点的类型
{
    char c;
    struct node *next;
}qnode,*basic_node;

typedef struct            //队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定
{
    qnode *head;
    qnode *rear;
}queue,*Q;

main()
{
    Q q;    //定义队列，结构体变量q中含有头指针head和尾指针rear，所以q是一个完整的队列（只不过队列为空）
            //事实上，任何由Q定义的结构体变量都是一个独立完整的队列
    basic_node p,l;        //basic_node是基本结点类型，即是独立的结点，它是组成队列的基本元素。
    //基本结点p,l和队列q的关系可由下图表示：
    //  (q->head)--->p--->l--->p--->l--->……--->p--->l--->(q->rear)
    char ch;

    q=(Q)malloc(sizeof(queue));
    q->head=NULL;    //初始化时队列为空
    q->rear=NULL;

    printf("输入队列元素:\n");
    scanf("%c",&ch);
    getchar();
    
    while(ch!='!')
    {
        p=(qnode*)malloc(sizeof(qnode));
        p->c=ch;
        p->next=NULL;        //新来的元素一定在队列的最后，它的后面没有其它元素
        if(q->head==NULL)
        {
            q->head=p;        //第一个元素入队时，队头指针指向它
            l=q->head;        //l指向第一个元素
        }
        l->next=p;            //使前一个元素指向当前入队的新元素
        l=p;                //l移动到当前新元素，以备用下次入队操作
        q->rear=p;            //修改队尾指针，使其总是指向当前最后一个队列元素
        scanf("%c",&ch);
        getchar();
    }
    l=q->head;
    while(l!=NULL)
    {
        printf("%c<--",l->c);
        l=l->next;
    }
    printf("\n");
    printf("头指针指向元素为%c\t尾指针指向元素为%c\n",q->head->c,q->rear->c );
}


//All copyright are preserved bycobby

//入队和出队

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

typedef struct node            //队列结点的基本数据结构，即队列中每个结点的类型
{
    char c;
    struct node *next;
}qnode,*basic_node;

typedef struct            //队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定
{
    qnode *head;
    qnode *rear;
}queue,*Q;

main()
{
    Q q;    //定义队列，结构体变量q中含有头指针head和尾指针rear，所以q是一个完整的队列（只不过队列为空）
            //事实上，任何由Q定义的结构体变量都是一个独立完整的队列
    basic_node p,l;        //basic_node是基本结点类型，即是独立的结点，它是组成队列的基本元素。
    //基本结点p,l和队列q的关系可由下图表示：
    //  (q->head)--->p--->l--->p--->l--->……--->p--->l--->(q->rear)
    char ch;
    int choice;

    q=(Q)malloc(sizeof(queue));
    q->head=NULL;    //初始化时队列为空
    q->rear=NULL;

    printf("输入队列元素:\n");
    scanf("%c",&ch);
    getchar();
    
    while(ch!='!')
    {
        p=(qnode*)malloc(sizeof(qnode));
        p->c=ch;
        p->next=NULL;        //新来的元素一定在队列的最后，它的后面没有其它元素
        if(q->head==NULL)
        {
            q->head=p;        //第一个元素入队时，队头指针指向它
            l=q->head;        //l指向第一个元素
        }
        l->next=p;            //使前一个元素指向当前入队的新元素
        l=p;                //l移动到当前新元素，以备用下次入队操作
        q->rear=p;            //修改队尾指针，使其总是指向当前最后一个队列元素
        scanf("%c",&ch);
        getchar();
    }
    l=q->head;
    while(l!=NULL)
    {
        printf("%c<--",l->c);
        l=l->next;
    }
    printf("\n");
    printf("头指针指向元素为%c\t尾指针指向元素为%c\n",q->head->c,q->rear->c );


    //以上建立了一个队列

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

    if(choice==1)
    {
        printf("\n输入要入队的元素:\n");
        scanf("%c",&ch);
        getchar();
        p=(qnode*)malloc(sizeof(qnode));    //给新入队的元素分配内存空间
        p->c=ch;
        p->next=NULL;        //新元素为最后一个元素
        q->rear->next=p;    //原来最后一个元素指向新入队的元素
        q->rear=p;            //修改队尾指针，使其指向当前最后一个元素
    }
    else if(choice==2)
        q->head=q->head->next;
    else
        exit(0);

    l=q->head;
    while(l!=NULL)
    {
        printf("%c<--",l->c);
        l=l->next;
    }
    printf("\n");
    printf("头指针指向元素为%c\t尾指针指向元素为%c\n",q->head->c,q->rear->c );
}


//All copyright are preserved bycobby
//循环队列建立

#include<stdio.h>
#include<malloc.h>
#define MAX 8

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

main()
{
    queue *q;
    char ch;
    int i;
    
    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();
    }

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


//All copyright are preserved bycobby
//循环队列的入队和出队操作

#include<stdio.h>