大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > 数据结构与算法基本程序合集

数据结构与算法基本程序合集(2)

关键词:数据结构算法基本程序  阅读(2758) 赞(55)

[摘要]本文是数据结构与算法基本程序合集,与大家分享。
//单链表就地逆置
#define NULL 0            /*宏定义*/
typedef struct node        /*定义结点类型的数据结构*/
{
    char c;            /*数据域,类型为字符型*/
    struct node *next;    /*指针域,类型为本结构体类型*/
}Node,*L;            /*类型重定义,即Node和*L和struct node等价*/
 
main()
{
    L l,p,q,r;        /*用指针类型定义三个结点类型的指针*/
    char ch;
    l=(L)malloc(sizeof(Node));    /*分配内存空间*/
    l->c='\0';            /*为头结点的数据域赋值,值为空*/
    l->next=NULL;            /*指明下一个结点目前不存在*/
    q=l;                /*q为游动指针,链表结点的连结要用*/
    printf("Input a character:\n");
    scanf("%c",&ch);
    getchar();
    while(ch!='!')            /*输入!表示输入结束*/
    {
        p=(L)malloc(sizeof(Node));    /*为新输入的数据分配内存空间*/
        p->c=ch;
        p->next=NULL;            /*新输入的结点在链表的最后,即它的后面没有其它元素*/
        q->next=p;            /*q用于将上一个元素链接至当前新元素*/
        q=p;                /*q自己移到当前最后一个元素,以备继续链接所用*/
        scanf("%c",&ch);
        getchar();
    }
    q=l;                /*输入整个链表前,先将q移到链表头,l一般不动*/
    while(q->next!=NULL)        /*若q所指向的元素后面还有其它元素,则将该元素的数据输出*/
    {
        printf("%c-->",q->next->c);    /*q->next->c表示q所指向的下一个元素的数据*/
        q=q->next;            /*完成该元素的输出后,q移至下一个元素重复输出操作*/
    }
    printf("\n");
 
    //以上完成了单链表的创建
    q=l->next;
    p=q->next;
    r=p->next;
    q->next=NULL;
    while(r!=NULL)
    {
        p->next=q;
        q=p;
        p=r;
        if(r->next!=NULL)    //r后面还有结点,则逆置继续
            r=r->next;
        else
            break;
    }
    r->next=q;
    l->next=r;        //头结点指向最后一个结点
 
    q=l;                /*输入整个链表前,先将q移到链表头,l一般不动*/
    while(q->next!=NULL)        /*若q所指向的元素后面还有其它元素,则将该元素的数据输出*/
    {
        printf("%c-->",q->next->c);    /*q->next->c表示q所指向的下一个元素的数据*/
        q=q->next;            /*完成该元素的输出后,q移至下一个元素重复输出操作*/
    }
    printf("\n");
}
 

//约瑟夫环问题
 
#include<stdio.h>
#include<malloc.h>
 
typedef struct lnode
{
    int num;
    struct lnode *next;
}node,*L;
 
main()
{
    int amount,start,circle,n,c;
    L p,l,q;
 
    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);
    
}


相关评论