发布时间 : 星期一 文章数据结构习题集与实验指导更新完毕开始阅读1112372ef5ec4afe04a1b0717fd5360cbb1a8d68
.
for(i=0;y!='\\n';i++) { scanf(\ if((y==')'&&head->data=='(')||(y==']'&&head->data=='[')||(y=='}'&&head->data=='{')) pop(); else if((y=='(')||(y=='[')||(y=='{')) push(y);
/*调试程序显示，y并没有被推入堆栈中。即head->data的值在Push中显示为y的值，但是出Push函数。马上变成Null。*/ else continue; } if(head->next==NULL) tag=TRUE; else tag=FALSE; }
/*总结： 由于head为全局变量，所以不应该将其再次作为函数的变量。因为C语言的函数变量是传值机制，所以在函数中对参数进行了拷贝复本，所以不能改变head的数值。*/
4.假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。
解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他两种见简答题）；
思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1； 若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。
实验三 串的应用
[实验目的]：掌握串的数据类型定义，串的存储结构； 掌握串的基本操作的实现和应用。 [实验题目]：
1、编写一个实现串的置换操作Replace(&S, T, V)的算法。 解：
int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为 V,并返回置换次数 {
for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V));
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后
.
.
n++; n++; }//if return n; }//Replace
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?
2. 写出将字符串反序的递归或递推算法，例如字符串为“abcsxw”，反序为“wxscba” 请注意递归和递推的区别！递推是由“小”到“大”递进； 递归是由“大”到“小”嵌套。 算法思路：
① 假定用单链表结构存储字符串；
if没有到尾部字符就不停调用自身函数，直至到达末尾，再从尾部返回并打印字符； 否则就打印当前字符并返回。
递归算法的一般形式： Invert(stringlistnode *p){
void p(参数表){ if(!p)return(0);
if （递归结束条件） else Invert(p->next);
可直接求解步骤； 基本项 printf(“%c”, p->data)
else p（较小的参数）； 归纳项 }
} 如果当前串长为0,则return(-1)
否则开始递归：
if 串没有到末尾，则P=P->next; 再调用invert(s); else printf(p->data); return
void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r {
StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) {
StrAssign(c,SubString(s,i,1));
StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 /这是递推算法。 }
}//String_Reverse
实验四 数组
[实验目的]：掌握数组的定义和实现，加深对数组的类型理解。 掌握数组的存储结构和访问方式。 掌握特殊矩阵的存储方法。 [实验题目]：
1 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组C存放结果矩阵。 #include
#define MAXSIZE 100 typedef struct {
.
.
int row, col; int e; }Triple;
typedef struct {
Triple data[MAXSIZE+1]; int m, n, len; }TSMatrix;
void Input(TSMatrix *pA) {
int nrow, ncol, num, elem, i;
printf(\请输入矩阵的行数、列数和非零元素个数：\ scanf(\ pA->m = nrow; pA->n = ncol; pA->len = num;
for(i = 1; i <= num; i++) {
printf(\请输入第 %d 个元素的行号、列号和元素值：\ scanf(\ pA->data[i].row = nrow; pA->data[i].col = ncol; pA->data[i].e = elem; } }
void Print(TSMatrix *pA) {
int i, j, t;
for(i = 1, t =1; i <= pA->m; i++) {
for(j = 1; j <= pA->n; j++) {
if(pA->data[t].row == i && pA->data[t].col ==j) {
printf(\ t++; } else
printf(\ }
printf(\ } }
void Add(TSMatrix *pA, TSMatrix *pB, TSMatrix *pC) {
int i, j, t;
.
.
if(pA->m != pB->m || pA->n != pB->n) {
printf(\两个矩阵的行数与列数不相等，不能相加！\\n\ return; }
pC->m = pA->m; pC->n = pA->n; i = 1; j = 1; t = 0;
while(i <= pA->len && j <= pB->len) {
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) < ((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) ) {
t++;
pC->data[t].row = pA->data[i].row; pC->data[t].col = pA->data[i].col; pC->data[t].e = pA->data[i].e; i++; } else
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) > ((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) ) {
t++;
pC->data[t].row = pB->data[j].row; pC->data[t].col = pB->data[j].col; pC->data[t].e = pB->data[j].e; j++; } else
if(pA->data[i].e + pB->data[j].e != 0) {
t++;
pC->data[t].row = pA->data[i].row; pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e + pB->data[j].e; i++; j++; } }
while(i <= pA->len) {
t++;
pC->data[t].row = pA->data[i].row;
.