【C语言】数据结构C语言版实验4 栈与字符串

末蓝、 2022-12-27 09:14 175阅读 0赞

/*
    利用顺序栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
    */
    /**********************************/
    /*文件名称：lab4_01.c                 */
    /**********************************/
    #include "seqstack.h"
    /*请将本函数补充完整，并进行测试*/
    void Dto16(int m)
    {   seqstack s;            /*定义顺序栈*/
        init(&s);
        printf("十进制数%u对应的十六进制数是：",m); //%d 输出有符号十进制数  %u 输出无符号十进制数 
        while (m)
        {
            push(&s,m%16);
            m=m/16;
        }
        while (!empty(&s))
                    printf("%x",pop(&s));
        printf("\n");
    }
    int main()
    {    int m;
         printf("请输入待转换的十进制数：\n");
         scanf("%u",&m);
         Dto16(m);
         return 0;
    }

/*
    利用链式栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
    */
    /**********************************/
    /*文件名称：lab4_02.c                 */
    /**********************************/
    #include "linkstack.h"
    /*请将本函数补充完整，并进行测试*/
    void Dto16(unsigned int m)
    {
        linkstack s;
        s=init();
        printf("十进制数%u对应的十六进制数是：",m);
        while (m)
        {
            s=push(s,m%16);
            m/=16;
        }
        while (!empty(s))
                   {
                        printf("%x",read(s));
                        s=pop(s);
                   }
        printf("\n");
    }
    int main()
    {
            unsigned int m;
            printf("请输入待转换的十进制数：\n");
            scanf("%u",&m);
            Dto16(m);
            return 0;
    }

#include <stdio.h>
    #include "stack.h"  /*引入自定义的字符栈结构*/
    /**********************/
    /* 判断是否为运算符   */
    /*********************/
    int is_op(char op)
     {
       switch(op)
      { case '+':
        case '-':
        case '*':
        case '/':return 1;
        default:return 0;
        }
     }
    /****************************/
    /*   判断运算符的优先级     */
    /****************************/
    int priority(char op)
       {
         switch(op)
           {
              case '(':return 0;
              case '+':
              case '-':return 1;
              case '*':
              case '/':return 2;
            default: return -1;
            }
      }
    /*********************************/
    /*中缀表达式，转换为后缀表达式   */
    /*********************************/
    void postfix(char e[],char f[])
     {seqstack opst;
      int i,j;
      initstack(&opst);
      push(&opst,'\0');
      i=j=0;
      while (e[i]!='\0')
       { if ((e[i]>='0' && e[i]<='9') || e[i]=='.')
               f[j++]=e[i];                     /*数字*/
          else if (e[i]=='(')                /*左括号*/
                   push(&opst,e[i]);
               else if (e[i]==')')           /*右括号*/
                  { while (stacktop(&opst)!='(')
                            f[j++]=pop(&opst);
                      pop(&opst);            /*'('出栈*/
                   }
               else if (is_op(e[i]))         /* '+ ,-, *, /' */
                      {f[j++]=' ';           /*用空格分开两个操作数*/
                       while (priority(stacktop(&opst))>=priority(e[i]))
                           f[j++]=pop(&opst);
                       push(&opst,e[i]);     /*当前元进栈*/
                       }
           i++;  /*处理下一元*/
        }
        while (!stackempty(&opst))
            f[j++]=pop(&opst);
        f[j]='\0';
      }
    /****************************************/
    /*    将数字字符串转变成数值            */
    /****************************************/
    float readnumber(char f[],int *i)
      {
         float x=0.0;
       int k=0;
       while (f[*i]>='0' && f[*i]<='9') /*处理整数部分*/
       {
           x=x*10+(f[*i]-'0');
            (*i)++;
       }
       if (f[*i]=='.') /*处理小数部分*/
           {  (*i)++;
                while (f[*i]>='0' && f[*i]<='9')
                        {   x=x*10+(f[*i]-'0');
                            (*i)++;
                            k++;
                        }
          }
      while (k!=0)
        {       x=x/10.0;
                k=k-1;
        }
        printf("\n*%f*",x);
        return(x);
    }
    /****************************************/
    /*         后缀表达式求值程序           */
    /****************************************/
    double  evalpost(char f[])
      {  double   obst[50]; /*操作数栈*/
         int i=0,top=-1;
         /*请将本函数补充完整*/
        float x;
        while(f[i]!='\0')
        {
            if(f[i]>='0'&&f[i]<='9')
                obst[++top]=readnumber(f,&i);
            else if(f[i]==' ')
                i++;
            else if(f[i]=='+')
            {
                x=obst[top--];
                obst[top]=x+obst[top];
                i++;
            }
            else if(f[i]=='-')
            {
                x=obst[top--];
                obst[top]=x-obst[top];
                i++;
            }
            else if(f[i]=='*')
            {
                x=obst[top--];
                obst[top]=x*obst[top];
                i++;
            }
            else if(f[i]=='/')
            {
                x=obst[top--];
                obst[top]=x/obst[top];
                i++;
            }
        }
        return obst[top];
      }
    /*
    主程序：输入中缀表达式，经转换后输出后缀表达式
    */
    int main()
     {
            char e[50],f[50];
            int i,j;
            printf("\n\n请输入中缀表达式:\n");
            gets(e);
            postfix(e,f);
            i=0;
            printf("\n\n对应的后缀表达式为: [");
            while (f[i]!='\0')
                    printf("%c",f[i++]);
            printf("]");
            printf("\n\n计算结果为 :");
            printf("\n\n%f",evalpost(f));
            return 0;
    }

