实验一

/*
利用顺序栈结构，编写算法函数void Dto16(unsigned int m)实现十进制无符号整数m到十六进制数的转换功能。
*/
/**********************************/
/*文件名称：lab4_01.c                 */
/**********************************/
#include "seqstack.h"
/*请将本函数补充完整，并进行测试*/
void Dto16(int m)
{   seqstack s;			/*定义顺序栈*/init(&s);printf("十进制数%u对应的十六进制数是：",m);while (m){push(&s,m%16);//有地址，不用返回 m=m/16; }while (!empty(&s))putchar(read(&s)?pop(&s)+48:pop(&s)+55);//参考一下asc码，前面是数字，后面是字母 printf("\n");
}
int main()
{    int m;printf("请输入待转换的十进制数：\n");scanf("%u",&m);Dto16(m);return 0;
}

总结

按照十进制转十六进制带进函数里面，在读取时每一个转asc码十六进制前九个数字后六个字母

实验二

/*
利用链式栈结构，编写算法函数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;
}

总结

这里%x直接按16进制 输出了。先把每一次取的余数存起来，再将每一次的余数按十六进制输出

实验三

#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') //f(i)存的是 上面的后缀表达式 {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;
} 

总结

当程序没有结束时，将数字入栈，如果是空格，继续往下走，若是运算符，就找到倒数两个数做运算

实验四

/*
已知字符串采用带结点的链式存储结构（详见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 p,m,L,r;L=r=(linkstring)malloc(sizeof(linknode));r->next=NULL;//带结点赋空值 int t=0;p=s->next;//p指针指上去 while(p&&t<i) {p=p->next;t++;}if(!p)//注意判断没有找到起点 {printf("没有找到起点");return NULL; }t=0;while(p&&t<=i+len+1)//后面代表循环的次数 {m=(linkstring)malloc(sizeof(linknode));m->data=p->data;r->next=m;r=m;p=p->next;//p接着往下走呀！别忘了t++; }r->next=NULL;return L;
}
int main()
{   linkstring str1,str2;str1=creat();                  /*建字符串链表*/print(str1);str2=substring(str1,3,5);    /*测试，从第3个位置开始取长度为5的子串,请自行构造不同测试用例*/print(str2);                   /*输出子串*/delList(str1);delList(str2);return 0;
}

总结

找到第i个位置，将后面长度为len的通过尾插法插入新的链表。注意：判断没有找到起点的情况，

实验五

/*
字符串采用带头结点的链表存储，设计算法函数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,pre;int t=0;pre=s;p=s->next;//p指针指上去 while(p&&t<i) {pre=p;p=p->next;t++;}if(!p)//注意判断没有找到起点 {printf("没有找到起点");return NULL; }t=0;while(p&&t<=i+len)//后面代表循环的次数 {pre->next=p->next;free(p);p=pre->next;//p接着往下走呀！别忘了t++; }return s;
}
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 s1,t1,p;p=s->next;while(p){s1=p;//给他多赋值一个是因为要返回第一次出现的位置，而匹配已经走到后面了 t1=t->next;while(s1&&t1&&s1->data==t1->data){s1=s1->next;t1=t1->next;}if(t1==NULL)//子串走完 {return p;}else{ p=p->next;	} }return NULL;//若p没找到，返回空 
}
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);elseprintf("匹配不成功！\n");delList(s);delList(t);return 0;
}

总结

大循环套小循环，如果 出现主串和子串头一个数相等，那么就进入小循环，等循环结束，如果子串走完，那么直接返回第一个位置，没走完则主串往下走一个位置

实验七

/*
利用朴素模式匹配算法，将模式t在主串s中所有出现的位置存储在带头结点的单链表中。
*/
#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 m,n,i,j,k;m=strlen(s);n=strlen(t);for(i=0;i<m-n+1;i++)//这里注意长度不能越界 {k=i;j=0;while(j<n){if(s[k]==t[j]){k++;j++;}else{break;}}if(j==n)//子串长度与匹配长度相同 {return i;}}return -1;
} 
/*利用朴素模式匹配算法，将模式t在s中所有出现的位置存储在带头结点的单链表中,请将函数补充完整*/
linklist indexall(char *s,char *t)
{int m,n;int i,j,k;linklist head,r,p;head=r=(linklist)malloc(sizeof(linknode));head->next=NULL;m=strlen(s);n=strlen(t);for(i=0;i<m-n+1;i++){k=i;j=0;while(j<n){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;}}if(p==0) return -1;else{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;next[0]=-1;i=0;j=-1;while(i<p.length){if(j==-1||p.str[i]==p.str[j]){++i;++j;next[i]=j;}elsej=next[j];}for(i=0;i<p.length;i++)printf("%d",next[i]);
}
/*快速模式匹配算法，请将函数补充完整*/
int kmp(seqstring t,seqstring p,int next[])
{int i,j;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];}if (j==p.length) return (i-p.length);else return(-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;
}

