北邮算法与数据结构习题参考答案

. . . .

作业参考答案

一、（带头结点）多项式乘法 C = A×B：

void PolyAdd ( list &C, list R) // R 为单个结点 {

p=C;

while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->expexp))

{ R->next=p->next; p->next=R; } else { p->next->inf += R->inf; delete R; if ( ! p->next->inf )

{ R=p->next; p->next=R->next; delete R; } } }

void PolyMul ( list A, list B, list &C ) {

C=new struct node; C->next=NULL; q=B->next; While ( q ) {

p=A->next; while ( p ) {

r = new struct node; r->exp = p->exp + q->exp; r->inf = p-> inf * q->inf; PolyAdd(C, r); p=p->next; }

q=q->next; } }

二、梵塔的移动次数：

已知移动次数迭代公式为： M ( n ) = 2M ( n-1 ) + 1 初值为： M ( 0 ) = 0

则： M ( n ) = 2 ( 2M ( n-2 ) + 1 ) + 1 = 4M ( n-2 ) + 3

. . . . .

. . . .

= 8M ( n-3 ) + 7

= 2iM ( n-i ) + 2i – 1

若n=i , 则M ( n-n ) = 0, 故：M ( n ) = 2nM ( n-n ) + 2n – 1 = 2n – 1 所以，梵塔的移动次数为2n – 1次。

三、简化的背包问题：

void Pack ( int m, int i, int t ) // 初始值为: 1 1 t {

for ( k=i; k<=n; k++ ) {

solution[m] = weight[k]; if ( t == weight[k] ) {

for ( j=1; j<=m; j++ ) cout<

} else if ( t > weight[k] ) Pack ( m+1, k+1, t - weight[k] ); } }

四、判断括号是否配对：

int Correct ( string s ) {

Inistack(Q);

for ( i=0; s[i] == ‘=’; i++ ) // 表达式以‘=’结束 {

switch ( s[i] ) {

case ‘(’: case ‘[’: case ‘{’:

Push ( Q, s[ i ] ); break; case ‘)’: case ‘]’: case ‘}’:

. . . . .

. . . .

if ( Empty(Q)) return 0; t=Pop(Q); if ( ! Matching( t, s[i] )) return 0; }

}

if ( ! Empty(Q) ) return 0; return 1; }

五、堆栈可能的输出：

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

六、用两个堆栈实现一个队列：

int FullQ ( ) {

if (Full (S1) && ! Empty (S2)) return 1; return 0; }

int EmptyQ ( ) {

if ( Empty (S1) && Empty (S2)) return 1; return 0; }

void Enqueue ( elemtype x) {

if (Full(S1)) if (Empty(S2)) while (! Empty (S1)) Push(S2, Pop(S1));

if (! Full(S1)) Push(S1, x); }

elemtype Dequeue ( ) {

if (Empty(S2)) while (! Empty(S1)) Push(S2, Pop(S1)); if (! Empty(S2)) return Pop(S2);

. . . . .

. . . .

}

七、生成新串及字符第一次出现位置：

int Index ( string S, string T ) {

for ( i=1; i + Len(T)-1<=Len(S); i++ )

if Equal ( Sub ( S, I, Len (T)), T ) return i; return 0; }

void CreatNewStr ( string S, string T, string R, arrant P) {

R=“”; j=0;

for ( i=1; i<=Len(S); i++ ) {

ch=Sub( S, i, 1 );

if ( ! Index(T, ch) && ! Index(R, ch) ) { R=Concat(R, ch); P[j++]=i; } } }

八、块链字符串插入：

{为避免字符串部块间大量的数据移动，最好的方法是定义两种

字符串中不出现的字符作为空标记和串结束标记，如 ‘#’和 ‘$’；

也可只使用空标记，串结束以块尾指针为空表示，其算法如下： void Insert ( string S, string T, char ch) // 设块大小为m {

i=0; p=T;

while ((p->next) && (! i)) {

for ( j=1; j<=m; j++ ) if (p->str[j]==ch) i=j; if (! i) p=p->next; }

. . . . .

. . . .

if (! i) for ( j=1; j<=m; j++ ) if (p->str[j]==ch) i=j;

if (! i) p->next=S; else // S插在T后

{ // ch所在结点分裂，S插在T中分裂的两结点间

q= new struct node; q->str=p->str; q->next=p->next; for ( j=i; j<=m; j++ ) p->str[j]= ‘#’; p->next=S;

for ( j=1; jstr[j]= ‘#’; p=S; while ( p->next ) p=p->next; p->next=q; } }

九、上三角矩阵的存储：

k= (i-1)*n+j-i*(i-1)/2=(2n-i+1)*i/2+j-n f1=(2n-i+1)*i/2 f2=j c=-n

十、循环右移k位：

1 2 3 4 5 6 7 8 （n=8, k=3） 6 7 8 1 2 3 4 5 8 7 6 5 4 3 2 1

void Exch ( arrtype A, int st, int ed ) {

for ( i=st; i<=(st+ed) / 2; i++ ) A[i]←→A[ed-i+1]; }

void Shift ( arrtype A, int k, int n ) {

Exch(A, 1, n); Exch(A, 1, k); Exch(A, k+1, n) }

. . . . .