/*

利用顺序栈结构,编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。

*/

/**********************************/

/*文件名称:lab4_01.c */

/**********************************/

#include "seqstack.h"

/*请将本函数补充完整,并进行测试*/

void Dto16(int m)

{ seqstack s; /*定义顺序栈*/

init(&s);

printf("十进制数%u对应的十六进制数是:",m); //%d 输出有符号十进制数 %u 输出无符号十进制数

while (m)

{

push(&s,m%16);

m=m/16;

}

while (!empty(&s))

printf("%x",pop(&s));

printf("\n");

}

int main()

{ int m;

printf("请输入待转换的十进制数:\n");

scanf("%u",&m);

Dto16(m);

return 0;

}

/*

利用链式栈结构,编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。

*/

/**********************************/

/*文件名称:lab4_02.c */

/**********************************/

#include "linkstack.h"

/*请将本函数补充完整,并进行测试*/

void Dto16(unsigned int m)

{

linkstack s;

s=init();

printf("十进制数%u对应的十六进制数是:",m);

while (m)

{

s=push(s,m%16);

m/=16;

}

while (!empty(s))

{

printf("%x",read(s));

s=pop(s);

}

printf("\n");

}

int main()

{

unsigned int m;

printf("请输入待转换的十进制数:\n");

scanf("%u",&m);

Dto16(m);

return 0;

}

#include

#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;

int i,j;

initstack(&opst);

push(&opst,'\0');

i=j=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;

/*请将本函数补充完整*/

float x;

while(f[i]!='\0')

{

if(f[i]>='0'&&f[i]<='9')

obst[++top]=readnumber(f,&i);

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]=x-obst[top];

i++;

}

else if(f[i]=='*')

{

x=obst[top--];

obst[top]=x*obst[top];

i++;

}

else if(f[i]=='/')

{

x=obst[top--];

obst[top]=x/obst[top];

i++;

}

}

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;

}

/*

已知字符串采用带结点的链式存储结构(详见linksrting.h文件),

请编写函数linkstring substring(linkstring s,int i,int len),

在字符串s中从第i个位置起取长度为len的子串,函数返回子串链表。

*/

#include "linkstring.h"

/*请将本函数补充完整,并进行测试*/

linkstring substring(linkstring s, int i, int len)

{

linkstring head,pos=s->next,makenode,newlist;

int cnt=0;

head=(linkstring)malloc(sizeof(linknode));

head->next=NULL;

newlist=head;

while(pos)

{

if(cnt>=i&&cnt<=i+len-1)

{

makenode=(linkstring)malloc(sizeof(linknode));

makenode->data=pos->data,makenode->next=NULL;

newlist->next=makenode;

newlist=makenode;

}

if(cnt>=i+len)

break;

cnt++;

pos=pos->next;

}

return head;

}

int main()

{ linkstring str1,str2;

str1=creat(); /*建字符串链表*/

print(str1);

str2=substring(str1,3,5); /*测试,从第3个位置开始取长度为5的子串,请自行构造不同测试用例*/

print(str2); /*输出子串*/

delList(str1);

delList(str2);

return 0;

}

/*

字符串采用带头结点的链表存储,设计算法函数void delstring(linkstring s, int i,int len)

在字符串s中删除从第i个位置开始,长度为len的子串。

*/

/**********************************/

/*文件名称:lab4_05.c */

/**********************************/

#include "linkstring.h"

/*请将本函数补充完整,并进行测试*/

void delstring(linkstring s, int i, int len)

{

linkstring p,q,r;

int k=1;

p=s->next;

while(k

{

q=p;

p=p->next;

k++;

}

if(!p) //如果s串长度小于i,则无法删除

return;

else

{

k=1;

while(k

{

p=p->next;

k++;

}

if(!p) //如果s串中i后面的长度小于len,则无法删除

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); //逐个释放子串中的结点

}

}

}

}

int main()

{ linkstring str;

str=creat(); /*建字符串链表*/

print(str);

delstring(str,2,3); /*测试,从第2个位置删除长度为3的子串,请自行构造不同的测试用例 */

print(str); /*输出*/

delList(str);

return 0;

}