总结(多看看)

linkstack.h

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int datatype;
typedef struct node
{datatype data;struct node *next;
}linknode;typedef linknode * linkstack;
/**********************************/
/*函数名称：init()		 		*/
/*函数功能：初始化空栈             */
/**********************************/
linkstack init()
{return NULL;
}
/**********************************/
/*函数名称：empty()		 	       */
/*函数功能：判断栈是否为空        */
/**********************************/
int empty(linkstack  top)
{return top?0:1;
}
/**********************************/
/*函数名称：read()	 			     */
/*函数功能：读栈顶元                    */
/**********************************/
datatype read(linkstack top)
{if (empty(top)){printf("\n栈的空的！＼n");exit(1);}elsereturn top->data;
}
/**********************************/
/*函数名称：push()	 			     */
/*函数功能：进栈                        */
/**********************************/
linkstack push(linkstack top,datatype x)
{linkstack p;p=(linkstack)malloc(sizeof(linknode));p->data=x;p->next=top;top=p;return top;
}
/**********************************/
/*函数名称：pop()	 			     */
/*函数功能：出栈                        */
/**********************************/
linkstack  pop(linkstack top)
{linkstack p;if (empty(top)){printf("\n顺序栈是空的!\n");exit(1);}p=top;top=top->next;free(p);return top;
}

linkstring.h

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

seqstack.h

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int datatype;
typedef struct
{       datatype  a[MAXSIZE];int top;
}seqstack;
/**********************************/
/*函数名称：init()		 		*/
/*函数功能：初始化空栈             */
/**********************************/
void init(seqstack *st)
{st->top=0;
}
/**********************************/
/*函数名称：empty()		 	       */
/*函数功能：判断栈是否为空        */
/**********************************/
int empty(seqstack *st)
{return st->top?0:1;
}
/**********************************/
/*函数名称：read()	 			     */
/*函数功能：读栈顶元                    */
/**********************************/
datatype read(seqstack *st)
{   if (empty(st)){  printf("\n栈的空的！＼n");exit(1);}elsereturn st->a[st->top-1];
}
/**********************************/
/*函数名称：push()	 			     */
/*函数功能：进栈                        */
/**********************************/
void push(seqstack *st,datatype x)
{   if (st->top==MAXSIZE){printf("栈满，无法进栈！\n");exit(1);}st->a[st->top]=x;st->top++;//从下往上 
}
/**********************************/
/*函数名称：pop()	 			     */
/*函数功能：出栈                        */
/**********************************/
datatype  pop(seqstack *st)
{   if (st->top==0){   printf("\n顺序栈是空的!\n");exit(1);}return st->a[--st->top];//从上往下 
}

stack.h

/*字符栈的结构定义及其操作实现*/
#define seqstacksize  100      /*栈的最大空间大小*/
typedef char datatype;
typedef struct stack {datatype  data[seqstacksize] ;  /*向量data用于存储栈数据*/int  top;                       /*栈顶指示*/
}seqstack;void initstack(seqstack *s)         /*栈初始化*/
{ s->top=-1;
}int stackempty (seqstack *s)        /*判栈空*/
{ return s->top==-1;
}
int stackfull(seqstack *s)          /*判栈满*/
{return s->top==seqstacksize-1;
}
/*进栈*/
void push(seqstack *s, datatype x){ s->data[++s->top]=x;}
/*出栈*/
datatype pop(seqstack *s)
{ return s->data[s->top--];
}
/*取栈顶元*/
datatype stacktop(seqstack *s)
{ return s->data[s->top];
}