void poplkstack(lkstack *&top,datatype *y) {
lkstack *p;
if (top==0) printf(\
else{p=top;*y=p->data; top=p->next; free(p);}
}
main( ) {
int i,x,y; lkstack *head=0;
for(i=1; i<=n; i++) {scanf(“%d”,&x); pushlkstack(head,x);} for(i=1; i<=n; i++) {poplkstack(head,&y); printf(\
}
3． 入队列和出队列操作在顺序存储结构上的实现。其中函数insertsqcyqueue的功能是实现顺序循环队列的入队列操作，函数deletesqcyqueue的功能是实现顺序循环队列的出队列操作。 #include \typedef int datatype; #define m 100
#define n 10
typedef struct {int rear,front; datatype q[m];}sqcyqueue; void insertsqcyqueue(sqcyqueue &queue, datatype x)
{
if ((queue.rear+1)%m==queue.front) printf(\ else { queue.rear=(queue.rear+1)%m;queue.q[queue.rear]=x; } }
void deletesqcyqueue(sqcyqueue &queue, datatype *y) {
if (queue.front==queue.rear) printf(\
else {queue.front=(queue.front+1)%m;*y=queue.q[queue.front]; } }
main( ) {
sqcyqueue queue; queue.front=queue.rear=0; int i,x,y;
for(i=1; i<=n; i++) {scanf(“%d”,&x); insertsqcyqueue(queue,i);} for(i=1; i<=n; i++) {deletesqcyqueue(queue,&y);printf(\
}
4． 链式队列的入队列和出队列操作。其中函数insertlkqueue的功能是完成链式队列的入队列操作，函数deletelkqueue的功能是完成链式队列的出队列操作。 #include \#include \#define n 10
typedef int datatype;
typedef struct node{datatype data; struct node *next;} lkqueue;
void insertlkqueue(lkqueue *&front,lkqueue *&rear,datatype x) {
lkqueue *p;
p=(lkqueue *) malloc(sizeof(lkqueue)); p->data=x; p->next=0;
- 6 -
if(rear==0) front=rear=p; else {rear->next=p; rear=p;} }
void deletelkqueue(lkqueue *&front,lkqueue *&rear,datatype *y) {
lkqueue *p;
if(front==0) printf(\
else { p=front; front=front->next; *y=p->data; free(p); if(front==0) rear=front; } }
main( ) {
int i,x,y; lkqueue *front=0,*rear=0;
for(i=1;i<=n;i++) {scanf(“%d”,&x); insertlkqueue(front,rear,x);} for(i=1;i<=n;i++) {deletelkqueue(front,rear,&y); printf(\}
- 7 -
实验三 字符串和数组
一、 实验目标
1． 掌握求字符串长度、插入字符串、删除字符串、求主串的子串和模式匹配等操作在顺序存储结构的实现。 2． 理解基于映射的字符串匹配算法在顺序存储结构上的实现。 3． 理解求稀疏矩阵的转置矩阵算法在三元组表上的实现。
二、 实验内容
1. 求字符串长度、插入字符串、删除字符串、求主串的子串和模式匹配等操作在顺序存储结构的实现。其中函数lenstring的功能是实现求字符串长度，函数insertstring的功能是实现在第一个字符串中第start个位置的后面插入第二个字符串，函数deletestring的功能是实现删除字符串中从第start个位置开始的count个字符，函数substring的功能是实现将第一个字符串从start位置开始的count个字符复制到第二个字符串，函数matchstring的功能是实现简单的模式匹配算法（查找子串在主串中第一次出现的位置）。 #include \#include “string.h”
#define stringmaxlen 127 long lenstring (char s[ ]) {
int n=0; char *p=s;
while(*p!=?\\0?) {p++; n++;} return(n); }
void insertstring(char s[ ],long start,char t[ ]) {
long i, len1=strlen(s), len2=strlen(t);
if (start<0 || start>len1) printf(\
else if (len1+len2>=stringmaxlen) printf(\else {
for(i=len1-1;i>=start; i--) s[i+len2]=s[i]; for(i=0;i<=len2-1; i++) s[start+i]=t[i];
s[len1+len2]=?\\0?; }
}
void deletestring(char s[ ], long start, long count) {
long i,j,length=strlen(s); char *p,*q;
if (start<1||start>length) printf(\ else if (start+count-1>length) printf(\ {
i=start+count-1; j=start-1; p=s+i; q=s+j; while (*p!='\\0'){*q=*p; q++; p++;} *q='\\0'; } }
- 8 -
void substring(char s[ ], long start, long count, char t[ ])
{
long i,j,length=strlen(s);
if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i long matchstring(char t[ ], char p[ ]) { long i,j,k ,len1=strlen(t),len2=strlen(p); for(i=0; i<=len1-len2; i++) { for(k=i, j=0;j return(0); } main( ) { char s[ ]=\ printf(\ insertstring(s,8,t); printf(\ deletestring(s,1,3); printf(\ substring(s,1,4,t); printf(\ if (matchstring(s,\else printf(\ } 2. 基于映射的字符串匹配算法在顺序存储结构上的实现。其中函数rkindex的功能是在主串t中查找出子串p的所有位置。 #define n 7 #define pp 193 #define d 3 void rkindex(char p[],char t[]) { long i,j,k=0,x,y,z; for(i=1,x=1;i<=m-1;i++) x=(x*d) % pp; for(i=0,y=0;i<=m-1;i++) y=(y*d+p[i]) % pp; for(i=0,z=0;i<=m-1;i++) z=(z*d+t[i]) % pp; for(i=0;i<=n-m;i++,k=i) { if (y==z) {for(j=0;j<=m-1;j++,k++) if (p[j]!=t[k]) break; if (j==m) printf(\ if(i } main( ){char p[]=\} - 9 - 3. 稀疏矩阵的转置矩阵算法在三元组表上的实现。其中函数translatematrix的功能是实现将稀疏矩阵a转化为 稀疏矩阵b。 #include \typedef int datatype; #define m 100 struct triple{int i; int j; datatype v;}; struct sparsematrix{int mu; int nu; int tu; struct triple data[m];}; void translatematrix(struct sparsematrix a, struct sparsematrix &b) { int p,q=0,col; b.mu=a.nu; b.nu=a.mu; b.tu=a.tu; if (b.tu!=0) for(col=0; col if (a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q=q+1;} } main( ) { int i; struct sparsematrix a={4,4,6,{{0,0,20},{0,2,8},{0,3,10},{1,2,30},{2,3,16},{3,0,-9}}},b; translatematrix(a,b); for(i=0;i - 10 -