/*
    已知字符串采用带结点的链式存储结构(详见linksrting.h文件)，
    请编写函数linkstring substring(linkstring s,int i,int len)，
    在字符串s中从第i个位置起取长度为len的子串，函数返回子串链表。
    */
    #include "linkstring.h"
    /*请将本函数补充完整，并进行测试*/
    linkstring substring(linkstring  s, int i, int len)
    {
        linkstring head,pos=s->next,makenode,newlist;
        int cnt=0;
        head=(linkstring)malloc(sizeof(linknode));
        head->next=NULL;
        newlist=head;
        while(pos)
        {
            if(cnt>=i&&cnt<=i+len-1)
            {
                makenode=(linkstring)malloc(sizeof(linknode));
                makenode->data=pos->data,makenode->next=NULL;
                newlist->next=makenode;
                newlist=makenode;
            }
            if(cnt>=i+len)
                break;
            cnt++;
            pos=pos->next;
        }
        return head;
    }
    int main()
    {   linkstring str1,str2;
        str1=creat();                  /*建字符串链表*/
        print(str1);
        str2=substring(str1,3,5);    /*测试，从第3个位置开始取长度为5的子串,请自行构造不同测试用例*/
        print(str2);                   /*输出子串*/
        delList(str1);
        delList(str2);
        return 0;
    }

/*
    字符串采用带头结点的链表存储，设计算法函数void delstring(linkstring s, int i,int len)
    在字符串s中删除从第i个位置开始，长度为len的子串。
    */
    /**********************************/
    /*文件名称：lab4_05.c                 */
    /**********************************/
    #include "linkstring.h"
    /*请将本函数补充完整，并进行测试*/
    void delstring(linkstring  s, int i, int len)
    {
        linkstring p,q,r;
        int k=1;
        p=s->next;
        while(k<i&&p)     //查找待删除子串的起始位置
        {
            q=p;
            p=p->next;
            k++;
        }
        if(!p)              //如果s串长度小于i，则无法删除
            return;
        else
        {
            k=1;
            while(k<len&&p) //从第i个位置开始查找待删除子串的终点
            {
                p=p->next;
                k++;
            }
            if(!p)          //如果s串中i后面的长度小于len，则无法删除
                return ;
            else
            {
                if(!q)      //如果待删除子串位于s最前面
                {
                    r=s;
                    s=p->next;
                }
                else        //子串位于中间或者后面
                {
                    r=q->next;
                    q->next=p->next;
                }
                p->next=NULL; //待删除子串最后置为空
                while(r)
                {
                    p=r;
                    r=r->next;
                    free(p);   //逐个释放子串中的结点
                }
            }
        }
    }
    int main()
    {   linkstring str;
        str=creat();            /*建字符串链表*/
        print(str);
        delstring(str,2,3);     /*测试，从第2个位置删除长度为3的子串,请自行构造不同的测试用例  */
        print(str);               /*输出*/
        delList(str);
        return 0;
    }

