第六周总结

模板（了解） 模板函数：在重载函数过程中，功能相似但形参或返回值不同时，通过使用模板定义一个具有通用功能的函数，同时支持不同的参数和返回值。（利用已知函数进行函数的重载） 模板类：当类包含不确定的成员变量，或成员函数的返回类型、形参的类型不确定时，用模板类来解决。 格式：模板类名<模板参数> 对象名1，对象名2，……对象名（需在类前声明加上模板标志）

线性表 逻辑结构：任意一对相邻的数据元素之间存在序偶关系，且称a_i-1为a_i的前驱，a_i为a_i-1的后继。其中a₁无前驱，a_n无后继，除此之外每个元素有且仅有一个前驱和一个后继。

顺序表：线性表的顺序存储结构，用一段连续的地址依次存储线性表的数据元素（一维数组）

基本操作： 1、初始化：设置length为0. 2、建立顺序表：

template <class DataType> SeqList<DataType>::SeqList(DataType a[],int n) { if(n>MaxSize) throw "wrong parameter"; for(int i=0;i<n;i++) data[i]=a[i]; length=n; }

3、销毁数据表：析构函数 4、判空：判断length是否为0 5、求顺序表长度：返回length的值 6、历遍：按下标依次输出各元素

template <class DataType> SeqList<DataType>::SeqList(DataType a[],int n) { for(int i=0;i<length;i++) cout<<data[i]<<"\t"; cout<<endl; }

7、按位查找：

template <class DataType> DataType SeqList<DataType>::Get(int i) { if(i<1 && i>length) throw "wrong Location"; else return data[i-1]; }

8、按值查找：

template <class DataType> int SeqList<DataType>::Locate(DataType x) { for(int i=0;i<length;i++) if(data[i]==x) return i+1; return 0; }

9、插入：

