北邮22信通：你是不是在looking for……那串代码？（2）第三章单链表

相信有了第二章顺序表的基础，小伙伴们学习第三章链表应该会轻松一点吧

目录

类模板下的单链表

1.1书上干净完整代码（无增改、适合自己动手实验）

1.2对书上代码的完善和对一些问题的验证和解释代码

1.补全一个函数：

2.this指针：

3.关于printlist函数的一点说明：（增改后代码第117行）

4.getlength函数最后一步为什么是--cnt（增改后代码第136行）：

5.增改后代码：

6.增改后代码效果图：

 7.增改后代码运行效果：

---

类模板下的单链表

1.1书上干净完整代码（无增改、适合自己动手实验）

下面是书上单链表实现通信录的干净完整代码，基本一字不差~  有需要的友友可以拿走~

#include <iostream>
using namespace std;class phonebook
{
private:int ID;string name;string phone;string group;
public:phonebook() {};phonebook(int ID, string name, string phone, string group){this->ID = ID;this->name = name;this->phone = phone;this->group = group;}void print(){cout << this->ID << " " << this->name << " "<< this->phone << " " << this->group << endl;}bool operator==(phonebook& p){return (p.ID == this->ID) ? true : false;}
};template<class temp>
struct node
{temp data;node* next;
};template <class temp>
class linklist
{
private:node<temp>* front;
public:linklist(){this->front = new node<temp>;this->front->next = nullptr;}linklist(temp a[], int n);~linklist();void printlist();int getlengh() {};node<temp>* get(int i);int locate(temp x);void insert(int i, temp x);temp del(int i);
};//头插法
template<class temp>
linklist<temp>::linklist(temp a[], int n)
{this->front = new node<temp>;this->front->next = NULL;for (int i = n - 1; i >= 0; i--){node<temp>* s = new node<temp>;s->data = a[i];s->next = this->front->next;this->front->next = s;}
}//尾插法
/*
template<class temp>
linklist<temp>::linklist(temp a[], int n)
{this->front = new node<temp>;node<temp>* r = this->front();for (int i = 0; i < n; i++){node<temp>* s = new node<temp>;s->data = a[i];r->next = s;r = s;}r->next = NULL;
}
*/template<class temp>
linklist<temp>::~linklist()
{node<temp>* p = this->front;while (p != NULL){this->front = p;p = p->next;delete front;}
}template<class temp>
void linklist<temp>::printlist()
{node<temp>* p = this->front->next;while (p != NULL){p->data.print();//数据域中的print方法(需要用户自定义)p = p->next;}cout << endl;
}//按位置查找，返回地址
template<class temp>
node<temp>* linklist<temp>::get(int i)
{node<temp>* p = this->front->next;int j = 1;while (p != NULL && j != i){p = p->next;j++;}return p;
}//按值查找，返回位置
template<class temp>
int linklist<temp>::locate(temp x)
{node<temp>* p = this->front->next;int j = 1;while (p != NULL){if (p->data == x)return j;p = p->next;j++;}return -1;//如果没有找到，返回无效值
}template <class temp>
void linklist<temp>::insert(int i, temp x)
{node<temp>* p = this->front;if (i != 1)p = get(i - 1);//get(i - 1)表示要插入的位置的前一个结点地址if (p != NULL){node<temp>* s = new node<temp>;s->data = x;s->next = p->next;p->next = s;}else{cout << "插入位置错误:" << endl;exit(0);}
}template<class temp>
temp linklist<temp>::del(int i)
{node<temp>* p = this->front;if (i != 1)p = get(i - 1);node<temp>* q = p->next;p->next = q->next;temp x = q->data;delete q;return x;
}int main()
{phonebook pbook[4] ={{20181208,"mary","13011221827","classmates"},{20181127,"tom","13934621123","family"},{20181156,"john","1324579880","classmates"},{20181133,"lisa","1378001822","teacher"}};phonebook record(20181209, "phoenix", "1590209020", "teacher");linklist<phonebook>list(pbook, 4);cout << "通信录内容列表:" << endl;list.printlist();list.insert(1, record);cout << "通信录内容列表:" << endl;list.printlist();phonebook x = list.del(3);cout << "删除元素:" << endl;x.print();cout << "通信录内容列表:" << endl;list.printlist();int p = list.locate(record);cout << "phoenix的位置是:" << p << endl;return 0;
}

代码效果图：

 

运行效果图：

1.2对书上代码的完善和对一些问题的验证和解释代码

（自己增改部分已经在代码中标明，有助于友友们对问题的理解）

1.补全一个函数：

        书上没有对getlength函数做定义，本代码已经补全；

2.this指针：

        “this->”，是个指针，p用没有，就是本人觉得写着顺手，看代码的时候直接忽略即可~

3.关于printlist函数的一点说明：（增改后代码第117行）

        为什么printlist函数是从this->front->next开始打印数据，而不是this->front呢？

        因为无论在显示构造函数还是隐式构造函数中，都没有对头结点的数据域赋值。

        如果我们将this->front->next改成this->front：程序不会报错，但是会在头结点数据域输出的位置输出一串乱码。这代表头结点的存储地址。

        为了便于验证，我们在linklist中添加了getfront函数，用来输出头结点的数据域。

        （见增改后代码第51行函数声明）验证结果已在运行框中显示。

4.getlength函数最后一步为什么是--cnt（增改后代码第136行）：

        其实有了说明3的解释，相信大家应该都能大概明白，这个顺序表的实际长度确实是cnt的，但是因为头结点默认不存放有效数据，所以考虑有效长度时不将其算在内。

5.增改后代码：

#include <iostream>
using namespace std;class phonebook
{
private:int ID;string name;string phone;string group;
public:phonebook() {};phonebook(int ID, string name, string phone, string group){this->ID = ID;this->name = name;this->phone = phone;this->group = group;}void print(){cout << this->ID << " " << this->name << " "<< this->phone << " " << this->group << endl;}bool operator==(phonebook& p){return (p.ID == this->ID) ? true : false;}
};template<class temp>
struct node
{temp data;node* next;
};template <class temp>
class linklist
{
private:node<temp>* front;
public:linklist(){this->front = new node<temp>;this->front->next = nullptr;}linklist(temp a[], int n);~linklist();temp getfront();//自己增加部分 书上无void printlist();int getlengh();node<temp>* get(int i);int locate(temp x);void insert(int i, temp x);temp del(int i);
};//头插法
template<class temp>
linklist<temp>::linklist(temp a[], int n)
{this->front = new node<temp>;this->front->next = NULL;for (int i = n - 1; i >= 0; i--){node<temp>* s = new node<temp>;s->data = a[i];s->next = this->front->next;this->front->next = s;}
}//尾插法
/*
template<class temp>
linklist<temp>::linklist(temp a[], int n)
{this->front = new node<temp>;node<temp>* r = this->front();for (int i = 0; i < n; i++){node<temp>* s = new node<temp>;s->data = a[i];r->next = s;r = s;}r->next = NULL;
}
*/template<class temp>
linklist<temp>::~linklist()
{node<temp>* p = this->front;while (p != NULL){this->front = p;p = p->next;delete front;}
}//自己增加部分 书上无
template<class temp>
temp linklist<temp>::getfront()
{node<temp>* p = front;temp x = p->data;return x;
}template<class temp>
void linklist<temp>::printlist()
{node<temp>* p = this->front->next;//见说明3.while (p != NULL){p->data.print();//数据域中的print方法(需要用户自定义)p = p->next;}cout << endl;
}template<class temp>
int linklist<temp>::getlengh()
{node<temp>* p = this->front;int cnt = 0;while (p != NULL){p = p->next;cnt++;}return --cnt;//见说明4
}//按位置查找，返回地址
template<class temp>
node<temp>* linklist<temp>::get(int i)
{node<temp>* p = this->front->next;int j = 1;while (p != NULL && j != i){p = p->next;j++;}return p;
}//按值查找，返回位置
template<class temp>
int linklist<temp>::locate(temp x)
{node<temp>* p = this->front->next;int j = 1;while (p != NULL){if (p->data == x)return j;p = p->next;j++;}return -1;//如果没有找到，返回无效值
}template <class temp>
void linklist<temp>::insert(int i, temp x)
{node<temp>* p = this->front;if (i != 1)p = get(i - 1);//get(i - 1)表示要插入的位置的前一个结点地址if (p != NULL){node<temp>* s = new node<temp>;s->data = x;s->next = p->next;p->next = s;}else{cout << "插入位置错误:" << endl;exit(0);}
}template<class temp>
temp linklist<temp>::del(int i)
{node<temp>* p = this->front;if (i != 1)p = get(i - 1);node<temp>* q = p->next;p->next = q->next;temp x = q->data;delete q;return x;
}int main()
{phonebook pbook[4] ={{20181208,"mary","13011221827","classmates"},{20181127,"tom","13934621123","family"},{20181156,"john","1324579880","classmates"},{20181133,"lisa","1378001822","teacher"}};phonebook record(20181209, "phoenix", "1590209020", "teacher");linklist<phonebook>list(pbook, 4);cout << "通信录内容列表:" << endl;list.printlist();//自己增加部分 书上无cout << "验证头结点数据无效:" << endl;phonebook y = list.getfront();cout << "头结点数据为:" << endl;y.print();cout << endl;list.insert(1, record);cout << "通信录内容列表:" << endl;list.printlist();phonebook x = list.del(3);cout << "删除元素:" << endl;x.print();cout << "通信录内容列表:" << endl;list.printlist();int p = list.locate(record);cout << "phoenix的位置是:" << p << endl;//自己增加部分 书上无cout << "通信录的长度为:" << endl;cout << list.getlengh();return 0;
}

6.增改后代码效果图：

 7.增改后代码运行效果：

 

上一篇文章：数据结构与算法  第二章 顺序表  请参考以下链接 ~

https://blog.csdn.net/bc202205/article/details/129311232?spm=1001.2014.3001.5501

写码不易，关注一下作者再走呗o(╥﹏╥)o

谢谢支持~