数据结构-实验四（栈与字符串)
1.利用顺序栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
#include "seqstack.h"
/*请将本函数补充完整，并进行测试*/
void Dto16(int m)
{ seqstack s; /*定义顺序栈*/
init(&s);
printf("十进制数%u对应的十六进制数是：",m);
while (m)
{
push(&s,m%16);
m/=16;
}
while (!empty(&s))
putchar( read(&s)<10? pop(&s)+48: pop(&s)+55 );
printf("\n");
}
int main()
{ int m;
printf("请输入待转换的十进制数：\n");
scanf("%u",&m);
Dto16(m);
return 0;
}
2.利用链式栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
#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;
}
3.判断是否为运算符，判断运算符的优先级 ，缀表达式，转换为后缀表达式，将数字字符串转变成数值 ， 后缀表达式求值程序。
#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;
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;
/*请将本函数补充完整*/
double 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]=obst[top]-x;
i++;
}
else if (f[i]=='*')
{ x=obst[top--];
obst[top]=obst[top]*x;
i++;
}
else if (f[i]=='/')
{ x=obst[top--];
obst[top]=obst[top]/x;
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;
}
4.已知字符串采用带结点的链式存储结构（详见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,r,q,p;
int k=1;
head=r=(linkstring)malloc(sizeof(linknode));
r->next=NULL;
p=s->next;
while (p && k<i) //找子串起点
{
p=p->next;
k++;
}
if (!p) return head; //起点超过链表长度
else
{
k=1;
while (p && k<=len) //生成子串链表
{
q=(linkstring)malloc(sizeof(linknode));
q->data=p->data;
r->next=q;
r=q;
p=p->next;
k++;
}
r->next=NULL;
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;
}