数据结构算法与解析（STL版含源码）_数据结构是不是stl源码

#include <iomanip>  //setw()等
#include <queue>   //STL中的队列与优先队列
#include <deque>  //STL中的双端队列
#include <bitset>   //STL中的位集合
#include <algorithm> //STL中的通用算法
#include <ctime>  //clock()等
#include <cstdarg>  //提供宏va_start、va_arg、va_end，用于存取长参数表
#include <assert.h>  //assert宏
1
2
3
4
5
6
7
8

C.h 几乎各程序都需要用到的文件包含宏命令和使用名空间

第1章 线性表

线性表：抽象的数据类型。
逻辑结构：除第一个元素外，每个元素都有一个前驱；除最后一个元素外，每个元素都有一个后驱。
物理结构：顺序、单链、双向链。
STL：vector（顺序表）、list（链表）。

1.1 顺序存储结构

特点：易实现随机查找；但插入或删除时操作复杂。
适用于稳定的线性表，例如职工工资表、学生学籍表。

1.1.1 顺序表

头文件：
SqList.h 顺序表的类（SqList类）
Func1-1.h 5个常用的函数
Func1-2.h 定义模板的实参Student及对其的I/O操作

//SqList.h 顺序表的类（SqList类）
SqList(const SqList &L) //拷贝构造函数
SqList& operator=(const SqList &L) //重载赋值运算符
{
   
  以上俩个函数关键在于：
  1、若成员数据中有指针数据，则需额外申请空间，以创造两个对象。
  2、重载赋值运算符函数需警惕L=L;且需释放原有空间;return *this;。
}
bool PriorElem(T e, bool(*eq)(T, T), T &pre_e)const //查找第一个与e满足eq()关系的数据，并用pre_e返回其前驱
{
   
  1、查询表中第一个与e满足eq()关系的数据，并返回其位序。
  2、判断该位序是否合法，是则用pre_e返回其前驱，否则返回false。
}
bool NextElem(T e, bool(*eq)(T, T), T &next_e)const //查找第一个与e满足eq()关系的数据，并用pre_e返回其前驱
bool ListInsert(int i, T e) //在位置i处插入新数据e。
{
   
  1、创造两个T型指针，其中一个指向位置i是为q，另一个指向位置末端是为p。
  2、for(p依次自减，直到与位置q相等) {
   p指向的数据依次后移；}
  3、位置q指向的数据更换为e。
}
bool ListDelete(int i, T &e) //删除位置i处的数据，并用e返回。
{
   
  1、创造两个T型指针，其中一个指向位置i是为q，另一个指向位置末端是为p。
  2、位置q指向的数据赋值给e。
  3、for(p依次自减，直到与位置q-1相等) {
   p指向的数据依次前移；}
}
template<typename T>
void SqList<T>::ListTraverse(void(*visit)(T&))const //类内声明类外定义；函数指针的使用
{
   函数也可做为另一个的函数参数，但是形参类型需为指针类型，即函数指针。}
friend void MergeList(const SqList<T>&, const SqList<T>&, SqList<T>&);//归并两个有序的顺序表得到新的有序顺序表的算法
{
   友元函数用于类中，可以访问类中任意成员。
  1、创建五个指针； T *pa, *pa_last, *pb, *pb_last, *pc;//pa系列指向线性表La；pb系列指向线性表Lb；pc系列指向线性表Lc
  2、将pa和pb指的数据按升序依次赋给pc，直到pa=pa_last或者pb=pb_last
  3、判断pa和pb哪一个未指向末端，并将其剩下的值赋给pc指的位置。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

主程序：
测试一：普通类型
Main1-1.cpp 验证顺序表SqList类的成员函数
测试二：自定义类型
Main1-2.cpp T为用户自定义类型的实例
F1-1.txt 测试文件
测试三：归并算法（友元函数的使用）
Algo1-1.cpp 归并两个有序的顺序表得到新的有序顺序表的算法

1.1.2 vector线性表——STL的顺序存储结构

顺序线性表类（vector）
测试一：基本类型
Algo1-2.cpp STL中vector使用基本数据类型
测试二：自定义类型
Algo1-3.cpp 在STL中vector使用自定义数据类型

//Algo1-2.cpp STL中向量（顺序线性表）的应用
vector<int>::iterator ip;
vector<int>::const_iterator cip; //vector类中的 const_iterator类 数据成员
a.push_back(i); a.insert(ip, 9); a.erase(a.begin()+4); a.clear(); a.size(); a.capacity(); a.empty(); 

sort(a.begin(), a.end()); 
sort(a.begin(), a.end(), greater<int>());//降序排列;仿函数的使用
reverse(a.begin(), a.end());

//Algo1-3.cpp 在STL中vector使用自定义数据类型
bool InputFromFile(ifstream &f, Student &c) //建议使用这种文件输入；而不是下列的重载运算符>>
{
   
	f>>c.name>>c.score;
	return f.good();
}
ifstream& operator>>(ifstream &f, Student& c)
{
   
	f>>c.name>>c.score;
	return f;
}
ifstream fin("F1-1.txt");
Student e;
while(!fin.eof()) //没有到文件尾
//while(fin.peek != EOF)
{
   
	if(InputFromFile(fin, e)) //也可重载运算符>>;然后 fin>>e;
		a.push_back(e);
}
fin.close();

bool cmp(Student a, Student b)
{
   
	return a.score<=b.score;
}
sort(a.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38