• 数据结构（C语言） 实验-栈与字符串

    删除子串

    字符串采用带头结点的链表存储，设计算法函数void delstring(linkstring s, int i,int len)
    在字符串s中删除从第i个位置开始，长度为len的子串。

    1. void delstring(linkstring  s, int i, int len)
    2. {
    3.     linkstring p,q,r;
    4.     int cnt = 1;
    5.     p = s->next;
    6.     while (cnt < i && p) { //查找起始点
    7.         q = p;
    8.         p = p->next;
    9.         cnt++;
    10.     }
    11.     if (!p) {
    12.         return;
    13.     } else {
    14.         cnt = 1;
    15.         while (cnt < len && p) { //查找终点
    16.             p = p->next;
    17.             cnt++;
    18.         }
    19.         if (!p) {
    20.             return;
    21.         } else {
    22.             if (!q) { //子串在s前端
    23.                 r = s;
    24.                 s = p->next;
    25.             } else { //子串在中后端
    26.                 r = q->next;
    27.                 q->next = p->next;
    28.             }
    29.             p->next = NULL;
    30.             while (r) {
    31.                 p = r;
    32.                 r = r->next;
    33.                 free(p);
    34.             }
    35.         }
    36.     }
    37. }

    朴素字符串模式匹配

    1. #include 
    2. #include 
    3. #include 
    4. typedef struct node
    5. {		int data;
    6. 		struct node *next;
    7. }linknode;
    8. typedef linknode *linklist;
    9. /*朴素模式匹配算法,返回t中s中第一次出现的位置，没找到则返回-1，请将程序补充完整*/
    10. int index(char s[],char *t)
    11. {
    12.     int i,k,j;
    13.     int n,m;
    14. 	n=strlen(s);        //主串长度
    15. 	m=strlen(t);        //模式串长度
    16. 	for (i=0;i1;i++)
    17. 	{
    18. 		k=i;
    19. 		j=0;
    20. 		while (j
    21. 		{
    22. 			if (s[k]==t[j]) {k++;j++;}
    23. 			else
    24. 			  break;
    25. 		}
    26. 		if (j==m) return i;
    27. 	}
    28. 	return -1;
    29. }

    KMP算法

    1. #define maxsize 100
    2. typedef struct{
    3.       char str[maxsize];
    4.       int length ;
    5. } seqstring;
    6. /*求模式p的next[]值，请将函数补充完整*/
    7. void getnext(seqstring p,int next[])
    8. {
    9.     int i = 0, j = -1;
    10.     next[0] = -1;
    11.     while (i < p.length) {
    12.         if (j == -1 || p.str[i] == p.str[j]) {
    13.             next[++i] = ++j;
    14.         } else {
    15.             j = next[j];
    16.         }
    17.     }
    18.     for (i = 0; i < p.length; i++) {
    19.         printf("%3d",next[i]);
    20.     }
    21. }
    22. /*快速模式匹配算法，请将函数补充完整*/
    23. int kmp(seqstring t,seqstring p,int next[])
    24. {
    25.     int i = 0, j = 0;
    26.     while (i < t.length && j < p.length) {
    27.         if (j == -1 || t.str[i] == p.str[j]) {
    28.             i++;
    29.             j++;
    30.         } else {
    31.             j = next[j];
    32.         }
    33.     }
    34.     return j == p.length ? i - p.length : -1;
    35. }

    后缀表达式求值

    1. #include 
    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.   }
    31.  
    32. /*********************************/
    33. /*中缀表达式，转换为后缀表达式   */
    34. /*********************************/
    35. void postfix(char e[],char f[])
    36. {
    37.     seqstack opst;
    38.     initstack(&opst);
    39.     int i = 0, j = 0;
    40.     push(&opst, '\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.            }
    50.            pop(&opst);
    51.         } else if (is_op(e[i])) {
    52.             f[j++] = ' '; // 空格分开
    53.             while (priority(stacktop(&opst)) >= priority(e[i])) {
    54.                 f[j++] = pop(&opst); // 优先级高出栈
    55.             }
    56.             push(&opst, e[i]);
    57.         }
    58.         i++;
    59.     }
    60.     while (!stackempty(&opst)) {
    61.         f[j++] = pop(&opst);
    62.     }
    63.     f[j] = '\0';
    64. }
    65.  
    66. /****************************************/
    67. /*    将数字字符串转变成数值            */
    68. /****************************************/
    69. float readnumber(char f[],int *i)
    70. {
    71.     float x = 0.0;
    72.     int k = 0;
    73.     //整数部分
    74.     while (f[*i] >= '0' && f[*i] <= '9') {
    75.         x = x * 10 + (f[*i] - '0');
    76.         (*i)++;
    77.     }
    78.     //小数部分
    79.     if (f[*i] == '.') {
    80.         (*i)++;
    81.         while (f[*i] >= '0' && f[*i] <= '9') {
    82.             x = x * 10 + (f[*i] - '0');
    83.             (*i)++;
    84.             k++;
    85.         }
    86.     }
    87.     while (k != 0) {
    88.         x = x / 10.0;
    89.         k = k - 1;
    90.     }
    91.     printf("\n*%f*",x);
    92.     return x;
    93. }
    94.  
    95. /****************************************/
    96. /*         后缀表达式求值程序           */
    97. /****************************************/
    98. double  evalpost(char f[])
    99.   {  double   obst[50]; /*操作数栈*/
    100.      int i=0,top=-1;
    101.      /*请将本函数补充完整*/
    102.      double x;
    103.      while (f[i] != '\0') {
    104.         if (f[i] >= '0' && f[i] <= '9') {
    105.             // 转为浮点数
    106.             obst[++top] = readnumber(f,&i);
    107.             //printf("%lf",obst[top]);
    108.         } else if (f[i] == ' ') { //跳过空格
    109.             i++;
    110.         } else if (f[i] == '+') { //四则运算
    111.             x = obst[top--];
    112.             obst[top] = x + obst[top];
    113.             i++;
    114.         } else if (f[i] == '-') {
    115.             x = obst[top--];
    116.             obst[top] = obst[top] - x;
    117.             i++;
    118.         } else if (f[i] == '*') {
    119.             x = obst[top--];
    120.             obst[top] = x * obst[top];
    121.             i++;
    122.         } else if (f[i] == '/') {
    123.             x = obst[top--];
    124.             obst[top] = obst[top] / x;
    125.             i++;
    126.         }
    127.      }
    128.     //printf("%lf",obst[top]);
    129.     return obst[top];
    130.   }
    131.  
    132. /*
    133. 主程序：输入中缀表达式，经转换后输出后缀表达式
    134. */
    135. int main()
    136.  {
    137.         char e[50],f[50];
    138.         int i,j;
    139.         printf("\n\n请输入中缀表达式:\n");
    140.         gets(e);
    141.         postfix(e,f);
    142.         i=0;
    143.         printf("\n\n对应的后缀表达式为: [");
    144.         while (f[i]!='\0')
    145.                 printf("%c",f[i++]);
    146.         printf("]");
    147.         printf("\n\n计算结果为 :");
    148.         printf("\n\n%f",evalpost(f));
    149.         return 0;
    150. }

    附录

    1. #include 
    2. #include 
    3. typedef char datatype; 
    4. typedef struct node
    5. {   datatype data;
    6.     struct node *next;
    7. }linknode;
    8. typedef linknode *linkstring;
    9. /**********************************/
    10. /*函数名称：creat() 			      */
    11. /*函数功能：尾插法建立字符单链表         */
    12. /**********************************/
    13. linkstring creat()
    14. {   linkstring head,r,s;
    15.     datatype x;
    16.     head=r=(linkstring)malloc(sizeof(linknode));
    17.     head->next=NULL;
    18.     printf("请输入一个字符串（以回车结束）:\n");
    19.     scanf("%c",&x);
    20.     while (x!='\n')
    21.     {    s=(linkstring)malloc(sizeof(linknode));
    22.          s->data=x;
    23.          r->next=s;
    24.          r=s;
    25.          scanf("%c",&x);
    26.    }
    27.      r->next=NULL;
    28.     return head;
    29. }
    30. /**********************************/
    31. /*函数名称：print() 			      */
    32. /*函数功能：输出字符串                   */
    33. /**********************************/
    34. void print(linkstring head)
    35. {   linkstring p;
    36.     p=head->next;
    37.     printf("List is:\n");
    38.     while(p)
    39.     {   printf("%c",p->data);
    40.         p=p->next;
    41.     }
    42.     printf("\n");
    43. }
    44.  
    45. /*释放单链表的内容*/
    46. void delList(linkstring head)
    47. {
    48.   linkstring p=head;
    49.   while (p)
    50.   {
    51.     head=p->next;
    52.     free(p);
    53.     p=head;
    54.   }
    55. }

  • 相关阅读:
    APP基本测试用例
    【 java 常用类】StringBuffer 源码分析以及 StringBuffer 底层的数组扩容机制
    ESP 特权隔离机制介绍
    基于RFID技术的智能书架系统
    如何减少爬虫产生的网络负载：爬取间隔和缓存控制策略
    10min快速回顾C++语法（四）数组专题
    服务器是什么？它是用来干什么的？
    C语言堆栈计算器实现，中缀转后缀表达式运算过程
    Redis高可用之主从复制原理演进分析
    java8 Stream 常用的集合操作大全 Stream集合处理工具类整理
  • 原文地址：https://blog.csdn.net/fffffall/article/details/134337007