关于链表的增加和删减问题，能不能看看我的程序有啥问题？,C\C++交流,技术交流,鱼C论坛

丶不离不弃 发表于 2019-11-12 02:56:59

关于链表的增加和删减问题，能不能看看我的程序有啥问题？

本帖最后由丶不离不弃于 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 -->

*/
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 -->

*/
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';
}

人造人 发表于 2019-11-12 12:38:16

1.这是在干嘛？这可是构造函数

2.为什么需要一个tail ？为了加速链表的访问？如果不是，那就去掉，多一个变量就会多一些代码来操作这个变量，这会增加算法的复杂度

人造人 发表于 2019-11-12 12:41:10

本帖最后由人造人于 2019-11-12 12:52 编辑

对1的补充
构造函数是用来构造当前对象的，这是一个拷贝构造函数，就是拿一个同类的对象作为参考来构造当前对象，这里用的一般都是深拷贝

丶不离不弃 发表于 2019-11-12 14:22:38

人造人发表于 2019-11-12 12:41
对1的补充
构造函数是用来构造当前对象的，这是一个拷贝构造函数，就是拿一个同类的对象作为参考来构造当 ...

老师要求必须要加一个tail的

superbe 发表于 2019-11-12 14:44:05

只是改得能运行出结果了，还需要自己完善下。

#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;
}
head = new Node;
head->val = orig.head->val;
head->next = nullptr;
Node *p = orig.head->next;
if (p == nullptr) {
return;
}
Node * q = head;
for (; p != nullptr; p = p->next, q = q->next) {
Node *temp = new Node;
temp->val = p->val;
temp->next = nullptr;
q->next = temp;
}
tail = q;
}

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;
//}
cout << "calling move constructor." << endl; //TEST
orig.head = nullptr;
orig.tail = nullptr;
}

void addStart(int v) {
Node* temp = new Node();
temp->val = v;
temp->next = head;
if (head == nullptr) {////
tail = temp;
}
head = temp;
}

void addEnd(int v) {
Node* temp = new Node();
temp->val = v;
//temp = temp->next = nullptr;
temp->next = nullptr; ////
if (head == nullptr) {
head = temp;
tail = temp;
//temp = nullptr;
}
else {
tail->next = temp;
tail = temp;
}
}

void removeStart() {
if (head == nullptr) {//链表为空的情况
return;
}
//Node *temp = new Node;
//temp = head;
Node *temp = head;////
head = head->next;
delete temp;
if (head == nullptr) { //只有一个节点的情况
tail = nullptr;
}
}

void removeEnd() {
//Node* current = new Node;
//Node* previous = new Node;
if (head == nullptr) { //链表为空的情况
return;
}
if (head->next == nullptr) {//只有一个节点的情况
delete head;
head = nullptr;
tail = nullptr;
return;
}
Node *current, *previous; ////
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 -->

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';

LinkedList2 d(move(c));
cout << d << '\n'; //TEST

}

丶不离不弃 发表于 2019-11-13 06:50:46

本帖最后由丶不离不弃于 2019-11-13 10:36 编辑

superbe 发表于 2019-11-12 14:44
只是改得能运行出结果了，还需要自己完善下。

谢谢，我还有几个问题不明白，关于你帮我改的代码：
1.copy constructor 我还是不是特别明白，从39行开始到46行，我的理解是把一个orig.链表复制到一个新的链表里，然后你的p可不可以理解为一个媒介作用的指针？但是我对你用的temp以及q指针还是不是特别明白，或许是我还没有理解这个copy的含义，你可以解释一下吗，然后能注释一下从27行～46行的意思吗？谢谢。

2.55行那里，这个=的复制不需要把出了头部和尾部以及他们之间所有的node都复制吗，为啥这里只需要考虑到头部和尾部就好了呢？

3.move constructor也是和第二问通用的问题。

