受限制的链表操作，新人们，来练习，200分奖励！
[SICP]中有一个练习，"反向一个list"，在Lisp中，一个list是由多个有序对构成，描述如下：
list: (1, 2, 3, 4)
为有序对
(1 (2 (3 (4, null))))
Lisp提供了有序对的三种操作，
cons(a, b), 以 a, b构造有序对(a,b)
car(t), 取得有序对t的第一个元素, car(cons(a,b)) == a
cdr(t), 取得有序对t的第二个元素, cdr(cons(a,b)) == b
列表(1,2,3,4)由
t = cons(1, cons(2, cons(3, cons(4, NULL))))
构成, car(t) == 1, cdr(t) == (2, 3, 4)。
假设，在C++中，使用如下代码完成类似Lisp的有序对：
(代码见后）
（main函数里面是一个简短的测试代码）
题目是，只使用如上car, cdr函数，完成下列函数：
1. int length(node* p); //求list的长度
2. node* append(node* p1, node* p2); //将p2附加到p1后，且符合list的定义
3. node* last_pair(node* p); //返回最后一个有序对, i.e. (1, (2, (3, null))) 返回 (3, null)
4. node* reverse(node* p); //将p反向，i.e. (1, (2, (3, null))) -> (3, (2, (1, null)))
要求，当然是代码精简，思路明确。
#include <iostream>
struct node
{
union {
int car_v;
node* car_p;
};
int type_car;
union {
int cdr_v;
node* cdr_p;
};
int type_cdr;
};
const int type_node = 1;
const int type_int = 2;
struct ret
{
union {
node* p;
int v;
};
int type;
};
ret car(const node*);
ret cdr(const node*);
std::ostream& operator << (std::ostream& s, const node& n);
std::ostream& operator << (std::ostream& s, const ret& r)
{
if (r.type == type_int) {
s << r.v;
} else {
if (r.p != 0)
s << *(r.p);
else
s << "null";
}
return s;
}
std::ostream& operator << (std::ostream& s, const node& n)
{
s << "(" << car(&n) << ", " << cdr(&n) << ")";
return s;
}
node* cons(int car, node* cdr)
{
node n;
n.car_v = car;
n.type_car = type_int;
n.cdr_p = cdr;
n.type_cdr = type_node;
return new node(n);
}
node* cons(node* car, int cdr)
{
node n;
n.car_p = car;
n.type_car = type_node;
n.cdr_v = cdr;
n.type_cdr = type_int;
return new node(n);
}
node* cons(int car, int cdr)
{
node n;
n.car_v = car;
n.type_car = type_int;
n.cdr_v = cdr;
n.type_cdr = type_int;
return new node(n);
}
node* cons(node* car, node* cdr)
{
node n;
n.car_p = car;
n.type_car = type_node;
n.cdr_p = cdr;
n.type_cdr = type_node;
return new node(n);
}
ret car(const node* p)
{
ret r;
r.v = p->car_v;
r.type = p->type_car;
return r;
}
ret cdr(const node* p)
{
ret r;
r.v = p->cdr_v;
r.type = p->type_cdr;
return r;
}
void rel(node* p)
{
if (p == 0) return;
ret r = car(p);
if (r.type == type_node)
rel(r.p);
r = cdr(p);
if (r.type == type_node)
rel(r.p);
delete p;
}
int main()
{
node* p = cons(1, 2);
std::cout << *p << std::endl;
node* plist = cons(1, cons(2, cons(3, (node*)0)));
std::cout << *plist << std::endl;
rel(p);
rel(plist);
return 0;
}
问题点数：200、回复次数：36Top
1 楼dot99（又来混CSDN来了）回复于 2006-03-19 04:27:00 得分 0
修正一下，
补充宏定义
#define nil (node*)0
由于疏忽，函数node* cons(int car, int cdr)和node* cons(node* car, int cdr)有误
改为
node* cons(int car, int cdr)
{
return cons(car, cons(cdr, nil));
}
node* cons(node* car, int cdr)
{
return cons(car, cons(cdr, nil));
}
删除原来的函数后，将以上两个函数添加在main之前cons(node*, node*)之后（修订后代码见后）
补充一下
length的长度是指一个层上的长度，并不计算子节点
也就是
(1, (2, (3, null))) 长度为 3; 构造为cons( 1, cons(2, 3))
((1, 2), (3, null)) 长度为 2; 构造为cons( cons(1, 2), 3)
修订代码：
#include<iostream>
struct node
{
union {
int car_v;
node* car_p;
};
int type_car;
union {
int cdr_v;
node* cdr_p;
};
int type_cdr;
};
const int type_node = 1;
const int type_int = 2;
struct ret
{
union {
node* p;
int v;
};
int type;
};
ret car(const node*);
ret cdr(const node*);
std::ostream& operator << (std::ostream& s, const node& n);
std::ostream& operator << (std::ostream& s, const ret& r)
{
if (r.type == type_int) {
s << r.v;
} else {
if (r.p != 0)
s << *(r.p);
else
s << "null";
}
return s;
}
std::ostream& operator << (std::ostream& s, const node& n)
{
s << "(" << car(&n) << ", " << cdr(&n) << ")";
return s;
}
#define nil (node*)0
node* cons(int car, node* cdr)
{
node n;
n.car_v = car;
n.type_car = type_int;
n.cdr_p = cdr;
n.type_cdr = type_node;
return new node(n);
}
node* cons(node* car, node* cdr)
{
node n;
n.car_p = car;
n.type_car = type_node;
n.cdr_p = cdr;
n.type_cdr = type_node;
return new node(n);
}
node* cons(node* car, int cdr)
{
return cons(car, cons(cdr, nil));
}
node* cons(int car, int cdr)
{
return cons(car, cons(cdr, nil));
}
ret car(const node* p)
{
ret r;
r.v = p->car_v;
r.type = p->type_car;
return r;
}
ret cdr(const node* p)
{
ret r;
r.v = p->cdr_v;
r.type = p->type_cdr;
return r;
}
void rel(node* p)
{
if (p == 0) return;
ret r = car(p);
if (r.type == type_node)
rel(r.p);
r = cdr(p);
if (r.type == type_node)
rel(r.p);
delete p;
}
int main()
{
node* p = cons(1, 2);
std::cout << *p << std::endl;
node* plist = cons(1, cons(2, cons(3, nil)));
std::cout << *plist << std::endl;
rel(p);
rel(plist);
return 0;
}
Top
2 楼dot99（又来混CSDN来了）回复于 2006-03-19 04:33:48 得分 0
补充一题
int list_ref(node* p, int n); //返回list第n个元素(0开始) i.e. (1, (2, (3, null)))的第2个元素为3,第1个元素为2Top
3 楼BFG_10K（dot99马甲）回复于 2006-03-19 04:43:20 得分 0
半夜..精神恍惚，最后一次更正题目：
ret list_ref(node* p, int n); //返回list第n个元素(0开始) i.e. (1, (2, (3, null)))的第2个元素为3,第1个元素为2Top
4 楼ugg（逸学堂(exuetang.net)）回复于 2006-03-19 10:21:13 得分 0
MarkTop
5 楼cunsh（村少）回复于 2006-03-19 12:06:56 得分 0
upTop
6 楼linuxchenyy（阿雨（linux,c/c++初学者，大虾们：抱拳～～久仰～））回复于 2006-03-19 12:11:38 得分 0
不错.强.
学习中Top
7 楼bjstcm（快毕业了~~~）回复于 2006-03-19 13:07:19 得分 0
markTop
8 楼MagicCarmack（MagiC++）回复于 2006-03-19 14:43:39 得分 0
不错不错
Top
9 楼atgjplh（永远的C/C++(unix/liunx)）回复于 2006-03-19 15:14:29 得分 0
接分!学习Top
10 楼fiftymetre（50米深蓝）回复于 2006-03-19 16:58:51 得分 0
搞什么啊，在这里自说自画的，演唱还演讲？t = cons(1, cons(2, cons(3, cons(4, NULL))))看到这种东西，偶就晕了。。。。。。。:(
楼主我认为你还是应该把注释都写明了，不要怕麻烦了。既然做好事就做到底吧。不然换来一堆一堆的mark没意思的。
Top
11 楼dot99（又来混CSDN来了）回复于 2006-03-19 17:45:59 得分 0
50米阿...注释写清楚了
提供的代码只是辅助测试用，要是用Lisp也没关系
我已经写清楚了，只使用car, cdr, cons完成题目
car, cdr, cons的语义也写得明明白白，要我还怎么注释....Top
12 楼dot99（又来混CSDN来了）回复于 2006-03-19 18:54:55 得分 0
cons: construct
car: Contents of Address part of Register
cdr: Contents of Decrement part of Register
由于历史的原因，car cdr就沿用下来，表示有序对的第一个元素和后一个元素Top
13 楼popoxx（我笑）回复于 2006-03-20 08:04:21 得分 0
正好在学习数据结构，谢谢lzTop
14 楼xiaohuoma7620（小火马）回复于 2006-03-20 09:43:17 得分 0
3xTop
15 楼iambic（）回复于 2006-03-20 10:04:46 得分 0
不大想看，拿个分吧。Top
16 楼bugouku（不够酷）回复于 2006-03-20 12:02:31 得分 0
up
Top
17 楼Ninstein（www.Ninstein.Com）回复于 2006-03-20 12:31:18 得分 0
JF 精神上支持LZ LZ就物质上支持俺Top
18 楼shaobolovelinglijun（邵波一生一世爱凌丽君）回复于 2006-03-20 13:17:54 得分 0
顶贴。不需要理由。Top
19 楼chrisboyer（ChrisBoyer）回复于 2006-03-20 20:51:06 得分 0
跟据你二楼修正的
node* cons(int car, int cdr)
{
return cons(car, cons(cdr, nil));
}
函数，不会出现这样的list：((1, 2), (3, null)) 。
cons( cons(1, 2), 3)构造出的list为((1, (2, null)), (3, null))。那它的长度是２还３呢？你说的“length的长度是指一个层上的长度，并不计算子节点”我有些不明白是什么意思。
Top
20 楼manplus（魅力加加）回复于 2006-03-20 21:17:20 得分 0
搞什么 mark先Top
21 楼vincent_yuen（石班）回复于 2006-03-20 21:56:35 得分 0
just UP UPTop
22 楼dot99（又来混CSDN来了）回复于 2006-03-20 22:01:30 得分 0
to chrisboyer(ChrisBoyer) :
看了一下，二楼的修正的确出现了麻烦，你说的无法构建（1, 2），谢谢提醒，更正如下：
代码维持原状（顶楼），cons(1, 2)构造出的有序对为(1,2)。
现添加一个操作
node* list_iter(va_list v);
node* list(int m, ...) //这个是添加的操作, m表示后面的参数个数
{
va_list v;
va_start(v, m);
node* p = cons( va_arg(v, int) , list_iter(m-1, v));
va_end(v);
return p;
}
node* list_iter(int m, va_list v)
{
if (m == 0)
return nil;
return cons(va_arg(v, int), list_iter(m-1, v));
}
我原来的目的是为了让cons更容易构造list, 所以简化, 这样反而出现无法构建(1, 2)的情况
是我的错误，谢谢提醒。
现在使用list构造表，而不是原来的cons
那么要构造表( (1, 2) 3)
应该使用代码
node* p = list(2, cons(1, 2), 3);
也就是
cons( cons(1, 2), cons(3, nil));
而length(p) == 2
注意(1, 2)是一个有序对，而(1 2)是一个列表，相应的有序对为(1, (2, nil))
列表(3)的有序对为(3, nil)
下面的代码
list(2, list(2, 1, 2), 3);
构造出的表为
((1 2) 3)
相应的有序对表示为((1, (2, nil)), (3, nil))
length为2
car为(1 2) //这个是表
cdr为(3, nil) //这个是有序对
我在表述Lisp的语义时太不谨慎了，无意的简化，带来更多的麻烦。
Top
23 楼dot99（又来混CSDN来了）回复于 2006-03-20 22:05:09 得分 0
对于列表，可以把它看作是链表，而有序对看作是链表的node，car(list)得到的是元素的内容，cdr(list)得到的是后继指针。
Top
24 楼dot99（又来混CSDN来了）回复于 2006-03-20 22:16:09 得分 0
补充一个错误类型
const int type_error = 0;
并在ret的operator <<中
加入
if(r.type == type_error) return s << "error";
避免做题时遇到问题。
上面的代码未经过严格测试，欢迎指出错误。
Top
25 楼sftk（星海传说）回复于 2006-03-20 22:39:57 得分 0
dingTop
26 楼dot99（又来混CSDN来了）回复于 2006-03-20 22:40:08 得分 0
上面的list有仔细看了，有严重问题：
编译器不会保证参数的求值顺序，且宏va_arg(v, int)带有副作用
所以，应该些
int n = va_arg(v, int);
cons(n, list_iter(m-1, v));
对不住大家了。Top
27 楼lei001（太极）回复于 2006-03-20 23:20:38 得分 0
markTop
28 楼dot99（又来混CSDN来了）回复于 2006-03-20 23:28:38 得分 0
另外list的处理有限，对于元素为node*的情况没有写进去，请大家完成。
Top
29 楼nipcdll（）回复于 2006-03-21 09:37:20 得分 0
学习Top
30 楼dream_forever（小龙）回复于 2006-03-21 16:49:16 得分 0
我刚刚入门 第一次看到这么长的程序
感觉：晕 晕 晕
俺不行了 打发点分吧，或许可以医好我Top
31 楼bohlee（我心澎湃）回复于 2006-03-21 16:55:40 得分 0
markTop
32 楼jinjiajie（leorio）回复于 2006-03-21 17:46:54 得分 0
.........MARK,有空看，没空就不看了Top
33 楼Xy4Ever（邪恶漫步者）回复于 2006-03-22 17:05:18 得分 0
同楼上的Top
34 楼dot99（又来混CSDN来了）回复于 2006-03-24 10:39:29 得分 0
这题很难么？Top
35 楼liangkai12（智多星）回复于 2006-03-25 22:50:57 得分 0
题目没看懂Top
36 楼hhhrrrsss（十五维）回复于 2006-03-25 23:25:41 得分 0
饶了我们吧楼主，干脆一次性给齐吧，我快崩溃了。
Top
