数据结构实验4-栈与字符串

avatar 2016年12月05日11:55:40 1 9116 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
 
  1. /*
  2. 利用顺序栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
  3. */
  4. /**********************************/
  5. /*文件名称：lab4_01.c                 */
  6. /**********************************/
  7. #include "seqstack.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. void Dto16(int m)
  10. {   seqstack s;            /*定义顺序栈*/
  11.     init(&s);
  12.     printf("十进制数%u对应的十六进制数是：",m); //%d 输出有符号十进制数  %u 输出无符号十进制数 
  13.     while (m)
  14.     {
  15.         push(&s,m%16);
  16.         m=m/16;
  17.     }
  18.     while (!empty(&s))
  19.                 printf("%x",pop(&s));
  20.     printf("\n");
  21. }
  22. int main()
  23. {    int m;
  24.      printf("请输入待转换的十进制数：\n");
  25.      scanf("%u",&m);
  26.      Dto16(m);
  27.      return 0;
  28. }

  1. /*
  2. 利用链式栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
  3. */
  4. /**********************************/
  5. /*文件名称：lab4_02.c                 */
  6. /**********************************/
  7. #include "linkstack.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. void Dto16(unsigned int m)
  10. {
  11.     linkstack s;
  12.     s=init();
  13.     printf("十进制数%u对应的十六进制数是：",m);
  14.     while (m)
  15.     {
  16.         s=push(s,m%16);
  17.         m/=16;
  18.     }
  19.     while (!empty(s))
  20.                {
  21.                     printf("%x",read(s));
  22.                     s=pop(s);
  23.                }
  24.     printf("\n");
  25. }
  28. int main()
  29. {
  30.         unsigned int m;
  31.         printf("请输入待转换的十进制数：\n");
  32.         scanf("%u",&m);
  33.         Dto16(m);
  34.         return 0;
  35. }

  1. #include <stdio.h>
  2. #include "stack.h"  /*引入自定义的字符栈结构*/
  3. /**********************/
  4. /* 判断是否为运算符   */
  5. /*********************/
  6. int is_op(char op)
  7.  {
  8.    switch(op)
  9.   { case '+':
  10.     case '-':
  11.     case '*':
  12.     case '/':return 1;
  13.     default:return 0;
  14.     }
  15.  }
  16. /****************************/
  17. /*   判断运算符的优先级     */
  18. /****************************/
  19. int priority(char op)
  20.    {
  21.      switch(op)
  22.        {
  23.           case '(':return 0;
  24.           case '+':
  25.           case '-':return 1;
  26.           case '*':
  27.           case '/':return 2;
  28.         default: return -1;
  29.         }
  30.   }
  32. /*********************************/
  33. /*中缀表达式，转换为后缀表达式   */
  34. /*********************************/
  35. void postfix(char e[],char f[])
  36.  {seqstack opst;
  37.   int i,j;
  38.   initstack(&opst);
  39.   push(&opst,'\0');
  40.   i=j=0;
  41.   while (e[i]!='\0')
  42.    { if ((e[i]>='0' && e[i]<='9') || e[i]=='.')
  43.            f[j++]=e[i];                     /*数字*/
  44.       else if (e[i]=='(')                /*左括号*/
  45.                push(&opst,e[i]);
  46.            else if (e[i]==')')           /*右括号*/
  47.               { while (stacktop(&opst)!='(')
  48.                         f[j++]=pop(&opst);
  49.                   pop(&opst);            /*'('出栈*/
  50.                }
  51.            else if (is_op(e[i]))         /* '+ ,-, *, /' */
  52.                   {f[j++]=' ';           /*用空格分开两个操作数*/
  53.                    while (priority(stacktop(&opst))>=priority(e[i]))
  54.                        f[j++]=pop(&opst);
  56.                    push(&opst,e[i]);     /*当前元进栈*/
  57.                    }
  58.        i++;  /*处理下一元*/
  59.     }
  61.     while (!stackempty(&opst))
  62.         f[j++]=pop(&opst);
  63.     f[j]='\0';
  64.   }
  65. /****************************************/
  66. /*    将数字字符串转变成数值            */
  67. /****************************************/
  68. float readnumber(char f[],int *i)
  69.   {float x=0.0;
  70.    int k=0;
  71.    while (f[*i]>='0' && f[*i]<='9') /*处理整数部分*/
  72.    {
  73.        x=x*10+(f[*i]-'0');
  74.         (*i)++;
  75.    }
  76.    if (f[*i]=='.') /*处理小数部分*/
  77.        {  (*i)++;
  78.             while (f[*i]>='0' && f[*i]<='9')
  79.                     {   x=x*10+(f[*i]-'0');
  80.                         (*i)++;
  81.                         k++;
  82.                     }
  83.       }
  84.   while (k!=0)
  85.     {       x=x/10.0;
  86.             k=k-1;
  87.     }
  88.     printf("\n*%f*",x);
  89.     return(x);
  90. }
  92. /****************************************/
  93. /*         后缀表达式求值程序           */
  94. /****************************************/
  95. double  evalpost(char f[])
  96.   {  double   obst[50]; /*操作数栈*/
  97.      int i=0,top=-1;
  98.      /*请将本函数补充完整*/
  99.     float x;
  100.     while(f[i]!='\0')
  101.     {
  102.         if(f[i]>='0'&&f[i]<='9')
  103.             obst[++top]=readnumber(f,&i);
  104.         else if(f[i]==' ')
  105.             i++;
  106.         else if(f[i]=='+')
  107.         {
  108.             x=obst[top--];
  109.             obst[top]=x+obst[top];
  110.             i++;
  111.         }
  112.         else if(f[i]=='-')
  113.         {
  114.             x=obst[top--];
  115.             obst[top]=x-obst[top];
  116.             i++;
  117.         }
  118.         else if(f[i]=='*')
  119.         {
  120.             x=obst[top--];
  121.             obst[top]=x*obst[top];
  122.             i++;
  123.         }
  124.         else if(f[i]=='/')
  125.         {
  126.             x=obst[top--];
  127.             obst[top]=x/obst[top];
  128.             i++;
  129.         }
  130.     }
  131.     return obst[top];
  132.   }
  135. /*
  136. 主程序：输入中缀表达式，经转换后输出后缀表达式
  137. */
  138. int main()
  139.  {
  140.         char e[50],f[50];
  141.         int i,j;
  142.         printf("\n\n请输入中缀表达式:\n");
  143.         gets(e);
  144.         postfix(e,f);
  145.         i=0;
  146.         printf("\n\n对应的后缀表达式为: [");
  147.         while (f[i]!='\0')
  148.                 printf("%c",f[i++]);
  149.         printf("]");
  150.         printf("\n\n计算结果为 :");
  151.         printf("\n\n%f",evalpost(f));
  152.         return 0;
  153. }

  1. /*
  2. 已知字符串采用带结点的链式存储结构（详见linksrting.h文件），
  3. 请编写函数linkstring substring(linkstring s,int i,int len)，
  4. 在字符串s中从第i个位置起取长度为len的子串，函数返回子串链表。
  5. */
  7. #include "linkstring.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. linkstring substring(linkstring  s, int i, int len)
  10. {
  11.     linkstring head,pos=s->next,makenode,newlist;
  12.     int cnt=0;
  13.     head=(linkstring)malloc(sizeof(linknode));
  14.     head->next=NULL;
  15.     newlist=head;
  16.     while(pos)
  17.     {
  18.         if(cnt>=i&&cnt<=i+len-1)
  19.         {
  20.             makenode=(linkstring)malloc(sizeof(linknode));
  21.             makenode->data=pos->data,makenode->next=NULL;
  22.             newlist->next=makenode;
  23.             newlist=makenode;
  24.         }
  25.         if(cnt>=i+len)
  26.             break;
  27.         cnt++;
  28.         pos=pos->next;
  29.     }
  30.     return head;
  32. }
  33. int main()
  34. {   linkstring str1,str2;
  35.     str1=creat();                  /*建字符串链表*/
  36.     print(str1);
  37.     str2=substring(str1,3,5);    /*测试，从第3个位置开始取长度为5的子串,请自行构造不同测试用例*/
  38.     print(str2);                   /*输出子串*/
  39.     delList(str1);
  40.     delList(str2);
  41.     return 0;
  42. }

  1. /*
  2. 字符串采用带头结点的链表存储，设计算法函数void delstring(linkstring s, int i,int len)
  3. 在字符串s中删除从第i个位置开始，长度为len的子串。
  4. */
  5. /**********************************/
  6. /*文件名称：lab4_05.c                 */
  7. /**********************************/
  8. #include "linkstring.h"
  9. /*请将本函数补充完整，并进行测试*/
  10. void delstring(linkstring  s, int i, int len)
  11. {
  12.     linkstring p,q,r;
  13.     int k=1;
  14.     p=s->next;
  15.     while(k<i&&p)     //查找待删除子串的起始位置
  16.     {
  17.         q=p;
  18.         p=p->next;
  19.         k++;
  20.     }
  21.     if(!p)              //如果s串长度小于i，则无法删除
  22.         return;
  23.     else
  24.     {
  25.         k=1;
  26.         while(k<len&&p) //从第i个位置开始查找待删除子串的终点
  27.         {
  28.             p=p->next;
  29.             k++;
  30.         }
  31.         if(!p)          //如果s串中i后面的长度小于len，则无法删除
  32.             return ;
  33.         else
  34.         {
  35.             if(!q)      //如果待删除子串位于s最前面
  36.             {
  37.                 r=s;
  38.                 s=p->next;
  39.             }
  40.             else        //子串位于中间或者后面
  41.             {
  42.                 r=q->next;
  43.                 q->next=p->next;
  44.             }
  45.             p->next=NULL; //待删除子串最后置为空
  46.             while(r)
  47.             {
  48.                 p=r;
  49.                 r=r->next;
  50.                 free(p);   //逐个释放子串中的结点
  51.             }
  52.         }
  53.     }
  54. }
  55. int main()
  56. {   linkstring str;
  57.     str=creat();            /*建字符串链表*/
  58.     print(str);
  59.     delstring(str,2,3);     /*测试，从第2个位置删除长度为3的子串,请自行构造不同的测试用例  */
  60.     print(str);               /*输出*/
  61.     delList(str);
  62.     return 0;
  63. }

  1. /*
  2. 字符串采用带头结点的链表存储，编写函数linkstring index(linkstring s, linkstring t)，
  3. 查找子串t在主串s中第一次出现的位置，若匹配不成功，则返回NULL。
  4. */
  6. #include "linkstring.h"
  7. /*请将本函数补充完整，并进行测试*/
  8. linkstring index(linkstring  s, linkstring t)
  9. {
  10.     linkstring p,s1,t1;
  11.     p=s->next;
  12.     while(p)        //p记录匹配的起点
  13.     {
  14.         s1=p;       //s1记录s比较的当前位置
  15.         t1=t->next; //s2记录t比较的当前位置
  16.         while(s1&&t1&&s1->data==t1->data)
  17.         {
  18.             s1=s1->next;
  19.             t1=t1->next;
  20.         }
  21.         if(!t1) return p;   //如果匹配成功，则返回p
  22.         p=p->next;
  23.     }
  24.     return NULL;
  25. }
  26. int main()
  27. {   linkstring s,t,p=NULL;
  28.     s=creat();                  /*建立主串链表*/
  29.     t=creat();                    /*建立子串链表*/
  30.     print(s);
  31.     print(t);
  32.     p=index(s,t);
  33.     if(p)
  34.             printf("匹配成功，首次匹配成功的位置结点值为%c\n",p->data);
  35.     else
  36.             printf("匹配不成功！\n");
  37.     delList(s);
  38.     delList(t);
  39.     return 0;
  40. }

  1. /*
  2. 利用朴素模式匹配算法，将模式t在主串s中所有出现的位置存储在带头结点的单链表中。
  3. */
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <stdlib.h>
  7. typedef struct node
  8. {        int data;
  9.         struct node *next;
  10. }linknode;
  11. typedef linknode *linklist;
  12. /*朴素模式匹配算法,返回t中s中第一次出现的位置，没找到则返回-1，请将程序补充完整*/
  13. int index(char *s,char *t)
  14. {
  15.     int m,n,i,j,k;
  16.     m=strlen(s);
  17.     n=strlen(t);
  18.     for(i=0;i<=m-n;i++)
  19.     {
  20.         k=i;
  21.         j=0;
  22.         while(j<n)
  23.         {
  24.             if(s[k]==t[j])
  25.             {
  26.                 k++;
  27.                 j++;
  28.             }
  29.             else
  30.                 break;
  31.         }
  32.         if(j==n)
  33.             return i;
  34.     }
  35.     return -1;
  36. }
  37. /*利用朴素模式匹配算法，将模式t在s中所有出现的位置存储在带头结点的单链表中,请将函数补充完整*/
  38. linklist indexall(char *s,char *t)
  39. {
  40.     linklist head,p,r;
  41.     int m,n,i,j,k;
  42.     head=(linklist)malloc(sizeof(linknode));
  43.     r=head;
  44.     m=strlen(s);
  45.     n=strlen(t);
  46.     for(i=0;i<=m-n;i++)
  47.     {
  48.         k=i;
  49.         j=0;
  50.         while(j<n)
  51.         {
  52.             if(s[k]==t[j])
  53.             {
  54.                 k++;
  55.                 j++;
  56.             }
  57.             else
  58.                 break;
  59.         }
  60.         if(j==n)
  61.         {
  62.             p=(linklist)malloc(sizeof(linknode));
  63.             p->data=i;
  64.             r->next=p;
  65.             r=p;
  66.         }
  67.     }
  68.     r->next=NULL;
  69.     return head;
  70. }
  71. /*输出带头结点的单链表*/
  72. void print(linklist head)
  73. {    linklist p;
  74.     p=head->next;
  75.     while(p)
  76.     {    printf("%5d",p->data);
  77.         p=p->next;
  78.     }
  79.     printf("\n");
  80. }
  81. int main()
  82. {    char s[80],t[80];
  83.     linklist head;
  84.     printf("请输入主串:\n");
  85.     gets(s);
  86.     printf("请输入模式串:\n");
  87.     gets(t);
  88.     int k=index(s,t);
  89.     printf("k=%d",k);
  90.     head=indexall(s,t);
  91.     printf("\n[ %s ]在[ %s ]中的位置有：\n",t,s);
  92.     print(head);
  93.     return 0;
  94. }

  1. /*
  2.   编写快速模式匹配KMP算法，请将相关函数补充完整。
  3. */
  4. #define maxsize 100
  5. typedef struct{
  6.       char str[maxsize];
  7.       int length ;
  8. } seqstring;
  9. /*求模式p的next[]值，请将函数补充完整*/
  10. void getnext(seqstring p,int next[])
  11. {
  12.     int i,j;
  13.     i=0;j=-1;
  14.     next[0]=-1;
  15.     while(i<p.length)
  16.     {
  17.         if(j==-1||p.str[i]==p.str[j])
  18.         {
  19.             ++i;
  20.             ++j;
  21.             next[i]=j;
  22.         }
  23.         else
  24.             j=next[j];
  25.     }
  26.     for(i=0;i<p.length;i++)
  27.         printf("%3d",next[i]);
  28. }
  29. /*快速模式匹配算法，请将函数补充完整*/
  30. int kmp(seqstring t,seqstring p,int next[])
  31. {
  32.     int i=0,j=0;
  33.     while(i<t.length&&j<p.length)
  34.     {
  35.         if(j==-1||t.str[i]==p.str[j])
  36.         {
  37.             i++;
  38.             j++;
  39.         }
  40.         else
  41.             j=next[j];
  42.     }
  43.     return j==p.length?i-p.length:-1;
  44. }
  45. int  main()
  46.  {   seqstring t, p;
  47.      int next[maxsize],pos;
  48.      printf("请输入主串：\n");
  49.      gets(t.str);
  50.      t.length=strlen(t.str);
  51.      printf("请输入模式串：\n");
  52.      gets(p.str);
  53.      p.length=strlen(p.str);
  54.      getnext(p,next);
  55.      pos=kmp(t,p,next);
  56.      printf("\n");
  57.      printf("%d",pos);
  58.      return 0;
  59. }



本文地址：http://liuyanzhao.com/3593.html

转载请注明

历史上的今天
十二月
05日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0