4.为啥addstart 和addend我加了一个new node可以，但是delete一个node如100行以及111 112行，删除头部的时候需要一个起到媒介作用的指针来删除，尾部需要两个指针，为啥这里不能写new node呢，而是直接创建一个指针就可以了呢？创建一个new node 和创建一个指针node在这里有啥区别呢？我不是特别明白，请问你可以和我说下吗？谢谢！

5.105行是不是写错了：head->next=nullptr;?

6.第20行，Node* q；可不可以理解为他就是现有的linkedlist？

7.第86~87行，我当时写的时候理解为如果head=nullptr，那么加一个end的话，那不是head和tail都是空吗？但是你写的是头部和尾部都为一个非空的呀，因为有数值v在temp里~~你能说一下为啥这样写吗，当时我也写错了我应该吧temp=nullptr放在86行前面的。

superbe 发表于 2019-11-13 14:58:20

本帖最后由 superbe 于 2019-11-15 00:48 编辑

1. copy constructor把orig链表每个节点数据复制到新节点，并将新节点添加到本链表。
p用来遍历orig的节点，q指向本链表的当前尾节点，temp指向新节点，temp节点添加到q节点后面。

LinkedList2(const LinkedList2& orig) {
if (orig.head == nullptr) {       //如果orig的头指针为null说明链表为空，
   head = nullptr;                   //那么本链表也置为空
   return;                               //这里少了tail=nullptr;
}
head = new Node;                //new一个新节点将做为本链表的头节点
head->val = orig.head->val; //把orig头节点的数据复制到新头节点
head->next = nullptr;             //暂时将下一个节点的指针置为null
Node *p = orig.head->next; //指针p指向orig的第二个节点(后面用它遍历orig)
if (p == nullptr) {                   //如果p为null说明orig没有第二个节点了，返回
   return;                               //这里少了tail=head;
}
Node * q = head;                   //指针q指向新的头节点(下面随着添加后移)
for (; p != nullptr; p = p->next, q = q->next) {//用p遍历orig，如果p不为null就用p中数据构造一个新节点添加到本链表
                                                                           //如果p为null说明遍历完了，循环结束。
   Node *temp = new Node;    //temp指向一个新节点
   temp->val = p->val;          //将p节点数据复制到新节点
   temp->next = nullptr;          //暂时将下一个节点的指针置为null
   q->next = temp;                //修改q节点的next(next指向新节点)
}
tail = q;                                  //tail指向最后添加的节点
}
后来我想，当orig为null时实现成直接返回，不对现有链表操作应该更合理吧。

2. 在bitmap那个程序里老师讲过这种new way吧。这种方式就不用像old way那样复制内存了。由于不是按引用传递，传参时会调用copy constructor创建一个链表，operator=里通过swap获得了该链表的head和tail，只要确定了head和tail那么本链表也就确定了。退出operator=时，由于orig是临时变量，会调用析构函数销毁创建的链表(由于swap，其实是本链表原来的旧链表)。

3. 与2.有点类似。move constructor把orig的head和tail传给本链表，那么orig和本链表指向同一链表，就不用复制了。使用moveconstructor的前提是orig原来的链表不再使用了，所以应该使orig.head和orig.tail置为null。你可以在main里验证下链表被move后再cout看有什么结果。

4. 这里原来的代码也没错，可以运行，只是我觉得不好。以removeStart中的Node *temp = new Node; temp = head; 为例，先创建了一个新节点把地址给了temp，然后又把head地址给了temp，等于给了两次地址，你的目的是要使用head的地址，直接一步Node*temp = head不就行了吗，干嘛要中间创建一个对象多此一举呢。removeEnd是同样的问题。

5. 这段代码是这样的：
Node *temp = head;
head = head->next;
delete temp;
if (head == nullptr) { //只有一个节点的情况
   tail = nullptr;
}
temp指向头节点，然后head指针修改为head->next，意图指向下一个节点，但如果head->next成员的值就是null的话，那么head赋值后也变成了null，表明没有后续节点了。所以delete temp;删除头节点后链表为空，应该将tail也置为null。这里逻辑上好象没问题。

