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

删除子串

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

void delstring(linkstring  s, int i, int len)
{linkstring p,q,r;int cnt = 1;p = s->next;while (cnt < i && p) { //查找起始点q = p;p = p->next;cnt++;}if (!p) {return;} else {cnt = 1;while (cnt < len && p) { //查找终点p = p->next;cnt++;}if (!p) {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);}}}
}

朴素字符串模式匹配

#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 i,k,j;int n,m;n=strlen(s);        //主串长度m=strlen(t);        //模式串长度for (i=0;i<n-m+1;i++){k=i;j=0;while (j<m){if (s[k]==t[j]) {k++;j++;}elsebreak;}if (j==m) return i;}return -1;
}

KMP算法

#define maxsize 100
typedef struct{char str[maxsize];int length ;
} seqstring;
/*求模式p的next[]值，请将函数补充完整*/
void getnext(seqstring p,int next[])
{int i = 0, j = -1;next[0] = -1;while (i < p.length) {if (j == -1 || p.str[i] == p.str[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;
}

后缀表达式求值

#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;initstack(&opst);int i = 0, j = 0;push(&opst, '\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;/*请将本函数补充完整*/double x;while (f[i] != '\0') {if (f[i] >= '0' && f[i] <= '9') {// 转为浮点数obst[++top] = readnumber(f,&i);//printf("%lf",obst[top]);} 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] = obst[top] - x;i++;} else if (f[i] == '*') {x = obst[top--];obst[top] = x * obst[top];i++;} else if (f[i] == '/') {x = obst[top--];obst[top] = obst[top] / x;i++;}}//printf("%lf",obst[top]);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;
}

附录

#include <stdlib.h>
#include <stdio.h>
typedef char datatype; 
typedef struct node
{   datatype data;struct node *next;
}linknode;
typedef linknode *linkstring;
/**********************************/
/*函数名称：creat() 			      */
/*函数功能：尾插法建立字符单链表         */
/**********************************/
linkstring creat()
{   linkstring head,r,s;datatype x;head=r=(linkstring)malloc(sizeof(linknode));head->next=NULL;printf("请输入一个字符串（以回车结束）:\n");scanf("%c",&x);while (x!='\n'){    s=(linkstring)malloc(sizeof(linknode));s->data=x;r->next=s;r=s;scanf("%c",&x);}r->next=NULL;return head;
}
/**********************************/
/*函数名称：print() 			      */
/*函数功能：输出字符串                   */
/**********************************/
void print(linkstring head)
{   linkstring p;p=head->next;printf("List is:\n");while(p){   printf("%c",p->data);p=p->next;}printf("\n");
}/*释放单链表的内容*/
void delList(linkstring head)
{linkstring p=head;while (p){head=p->next;free(p);p=head;}
}