北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

上一篇文章：

北邮22信通：（4）实验1 题目一 ：线性表的实现_青山如墨雨如画的博客-CSDN博客

下一篇文章：

北邮22信通：（6）实验1 题目三 ：通讯录管理_青山如墨雨如画的博客-CSDN博客

目录

1.实验要求：

2.程序分析：

2.1存储结构：

2.2关键算法分析：

        2.2.1.关键算法：

        2.2.2代码详细分析：

2.3其他

3.完整代码

4.运行结果： 

1.实验要求：

顺序从小到大或者从大到小都可以；

考虑如下情况：（假如按照从小到大）

List.data>list2.data,new.data=?

List.length!=list2.length ，如何合并？

处理list1.next==NULL;

处理list2.next==NULL;

2.程序分析：

2.1存储结构：

        单链表：

2.2关键算法分析：

        2.2.1.关键算法：

                自动在链表末尾增加结点的函数，

                打印链表的函数，友元函数：有序链表合并的函数；

        2.2.2代码详细分析：

                2.2.2.1单链表自动在末尾添加结点的函数：

                        时间复杂度：O(n)

                        定义一个指针，遍历链表使指针指向最后一个结点；

                        新建一个结点，数据域赋值，指针域置空；

                        将指针指向的结点的next指针指向新建结点

template<class temp>
void linklist<temp>::autoinsert(temp x)
{node<temp>* s = new node<temp>;s->data = x;s->next = NULL;node<temp>* p = this->front;while (p->next!=NULL)p = p->next;p->next = s;
}

                2.2.2.2友元函数：有序链表合并的函数：

                        参数说明：此函数共设置了3个形参，前两个形参用来传递将要合并的链表，

                        第三个形参用来记录合并后的链表；

                        定义指向linklist0的首结点地址的指针p0和指向linklist1首结点地址的指针p1；

                        归并排序；

                        时间复杂度：O(n)

                        当运行至p1或者p2为指向NULL的时候终止；

                        定义一个指针用来代替还没有指向NULL的那个指针（p0或者p1）

                        将没有用完的链表按顺序插入到结果链表中；

	friend void combinelist(linklist<temp>& linklist0,linklist<temp>&linklist1,linklist<temp>&linklist2){node<temp>* p0 = linklist0.front->next;node<temp>* p1 = linklist1.front->next;while (p0 != NULL && p1 != NULL){if (p0->data > p1->data){linklist2.autoinsert(p1->data);p1 = p1->next;}else if (p0->data < p1->data){linklist2.autoinsert(p0->data);p0 = p0->next;}else{linklist2.autoinsert(p0->data);p1 = p1->next;p0 = p0->next;}}node<temp>* temp0=NULL;if (p0 != NULL && p1 == NULL) temp0 = p0;if (p0 == NULL && p1 != NULL) temp0 = p1;if (p0 == NULL && p1 == NULL) return;while (temp0 != NULL){linklist2.autoinsert(temp0->data);temp0 = temp0->next;}return;}

2.3其他

调试时遇到的问题：

关于combinelist返回值类型的问题：

combinelist返回值类型为什么不能是linklist<temp>而必须是void类型？

因为如果函数的返回值类型是linklist<temp>,那么函数执行完毕之后，combinelist函数中定义的储存结果的数据类型为linklist<temp>的链表会被自动析构掉，因而无法返回有效值。

改正的方法是，将函数的返回值类型改为void类型。在传入形参时，除了两个将要执行合并的链表之外，再传入一个储存结果的链表的引用。引用是实参的别名，在执行函数之后不会被析构掉，因此成功储存了结果值。

3.完整代码

#include <iostream>
#include <iomanip>
using namespace std;
class student
{
private:int ID;string name;double scores;
public:student();student(int, string, double);void getinfo(int, string, double);void print();bool operator > (student& s){return (this->scores > s.scores) ? true : false;}bool operator<(student& s){return (this->scores < s.scores) ? true : false;}bool operator==(student& s){return (this->scores == s.scores) ? true : false;}
};inline student::student()
{this->ID = 0;this->name = "unkonwn_name";this->scores = 0;
}inline student::student(int ID, string name, double scores)
{this->ID = ID;this->name = name;this->scores = scores;
}inline void student::getinfo(int ID, string name, double scores)
{this->ID = ID;this->name = name;this->scores = scores;
}inline void student::print()
{cout << setiosflags(ios::left);cout << "ID:" << setw(8) << this->ID;cout << "name:" << setw(8) << this->name;cout << "scores:" << setw(8) << this->scores;cout << endl;
}template <class temp>
struct node
{temp data;node<temp>* 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 autoinsert(temp);void printlist();friend void combinelist(linklist<temp>& linklist0,linklist<temp>&linklist1,linklist<temp>&linklist2){node<temp>* p0 = linklist0.front->next;node<temp>* p1 = linklist1.front->next;while (p0 != NULL && p1 != NULL){if (p0->data > p1->data){linklist2.autoinsert(p1->data);p1 = p1->next;}else if (p0->data < p1->data){linklist2.autoinsert(p0->data);p0 = p0->next;}else{linklist2.autoinsert(p0->data);p1 = p1->next;p0 = p0->next;}}node<temp>* temp0=NULL;if (p0 != NULL && p1 == NULL) temp0 = p0;if (p0 == NULL && p1 != NULL) temp0 = p1;if (p0 == NULL && p1 == NULL) return;while (temp0 != NULL){linklist2.autoinsert(temp0->data);temp0 = temp0->next;}return;}
};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()
{node<temp>* p = this->front;while (p != NULL){this->front = p;p = p->next;delete front;}
}template<class temp>
void linklist<temp>::autoinsert(temp x)
{node<temp>* s = new node<temp>;s->data = x;s->next = NULL;node<temp>* p = this->front;while (p->next!=NULL)p = p->next;p->next = s;
}template<class temp>
void linklist<temp>::printlist()
{node<temp>* p = this->front->next;while (p != NULL){p->data.print();p = p->next;}cout << endl;
}int main()
{system("color 0A");student stu1[3];int ID;string name;double scores;cout << "请输入一班学生的学号 姓名成绩，每个学生的信息占一行:" << endl;for (int i = 0; i < 3; i++){cin >> ID >> name >> scores;stu1[i].getinfo(ID, name, scores);}linklist<student>list1(stu1, 3);list1.printlist();student stu2[3];cout << "请输入二班学生的学号 姓名 成绩 ，每个学生的信息占一行:" << endl;for (int i = 0; i < 3; i++){cin >> ID >> name >> scores;stu2[i].getinfo(ID, name, scores);}linklist<student>list2(stu2, 3);list2.printlist();//测试autoinsert函数/*student record(10, "zhangzhenzhe", 120);list2.autoinsert(record);list2.printlist();*/linklist<student>list3;combinelist(list1,list2,list3);list3.printlist();return 0;
}/*测试数据：
list11 zhang 100
2 li 98
3 liu 96list 24 zhao 99
5 qian 97
6 sun  80combine 1 zhang 100
2 li 98
3 liu 96
4 zhao 99
5 qian 97
6 sun  80
*/

4.运行结果： 

代码效果图：

程序运行结果：

写码不易，点个赞再走呗o(╥﹏╥)o

谢谢支持~