/*
利用顺序栈结构，编写算法函数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; } 文章来源
发表评论