Delete substring
The string is stored in a linked list with the leading node, and the algorithm function void delstring(linkstring s, int i, int len) is designed.
Delete the substring starting from the i-th position and having a length of len in the string s.
void delstring(linkstring s, int i, int len)
{
linkstring p,q,r;
int cnt = 1;
p = s->next;
while (cnt < i & amp; & amp; p) { //Find the starting point
q = p;
p = p->next;
cnt + + ;
}
if (!p) {
return;
} else {
cnt = 1;
while (cnt < len & amp; & amp; p) { //Find the end point
p = p->next;
cnt + + ;
}
if (!p) {
return;
} else {
if (!q) { //The substring is in front of s
r = s;
s = p->next;
} else { //The substring is in the middle and backend
r = q->next;
q->next = p->next;
}
p->next = NULL;
while (r) {
p = r;
r = r->next;
free(p);
}
}
}
}
Naive string pattern matching
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node
{ int data;
struct node *next;
}linknode;
typedef linknode *linklist;
/* Naive pattern matching algorithm, returns the position of the first occurrence of s in t, if not found, returns -1, please complete the program*/
int index(char s[],char *t)
{
int i,k,j;
int n,m;
n=strlen(s); //main string length
m=strlen(t); //Pattern string length
for (i=0;i<n-m + 1;i + + )
{
k=i;
j=0;
while (j<m)
{
if (s[k]==t[j]) {k + + ;j + + ;}
else
break;
}
if (j==m) return i;
}
return -1;
}
KMP algorithm
#define maxsize 100
typedef struct{
char str[maxsize];
int length;
} seqstring;
/*To find the next[] value of pattern p, please complete the function*/
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("=",next[i]);
}
}
/*Fast pattern matching algorithm, please complete the function*/
int kmp(seqstring t,seqstring p,int next[])
{
int i = 0, j = 0;
while (i < t.length & amp; & amp; 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;
}
Postfix expression evaluation
#include <stdio.h>
#include "stack.h" /*Introduce a custom character stack structure*/
/************************/
/* Determine whether it is an operator */
/************************/
int is_op(char op)
{
switch(op)
{ case ' + ':
case '-':
case '*':
case '/':return 1;
default:return 0;
}
}
/******************************/
/* Determine the priority of the operator */
/******************************/
int priority(char op)
{
switch(op)
{
case '(':return 0;
case ' + ':
case '-':return 1;
case '*':
case '/':return 2;
default: return -1;
}
}
/**********************************/
/*Infix expression, converted to postfix expression */
/**********************************/
void postfix(char e[],char f[])
{
seqstack opst;
initstack( & amp;opst);
int i = 0, j = 0;
push( & amp;opst, '\0');
while (e[i] != '\0') {
if ((e[i] >= '0' & amp; & amp; e[i] <= '9') || e[i] == '.') {
f[j + + ] = e[i];//number
} else if (e[i] == '(') {
push(& amp;opst, e[i]);//The left bracket is pushed onto the stack
} else if (e[i] == ')') {
while (stacktop( & amp;opst) != '(') {
f[j + + ] = pop( & amp;opst); // Pop the stack in sequence
}
pop( & amp;opst);
} else if (is_op(e[i])) {
f[j + + ] = ' '; // separated by spaces
while (priority(stacktop( & amp;opst)) >= priority(e[i])) {
f[j + + ] = pop( & amp;opst); // Priority is raised from the stack
}
push(& amp;opst, e[i]);
}
i + + ;
}
while (!stackempty( & amp;opst)) {
f[j + + ] = pop( & amp;opst);
}
f[j] = '\0';
}
/******************************************/
/* Convert numeric string into numerical value */
/******************************************/
float readnumber(char f[],int *i)
{
float x = 0.0;
int k = 0;
//integer part
while (f[*i] >= '0' & amp; & amp; f[*i] <= '9') {
x = x * 10 + (f[*i] - '0');
(*i) + + ;
}
//decimal part
if (f[*i] == '.') {
(*i) + + ;
while (f[*i] >= '0' & amp; & amp; f[*i] <= '9') {
x = x * 10 + (f[*i] - '0');
(*i) + + ;
k++;
}
}
while (k != 0) {
x = x / 10.0;
k = k - 1;
}
printf("\
*%f*",x);
return x;
}
/****************************************/
/* Postfix expression evaluator */
/****************************************/
double evalpost(char f[])
{ double obst[50]; /*operand stack*/
int i=0,top=-1;
/*Please complete this function*/
double x;
while (f[i] != '\0') {
if (f[i] >= '0' & amp; & amp; f[i] <= '9') {
// Convert to floating point number
obst[ + + top] = readnumber(f, & amp;i);
//printf("%lf",obst[top]);
} else if (f[i] == ' ') { //Skip spaces
i + + ;
} else if (f[i] == ' + ') { //Four arithmetic operations
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];
}
/*
Main program: input the infix expression and output the postfix expression after conversion
*/
int main()
{
char e[50],f[50];
int i,j;
printf("\
\
Please enter the infix expression:\
");
gets(e);
postfix(e,f);
i=0;
printf("\
\
The corresponding suffix expression is: [");
while (f[i]!='\0')
printf("%c",f[i + + ]);
printf("]");
printf("\
\
The calculation result is:");
printf("\
\
%f",evalpost(f));
return 0;
}
appendix
#include <stdlib.h>
#include <stdio.h>
typedef char datatype;
typedef struct node
{ datatype data;
struct node *next;
}linknode;
typedef linknode *linkstring;
/************************************/
/*Function name: creat() */
/*Function: Create a singly linked list of characters by tail interpolation */
/************************************/
linkstringcreat()
{ linkstring head,r,s;
datatype x;
head=r=(linkstring)malloc(sizeof(linknode));
head->next=NULL;
printf("Please enter a string (end with carriage return):\
");
scanf("%c", & amp;x);
while (x!='\
')
{ s=(linkstring)malloc(sizeof(linknode));
s->data=x;
r->next=s;
r=s;
scanf("%c", & amp;x);
}
r->next=NULL;
return head;
}
/************************************/
/*Function name: print() */
/*Function: output string */
/************************************/
void print(linkstring head)
{ linkstring p;
p=head->next;
printf("List is:\
");
while(p)
{ printf("%c",p->data);
p=p->next;
}
printf("\
");
}
/*Release the contents of the singly linked list*/
void delList(linkstring head)
{
linkstring p=head;
while (p)
{
head=p->next;
free(p);
p=head;
}
}