/*
    字符串采用带头结点的链表存储，编写函数linkstring index(linkstring s, linkstring t)，
    查找子串t在主串s中第一次出现的位置，若匹配不成功，则返回NULL。
    */
    #include "linkstring.h"
    /*请将本函数补充完整，并进行测试*/
    linkstring index(linkstring  s, linkstring t)
    {
        linkstring p,s1,t1;
        p=s->next;
        while(p)        //p记录匹配的起点
        {
            s1=p;       //s1记录s比较的当前位置
            t1=t->next; //s2记录t比较的当前位置
            while(s1&&t1&&s1->data==t1->data)
            {
                s1=s1->next;
                t1=t1->next;
            }
            if(!t1) return p;   //如果匹配成功，则返回p
            p=p->next;
        }
        return NULL;
    }
    int main()
    {   linkstring s,t,p=NULL;
        s=creat();                  /*建立主串链表*/
        t=creat();                    /*建立子串链表*/
        print(s);
        print(t);
        p=index(s,t);
        if(p)
                printf("匹配成功，首次匹配成功的位置结点值为%c\n",p->data);
        else
                printf("匹配不成功！\n");
        delList(s);
        delList(t);
        return 0;
    }

/*
    利用朴素模式匹配算法，将模式t在主串s中所有出现的位置存储在带头结点的单链表中。
    */
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    typedef struct node
    {        int data;
            struct node *next;
    }linknode;
    typedef linknode *linklist;
    /*朴素模式匹配算法,返回t中s中第一次出现的位置，没找到则返回-1，请将程序补充完整*/
    int index(char *s,char *t)
    {
        int m,n,i,j,k;
        m=strlen(s);
        n=strlen(t);
        for(i=0;i<=m-n;i++)
        {
            k=i;
            j=0;
            while(j<n)
            {
                if(s[k]==t[j])
                {
                    k++;
                    j++;
                }
                else
                    break;
            }
            if(j==n)
                return i;
        }
        return -1;
    }
    /*利用朴素模式匹配算法，将模式t在s中所有出现的位置存储在带头结点的单链表中,请将函数补充完整*/
    linklist indexall(char *s,char *t)
    {
        linklist head,p,r;
        int m,n,i,j,k;
        head=(linklist)malloc(sizeof(linknode));
        r=head;
        m=strlen(s);
        n=strlen(t);
        for(i=0;i<=m-n;i++)
        {
            k=i;
            j=0;
            while(j<n)
            {
                if(s[k]==t[j])
                {
                    k++;
                    j++;
                }
                else
                    break;
            }
            if(j==n)
            {
                p=(linklist)malloc(sizeof(linknode));
                p->data=i;
                r->next=p;
                r=p;
            }
        }
        r->next=NULL;
        return head;
    }
    /*输出带头结点的单链表*/
    void print(linklist head)
    {    linklist p;
        p=head->next;
        while(p)
        {    printf("%5d",p->data);
            p=p->next;
        }
        printf("\n");
    }
    int main()
    {    char s[80],t[80];
        linklist head;
        printf("请输入主串:\n");
        gets(s);
        printf("请输入模式串:\n");
        gets(t);
        int k=index(s,t);
        printf("k=%d",k);
        head=indexall(s,t);
        printf("\n[ %s ]在[ %s ]中的位置有：\n",t,s);
        print(head);
        return 0;
    }

/*
      编写快速模式匹配KMP算法，请将相关函数补充完整。
    */
    #define maxsize 100
    typedef struct{
          char str[maxsize];
          int length ;
    } seqstring;
    /*求模式p的next[]值，请将函数补充完整*/
    void getnext(seqstring p,int next[])
    {
        int i,j;
        i=0;j=-1;
        next[0]=-1;
        while(i<p.length)
        {
            if(j==-1||p.str[i]==p.str[j])
            {
                ++i;
                ++j;
                next[i]=j;
            }
            else
                j=next[j];
        }
        for(i=0;i<p.length;i++)
            printf("%3d",next[i]);
    }
    /*快速模式匹配算法，请将函数补充完整*/
    int kmp(seqstring t,seqstring p,int next[])
    {
        int i=0,j=0;
        while(i<t.length&&j<p.length)
        {
            if(j==-1||t.str[i]==p.str[j])
            {
                i++;
                j++;
            }
            else
                j=next[j];
        }
        return j==p.length?i-p.length:-1;
    }
    int  main()
     {   seqstring t, p;
         int next[maxsize],pos;
         printf("请输入主串：\n");
         gets(t.str);
         t.length=strlen(t.str);
         printf("请输入模式串：\n");
         gets(p.str);
         p.length=strlen(p.str);
         getnext(p,next);
         pos=kmp(t,p,next);
         printf("\n");
         printf("%d",pos);
         return 0;
    }