6. 不能这样认为，q是一个节点的指针。在析构函数里从头遍历每一个节点并delete，这个过程中需要先暂存下一个节点的指针(这就是q的作用)，再delete这个节点，如果顺序反了，先delete temp，再q = temp->next就会出错，因为temp内存已经被释放了。

7. 没太明白你的意思。我的理解是这样的：无论链表是否为空，必定要先创建一个Node，然后如果链表为空那么这个节点就做为头和尾节点，如果不为空，就将这个节点添加到最后。你原来的代码temp = temp->next = nullptr;无论链表空否，temp都是null，会影响到tail为null，导致以后addEnd出错。

如果有不对的或不明白的再探讨，我是一知半解，担心误导了你。

丶不离不弃 发表于 2019-11-14 06:29:43

superbe 发表于 2019-11-13 14:58
1. copy constructor把orig链表每个节点数据复制到新节点，并将新节点添加到本链表。
p用来遍历orig的节点 ...

emmm，我看完了你说的，还有一些疑问：
1.你的第一问回答，关于copy constructor，需要将orig.list复制到list中，你的方法就是创建一个head为新的节点，将orig.head数据复制进去，然后创建*q来遍历本链表。然后创建一个*p指针指向orig的第二个节点，用*p来遍历orig.list。最后创建temp来指向*p，随着*p遍历orig.list，将*q->next=temp也就是q=p？从而达到给本链表copy的目的？我理解的对吗？

2.承接上面的问题，如果用*q来遍历head，通过对*p来进行一些列的赋值以及赋地址操作，我的理解是这不就就是仅仅对于*q的操作吗？难道对*q的操作就是对本链表的操作？因为q在开始=head的原因？然后对*q的操作就等于对本链表的操作吗？我这里有些不明白，我不知道你懂不懂我的意思？

3.我的一个初步的设想；既然要将orig.list复制到本链表，那我创建一个媒介*temp来遍历orig.list，然后将本list=orig.head; 然后将本链表-->next=temp不就可以了吗？但是仔细一想好像还差个能够遍历本链表的媒介，那就再创建个*q来遍历本链表试试？就不需要创建那么多额外的指针了？我不知道你明白我的意思不，我的目的就是简化一下。

4.你的第三小问的解答，“orig和本链表指向同一链表”这个是啥意思，我的理解是采用new way，copy constructor 以及move constructor，本链表和原链表都有相同的地址？无论他们是复制还是搬移。然后采用new way，是不是只要是头部和尾部确认了，那么整个链表就确定了？

5.针对我的第7问，我的意思是如果开始的时候，无论这个链表又多长？如果head=null，是不是后面所有的节点都是空？我不知道我的理解有没有错，还是属于这种情况如果head=null，那么这个链表只可能有一个节点，而且这个节点为空？如果需要在最后添加一个节点，但是前一个也就是head节点为空，那么添加的这个节点也为空？2个空节点存在吗？

6.我依然对Node *temp=new Node以及Node* q=head有点疑惑，在add中，因为本来就要添加一个节点，所以是不是必须要写成前一个？但是delete节点的时候采用前一个的话是不是就赋予了2次地址，有些不必要，所以就采用后一个对吗？emmmmm我感觉我有点晕了 new Node是啥意思？和单独创建个指针Node* q有啥区别吗。。。。。。。。。。。。可以理解为前者就是生了一个真的小孩，后一个是一个想象中的小孩？哈哈哈哈～～！

superbe 发表于 2019-11-15 01:25:20

本帖最后由 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了。

丶不离不弃 发表于 2019-11-15 05:34:40

superbe 发表于 2019-11-15 01:25
1. 前面理解的对，后面这句话“最后创建temp来指向*p，随着*p遍历orig.list，将*q->next=temp也就是q=p？” ...

明白啦，谢谢啦～～

页: [1]

鱼C论坛's Archiver

关于链表的增加和删减问题，能不能看看我的程序有啥问题？