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

 
  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. }
  26. int main()
  27. {
  28.         unsigned int m;
  29.         printf("请输入待转换的十进制数:\n");
  30.         scanf("%u",&m);
  31.         Dto16(m);
  32.         return 0;
  33. }
 
  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.         defaultreturn -1;
  29.         }
  30.   }
  31. /*********************************/
  32. /*中缀表达式,转换为后缀表达式   */
  33. /*********************************/
  34. void postfix(char e[],char f[])
  35.  {seqstack opst;
  36.   int i,j;
  37.   initstack(&opst);
  38.   push(&opst,'\0');
  39.   i=j=0;
  40.   while (e[i]!='\0')
  41.    { if ((e[i]>='0' && e[i]<='9') || e[i]=='.')
  42.            f[j++]=e[i];                     /*数字*/
  43.       else if (e[i]=='(')                /*左括号*/
  44.                push(&opst,e[i]);
  45.            else if (e[i]==')')           /*右括号*/
  46.               { while (stacktop(&opst)!='(')
  47.                         f[j++]=pop(&opst);
  48.                   pop(&opst);            /*'('出栈*/
  49.                }
  50.            else if (is_op(e[i]))         /* '+ ,-, *, /' */
  51.                   {f[j++]=' ';           /*用空格分开两个操作数*/
  52.                    while (priority(stacktop(&opst))>=priority(e[i]))
  53.                        f[j++]=pop(&opst);
  54.                    push(&opst,e[i]);     /*当前元进栈*/
  55.                    }
  56.        i++;  /*处理下一元*/
  57.     }
  58.     while (!stackempty(&opst))
  59.         f[j++]=pop(&opst);
  60.     f[j]='\0';
  61.   }
  62. /****************************************/
  63. /*    将数字字符串转变成数值            */
  64. /****************************************/
  65. float readnumber(char f[],int *i)
  66.   {float x=0.0;
  67.    int k=0;
  68.    while (f[*i]>='0' && f[*i]<='9') /*处理整数部分*/
  69.    {
  70.        x=x*10+(f[*i]-'0');
  71.         (*i)++;
  72.    }
  73.    if (f[*i]=='.'/*处理小数部分*/
  74.        {  (*i)++;
  75.             while (f[*i]>='0' && f[*i]<='9')
  76.                     {   x=x*10+(f[*i]-'0');
  77.                         (*i)++;
  78.                         k++;
  79.                     }
  80.       }
  81.   while (k!=0)
  82.     {       x=x/10.0;
  83.             k=k-1;
  84.     }
  85.     printf("\n*%f*",x);
  86.     return(x);
  87. }
  88. /****************************************/
  89. /*         后缀表达式求值程序           */
  90. /****************************************/
  91. double  evalpost(char f[])
  92.   {  double   obst[50]; /*操作数栈*/
  93.      int i=0,top=-1;
  94.      /*请将本函数补充完整*/
  95.     float x;
  96.     while(f[i]!='\0')
  97.     {
  98.         if(f[i]>='0'&&f[i]<='9')
  99.             obst[++top]=readnumber(f,&i);
  100.         else if(f[i]==' ')
  101.             i++;
  102.         else if(f[i]=='+')
  103.         {
  104.             x=obst[top--];
  105.             obst[top]=x+obst[top];
  106.             i++;
  107.         }
  108.         else if(f[i]=='-')
  109.         {
  110.             x=obst[top--];
  111.             obst[top]=x-obst[top];
  112.             i++;
  113.         }
  114.         else if(f[i]=='*')
  115.         {
  116.             x=obst[top--];
  117.             obst[top]=x*obst[top];
  118.             i++;
  119.         }
  120.         else if(f[i]=='/')
  121.         {
  122.             x=obst[top--];
  123.             obst[top]=x/obst[top];
  124.             i++;
  125.         }
  126.     }
  127.     return obst[top];
  128.   }
  129. /*
  130. 主程序:输入中缀表达式,经转换后输出后缀表达式
  131. */
  132. int main()
  133.  {
  134.         char e[50],f[50];
  135.         int i,j;
  136.         printf("\n\n请输入中缀表达式:\n");
  137.         gets(e);
  138.         postfix(e,f);
  139.         i=0;
  140.         printf("\n\n对应的后缀表达式为: [");
  141.         while (f[i]!='\0')
  142.                 printf("%c",f[i++]);
  143.         printf("]");
  144.         printf("\n\n计算结果为 :");
  145.         printf("\n\n%f",evalpost(f));
  146.         return 0;
  147. }
 
  1. /*
  2. 已知字符串采用带结点的链式存储结构(详见linksrting.h文件),
  3. 请编写函数linkstring substring(linkstring s,int i,int len),
  4. 在字符串s中从第i个位置起取长度为len的子串,函数返回子串链表。
  5. */
  6. #include "linkstring.h"
  7. /*请将本函数补充完整,并进行测试*/
  8. linkstring substring(linkstring  s, int i, int len)
  9. {
  10.     linkstring head,pos=s->next,makenode,newlist;
  11.     int cnt=0;
  12.     head=(linkstring)malloc(sizeof(linknode));
  13.     head->next=NULL;
  14.     newlist=head;
  15.     while(pos)
  16.     {
  17.         if(cnt>=i&&cnt<=i+len-1)
  18.         {
  19.             makenode=(linkstring)malloc(sizeof(linknode));
  20.             makenode->data=pos->data,makenode->next=NULL;
  21.             newlist->next=makenode;
  22.             newlist=makenode;
  23.         }
  24.         if(cnt>=i+len)
  25.             break;
  26.         cnt++;
  27.         pos=pos->next;
  28.     }
  29.     return head;
  30. }
  31. int main()
  32. {   linkstring str1,str2;
  33.     str1=creat();                  /*建字符串链表*/
  34.     print(str1);
  35.     str2=substring(str1,3,5);    /*测试,从第3个位置开始取长度为5的子串,请自行构造不同测试用例*/
  36.     print(str2);                   /*输出子串*/
  37.     delList(str1);
  38.     delList(str2);
  39.     return 0;
  40. }
 
  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. */
  5. #include "linkstring.h"
  6. /*请将本函数补充完整,并进行测试*/
  7. linkstring index(linkstring  s, linkstring t)
  8. {
  9.     linkstring p,s1,t1;
  10.     p=s->next;
  11.     while(p)        //p记录匹配的起点
  12.     {
  13.         s1=p;       //s1记录s比较的当前位置
  14.         t1=t->next; //s2记录t比较的当前位置
  15.         while(s1&&t1&&s1->data==t1->data)
  16.         {
  17.             s1=s1->next;
  18.             t1=t1->next;
  19.         }
  20.         if(!t1) return p;   //如果匹配成功,则返回p
  21.         p=p->next;
  22.     }
  23.     return NULL;
  24. }
  25. int main()
  26. {   linkstring s,t,p=NULL;
  27.     s=creat();                  /*建立主串链表*/
  28.     t=creat();                    /*建立子串链表*/
  29.     print(s);
  30.     print(t);
  31.     p=index(s,t);
  32.     if(p)
  33.             printf("匹配成功,首次匹配成功的位置结点值为%c\n",p->data);
  34.     else
  35.             printf("匹配不成功!\n");
  36.     delList(s);
  37.     delList(t);
  38.     return 0;
  39. }
 
  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 转载请注明  

发表评论

目前评论:1