马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 丶不离不弃 于 2019-11-12 14:27 编辑
链表的增加和删减，前面是析构器和复制构造器以及move构造器，能看看为啥我的程序编译没有问题但是什么结果都没出来呢？#include <iostream>
#include <cmath>
using namespace std;
class LinkedList2 {
private:
class Node { // LinkedList2::Node
public:
int val;
Node* next;
};
Node* head;
Node* tail;
public:
LinkedList2():head(nullptr),tail(nullptr){}
~LinkedList2() {
Node* q;
for(Node* temp=head;temp !=nullptr; temp=q){
q=temp->next;
delete temp;
}
};
LinkedList2(const LinkedList2& orig){
if (orig.head== nullptr) {
head = nullptr;
return;
}
Node* q;
for(Node* temp=head; temp !=nullptr; temp=temp->next){
q=temp;
q=q->next;
}
}
LinkedList2& operator =( LinkedList2 orig){
Node* q;
for(Node* temp=head; temp !=nullptr; temp=temp->next){
q=temp;
q=q->next;
}
swap(head,orig.head);
swap(tail,orig.tail);
return *this;
}
// move constructor
LinkedList2(LinkedList2&& orig):head(orig.head),tail(orig.tail){ // steal orig data while it's dying (nice)
for(Node* temp=orig.head; temp !=nullptr; temp=temp->next){
temp=nullptr;
}
}
void addStart(int v){
Node* temp = new Node();
temp->val = v;
temp->next = head;
head = temp;
}
void addEnd(int v){
Node* temp=new Node();
temp->val=v;
temp=temp->next=nullptr;
if(head==nullptr){
head=temp;
tail=temp;
temp=nullptr;
}
else{
tail->next=temp;
tail=temp;
}
}
void removeStart(){
Node *temp=new Node;
temp=head;
head=head->next;
delete temp;
}
void removeEnd(){
Node* current=new Node;
Node* previous=new Node;
current=head;
while(current->next !=nullptr){
previous=current;
current=current->next;
}
tail=previous;
previous->next=nullptr;
delete current;
}
friend ostream& operator<<(ostream& s, const LinkedList2& list){
for(Node* temp=list.head; temp !=nullptr; temp=temp->next){
s<<temp->val<<' ';
}
return s;
}
};
/**
head --> nullptr
head --> [ val=3 next= nullptr ]
head --> [val=1 next= ----> [ val=3 next= nullptr ]
*/
int main() {
LinkedList2 a;
a.addStart(3); // 3 is the first element in the list
a.addStart(1); // 1 3
a.addStart(4); // 4 1 3
for (int i = 1; i <= 5; i++)
a.addEnd(i);
a.removeStart();
a.removeEnd();
cout << a << '\n'; // print out the list, separated by spaces or commas
LinkedList2 b = a;
cout << b << '\n';
LinkedList2 c;
c.addStart(5);
c = b; // wipe out c, copy in b
cout << c << '\n';
}
老师给我们写了一个例子，但是总感觉有点问题，而且不是太懂。。。
如下：#include <iostream>
using namespace std;
class LinkedList {
private:
class Node { // LinkedList::Node
public:
int data;
Node* next;
Node(int v, Node* n) : data(v) {}
};
Node* head;
public:
LinkedList() : head(nullptr) {}
~LinkedList() {
Node* q;
for (Node* p = head; p != nullptr; p = q) {
q = p->next;
delete p;
}
}
// if you do not want to implement copy constructor use =delete (C++11)
// LinkedList(const LinkedList& orig) = delete;
// LinkedList& operator =(const LinkedList& orig) = delete;
// LinkedList(LinkedList&& orig) {}
LinkedList(const LinkedList& orig) {
if (orig.head== nullptr) {
head = nullptr;
return;
}
head = new Node(orig.head->data, nullptr);
Node* p = orig.head->next;
if (p == nullptr)
return;
// there are at least 2 nodes
Node* q = head;
for (; p != nullptr; p = p->next, q = q->next)
q->next = new Node(p->data, nullptr);
}
LinkedList& operator =(LinkedList copy) {
swap(head, copy.head);
return *this;
}
/*
_______
temp->| data|
| next|--> head
-------
*/
void addStart(int v) {
#if 0
Node* temp = new Node();
temp->data = v;
temp->next = head;
head = temp;
#endif
head = new Node(v, head);
}
void addEnd(int v) {
if (head == nullptr) {
head = new Node(v, nullptr);
return;
}
Node* p;
for (p = head; p->next != nullptr; p = p->next)
;
// p = pointing to the last element
p->next = new Node(v, nullptr);
}
friend ostream& operator <<(ostream& s, const LinkedList& list) {
for (Node* p = list.head; p != nullptr; p =p->next)
s << p->data << ' ';
return s;
}
};
int main() {
LinkedList a; // a is empty
a.addStart(3);
a.addEnd(1);
a.addStart(4);
cout << a;
}
附上老师的要求，要求将public里面的内容写完整，使得main函数的功能得以实现：class LinkedList2 {
private:
class Node { // LinkedList2::Node
public:
int val;
Node* next;
};
Node* head;
Node* tail;
public:
LinkedList2();
~LinkedList2() ;
LinkedList2(const LinkedList2& orig);
LinkedList2& operator =(const LinkedList2& orig);
// move constructor
LinkedList2(LinkedList2&& orig) { // steal orig data while it's dying (nice)
}
void addStart(int v);
void addEnd(int v);
void removeStart();
void removeEnd();
};
/**
head --> nullptr
head --> [ val=3 next= nullptr ]
head --> [val=1 next= ----> [ val=3 next= nullptr ]
*/
int main() {
LinkedList2 a;
a.addStart(3); // 3 is the first element in the list
a.addStart(1); // 1 3
a.addStart(4); // 4 1 3
for (int i = 1; i <= 5; i++)
a.addEnd(i);
a.removeStart();
a.removeEnd();
cout << a << '\n'; // print out the list, separated by spaces or commas
LinkedList2 b = a;
cout << b << '\n';
LinkedList2 c;
c.addStart(5);
c = b; // wipe out c, copy in b
cout << c << '\n';
}
本帖最后由 superbe 于 2019-11-15 02:10 编辑
1. 前面理解的对，后面这句话“最后创建temp来指向*p，随着*p遍历orig.list，将*q->next=temp也就是q=p？”不对，temp指向新建的一个节点，不是指向*p，从内存地址上来理解，temp节点跟*p完全不同。每次新建节点后，通过*q->next=temp;把新节点添加到本链表尾部，然后q=q->next使q后移，以便继续添加新节点。这种复制方式就是所谓的深拷贝，就是将实参链表在内存中复制了一份，互不影响。而浅拷贝只是把头尾指针赋值给head,tail，这样和实参链表实际上在内存中是同一份，其中一个delete了，等于另外一个也不能正常使用了。
2. “因为q在开始=head的原因？然后对*q的操作就等于对本链表的操作吗？”可以这么认为，根据这个head中的next成员(一个指向下一节点的指点)，就可以依次顺藤摸瓜，找到链表所有节点，直到尾节点。
3. 你的意思是遍历orig.list，把所有节点指针依次给本链表？这样的话，从一开头执行本链表.head=orig.head后，实际上就已经是同一链表了(后面就不用再遍历了)，从内存地址上理解一下。但这是不行的，涉及到内存分配的复制构造函数，应该使用深拷贝(见1.)。
4. 上面的代码copy constructor和new way operator=，本链表和原链表地址不同。而move constructor，本链表和原链表地址相同。这个operator=是这样的，由于不是按引用传递，传参时会调用copy constructor创建一个链表，然后operator=通过swap获得了该链表的head和tail，只要确定了head和tail那么本链表也就确定了。退出operator=时，由于orig是临时变量，会调用析构函数销毁创建的链表(由于swap，其实是本链表原来的旧链表)。我原来的理解也是不太对的。
5. “无论这个链表又多长？如果head=null”，这是不可能的，正常的链表只要链表中有节点，head就不会为null，至少也应该有一个节点就是head本身，通过head才能找到后续节点，head怎么能为null呢。当head为null，说明链表为空，如果需要在最后添加一个节点，那就只好新建一个节点把它做为head。
6. Node* temp=new Node这句new Node会分配一块内存并把地址给temp。Node* q;的话，只是声明一个指针变量，并没有给它赋值，不确定它里面保存的是什么值。
Node* q=head;就是声明的同时也给它赋值一个地址了。添加节点时需要创建一个真正的内存中的节点，当然要new了，删除节点时delete要求提供一个指针就可以把指向的内存释放，当然就不用new了。
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-11-12 02:56:59
置顶卡
千斤顶
显身卡
楼主