/*

字符串采用带头结点的链表存储,编写函数linkstring index(linkstring s, linkstring t),

查找子串t在主串s中第一次出现的位置,若匹配不成功,则返回NULL。

*/

#include "linkstring.h"

/*请将本函数补充完整,并进行测试*/

linkstring index(linkstring s, linkstring t)

{

linkstring p,s1,t1;

p=s->next;

while(p) //p记录匹配的起点

{

s1=p; //s1记录s比较的当前位置

t1=t->next; //s2记录t比较的当前位置

while(s1&&t1&&s1->data==t1->data)

{

s1=s1->next;

t1=t1->next;

}

if(!t1) return p; //如果匹配成功,则返回p

p=p->next;

}

return NULL;

}

int main()

{ linkstring s,t,p=NULL;

s=creat(); /*建立主串链表*/

t=creat(); /*建立子串链表*/

print(s);

print(t);

p=index(s,t);

if(p)

printf("匹配成功,首次匹配成功的位置结点值为%c\n",p->data);

else

printf("匹配不成功!\n");

delList(s);

delList(t);

return 0;

}

/*

利用朴素模式匹配算法,将模式t在主串s中所有出现的位置存储在带头结点的单链表中。

*/

#include

#include

#include

typedef struct node

{ int data;

struct node *next;

}linknode;

typedef linknode *linklist;

/*朴素模式匹配算法,返回t中s中第一次出现的位置,没找到则返回-1,请将程序补充完整*/

int index(char *s,char *t)

{

int m,n,i,j,k;

m=strlen(s);

n=strlen(t);

for(i=0;i<=m-n;i++)

{

k=i;

j=0;

while(j

{

if(s[k]==t[j])

{

k++;

j++;

}

else

break;

}

if(j==n)

return i;

}

return -1;

}

/*利用朴素模式匹配算法,将模式t在s中所有出现的位置存储在带头结点的单链表中,请将函数补充完整*/

linklist indexall(char *s,char *t)

{

linklist head,p,r;

int m,n,i,j,k;

head=(linklist)malloc(sizeof(linknode));

r=head;

m=strlen(s);

n=strlen(t);

for(i=0;i<=m-n;i++)

{

k=i;

j=0;

while(j

{

if(s[k]==t[j])

{

k++;

j++;

}

else

break;

}

if(j==n)

{

p=(linklist)malloc(sizeof(linknode));

p->data=i;

r->next=p;

r=p;

}

}

r->next=NULL;

return head;

}

/*输出带头结点的单链表*/

void print(linklist head)

{ linklist p;

p=head->next;

while(p)

{ printf("%5d",p->data);

p=p->next;

}

printf("\n");

}

int main()

{ char s[80],t[80];

linklist head;

printf("请输入主串:\n");

gets(s);

printf("请输入模式串:\n");

gets(t);

int k=index(s,t);

printf("k=%d",k);

head=indexall(s,t);

printf("\n[ %s ]在[ %s ]中的位置有:\n",t,s);

print(head);

return 0;

}

/*

编写快速模式匹配KMP算法,请将相关函数补充完整。

*/

#define maxsize 100

typedef struct{

char str[maxsize];

int length ;

} seqstring;

/*求模式p的next[]值,请将函数补充完整*/

void getnext(seqstring p,int next[])

{

int i,j;

i=0;j=-1;

next[0]=-1;

while(i

{

if(j==-1||p.str[i]==p.str[j])

{

++i;

++j;

next[i]=j;

}

else

j=next[j];

}

for(i=0;i

printf("%3d",next[i]);

}

/*快速模式匹配算法,请将函数补充完整*/

int kmp(seqstring t,seqstring p,int next[])

{

int i=0,j=0;

while(i

{

if(j==-1||t.str[i]==p.str[j])

{

i++;

j++;

}

else

j=next[j];

}

return j==p.length?i-p.length:-1;

}

int main()

{ seqstring t, p;

int next[maxsize],pos;

printf("请输入主串:\n");

gets(t.str);

t.length=strlen(t.str);

printf("请输入模式串:\n");

gets(p.str);

p.length=strlen(p.str);

getnext(p,next);

pos=kmp(t,p,next);

printf("\n");

printf("%d",pos);

return 0;

}

 

文章来源

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。