顺序存储模板+单链表线性表的实现数据结构与算法(C++)

1、3.模板顺序表类SqList#pragma once/文件名：CStu.h/Cstu类的定义与声明#ifndef _CStu_h#define _CStu_h#include"iostream"#include"cstdlib"#include"string"#include"iomanip"#include"SqList.h"using namespace std;/存储学生记录的类Cstuclass Cstu/重载输出流插入符<< 输出学生数据friend ostream &am

2、p;operator<<(ostream &os, const Cstu &stu);/重载输入流提取符>> 输入学生数据friend istream &operator >> (istream &is, Cstu &stu);private:string number;/学号string name;/姓名string grade;/年级string score;/成绩public:/构造函数Cstu(string nu = " ", string na = " ", strin

3、g gr = " ", string sc = " ");#endif/文件名：Cstu.cpp/类Cstu的实现#include"Cstu.h"/包含实现任意ElemType类型数据的输入与输出的类CDataTemp的定义与实现/存储学生记录的类Cstu的实现和定义/构造函数Cstu:Cstu(string nu, string na, string gr, string sc)number = nu;name = na;grade = gr;score = sc;/重载输出流插入符<< 输出学生数据ostream &a

4、mp;operator<<(ostream &os, const Cstu &stu)os << setiosflags(ios:left) << setw(8) << stu.number<< setiosflags(ios:left) << setw(12) << << setiosflags(ios:left) << setw(8) << stu.grade<< setiosflags(ios:left) << s

5、etw(8) << stu.score;return os;/重载输入流提取符>> 输入学生数据istream &operator >> (istream &is, Cstu &stu)cout << "请输入学生的学号：" is >> stu.number;cout << "请输入学生的姓名：" is >> ;cout << "请输入学生的年级：" is >> stu.grade;cou

6、t << "请输入学生的成绩：" is >> stu.score;cout << endl;return is;#pragma once/文件名：SqList.h/SqListInt类的定义与声明#ifndef _SqListInt_h#define _SqListInt_h#include"iostream"#include"cstdlib"#include"string"#include"iomanip"#include"CStu.h"

7、using namespace std;template <class ElemType>class SqListprotected:/ 顺序表实现的数据成员:int count;/ 元素个数int maxSize;/ 顺序表最大元素个数ElemType *elems;/ 元素存储空间public:/ 抽象数据类型方法声明及重载编译系统默认方法声明:void Init(int size);/ 初始化线性表bool Full() const;/ 判断线性表是否已满SqList(int size = 10);/ 构造函数模板virtual SqList();/ 析构函数模板int Le