template <class DataType> void SeqList<DataType>::Insert(int i,DataType x) { if(length>=MaxSize) throw "Overflow"; if(i<1 || i>length+1) throw "Location"; for(int j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++; }

10、删除：

template <class DataType> DataType SeqList<DataType>::Delete(int i) { int x; if(length==0) throw "Underflow"; if(i<1 || i>length) throw "Location"; x = data[i-1]; for(int j=i;j<length;j++) data[j-1] = data[j]; length--; return x; }

11、输出：

template <class DataType> void SeqList<DataType>::PrintList() { for(int i=0;i<length;i++) cout<<data[i]<<endl; }

例子：键盘输入10个数据元素，利用顺序表的基本操作，删除表中的最大和最小的数据元素。

#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int MaxSize = 100; template <class DataType> class SeqList { public: SeqList(){length=0;} SeqList(DataType a[],int n); ~SeqList(){} int Length(){return length;} DataType Get(int i); int Locate(DataType x); void Insert(int i,DataType x); DataType Delete(int i); void PrintList(); private: DataType data[MaxSize]; int length; }; template <class DataType> SeqList<DataType>::SeqList(DataType a[],int n) { if(n>MaxSize) throw "wrong parameter"; for(int i=0;i<n;i++) data[i]=a[i]; length=n; } template <class DataType> DataType SeqList<DataType>::Get(int i) { if(i<1 && i>length) throw "wrong Location"; else return data[i-1]; } template <class DataType> int SeqList<DataType>::Locate(DataType x) { for(int i=0;i<length;i++) if(data[i]==x) return i+1; return 0; } template <class DataType> void SeqList<DataType>::Insert(int i,DataType x) { if(length>=MaxSize) throw "Overflow"; if(i<1 || i>length+1) throw "Location"; for(int j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++; } template <class DataType> DataType SeqList<DataType>::Delete(int i) { int x; if(length==0) throw "Underflow"; if(i<1 || i>length) throw "Location"; x = data[i-1]; for(int j=i;j<length;j++) data[j-1] = data[j]; length--; return x; } template <class DataType> void SeqList<DataType>::PrintList() { for(int i=0;i<length;i++) cout<<data[i]<<endl; } int main() { SeqList<int> p; int minn=INF,maxn=0,x; for(int i=1;i<=10;i++) { cin>>x; minn=min(x,minn); maxn=max(x,maxn); p.Insert(i,x); } int weizhi=p.Locate(maxn); p.Delete(weizhi); weizhi=p.Locate(minn); p.Delete(weizhi); p.PrintList(); return 0; }

链表： 概念：用一组任意的存储单元存储线性表的数据元素（地址可以是连续的，也可以是不连续的），包括数据域和指针域，数据域存数据，指针域指示其后继的信息。 结点结构：

template <typename DataType> struct Node{ DataType data; //数据域 Node<DataType> *next //指针域

单链表实现：

template <typename DataType> struct Node { DataType data; //数据域 Node<DataType> *next; //指针域 }; template <typename DataType> class LinkList { public: LinkList( ); //无参构造函数，建立只有头结点的空链表 LinkList(DataType a[ ], int n); //有参构造函数，建立有n个元素的单链表 ~LinkList( ); //析构函数 int Length( ); //求单链表的长度 int Empety(); DataType Get(int i); //按位查找。查找第i个结点的元素值 int Locate(DataType x); //按值查找。查找值为x的元素序号 void Insert(int i, DataType x); //插入操作，第i个位置插入值为x的结点 DataType Delete(int i); //删除操作，删除第i个结点 void PrintList( ); //遍历操作，按序号依次输出各元素 private: Node<DataType> *first; //单链表的头指针 };

基本操作： 1、初始化：

template <typename DataType> LinkList<DataType> :: LinkList( ) { first = new Node<DataType>; //生成头结点 first->next = nullptr; //头结点的指针域置空 }

2、判空：判断单链表是否只有头结点，即first->next是否为空

template <typename DataType> int LinkList<DataType> :: Empety() { if(first->next == nullptr) return 1; else return 0; }

3、遍历

template <typename DataType> void LinkList<DataType> :: PrintList( ) { Node<DataType> *p = first->next; //工作指针p初始化 while (p != nullptr) { cout << p->data << "\t"; p = p->next; //工作指针p后移，注意不能写作p++ } }

4、求单链表长度：

template <typename DataType> int LinkList<DataType> :: Length( ) { Node<DataType> *p = first->next; //工作指针p初始化为开始接点 int count = 0; //累加器count初始化 while (p != nullptr) { p = p->next; count++; } return count; //注意count的初始化和返回值之间的关系 }

5、按位查找：

template <typename DataType> DataType LinkList<DataType> :: Get(int i) { Node<DataType> *p = first->next; //工作指针p初始化 int count = 1; //累加器count初始化 while (p != nullptr && count < i) { p = p->next; //工作指针p后移 count++; } if (p == nullptr) throw "位置"; else return p->data; }

6、按值查找：

template <typename DataType> int LinkList<DataType> :: Locate(DataType x) { Node<DataType> *p = first->next; //工作指针p初始化 int count = 1; //累加器count初始化 while (p != nullptr) { if (p->data == x) return count; //查找成功，结束函数并返回序号 p = p->next; count++; } return 0; //退出循环表明查找失败 }

7、插入：

template <typename DataType> void LinkList<DataType> :: Insert(int i, DataType x) { Node<DataType> *p = first, *s = nullptr ; //工作指针p初始化 int count = 0; while (p != nullptr && count < i - 1) //查找第i – 1个结点 { p = p->next; //工作指针p后移 count++; } if (p == nullptr) throw "位置"; //没有找到第i – 1个结点 else { s = new Node<DataType>; s->data = x; //申请结点s，数据域为x s->next = p->next; p->next = s; //将结点s插入到结点p之后 } }

8、构造函数-建立单链表：

template <typename DataType> //头插法 LinkList<DataType> :: LinkList(DataType a[ ], int n) { first = new Node<DataType>; first->next = nullptr; //初始化一个空链表 for (int i = 0; i < n; i++) { Node<DataType> *s; s = new Node<DataType>; s->data = a[i]; s->next = first->next; first->next = s; //将结点s插入到头结点之后 } }

9、删除：

template <typename DataType> DataType LinkList<DataType> :: Delete(int i) { DataType x; Node<DataType> *p = first, *q = nullptr; //工作指针p指向头结点 int count = 0; while (p != nullptr && count < i - 1) //查找第i-1个结点 { p = p->next; count++; } if (p == nullptr || p->next == nullptr) //结点p不存在或p的后继结点不存在 throw "位置"; else { q = p->next; x = q->data; //暂存被删结点 p->next = q->next; //摘链 delete q; return x; } }

10：销毁单链表：

template <typename DataType> DataType LinkList<DataType> :: ~Linklist() { Node<DataType> *p=first; while(first!=nullptr) //释放每一个结点的存储空间 { first=first->next; //first指向被释放结点的下一个结点 delete p; p=first; //工作指针p后移 } }