科技网站设计案例/做整站优化

这周本人在程序设计实验课上遇到了一道c++的链表构造题，对于我这种学过c初学c++不久的人来说花费的时间还蛮多的，收获当然也不少，鉴于链表真是一个非常非常重要的知识点，故把代码与自己的思考总结记录下来，方便以后查看。

题目TA已经把main.cpp和list.hpp文件写好了，我们只需要把list.cpp这个实现文件写好就行。
main.cpp就不用写了，只是TA自己的调用而已，关键是把头文件和实现文件写好。

1、已经被TA规定好的头文件：

#ifndef LIST
#define LIST#include <string>
#include <iostream>typedef struct node {int data;struct node* next;node(int data = 0, struct node* next = NULL) : data(data), next(next) {}
} node;class list {private:node* head;int _size;public:list();list(const list&);list& operator=(const list&);~list();// Capacitybool empty(void) const;int size(void) const;public:// output// list: [1,2,3,4,5]// output: 1->2->3->4->5->NULLstd::string toString(void) const;void insert(int position, const int& data);void erase(int position);void clear(void) {if (this->head != NULL) {node* p = this->head;while (p != NULL) {node* temp = p;p = p->next;delete temp;}this->head = NULL;}this->_size = 0;}list& sort(void);
};#endif

2、各种实现

1、一般和缺省构造函数，析构函数

#include "list.hpp"
#include <sstream>
#include <iostream>
#include <string>void swap(int*, int*);
std::string change(int i);list::list() {head = NULL;_size = 0;
}list::~list() {clear();
}

2、等号运算符的重载

list& list::operator =(const list& l) {clear();if (l.head == NULL) {head = NULL;_size = 0;} else {node* ptr = l.head -> next;_size = 1;head = new node(l.head -> data);for (int i = 1; i < l._size; i++) {insert(i, ptr -> data);ptr = ptr -> next;}_size = l._size;}return *this;
}

3、拷贝构造函数

list::list(const list& another) {this->head = NULL;this->_size = 0;*(this) = another;
}

4、判断是否为空

bool list::empty(void) const {if (head != NULL) return false;else return true;
}

5、遍历链表

其中change函数为一个自己定义的把int型转为string型的函数。
返回一个特定的string来表示链表的内容而已，对于链表的构建来说不是必须存在的。

std::string list::toString(void) const {std::string str = "";node *ptr = head;while (ptr != NULL) {str += change(ptr -> data);str += "->";ptr = ptr -> next;}str += "NULL";return str;
}

6、int转string

std::string change(int i) {std::stringstream ss;ss << i;return ss.str();
}

7、获得当前链表长度

int list::size(void) const {return _size;
}

8、往链表中插入一个元素

void list::insert(int position, const int& data) {if (position > _size) {return;} else {node *current = new node(data);if (position == 0) {current -> next = head;head = current;_size++;} else {node *ptr = head;while (--position) {ptr = ptr -> next;}current -> next = ptr -> next;ptr -> next = current;_size++;}}
}

9、从链表中清除一个元素

void list::erase(int position) {if (position < _size) {if (position != 0) {node *ptr = head;while (--position) {ptr = ptr -> next;}node *temp = ptr -> next;ptr -> next = temp -> next;delete temp;_size--;} else {node *temp = head;head = head -> next;delete temp;_size--;}} else {return;}
}

10、给链表中的元素重新排个序

list& list::sort(void) {int* a = new int[_size];node* ptr = head;int i = 0;while (ptr != NULL) {a[i++] = ptr -> data;ptr = ptr -> next;}for (int p = 0; p < _size - 1; p++) {for (int q = _size - 1; q > p; q--) {if (a[q - 1] > a[q]) swap(&a[q - 1], &a[q]);}}ptr = head;i = 0;while (ptr != NULL) {ptr -> data = a[i++];ptr = ptr -> next;}delete []a;return *this;
}

11、辅助交换的函数

void swap(int *a, int *b) {int temp;temp = *a;*a = *b;*b = temp;
}

3、小结

1、深拷贝

浅拷贝就是对于类按照成员变量逐步复制，当类里面的成员变量没有指针时，浅拷贝与深拷贝的效果是一样的，但是当成员变量里面存在指针时，浅拷贝就会出现不足。
举个例子：

因此，浅拷贝容易出现内存垃圾的现象，当程序持续运行时，将会降低计算机内存的利用效率。当我们没有在实现文件里自定义拷贝构造函数时，编译器会自动帮我们加上一个是浅拷贝的拷贝构造函数。所以，如果我们想要提高内存利用率，使用深拷贝的话，就需要自己实现，一步一步地拷贝过来，就像上面的代码一样。
这里因为重载了“=”的运算，“=”运算中实现的就是深拷贝，故此处的拷贝构造函数就直接利用“=”，以简化代码的长度。

需要指出的是，在等于号重载中，需要先把原来指向的内容给清空掉，即先调用一次clear（）函数，否则会出现内存泄漏的情况。

2、内存泄漏

程序不再需要动态创建对象时，一定要记住释放掉这些对象。否则这些空间会一直被占用，无法分配给别的程序使用；如果指向这些空间的指针指向了别处，将无法回收这些内存空间，这就是我们所说的内存泄漏。

1. 养成良好的编程习惯，在对原指针赋值的时候，时刻想着会不会出现内存块丢失的问题。
2. 可以维护一个容器，通过重载new和delete运算符来记录堆内存的申请
   3.通过eden系统的提示，慢慢寻找内存错误的源头（需要耐心和细心）（ps，Eden是我们学校的一个在线评测系统，其他的同学可能第三条不适用。。。但是可以用gdb来替代 :) ）

3、

这个是什么问题？
就是在写拷贝构造函数的没有一开始的两行，即不先给head和_size以默认值，直接调用重载的运算符“=”
这是因为拷贝构造函数与“=”有一点点的不同，拷贝构造函数进行时，对象还没有被创建出来，所以head为未定值，这样进行clear（）函数的话，会死在这里面。而“=”重载时，等号左边的对象已经被创建好了。。

4、为何重载等号时需要返回*this和引用？

改的是自己，即赋值运算符左边的对象，如果不是返回*this和引用，将会返回一个临时变量，虽然也可以实现，但是会加大内存的负荷，程序大时不推荐。

5、引用的小复习

double result;
double &re = result;
double *r = &result;

则*r和re等价，改(*r)的值等于改re的值

6、链表

解决链表问题时，一定要画图！！！！只有画好图了，指针之间的相互关系才能够比较清晰地呈现出来，这样写的时候正确率就高多了。

7、小结中的小结

此文作为自己的一个学习心得笔记，欢迎大家参考，主要的是链表的元素插入和删除的实现，拷贝构造函数和等于号运算符的重载的实现，其他的函数只是辅助迎合原题的设计而已，可以不用太过于关注。