8、ngth() const;/ 求线性表长度 bool Empty() const;/ 判断线性表是否为空void Clear();/ 将线性表清空void Traverse(void(*visit)(const ElemType &) const;/ 遍历线性表bool GetElem(int position, ElemType &e) const;/ 求指定位置的元素bool SetElem(int position, const ElemType &e);/ 设置指定位置的元素值bool Delete(int position, ElemType &e);

9、/ 删除元素bool Insert(int position, const ElemType &e);/ 插入元素SqList(const SqList &copy);/ 复制构造函数模板SqList &operator =(const SqList &copy);/ 重载赋值运算符;/ 判断线性表是否已满template <class ElemType>bool SqList<ElemType>:Full() constreturn count = maxSize;/ 初始化线性表template <class ElemType&

10、gt;void SqList<ElemType>:Init(int size)maxSize = size;/最大元素个数elems = new ElemTypemaxSize;/分配存储空间count = 0;/空线性表元素个数为0./ 构造函数模板，构造一个最大元素个数为size的空顺序表。template <class ElemType>SqList<ElemType>:SqList(int size)maxSize = size;/最大元素个数elems = new ElemTypemaxSize;/分配存储空间count = 0;/空线性表元素个数

11、为0./ 析构函数模板template <class ElemType>SqList<ElemType>:SqList()delete elems;/ 求线性表长度，返回线性表元素个数。template <class ElemType>int SqList<ElemType>:Length() constreturn count;/ 判断线性表是否为空template <class ElemType>bool SqList<ElemType>:Empty() constreturn count = 0;/ 将线性表清空te

12、mplate <class ElemType>void SqList<ElemType>:Clear()delete elems;count = 0;/ 遍历线性表，操作结果：依次对线性表的每个元素调用函数(*visit)。template <class ElemType>void SqList<ElemType>:Traverse(void(*visit)(const ElemType &) constfor (int pos = 1; pos <= Length(); pos+)(*visit)(elemspos - 1);/对

13、线性表的每个元素调用函数(*visit)。/ 求指定位置的元素template <class ElemType>bool SqList<ElemType>:GetElem(int position, ElemType &e) constif (position < 1 | position > Length()return false;elsee = elemsposition - 1;return true;/ 设置指定位置的元素值template <class ElemType>bool SqList<ElemType>:

14、SetElem(int position, const ElemType &e)if (position < 1 | position > Length()return false;elseelemsposition - 1 = e;return true;/ 删除元素template <class ElemType>bool SqList<ElemType>:Delete(int position, ElemType &e)ElemType tmp;if (position < 1 | position > Length()re

15、turn false;elseGetElem(position, e);for (int pos = position; pos <= Length(); pos+)GetElem(pos, tmp);SetElem(pos - 1, tmp);count-;return true;/ 插入元素template <class ElemType>bool SqList<ElemType>:Insert(int position, const ElemType &e)ElemType tmp;if (count = maxSize)return false;e

16、lse if (position < 1 | position > Length() + 1)return false;elsecount+;for (int pos = Length(); pos >= position; pos-)GetElem(pos, tmp);SetElem(pos + 1, tmp);SetElem(position, e);return true;/ 复制构造函数模板template <class ElemType>SqList<ElemType>:SqList(const SqList &copy)maxSiz

17、e = copy.maxSize;elems = new ElemTypemaxSize;count = copy.count;for (int pos = 1; pos <= Length(); pos+)elemspos - 1 = copy.elemspos - 1;/ 重载赋值运算符template <class ElemType>SqList<ElemType>& SqList<ElemType>:operator=(const SqList<ElemType> &copy)if (&copy != thi

18、s)maxSize = copy.maxSize;delete elems;elems = new ElemTypemaxSize;count = copy.count;for (int pos = 1; pos <= Length(); pos+)elemspos - 1 = copy.elemspos - 1;return *this;#endif/main.cpp/第3次：用模板实现顺序表类SqList,并测试.即SqListInt类的使用测试#include"CStu.h"#include"SqList.h"/查看数据函数template

19、<class ElemType>void show(const ElemType &e)cout << e << endl;int main()int sel = 0;cout << "请选择要操作的数据类型，输入1表示对整型数据的操作，输入2表示对学生数据的操作："cin >> sel;if (sel = 1)SqList<int> user;while (1)cout << "1.建立数据" << endl<< "2.插入数据

20、" << endl<< "3.删除数据" << endl<< "4.修改数据" << endl<< "5.显示数据" << endl<< "6.清空数据" << endl<< "7.其他退出" << endl;cin >> sel;switch (sel)case 1:int u_all = 0, u_num = 0;cout <<

21、 "请输入要建立的线性表的数据个数："cin >> u_all;user.Init(u_all);for (int i = 0; i < u_all; i+)cout << "请输入第" << i + 1 << "个数据：" << endl;cin >> u_num;user.Insert(i + 1, u_num);system("pause"); system("cls");break;case 2:if (use

22、r.Full()cout << "数据存储已满，无法继续存储。" << endl;elseint u_pos = 0, u_num = 0;cout << "请输入要插入数据的位置与的值：" cin >> u_pos >> u_num;if (user.Insert(u_pos, u_num)cout << "数据插入成功!" << endl;elsecout << "数据插入失败!" << endl;sys

23、tem("pause"); system("cls"); break;case 3:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elseint u_pos = 0, u_num = 0;cout << "请输入要删除的数据位置：" cin >> u_pos;if (user.Delete(u_pos, u_num)cout << "数据" << u_num <<

24、; "删除成功!" << endl;elsecout << "数据不存在!" << endl;system("pause"); system("cls"); break;case 4:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elseint u_pos = 0, u_num = 0;cout << "请输入要修改的数据位置与新的值：" cin >

25、;> u_pos >> u_num;if (user.SetElem(u_pos, u_num)cout << "数据修改成功!" << endl;elsecout << "数据不存在!" << endl;system("pause"); system("cls"); break;case 5:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elseuser

26、.Traverse(show);system("pause"); system("cls"); break;case 6:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elseuser.Clear();cout << "数据已清空!" << endl;system("pause"); system("cls"); break;default:exit(0);else if (s

27、el = 2)SqList<Cstu> user;while (1)cout << "1.建立数据" << endl<< "2.插入数据" << endl<< "3.删除数据" << endl<< "4.修改数据" << endl<< "5.显示数据" << endl<< "6.清空数据" << endl<<

28、"7.其他退出" << endl;cin >> sel;switch (sel)case 1:int u_all = 0;Cstu u_num;cout << "请输入要建立的线性表的数据个数："cin >> u_all;user.Init(u_all);for (int i = 0; i < u_all; i+)cout << "请输入第" << i + 1 << "个数据：" << endl;cin >&

29、gt; u_num;user.Insert(i + 1, u_num);system("pause"); system("cls");break;case 2:if (user.Full()cout << "数据存储已满，无法继续存储。" << endl;elseint u_pos = 0;Cstu u_num;cout << "请输入要插入数据的位置与的值：" cin >> u_pos >> u_num;if (user.Insert(u_pos, u_

30、num)cout << "数据插入成功!" << endl;elsecout << "数据插入失败!" << endl;system("pause"); system("cls"); break;case 3:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elseint u_pos = 0;Cstu u_num;cout << "请输入要删除的数据位置

31、：" cin >> u_pos;if (user.Delete(u_pos, u_num)cout << "数据" << u_num << "删除成功!" << endl;elsecout << "数据不存在!" << endl;system("pause"); system("cls"); break;case 4:if (user.Empty()cout << "当前没有数据，

32、请先插入数据!" << endl;elseint u_pos = 0;Cstu u_num;cout << "请输入要修改的数据位置与新的值：" cin >> u_pos >> u_num;if (user.SetElem(u_pos, u_num)cout << "数据修改成功!" << endl;elsecout << "数据不存在!" << endl;system("pause"); system(&qu

33、ot;cls"); break;case 5:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elsecout << setiosflags(ios:left) << setw(8) << "学号"<< setiosflags(ios:left) << setw(12) << "姓名"<< setiosflags(ios:left) << setw(8) &

34、lt;< "年级"<< setiosflags(ios:left) << setw(8) << "成绩" << endl;user.Traverse(show);system("pause"); system("cls"); break;case 6:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elseuser.Clear();cout << "

35、;数据已清空!" << endl;system("pause"); system("cls"); break;default:exit(0);elsecout << "输入错误！" << endl;return 0;4. 模板单链表表类Node#pragma once/文件名：CStu.h/Cstu类的定义与声明#ifndef _CStu_h#define _CStu_h#include"iostream"#include"cstdlib"#incl

36、ude"string"#include"iomanip"/这个头文件是声明一些 “流操作符”的，如：setw(int)来设置显示宽度。 #include"SimpleLinkList.h"using namespace std;/存储学生记录的类Cstuclass Cstu/重载输出流插入符<< 输出学生数据friend ostream &operator<<(ostream &os, const Cstu &stu);/重载输入流提取符>> 输入学生数据friend ist

37、ream &operator >> (istream &is, Cstu &stu);private:string number;/学号string name;/姓名string grade;/年级string score;/成绩public:/构造函数Cstu(string nu = " ", string na = " ", string gr = " ", string sc = " ");#endif/文件名：Cstu.cpp/类Cstu的实现#include"

38、Cstu.h"/包含实现任意ElemType类型数据的输入与输出的类CDataTemp的定义与实现/存储学生记录的类Cstu的实现和定义/构造函数Cstu:Cstu(string nu, string na, string gr, string sc)number = nu;name = na;grade = gr;score = sc;/重载输出流插入符<< 输出学生数据ostream &operator<<(ostream &os, const Cstu &stu)os << setiosflags(ios:left)

39、<< setw(8) << stu.number<< setiosflags(ios:left) << setw(12) << << setiosflags(ios:left) << setw(8) << stu.grade<< setiosflags(ios:left) << setw(8) << stu.score;return os;/重载输入流提取符>> 输入学生数据istream &operator >>

40、(istream &is, Cstu &stu)cout << "请输入学生的学号：" is >> stu.number;cout << "请输入学生的姓名：" is >> ;cout << "请输入学生的年级：" is >> stu.grade;cout << "请输入学生的成绩：" is >> stu.score;cout << endl;return is;#pragma

41、 once/文件名：SimpleLinkList.h/SimpleLinkList类的定义与声明#ifndef _SimpleLinkList_H#define _SimpleLinkList_H#include"iostream"#include"cstdlib"#include"string"#include"iomanip"#include"CStu.h"using namespace std;/ 结点类模板template <class ElemType>struct Nod

42、e/ 数据成员:ElemType data;/ 数据域Node<ElemType> *next;/ 指针域 / 构造函数模板:Node();Node(ElemType item, Node<ElemType> *link = NULL);/ 已知数据域和指针域建立结构;/ 无参数的构造函数模板template<class ElemType>Node<ElemType>:Node()next = NULL;/ 已知数据域和指针域建立结构template<class ElemType>Node<ElemType>:Node(E

43、lemType item, Node<ElemType> *link)data = item;next = link;/ 简单线性链表类模板template <class ElemType>class SimpleLinkListprotected:/ 链表实现的数据成员:Node<ElemType> *head;/ 头结点指针 / 辅助函数模板:Node<ElemType> *GetElemPtr(int position) const;/ 返回指向第position个结点的指针public:/ 抽象数据类型方法声明及重载编译系统默认方法声明:

44、void Init();/ 初始化线性表SimpleLinkList();/ 无参数构造函数模板virtual SimpleLinkList();/ 析构函数模板int Length() const;/ 求线性表长度 bool Empty() const;/ 判断线性表是否为空void Clear();/ 将线性表清空void Traverse(void(*visit)(const ElemType &) const;/ 遍历线性表bool GetElem(int position, ElemType &e) const;/ 求指定位置的元素bool SetElem(int p

45、osition, const ElemType &e);/ 设置指定位置的元素值bool Delete(int position, ElemType &e);/ 删除元素bool Insert(int position, const ElemType &e);/ 插入元素SimpleLinkList(const SimpleLinkList<ElemType> &copy);/ 复制构造函数模板SimpleLinkList<ElemType> &operator =(const SimpleLinkList<ElemType

46、> &copy);/ 重载赋值运算符;/ 返回指向第position个结点的指针template<class ElemType>Node<ElemType> *SimpleLinkList<ElemType>:GetElemPtr(int position) constNode<ElemType> *tmpPtr = head;int pos = 0;while (tmpPtr != NULL && pos < position)tmpPtr = tmpPtr->next;pos+;if (tmpPtr

47、!= NULL && pos = position)return tmpPtr;elsereturn NULL;/ 初始化线性表template <class ElemType>void SimpleLinkList<ElemType>:Init()head = new Node<ElemType>/ 无参数构造函数模板template<class ElemType>SimpleLinkList<ElemType>:SimpleLinkList()head = new Node<ElemType>/ 析构函

48、数模板template<class ElemType>SimpleLinkList<ElemType>:SimpleLinkList()Clear();delete head;/ 求线性表长度template<class ElemType>int SimpleLinkList<ElemType>:Length() constint count = 0;/ 计数器 for (Node<ElemType> *tmpPtr = head->next; tmpPtr != NULL; tmpPtr = tmpPtr->next)c

49、ount+;return count;/ 判断线性表是否为空template<class ElemType>bool SimpleLinkList<ElemType>:Empty() constreturn head->next = NULL;/ 将线性表清空template<class ElemType>void SimpleLinkList<ElemType>:Clear()ElemType tmpElem;while (!Empty()Delete(1, tmpElem);/ 遍历线性表template<class ElemTy

50、pe>void SimpleLinkList<ElemType>:Traverse(void(*visit)(const ElemType &) constfor (Node<ElemType> *tmpPtr = head->next; tmpPtr != NULL; tmpPtr = tmpPtr->next)(*visit)(tmpPtr->data);/ 求指定位置的元素template<class ElemType>bool SimpleLinkList<ElemType>:GetElem(int pos

51、ition, ElemType &e) constif (position<1 | position>Length()return false;elseNode<ElemType> *tmpPtr;tmpPtr = GetElemPtr(position);e = tmpPtr->data;return true;/ 设置指定位置的元素值template<class ElemType>bool SimpleLinkList<ElemType>:SetElem(int position, const ElemType &e)i

52、f (position<1 | position>Length()return false;elseNode<ElemType> *tmpPtr;tmpPtr = GetElemPtr(position);tmpPtr->data = e;return true;/ 删除元素template<class ElemType>bool SimpleLinkList<ElemType>:Delete(int position, ElemType &e)if (position<1 | position>Length()retu

53、rn false;elseNode<ElemType> *tmpPtr;tmpPtr = GetElemPtr(position - 1);Node<ElemType> *nextPtr = tmpPtr->next;tmpPtr->next = nextPtr->next;e = nextPtr->data;delete nextPtr;return true;/ 插入元素template<class ElemType>bool SimpleLinkList<ElemType>:Insert(int position,

54、const ElemType &e)if (position<1 | position>Length() + 1)return false;elseNode<ElemType> *tmpPtr;tmpPtr = GetElemPtr(position - 1);Node<ElemType> *newPtr;newPtr = new Node<ElemType>(e, tmpPtr->next);tmpPtr->next = newPtr;return true;/线性链表的复制构造函数模板和重载赋值运算符的算法与顺序表的相应算

55、法完全相同，可复制3.模板顺序类SqList？也可以修改如下。/ 复制构造函数模板template<class ElemType>SimpleLinkList<ElemType>:SimpleLinkList(const SimpleLinkList<ElemType> &copy)ElemType e;int length = copy.Length();Init();for (int pos = 1; pos <= length; pos+)copy.GetElem(pos, e);Insert(Length() + 1, e);/ 重载赋

56、值运算符template<class ElemType>SimpleLinkList<ElemType> &SimpleLinkList<ElemType>:operator =(const SimpleLinkList<ElemType> &copy)if (&copy != this)ElemType e;int length = copy.Length();Clear();for (int pos = 1; pos <= length; pos+)copy.GetElem(pos, e);Insert(Leng

57、th() + 1, e);return *this;#endif/main.cpp/第4次：用模板实现单链表表类,并测试。即SimpleLinkList类的使用测试#include"CStu.h"#include"SimpleLinkList.h"/查看数据函数template <class ElemType>void show(const ElemType &e)cout << e << endl;int main()int sel = 0;cout << "请选择要操作的数据类型，输入

58、1表示对整型数据的操作，输入2表示对学生数据的操作："cin >> sel;if (sel = 1)int u_all = 0, u_num = 0, u_pos = 0;SimpleLinkList<int> user;while (1)cout << "1.建立数据" << endl<< "2.插入数据" << endl<< "3.删除数据" << endl<< "4.修改数据" <<

59、; endl<< "5.显示数据" << endl<< "6.清空数据" << endl<< "7.其他退出" << endl;cin >> sel;switch (sel)case 1:cout << "请输入要建立的线性表的数据个数："cin >> u_all;user.Init();for (int i = 0; i < u_all; i+)cout << "请输入第&quo

60、t; << i + 1 << "个数据：" << endl;cin >> u_num;user.Insert(i + 1, u_num);system("pause"); system("cls"); break;case 2:cout << "请输入要插入数据的位置与的值：" cin >> u_pos >> u_num;if (user.Insert(u_pos, u_num)cout << "数据插入成功!

61、" << endl;elsecout << "数据插入失败!" << endl;system("pause"); system("cls"); break;case 3:if (user.Empty()cout << "当前没有数据，请先插入数据!" << endl;elsecout << "请输入要删除的数据位置：" cin >> u_pos;if (user.Delete(u_pos, u_num)cout << "数据&