关于C++中的链表问题

Question

我只学过C中的链表，是在结构体中有数据元素和结构体指针。如果在C++中需要将对象用链表的数据形式组织起来，两者之间的关系是什么样的？另外有没有什么好的教材或者例子推荐的？

Answer 1

// 最简单的写法是这样, 类似C的做法:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* link;
};
Node* createSample() {
Node* p30=new Node;
p30->data=30; p30->link=0;
Node* p20=new Node;
p20->data=20; p20->link=p30;
Node* p10=new Node;
p10->data=10; p10->link=p20;
return p10;
}
void print(Node* pHead) {
cout << " [ ";
for(Node* p=pHead; p!=0; p=p->link) {
cout << p->data << ", ";
}
cout << " ] ";
}
void main() {
Node* h=createSample();
print(h); // 印出 [ 10, 20, 30, ]
}
----------------
// 稍加改良的写法是这样, 把list当成一个类:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* link;
};
class List {
public:
Node* head;
};
List* createSample() {
Node* p30=new Node;
p30->data=30; p30->link=0;
Node* p20=new Node;
p20->data=20; p20->link=p30;
Node* p10=new Node;
p10->data=10; p10->link=p20;
List* ans=new List;
ans->head=p10;
return ans;
}
void print(List* pL) {
cout << " [ ";
for(Node* p=pL->head; p!=0; p=p->link) {
cout << p->data << ", ";
}
cout << " ] ";
}
void main() {
------------------
// 再改良的写法是这样, 把function装入list中:
#include <iostream>
using namespace std;

class Node {
public:
int data;
private:
Node* link;
friend class List;
};
class List {
Node* head;
public:
static List* createSample();
static void print(List* pL);
};
List* List::createSample() {
Node* p30=new Node;
p30->data=30; p30->link=0;
Node* p20=new Node;
p20->data=20; p20->link=p30;
Node* p10=new Node;
p10->data=10; p10->link=p20;
List* ans=new List;
ans->head=p10;
return ans;
}
void List::print(List* pL) {
cout << " [ ";
for(Node* p=pL->head; p!=0; p=p->link) {
cout << p->data << ", ";
}
cout << " ] ";
}
void main() {
List* p=List::createSample();
List::print(p); // 印出 [ 10, 20, 30, ]
}
--------------------
// 进一步的写法是这样, 把print写成nonstatic:
#include <iostream>
using namespace std;

class Node {
public:
int data;
private:
Node* link;
friend class List;
};
class List {
Node* head;
public:
static List* createSample();
void print();
};
List* List::createSample() {
Node* p30=new Node;
p30->data=30; p30->link=0;
Node* p20=new Node;
p20->data=20; p20->link=p30;
Node* p10=new Node;
p10->data=10; p10->link=p20;
List* ans=new List;
ans->head=p10;
return ans;
}
void List::print() {
cout << " [ ";
for(Node* p=this->head; p!=0; p=p->link) {
cout << p->data << ", ";
}
cout << " ] ";
}
void main() {
List* p=List::createSample();
p->print(); // 印出 [ 10, 20, 30, ]
}
-------------
还可以再添加 List的 constructor, destructor, assignment.

Answer 2

c++中的链表相对之下更为复杂。因为它要确立对象，用class来建立链表，需要共有成员、私有成员，还有类独特的封装性。并不是说你懂得函数构建就能写出来，c++的链表语法较之复杂，但可移植性非常好！关于此点只有你学了才能体会出来。另外，数据结构是一种思想，你c的链表学会了，c++学的也快。总之c++和c的却别很大，功能比c多，所以语法也有点复杂。但有些时候用起来是很方便的。

Answer 3

C++和c语言中的链表是一样的，C++是C语言的扩展，扩展的内容如下：
1、类（类的多态、封装、继承）
2、重载（重载是一个很重要的概念，包括函数的重载和运算符的重载）
3、一些小概念上的修改，new和delete运算符的增加const，等等.
4、C++是完全兼容C的，也就是里面有的概念，C++里都用，并且都能用。
所以，像链表，结构体，共同体。这些都是不变的。
有本书叫C++primer plus是我认为最好的一本C/C++教材。建议好好看看。

Answer 4

差别不大，如果你把成员写成public的话，把结构体指针换成对象的指针就行了。
但是类的功能可以更强大，你应该考虑在类中增加更多的成员函数。
或者你可以将链表的节点仍然用结构体写，但是用一个类来管理整个链表。

追问

你的意思是不是我在类的数据成员里面加一个类的指针就可以把该类对象的用链表的方式连接起来了？然后对数据进行操作的时候就把头结点也就是第一个对象的指针穿进函数里，然后对不同的对象进行操作？

追答

是的，但是如果成员是私有的，外部函数将无法访问，需要另外写接口函数。
所以一般会把有关的链表操作函数全部写成类的成员函数。
最好是把head指针放在另一个类里，用这个类的成员函数来实现功能。

追问

头指针放在另一个类里我不是很理解。假设我建立了一条客户类的对象链表，头结点按你的描述是什么状态呢？不放在自己这个类的第一个对象里吗？请解释一下哈，谢谢！

追答

比如你已经用C语言实现了一个链表，然后你在C语言中需要用各种函数来操作这个链接。
你可以将这个链表的头放在一个类list中，然后把所有的函数写成类的成员函数，包括遍历，添加，删除。然后在使用这个类的时候就可以完全使用成员函数来操作，而不用管指针的细节。
而如果你的链表节点也是用类写的话，每个节点的成员结构最好是一样的，最好不要把头放在某一个节点中。

Answer 5

定义一个指向对象的指针，再定义一个结构体，结构体成员为两个指针，前者指向对象，后者指向下一个结构体，或者你把类产生的对象放在静态区，人工分配内存吧