《数据结构——C语言描述》习题及答案-耿国华-2

}/*while()*/ return(1);

}/*StrReplace()*/

附加题:用链式结构实现定位函数。 【解答】

typedef struct Node { char data;

struct Node *next; }Node,*Lstring;

int strIndex(Lstring S, int pos, Lstring T)

/*从串S的pos序号起,串T第一次出现的位置 */ {

Node *p, *q, *Ppos; int i=0,,j=0;

if(T->next= =NULL || S->next =

=NULL) return(0);

p=S->next; q=T->next;

while(p!=NULL && jnext; j++;}

if(j!=pos) return(0); while(p!=NULL && q!=NULL) {

Ppos=p; /*Ppos

指向当前匹配的起始字符*/

if(p->data = = q->data)

{p=p->next; q=q->next;}

else /*从Ppos指向字符的下一个字符起从新匹配*/

{p=Ppos->next; q=T->head->next; i++;} }

if(q= =NULL) return(pos+i); /*匹配成功*/

else return(0); /*失败*/ }

第五章 数组和广义表

参考题 实习题

习 题

1.

假设有6行8列的二维数组A,每个元素占用6个字节,存

储器按字节编址。已知A的基地址为1000,计算: (1) 数组A共占用多少字节; (288)

(2) 数组A的最后一个元素的地址; (1282) (3) 按行存储时,元素A36的地址; (1126) (4) 按列存储时,元素A36的地址; (1192) [注意]:本章自定义数组的下标从1开始。

2. 设有三对角矩阵(aij)n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得B[k]= aij ,求: (1) 用i,j表示k的下标变换公式; (2) 用k表示i,j的下标变换公式。

i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或:

i = k/3 + 1, j = k - 2×( k/3 )

2.

假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩

阵相加的算法,另设三元组表C存放结果矩阵。 [提示]:参考P.28例、P.47例。

4.在稀疏矩阵的快速转置算法5.2中,将计算position[col]的方法稍加改动,使算法

只占用一个辅助向量空间。 [提示]:

(1) position[ k ] 中为第k列非零元素个数,k = 1, 2, …, n (2) position[ 0 ] = 1; (第1列中第一个非零元素的正确位置) (3) position[ k ] = position[ k – 1 ] + position[ k ] , k = 1,

2, …, n

(4) position[ k ] = position[ k – 1 ] , k = n, n – 1 , … ,1

5.写一个在十字链表中删除非零元素aij的算法。 [提示]:“删除”两次,释放一次。 6.画出下面广义表的两种存储结构图示: ((((a), b)), ((( ), d), (e, f)))

0 a 1 ∧ 1 1 ∧ 0 b 1 ∧ 1 ∧ 1 0 d 1 ∧ 1 ∧ 1 0 e 第一种存储结构(自底向上看) 1 1 ∧ 1 ∧ 0 f 7.求下列广义表运算的结果: (1) HEAD[((a,b),(c,d))]; (2) TAIL[((a,b),(c,d))]; (3) TAIL[HEAD[((a,b),(c,d))]];

联系客服:779662525#qq.com(#替换为@)