清华大学C++课程学习笔记——第九章群体类和群体数据的组织

（一）模板
1.函数模板
（1）背景描述：
同种逻辑处理不同类型的数据，需要重新写一个函数；
多个函数会给函数的修改带来困难、不一致问题
重载函数虽然为使用者提供了方便，但是编写者仍然需要都写一遍。
（2）模板使用

	template<模板参数表>
	函数定义

模板参数表的内容

eg：求绝对值函数模板

# include <iostream>
using namespace std;

template<typename T>
T abs(T x){
	return x<0?-x:x;
}
int  main(){
	int n = -5;
	double d = -5.5;
	cout<<abs(n)<<endl;
	cout<<abs(d)<<endl;
}

【注意】
2.类模板
（1）背景描述
为类声明一种模式；
使得类中的某系数据成员、成员函数参数、成员函数的返回值能取任意类型。
（2）模板使用
抽象数据类型

3.数组类模板
（1）背景描述
长度不可调、下标越界无法处理；
数组类——直接访问的线性群体
静态数组具有固定元素个数的群体、元素可以通过下标直接访问；
动态数组由一系列位置连续，任意数量相同类型的元素组成，元素个数在程序运行时可以改变；
< vector>实际上就是封装了一个动态数组
（2）模板使用

首先保证后一段链表有头结点，不然链表的后半部分就丢了

指针转换运算符使用
4.结点类模板
（1）背景描述
数组：在插入和删除元素时，其他元素也在频繁的移动
链表：动态数据结构，可以用来表示顺序访问的线性群体
由系列节点组成，结点可以在运行时动态生成（数据域和指向链表中下一个结点的指针）；
链表的头指针非常重要
（2）模板使用

//9_5.h
#ifndef NODE_CLASS
#define NODE_CLASS

//类声明部分
template <class T>
class Node
{
    private:
        Node<T> *next;	//指向后继结点的指针
    public:
        T data;	//数据域

        Node (const T& item, Node<T>* ptrnext = NULL);    // 构造函数
        void InsertAfter(Node<T> *p);	// 在本结点之后插入一个同类结点p 
        Node<T> *DeleteAfter(void);	// 删除本结点的后继结点，并返回其地址
        Node<T> *NextNode(void) const;	 // 获取后继结点的地址
};

// 类的实现部分
// 构造函数，初始化数据和指针成员
template <class T>
Node<T>::Node(const T& item, Node<T>* ptrnext) :  data(item), next(ptrnext)
{}
  
// 返回后继结点的指针
template <class T>
Node<T> *Node<T>::NextNode(void) const
{    return next;    } 

// 在当前结点之后插入一个结点p 
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
    p->next = next;	//p结点指针域指向当前结点的后继结点
    next = p;	//当前结点的指针域指向p 
}

// 删除当前结点的后继结点，并返回其地址
template <class T>
Node<T> *Node<T>::DeleteAfter(void)
{
Node<T> *tempPtr = next;	//将欲删除的结点地址存储到tempPtr中
    if (next == NULL)	//如果当前结点没有后继结点，则返回NULL
        return NULL;
    next = tempPtr->next;	//使当前结点的指针域指向tempPtr的后继结点
    return tempPtr;	//返回被删除的结点的地址
}

#endif  // NODE_CLASS

（3）链表的常用操作
生成链表、插入结点、查找结点、删除结点、遍历链表、清空链表
5.栈模板

函数调用是用栈结构实现的
应用：表达式处理
栈的状态：栈空、一般状态、栈满
栈的基本操作：初始化、入栈、出栈、清空栈、访问栈顶元素、坚持栈的状态
6.队列类模板
队列内模板是只能向一端添加元素从另一端删除元素的线性群体
队列的状态：队满、队空、一般状态
循环队列：将数组弯曲成环形，元素出队时后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。
（二）排序
1.相关概念
排序：将数据元素的任意序列，重新排列成一个关键字有序的序列
数据元素：数据的基本单位
关键字：数据元素中某个数据项的值
两种基本操作：比较两个数的大小、调整元素在序列中的位置
2.常用的排序方法
（1）选择排序：每一次从待排序序列中选择一个关键字最小的元素，顺序排在已排列序列的最后，直至全部排完。

template<class T>
void mySwap(T&x,T&y){
	T temp = x;
	x = y;
	y = temp;
}

template<class T>
void selectionSort(T a[],int n){
	for (int i = 0; i < n-1; i++)
	{
		int leastIndex = i;
		for (int j = i+1; i < n; j++)
		{
			if (a[j]<a[leastIndex])
			{
				leastIndex = j;
			}
			mySwap(a[i],a[leastIndex]);
			
		}	
	}	
}

（2）交换排序：两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。
程序优化思想：在程序中多加一个True or False来标注是否发生了交换。
（3）查找：
顺序查找：逐个查找
二分查找：对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，逐步缩小查找范围

template<class T>
int binSearch(const T list[], int n, const T &key){
	int low = 0;
	int high = n-1;
	while (low<=high)
	{
		int mid = (low + high)/2;
		if (key == list[mid])
		{
			return mid;
		}else if(key<list[mid])
		{
			high = mid - 1;/* code */
		}else
		{
			low = mid + 1;
		}	
	}
	return -1;
}