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

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

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

[摘要]本文是数据结构与算法基本程序合集,与大家分享。
三、队及其操作
//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>
#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);
}


相关评论