三、实习题
1. 写一个程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M 向N 进制（2或8或16）的转换。 （1）采用顺序存储结构实现栈。
（2）采用链表结构实现栈。
2. 阿克曼函数（Ackermann?s function）定义如下：
akm(m,n)=
n+1 当 m=0 时 akm(m-1,1) 当 m>0,n=0 时 akm(m-1,akm(m,n-1)) 当 m>0,n>0 时
人们之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。 （1）设计运用递归算法的源程序，上机运行。
（2）写一个非递归算法的源程序，上机运行。并进行比较。
3．二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。
1
1 1 1 2 1 1 3 3 1
31
实习四 串
一、实习目的
1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。
2. 熟悉C语言的字符和把字符串处理的原理和方法。下面简单介绍C相关知识： (1) 字符：
char ch; ch是单个字符变量 ch=?a?; ?a? 是字符常量 (2）字符串：
Char s1[10],*s2,s3[2][10];
S1 是一维字符数组，也称它是字符串变量；
S2 是指向字符的指针变量，可以给它分配一批单元存放字符，也称为串； S2=(char )malloc(sizeof(char)*10);
S3 是2行10列的二维字符数组，一般看做含有2个字符串的数组s3[0],s3[1]，每个串最多容10个字符；
下列赋值语句是错误的：
S1= “abcdefghi” ； 应该使用串拷贝函数：
strcpy(S1, “abcdefghi”); strcoy( S2, ”abcdefghi”);
strcpy(S3[0], ”123456789”); strcpy(S3[1], ”jklmnopqr”) ;
用双引号括起来的是字符串常量，在处理字符串常量时，注意总是有一个字符‘\\0’作为字符串常量的结尾 。”123456789”存入S3[0]要占用10个位置，而不是9个。S3[0][0]里是1，……，s3[0][8]里是9,s3[0][9]里是?\\0?（串尾标志）。 (3)常见的字符函数：
int strlen(streing)
string 可以是串变量或常量， 函数结果是串长度（不含‘\\0’）。
strcpy( str ,str2 );
str是串变量，str2可以是串变量或常量。函数的作用是将str2的串拷贝给串变量str。
int strcmp( str1 ,str2 );
str1，str2可以是串变量或常量，函数的作用是将两个串进行比较， 当 str1==str2，函数结果=0； 当 str1>str2， 函数结果>0； 当 str1 str1，str2可以是串变量或常量，函数的作用是将两个串进行连接，函数结果是连接后的新串。 二、实例 32 实现字符串置换操作。 #include int index(char *s, char *t,int pos); void replace(char *s,char *t,char *v); /* 主函数 */ main() { int k; char *s,t[]=\ s=(char *)malloc(100*sizeof(char)); printf(\ printf(\ replace(s,t,v); /* 调用串置换函数 */ printf(\} /* main */ /* 串的置换，将主串s中的t串，置换为v串 */ void replace(char *s,char *t,char *v) { int i,j,k,po,sl,tl; sl=strlen(s); tl=strlen(t); printf(\ po=0; while( po< sl-tl+1) { k=index(s,t,po); /* 调用串匹配函数 */ printf(\ i=k-1; for(j=0;j<=tl-1;j++) { s[i]=v[j];i++;} po=k+tl; printf(\ } } /* replace */ /* 串匹配函数 */ /* 从主串s的第pos个字符开始查找子串t，函数结果是子串t在主串s的pos开始之后首次出现的位置 */ int index(char *s, char *t, int pos) {int i,j,sl,tl; i=pos; j=1; sl=strlen(s); tl=strlen(t); while(i<=sl && j<=tl) if(s[i-1]==t[j-1]) {i++; j++; } else { i=i-j+1+1; j=1;} 33 if(j>tl) return(i-tl); else return(-1); } /* index */ 三、实习题 1. 将上述实例打入计算机，调试运行。 字符串常量的提供有多种手段。可以在定义串类型同时初始化串值： char t[]=\ 还可以使用语句gets(s)进行输入；也可以用scanf(\进行输入。请你试着用不同的方法修改、调试、运行程序。 2. 设计可以在主串s中第i个位置插入一个子串t的程序。 3. 设计可以在主串s中从第i个位置开始共取m个字符，求子串的程序。 实习五 数 组 一、实习目的 熟悉稀疏矩阵的“三元组表”和“十字链表”存储结构，运用它们进行矩阵简单运算处理。 二、实例 稀疏矩阵的十字链表存储与输出。 #include typedef struct OLnode {int i,j; /* 行号、列号域 */ Etype e; /* 数据域 */ struct OLnode *right,*down; /* 行向的、列向的指针域 */ } OLnode; /* 数据元素结点类型 */ typedef struct { OLnode *rh[5],*ch[5]; int mu,nu,tu; }Crosslist; /* 十字链表行、列表头 */ /* 函数声明 */ void creatMatrix(Crosslist *M); void out_M(Crosslist M); Crosslist ma; int z; /* 主函数 */ main() 34 { creatMatrix(&ma); out_M(ma); } /* main */ /* 十字链表的输出 */ void out_M(Crosslist M) { int i; OLnode *p; char ch； /* 输出矩阵的总行数、总列数、非零元素总个数 */ printf(\ for(i=1; i<=M.mu; i++) { p=M.rh[i]; /* 指向第i行 */ if(p){ printf(\ while(p){ printf(\ p=p->right; } } printf(\ } printf(“\\n 打回车键，返回。“); ch=getch(); } void creatMatrix(Crosslist *M) { int m,n,t,row,col,i,j; Etype va; OLnode *p,*q,*s; /* 输入矩阵的总行数、总列数、非零元素总个数 */ printf(\ for(i=1; i<=m;i++) M->rh[i]=NULL; for(j=1; j<=n;j++) M->ch[j]=NULL; M->mu=m; M->nu=n; M->tu=t; /* 建立成空十字链表 */ /* 以下为非零元素的逐一输入和插入 */ for(i=1;i<=M->tu;i++) { printf(\ p=(OLnode *)malloc(sizeof(OLnode)); p->i=row; p->j=col; p->e=va; /* 在第row行上链接 */ q=M->rh[row]; s=q; while(q!=NULL && q->j < col){ s=q; q=q->right;} p->right=q; if(q==M->rh[row])M->rh[row]=p; else s->right=p; /* 在第col列上链接 */ 35