清华大学课程讲义-数据结构答案5
2020-03-09 35页 doc 78KB 4阅读
is_833902
暂无简介
举报
清华大学课程讲义-数据结构答案55-1 已知A[n]为整数数组，试写出实现下列运算的递归算法：
(1) 求数组A中的最大整数。
(2) 求n个整数的和。
(3) 求n个整数的平均值。
【解答】
#include class RecurveArray { //数组类声明private: int *Elements; //数组指针 int ArraySize; //数组尺寸
int CurrentSize; ...
5-1 已知A[n]为整数数组，试写出实现下列运算的递归算法：
(1) 求数组A中的最大整数。
(2) 求n个整数的和。
(3) 求n个整数的平均值。
【解答】
#include class RecurveArray { //数组类private: int *Elements; //数组指针 int ArraySize; //数组尺寸
int CurrentSize; //当前已有数组元素个数public :
RecurveArray ( int MaxSize =10 ) :
ArraySize ( MaxSize ), Elements ( new int[MaxSize] ){ }~RecurveArray ( ) { delete [ ] Elements; }void InputArray(); //输入数组的内容int MaxKey ( int n ); //求最大值int Sum ( int n ); //求数组元素之和
float Average ( int n ); //求数组元素的平均值
};
void RecurveArray :: InputArray ( ){ //输入数组的内容
cout << "Input the number of Array: \n";
for ( int i = 0; i < ArraySize; i++ ) cin >> Elements[i];
}
int RecurveArray :: MaxKey ( int n ) { //递归求最大值
if ( n == 1 ) return Elements[0];
int temp = MaxKey ( n - 1 );
if ( Elements[n-1] > temp ) return Elements[n-1];
else return temp;
}
int RecurveArray :: Sum ( int n ) { //递归求数组之和
if ( n == 1) return Elements[0];
else return Elements[n-1] + Sum (n-1);
}
float RecurveArray :: Average ( int n ) { //递归求数组的平均值
if ( n == 1) return (float) Elements[0];
else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n;
}
int main ( int argc, char* argv [ ] ) { int size = -1;
cout << "No. of the Elements : ";
while ( size < 1 ) cin >> size;
RecurveArray ra ( size );
ra.InputArray();
cout<< "\nThe max is: " << ra.MaxKey ( ra.MaxSize ) << endl;
cout<< "\nThe sum is: " << ra.Sum ( ra.MaxSize ) << endl;
cout<< "\nthe avr is: " << ra.Average ( ra.MaxSize ) << endl;
return 0;
}
5-2 已知Ackerman函数定义如下：
(1) 根据定义，写出它的递归求解算法；
(2) 利用栈，写出它的非递归求解算法。
【解答】(1) 已知函数本身是递归定义的，所以可以用递归算法来解决：
unsigned akm ( unsigned m, unsigned n ) {
if ( m == 0 ) return n+1; // m == 0
else if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n == 0
else return akm ( m-1, akm ( m, n-1 ) ); // m > 0, n > 0
}
(2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从
结构中独立出来：
unsigned akm ( unsigned m, unsigned n ) {
unsigned v;
if ( m == 0 ) return n+1; // m == 0
if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n ==0
v = akm ( m, n-1 ) ); // m > 0, n > 0
return akm ( m-1, v );
}
计算akm(2, 1)的递归调用树如图所示：
akm(2, 1)
akm = 5
v = 3
akm = 5
akm(1, 3)
v =akm(2, 0)
v = 4
akm = 3
akm(0, 4) = 5
v = akm(1, 2)
akm(1, 1)
v = 3
akm(0, 3) = 4
v = akm(1, 1)
akm(0, 2) = 3
v =akm(1, 0)
v = 2
akm(0, 2) = 3
akm(0, 1) = 2
v = akm(1, 0)
v = 2
akm(0, 1) = 2
vm vn vm vn vm vn vm vn vm vn vm vn
用到一个栈记忆每次递归调用时的实参值，每个结点两个域{vm, vn}。对以上实例，栈的变化如下：
1 0 0 1
2 0 1 1 1 1 1 1 0 2
改akm(m-1,1) 改akm(m-1,1) v = n+1= 2 改akm(m-1,v) 改akm(m-1,v)
v = n+1 = 3
2 1 2 1 2 1 2 1 2 1 1 3
vm vn vm vn vm vn vm vn vm vn vm vn
1 1 1 1 0 2
1 0 0 1
1 2 1 2 1 2 0 3
1 3 1 3 1 3 1 3 0 4
改akm(m-1,1) v = n+1 = 2 改akm(m-1,v) 改akm(m-1,v) 改akm(m-1,v) 栈空, 返回v = 5
v = n+1 = 3 v = n+1 = 4 v = n+1 = 5
相应算法如下
#include
#include “stack.h”
#define maxSize 3500;
unsigned akm ( unsigned m, unsigned n ) {
struct node { unsigned vm, vn; }
stack st ( maxSize ); node w; unsigned v;
w.vm = m; w.vn = n; st.Push (w);
do {
while ( st.GetTop( ).vm > 0 ) { //计算akm(m-1, akm(m, n-1) )
while ( st.GetTop( ).vn > 0 ) //计算akm(m, n-1), 直到akm(m, 0)
{ w.vn--; st.Push( w ); }
w = st.GetTop( ); st.Pop( ); //计算akm(m-1, 1)
w.vm--; w.vn = 1; st.Push( w );
} //直到akm( 0, akm( 1, * ) )
w = st.GetTop(); st.Pop( ); v = w.vn++; //计算v = akm( 1, * )+1
if ( st.IsEmpty( ) == 0 ) //如果栈不空, 改栈顶为( m-1, v )
{ w = st.GetTop(); st.Pop( ); w.vm--; w.vn = v; st.Push( w ); }
} while ( st.IsEmpty( ) == 0 );
return v;
}
5-3 【背包问】设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1], w[2], …, w[n]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：）
【解答】 根据递归定义，可以写出递归的算法。
enum boolean { False, True }
boolean Knap( int s, int n ) {
if ( s == 0 ) return True;
if ( s < 0 || s > 0 && n < 1 ) return False;
if ( Knap ( s – W[n], n-1 ) == True )
{ cout << W[n] << ‘ , ’; return True; }
return Knap( s, n-1 );
}
若设w = { 0, 1, 2, 4, 8, 16, 32 }，s = 51, n = 6。则递归执行过程如下
递归
Knap(51, 6)
return True, 完成
Knap(51-32, 5)
return True, 打印32
Knap(19-16, 4)
return True, 打印16
Knap(3-8, 3)
return False
Knap(3, 3)
return True, 无动作
s = -5 < 0
return False
Knap(3-4, 4)
return False
Knap(3, 2)
return True, 无动作
s = -1 < 0
return False
Knap(3-2, 1)
return True, 打印2
Knap(1-1, 0)
return True, 打印1
s = 0
return True
5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行，…。第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提示：用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列。)
【解答】此为典型的回溯法问题。
1# 次对角线
0# 次对角线
0 1 2 3
2# 次对角线
3# 次对角线
4# 次对角线
5# 次对角线
6# 次对角线
0# 主对角线
1# 主对角线
0
1
2
3
3# 主对角线
2# 主对角线
4# 主对角线
6# 主对角线
5# 主对角线
在解决8皇后时，采用回溯法。在安放第 i 行皇后时，需要在列的方向从 1 到 n 试探( j = 1, …, n )：首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。
解题时设置 4 个数组：
col [n] ：col[i] 标识第 i 列是否安放了皇后
md[2n-1] ：md[k] 标识第 k 条主对角线是否安放了皇后
sd[2n-1] ：sd[k] 标识第 k 条次对角线是否安放了皇后
q[n] ：q[i] 记录第 i 行皇后在第几列
利用行号i和列号j计算主对角线编号k的方法是k = n+i-j-1；计算次对角线编号k的方法是k = i+j。n皇后问题解法如下：
void Queen( int i ) {
for ( int j = 1; j <= n; j++ ) {
if ( col[j] == 0 && md[n+i-j-1] == 0 && sd[i+j] == 0 ) { //第 i 行第 j 列没有攻击
col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; //在第 i 行第 j 列安放皇后
if ( i == n ) { //输出一个布局
for ( j = 0; j <= n; j++ ) cout << q[j] << ‘,’;
cout << endl;
}
else Queen ( i+1 ); //在第i+1行安放皇后
}
col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; //撤消第 i 行第 j 列的皇后
}
}
5-5 已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：
(1) 求链表中的最大整数。
(2) 求链表的结点个数。
(3) 求所有整数的平均值。
【解答】
#include //定义在头文件"RecurveList.h"中
class List;
class ListNode { //链表结点类
friend class List;
private:
int data; //结点数据
ListNode *link; //结点指针
ListNode ( const int item ) : data(item), link(NULL) { } //构造函数
};
class List { //链表类
private:
ListNode *first, current;
int Max ( ListNode *f );
int Num ( ListNode *f );
float Avg ( ListNode *f, int& n );
public:
List ( ) : first(NULL), current (NULL) { } //构造函数
~List ( ){ } //析构函数
ListNode* NewNode ( const int item ); //创建链表结点, 其值为item
void NewList ( const int retvalue ); //建立链表, 以输入retvalue结束
void PrintList ( ); //输出链表所有结点数据
int GetMax ( ) { return Max ( first ); } //求链表所有数据的最大值
int GetNum ( ) { return Num ( first ); } //求链表中数据个数
float GetAvg ( ) { return Avg ( first ); } //求链表所有数据的平均值
};
ListNode* List :: NewNode ( const int item ) { //创建新链表结点
ListNode *newnode = new ListNode (item);
return newnode;
}
void List :: NewList ( const int retvalue ) { //建立链表, 以输入retvalue结束
first = NULL; int value; ListNode *q;
cout << "Input your data:\n"; //提示
cin >> value; //输入
while ( value != retvalue ) { //输入有效
q = NewNode ( value ); //建立包含value的新结点
if ( first == NULL ) first = current = q; //空表时, 新结点成为链表第一个结点
else { current->link = q; current = q; } //非空表时, 新结点链入链尾
cin >> value; //再输入
}
current->link = NULL; //链尾封闭
}
void List :: PrintList ( ) { //输出链表
cout << "\nThe List is : \n";
ListNode *p = first;
while ( p != NULL ) { cout << p->data << ' '; p = p->link; }
cout << ‘\n’;
}
int List :: Max ( ListNode *f ) { //递归算法 : 求链表中的最大值
if ( f ->link == NULL ) return f ->data; //递归结束条件
int temp = Max ( f ->link ); //在当前结点的后继链表中求最大值
if ( f ->data > temp ) return f ->data; //如果当前结点的值还要大, 返回当前检点值
else return temp; //否则返回后继链表中的最大值
}
int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数
if ( f == NULL ) return 0; //空表, 返回0
return 1+ Num ( f ->link ); //否则, 返回后继链表结点个数加1
}
float List :: Avg ( ListNode *f , int& n ) { //递归算法 : 求链表中所有元素的平均值
if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件
{ n = 1; return ( float ) (f ->data ); }
else { float Sum = Avg ( f ->link, n ) * n; n++; return ( f ->data + Sum ) / n; }
}
#include "RecurveList.h" //定义在主文件中
int main ( int argc, char* argv[ ] ) {
List test; int finished;
cout << “输入建表结束标志数据 ：”;
cin >> finished; //输入建表结束标志数据
test.NewList ( finished ); //建立链表
test.PrintList ( ); //打印链表
cout << "\nThe Max is : " << test.GetMax ( );
cout << "\nThe Num is : " << test.GetNum ( );
cout << "\nThe Ave is : " << test.GetAve () << '\n';
printf ( "Hello World!\n" );
return 0;
}
5-6 画出下列广义表的图形表示和它们的存储表示：
(1) D(A(c), B(e), C(a, L(b, c, d)))
(2) J1(J2(J1, a, J3(J1)), J3(J1))
【解答】(1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1))
J1
J2
J3
C
B
A
D
c
b
a
e
L
a
d
c
0 J1
2
2
∧
J1
∧
A
0 B
∧
B
0 A
1 e
2
∧
2
0 D
D
1 c
2
J2
∧
1 a
2
0 J2
2
0 C
2
1 a
C
∧
∧
0 J3
J3
2
∧
0 L
1 d
1 c
1 b
L
5-7 利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：
(1) L1(apple, pear, banana, orange)
(2) L2((apple, pear), (banana, orange))
(3) L3(((apple), (pear), (banana), (orange)))
(4) L4((((apple))), ((pear)), (banana), orange)
(5) L5((((apple), pear), banana), orange)
(6) L6(apple, (pear, (banana), orange))
【解答】
(1) Head (Tail (Tail (L1) ) )
(2) Head (Head (Tail (L2) ) )
(3) Head (Head (Tail (Tail (Head (L3) ) ) ) )
(4) Head (Head (Tail (Tail (L4) ) ) )
(5) Head (Tail (Head(L5) ) )
(6) Head (Head (Tail (Head (Tail (L6) ) ) ) )
5-8 广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。
(1) 试定义该广义表的类结构；
(2) 采用递归的算法对一个非递归的广义表进行遍历。
(3) 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。
【解答】(1) 定义广义表的类结构
为了简化广义表的操作，在广义表中只包含字符型原子结点，并用除大写字母外的字符表示数据，表头结点中存放用大写字母表示的表名。这样，广义表中结点类型三种：表头结点、原子结点和子表结点。
class GenList; //GenList类的前视声明
class GenListNode { //广义表结点类定义
friend class Genlist;
private:
int mark, utype; // utype ＝0 / 1 / 2, mark是访问标记, 未访问为0
GenListNode* tlink; //指向同一层下一结点的指针
union { //联合
char listname; // utype = 0, 表头结点情形：存放表名
char atom; // utype = 1, 存放原子结点的数据
GenListNode* hlink; // utype = 2, 存放指向子表的指针
} value;
public:
GenListNode ( int tp, char info ) : mark (0), utype (tp), tlink (NULL) //表头或原子结点构造函数
{ if ( utype == 0 ) value.listname = info; else value.atom = info; }
GenListNode (GenListNode* hp ) //子表构造函数
: mark (0), utype (2), value.hlink (hp) { }
char Info ( GenListNode* elem ) //返回表元素elem的值
{ return ( utype == 0 ) ? elem->value.listname : elem->value.atom; }
};
class GenList { //广义表类定义
private:
GenListNode *first; //广义表头指针
void traverse ( GenListNode * ls ); //广义表遍历
void Remove ( GenListNode* ls ); //将以ls为表头结点的广义表结构释放
public:
Genlist ( char& value ); //构造函数, value是指定的停止建表标志数据
~GenList ( ); //析构函数
void traverse ( ); //遍历广义表
}
(2) 广义表遍历的递归算法
void GenList :: traverse ( ) { //共有函数
traverse ( first );
}
#include
void GenList :: traverse ( GenListNode * ls ) { //私有函数, 广义表的遍历算法
if ( ls != NULL ) {
ls->mark = 1;
if ( ls->utype == 0 ) cout << ls->value.listname << ‘(’; //表头结点
else if ( ls->utype == 1 ) { //原子结点
cout << ls->value.atom;
if ( ls->tlink != NULL ) cout << ‘,’;
}
else if ( ls->utype == 2 ) { //子表结点
if ( ls->value.hlink->mark == 0 ) traverse( ls->value.hlink ); //向表头搜索
else cout << ls->value.hlink->value.listname;
if ( ls->tlink != NULL ) cout << ‘,’;
}
traverse ( ls->tlink ); //向表尾搜索
}
∧
else cout << ‘)’;
}
0 0 A
0 2
0 2
∧
0 1 a
0 0 C
∧
∧
0 1 e
0 2
0 0 D
0 2
0 1 y
0 1 x
0 0 E
对上图所示的广义表进行遍历，得到的遍历结果为A(C(E(x, y), a), D(E, e) )。
(3) 利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。
#include
#include “stack.h”
void GenList :: traverse ( GenListNode *ls ) {
Stack *> st;
while ( ls != NULL ) {
ls->mark = 1;
if ( ls->utype == 2 ) { //子表结点
if ( ls->value.hlink->mark == 0 ) //该子表未访问过
{ st.Push ( ls->tlink ); ls = ls->value.hlink; } //暂存下一结点地址, 访问子表
else {
cout << ls->value.hlink->value.listname; //该子表已访问过, 仅输出表名
if ( ls->tlink != NULL ) { cout << ‘,’; ls = ls->tlink; }
}
}
else {
if ( ls->utype == 0 ) cout << ls->value.listname << ‘(’; //表头结点
else if ( ls->utype == 1 ) { //原子结点
cout << ls->value.atom;
if ( ls->tlink != NULL ) cout << ‘,’;
}
if ( ls->tlink == NULL ) { //子表访问完, 子表结束处理
cout >> ‘)’;
if ( st.IsEmpty( ) == 0 ) { //栈不空
ls = st.GetTop ( ); st.Pop ( ); //退栈
if ( ls != NULL ) cout << ‘,’;
else cout << ‘)’;
}
}
else ls = ls->tlink; //向表尾搜索
}
}
}
(4) 广义表建立操作的实现
#include
#include
#include “stack.h”
const int maxSubListNum = 20; //最大子表个数
GenList :: GenList ( char& value ) {
Stack st (maxSubListNum); //用于建表时记忆回退地址
SeqList Name (maxSubListNum); //记忆建立过的表名
SeqList Pointr (maxSubListNum); //记忆对应表头指针
GenListNode * p, q, r; Type ch; int m = 0, ad, br; //m为已建表计数, br用于对消括号
cout << “广义表停止输入标志数据value : ”; cin >> value;
cout << “开始输入广义表数据, 如A(C(E( x, y ), a ), D(E(x, y), e) )”
cin >> ch; first = q = new GenListNode ( 0, ch ); //建立整个表的表头结点
if ( ch != value ) { Name.Insert (ch, m); Pointr.Insert (q, m); m++; } //记录刚建立的表头结点
else return 1; //否则建立空表, 返回1
cin >> ch; if ( ch == ‘(’ ) st.Push ( q ); //接着应是‘(’, 进栈
cin >> ch;
while ( ch != value ) { //逐个结点加入
switch ( ch ) {
case ‘(’ : p = new GenListNode ( q ); //建立子表结点, p->hlink = q
r = st.GetTop( ); st.Pop( ); r->tlink = p; //子表结点插在前一结点r之后
st.Push( p ); st.Push( q ); //子表结点及下一表头结点进栈
break;
case ‘)’ : q->tlink = NULL; st.pop( ); //子表建成, 封闭链, 退到上层
/
本文档为【清华大学课程讲义-数据结构答案5】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
相关资料
- 管理学-周三多(第五版)管理学名词解释和简答
- 事业单位工作人员流动审批表
- 会务基本知识
- 核心素养下的小学数学计算教学设计
- 样板先行管理制度指引
- 幕墙工程监理细则
- 自-京福铁路隧道二衬技术交底
- 有你陪伴的日子
- 各品牌复印机logo
- 广西壮族自治区义务教育学校常规管理
- 秋灯琐忆 (清 蒋坦)
- 《岩石力学》的考研计算题
- 创新设计——TRIZ系统化创新教程教学课件 作者 张换高第15章 技术成熟度及其预测
- 横店影视城景区介绍-横店影视城景点PPT（经典版）
- 药品召回通知单
- 13探究电功率跟电流、电压的关系实验报告
- 了不起的盖茨比开题报告
- 内蒙古自治区公共资源交易评标评审专家劳务报酬支付标准和其他交易服务收费标准
- TSG Q7002-2019 起重机械型式试验规则
- 小学心理健康教育工作总结的小学心理健康教育工作总结
热门搜索
- 最新制造业企业最实用的薪酬制度
- 鲁东大学校考现代语言学试题A卷
- 唐明制药班组建设材料
- 建筑垃圾外包合同
- 南京工程学院《数据结构》复习资料
- 日本地名大全
- 保费缴款通知书
- 林业工作站站徽
- 个人简历封面和模板集合
- (新版)厦门市市政工程竣工验收报告
- 中班游戏观察记录
- 石油化工建设工程施工安全技术规范
- 统编版小学三年级语文上册教学计划
- 防雷产品安装记录
- 最新制造业企业最实用的薪酬制度
- 鲁东大学校考现代语言学试题A卷
- 唐明制药班组建设材料
- 建筑垃圾外包合同
- 南京工程学院《数据结构》复习资料
- 日本地名大全
- 保费缴款通知书
- 林业工作站站徽
- 个人简历封面和模板集合
- (新版)厦门市市政工程竣工验收报告
- 中班游戏观察记录
- 石油化工建设工程施工安全技术规范
- 统编版小学三年级语文上册教学计划
- 防雷产品安装记录
你可能还喜欢
- [方案]聚合物长期性能评价简介(UL746B)
- 圆通的运费模板
- 期货交易策略斯坦利克罗
- 普通话水平测试题60篇(带注音)
- 一种重力压缩空气储能系统及其工作方法
- 2019年五年级叙事作文-童年就像海边的贝壳650字
- 小学生一年级踢足球看图写话作文【五篇】
- 2020年感恩教育主题班会PPT课件
- 火力发电厂锅炉压力容器及压力管道技术监督标准
- 全国工业和信息化职业教育教学指导委员会20xx20xx年度科
- 温儒敏《中国现当代文学专题研究》笔记和典型题(含考研真题)详解(茅盾精品
- 医院资金管理相关问题探索
- 单相桥式整流滤波电路测量计算表格
- 浅谈如何让学生将知识内化于心外化于行——学习“三化？三境”教学法体会
- 十佳马赛克电影镜头露点镜头都被马了
- 学生信息管理系统面向对象分析设计
- 雅歌书查经
- 雅歌书查经
- 雅歌书查经
- 雅歌书查经
浙公网安备 33021202002483