《软件技术基础》实验指导（含答案）(3)

}

//顺序栈出栈

datatype pop(stack*s) { datatype temp; s->top--; temp=s->elements[s->top+1]; return temp; }

//判字符串是否中心对称

int symmetry(linklist*head,stack*s) { int n=length(head)/2; linklist*p=head->next; datatype x; for(int i=0;idata); p=p->next; } if(length(head)%2==1) p=p->next; while(p!=NULL){ x=pop(s); if(x==p->data) p=p->next; else return 0; } return 1; }

实验二：第2题

//循环队列入队出队的程序代码 #include #include #include

//循环队列的结构类型定义 const int m=5;

typedef int datatype; typedef struct

{ datatype sequ[m]; int rear, quelen; }qu;

void setnull(qu*);

void enqueue(qu*, datatype); datatype *dequeue(qu*);

void main() { qu *sq;

datatype x, *p;

 

11

int key;

sq=(qu*)malloc(sizeof(qu)); setnull(sq); do

{ printf( 2.Delete Queue -1.Quit: scanf( switch(key)

{ case 1: printf( enqueue(sq,x); break; case 2: p=dequeue(sq); if(p!=NULL) printf( break; case -1: exit(0); }

}while(1); }

//置空队

void setnull(qu *sq) { sq->rear=m-1; sq->quelen=0; }

//入队

void enqueue(qu *sq, datatype x)

{ if(sq->quelen==m) printf( else { sq->quelen++; sq->rear=(sq->rear+1)%m; sq->sequ[sq->rear]=x; } }

//出队

datatype *dequeue(qu *sq) { datatype *temp; if(sq->quelen==0) { printf( else { temp=(datatype*)malloc(sizeof(datatype)); sq->quelen--; *temp=sq->sequ[(sq->rear-sq->quelen+m)%m]; return (temp); } }

实验三：第1题

//模式匹配的程序代码 #include #include #include

 

12

//顺序串的结构类型定义 #define maxsize 100 typedef struct { char str[maxsize]; int len; }seqstring;

int Index(seqstring*, seqstring*);

void main() { seqstring*S,*subS; S=(seqstring*)malloc(sizeof(seqstring)); subS=(seqstring*)malloc(sizeof(seqstring)); printf(输入串： S->len=strlen(S->str); printf(输入子串： subS->len=strlen(subS->str); if(Index(S,subS)>0) printf(匹配成功！\n else printf(匹配失败！\n}

//顺序串的朴素模式匹配

int Index(seqstring*S, seqstring*T) { int i=1,j=1; //位序从1开始 while(i<=S->len&&j<=T->len) if(S->str[i-1]==T->str[j-1])

{ i++; j++; } //继续比较后面的字符 else

{ i=i-j+2; j=1; } //本趟不匹配，设置下一趟匹配的起始位序 if(j>T->len) return(i-T->len); //匹配成功 else return(-1); //匹配不成功 }

实验三：第2题

//删除子串的程序代码 #include #include #include

//顺序串的结构类型定义 #define maxsize 100 typedef struct { char str[maxsize]; int len; }seqstring;

void strPut(seqstring*);

 

13

void strDelete(seqstring*,int,int); void main() { seqstring*S; int i,m; S=(seqstring*)malloc(sizeof(seqstring)); printf(输入串： S->len=strlen(S->str); strPut(S); printf(删除的开始位置: printf(删除的字符个数: strDelete(S,i,m); strPut(S); }

//输出串

void strPut(seqstring*S) { int i; for(i=0;ilen;i++) printf( printf(}

//删除子串

void strDelete(seqstring*S,int i,int m) { char temp[maxsize]; if(i<=S->len){ strncpy(temp,S->str,i-1); strcpy(temp+i-1,S->str+i+m-1); strcpy(S->str,temp); if(i<=S->len) if(i+m-1<=S->len) S->len=S->len-m; else S->len=S->len-i+1; } }

实验四：第1题 //找马鞍点程序代码 #include #include //数组的结构类型定义 const int m=3; const int n=3; typedef struct{ int A[m+1][n+1]; int max[m+1],min[n+1]; }array;

 

14

void minmax(array*);

void main() { array*pa=(array*)malloc(sizeof(array)); int i, j;

for (i=1;i<=m;i++) for (j=1;j<=n;j++)

scanf( minmax(pa); }

//找马鞍点

void minmax(array*p) { int i,j,have=0; for(i=1;i<=m;i++) { p->min[i]=p->A[i][1]; for(j=2;j<=n;j++) if(p->A[i][j]min[i]) p->min[i]=p->A[i][j]; }

for (j=0;jmax[j]=p->A[1][j]; for(i=2;i<=m;i++) if(p->A[i][j]>p->max[j]) p->max[j]=p->A[i][j]; }

for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(p->min[i]==p->max[j]) { printf( have=1; }

if(!have) printf(矩阵中没有马鞍点！\n}

实验四：第2题

//对称矩阵相乘的程序代码 #include #include

//数组结构类型的定义.h const int n=3;

const int size=n*(n+1)/2; typedef int datatype; typedef struct{ datatype A[size],B[size],C[n][n]; }array;

 

15