2021-2022年小学期 程序设计开发实践 随堂笔记

作者：筱柒_Littleseven

2022/08/08 Class1 对于数据结构的理解

首先对于程序编写和项目开发来说，主要的部分是对于数据的储存、处理分析的过程，而并非仅仅通过学习过的语法知识完成对程序的编写。而数据结构和算法则是对于获取到的数据进行有效的储存并进行计算分析的工具。对于一个复杂的问题，例如我们现在要从理工大学开发区校区组织学生们去到主校区参加典礼活动，那么数据结构就相当于是选择哪种交通工具来接送学生，那么我们就会发现，在人数较少时，租用小型客车或者中型客车就更适合，而人数多的时候，就租用大型客车更适合；而算法则是涉及到一个车上要怎么安排学生、怎么安排行车路线等等的问题。而在计算机应用当中，会涉及到更多样更复杂问题，那么很显然，对于不同的问题、不同的情况、选择正确的数据结构是高效完成程序设计的基础，也是能够选择合适算法的基础。所以数据结构是程序设计当中很重要的一部分。

数组与结构体的特点与应用 数组：

数组是一种线性表数据结构，主要作用是利用一组连续的内存空间存储一组有相同类型的数据结构。

由于数组是利用一组连续的内存空间，所以数组的内存大小通常是有限的，这也导致了一个数组可以存储的数据量通常是有限的。

而由于线性表的结构特性，数组中的元素都是前后关系，也就是操作只有向前操作和向后操作两种。所以在数组当中插入和删除数据时需要将其他数据迁移，复杂度较高。

数组中进行查找操作的时间复杂度：

• 通过下标查找值： O ( 1 ) O(1) O(1)
• 通过值查找下标：
  • 有序情况下： O ( l o g n ) O(logn) O(logn)（最优）
  • 无序情况下： O ( n ) O(n) O(n)

数组中在指定位置插入或删除数据（保证原数组顺序）： O ( n ) O(n) O(n)（最差）

数组支持多维度，简单来说即数组的数组，但也受到数组“连续内存空间”和“相同类型”的限制。

结构体：

结构体是一种重要的数据类型，是由一系列成员数据组成，不同成员之间的类型可以不同。所以结构体通常用于表示类型不同但又相关联的若干个数据。结构体提供了将若干个不同数据类型的数据组合为一个数据类型，将若干个不同数据类型的变量组合为一个变量的功能。同时一个结构体的成员也可以是一个结构体。

链表的基本概念和基本操作 基本概念

链表有若干个结点以及结点之间的指针相连接构成。链表中的每个结点都可以包含一个或者多个储存数据的成员。例如对于一个学生结点可以有姓名、学号等，对于一个数据结点可以有编号、权值等。而一个节点当中除了若干个数据成员外，还有包含一个后继指针指向下一个结点的地址。

一个非空链表的第一个结点称为链表的头，而对于链表中成员的访问，即是用一个指针从链表头开始，沿着每个结点的后继指针向其余的结点进行访问，而链表结构中最后一个节点的指针会指向空（NULL）代表链表的结束。

相对于同样是线性表结构的数组来说，链表中的数据在内存中并不是占据连续空间的，而这也让链表不像指针一样受到初始化空间大小的限制，同时由于链表中存储数据的顺序是通过指针的指向实现的，而不是通过相邻地址的顺序实现的，那么对链表中的数据进行插入和删除操作即可在 O ( 1 ) O(1) O(1)的时间复杂度下完成。但也正是因为内存的无序性，导致链表的查询时间复杂度为 O ( n ) O(n) O(n)。

基本操作

创建、遍历、删除链表，插入与删除节点

#include 
#include 
#include 
using namespace std;


struct List {
    double val; // 存该结点的权值
    List *nxt = NULL; // 存下一结点的地址
} *head = NULL;


struct List *ListHead; // 链表头指针


struct List * List_Creat() {
    struct List *pHead = NULL, *pTail = NULL, *pNew = NULL; // 新建链表首、尾指针和新建结点并均置空
    bool Input = 1; string Input_Str; // 读入及判定变量
    
    double New; // 读入首个数据
    cout << "请输入存入链表中的数据：";
    cin >> New;

    while (Input) {
        pNew = (struct List *)malloc(sizeof(struct List)); // 新建结点，将数据存入节点中
        pNew->val = New;
        pNew->nxt = NULL;

        if(pHead == NULL) { // 当前链表中没有结点的情况
            pHead = pNew;
            pTail = pNew;
        }
        else {  // 当前链表中已经有结点的情况
            pTail->nxt = pNew;
            pTail = pNew;
        }

        cout << "若继续输入数据，直接输入数据；若停止输入数据，输入"!"" << endl;  // 判定是否需要继续加入数据
        cin >> Input_Str;
        if (Input_Str == "!") Input = 0;
        else {
            New = stod(Input_Str);
        }
    }
    return pHead; // 返回初始化完毕的链表的头指针
}


struct List * List_Find(double val) {
    struct List *pCur = ListHead;  // 光标指针
    while (pCur != NULL) {
        if (pCur->val == val) return pCur;  // 找到返回当前位置
        else {
            pCur = pCur->nxt;
        }
    }
    return NULL;  // 找不到返回空
}


void List_InsertNode(double val) {
    struct List *pCur = NULL, *pNew = NULL;  // 光标指针负责找到位置，新建指针负责加入链表
    pNew = (struct List *)malloc(sizeof(struct List));
    pNew->val = val;
    pNew->nxt = NULL;

    if (ListHead == NULL) {
        ListHead = pNew;
    }
    else {
        pCur = ListHead;
        while (pCur->nxt != NULL) {
            pCur = pCur->nxt;
        }
        pCur->nxt = pNew;
    }
}


bool List_DeleteNode(double val) {
    struct List *pCur = NULL, *pLstCur = NULL;
    if (ListHead == NULL) {  // 情况1：列表为空列表
        cout << "ERROR!" << endl;
        return 0;
    }
    else if (ListHead->val == val) {  // 情况2：表头为要删除的数据，则要将表头后移
        ListHead = ListHead->nxt;
        return 1;
    }
    else {  // 情况3：正常删除数据
        pCur = ListHead;
        while (pCur->nxt != NULL) {
            pLstCur = pCur;
            pCur = pCur->nxt;
            if (pCur->val == val) {
                pLstCur->nxt = pCur->nxt;
                delete(pCur);
                return 1;
            }
        }
        return 0;
    }
}


void List_Show() {
    struct List *pCur = ListHead;
    int total = 0;  // 统计全部元素个数
    if (pCur != NULL) {
        cout << pCur->val;
        total ++ ;
        pCur = pCur->nxt;
    }
    while (pCur != NULL) {
        cout << " -> " << pCur->val;
        total ++ ;
        pCur = pCur->nxt;
    }
    cout << endl << "Total:" << total << endl;
}


void List_Delete() {
    struct List *pCur = ListHead;
    while (pCur != NULL) {
        ListHead = ListHead->nxt;
        delete(pCur);
        pCur = ListHead;
    }
    ListHead = NULL;
    cout << "Finish!" << endl;
}


int main() {
    ListHead = List_Creat();
    List_Show();
    List_InsertNode(100.01);
    List_InsertNode(200.02);
    List_DeleteNode(1);
    List_Show();
    struct List *findresult;
    findresult = List_Find(100.01);
    if(findresult!=NULL) cout << "Found" << endl;
    else cout << "Not Found" << endl;
    List_DeleteNode(100.01);
    findresult = List_Find(100.01);
    if(findresult!=NULL) cout << "Found" << endl;
    else cout << "Not Found" << endl;
}

Input：

2.03
1
3.99
100
255.01
!

Output：

请输入存入链表中的数据：2.03
若继续输入数据，直接输入数据；若停止输入数据，输入"!"
1
若继续输入数据，直接输入数据；若停止输入数据，输入"!"
3.99
若继续输入数据，直接输入数据；若停止输入数据，输入"!"
100
若继续输入数据，直接输入数据；若停止输入数据，输入"!"
255.01
若继续输入数据，直接输入数据；若停止输入数据，输入"!"
!
2.03 -> 1 -> 3.99 -> 100 -> 255.01
Total:5
2.03 -> 3.99 -> 100 -> 255.01 -> 100.01 -> 200.02
Total:6
Found
Not Found

进阶操作

设计基于数组和链表的算法解决约瑟夫问题

链表：

#include 
using namespace std;

int total = 41;

struct People {
    int id;
    People *nxt = NULL;
};

struct People * Peoplelist;

struct People * Create() {
    struct People *phead = NULL, *ptail = NULL, *ptmp = NULL;
    phead = (struct People *)malloc(sizeof(struct People));
    phead->id = 1;
    phead->nxt = NULL;
    ptail = phead;
    for (int i = 2; i <= 41; i ++ ) {
        ptmp = (struct People *)malloc(sizeof(struct People));
        ptmp->id = i;
        ptmp->nxt = NULL;
        ptail->nxt = ptmp;
        ptail = ptmp;
    }
    ptail->nxt = phead;
    return phead;
}

void Deal() {
    struct People *pcur = Peoplelist, *plstcur = NULL;
    int order = 0;
    while (pcur->nxt != NULL && total > 2) {
        if (order == 2) {
            plstcur->nxt = pcur->nxt;
            cout << "Kill:" << pcur->id << endl;
            total -- ;
            // pcur = pcur->nxt;
        }
        order = (order + 1) % 3;
        plstcur = pcur;
        pcur = pcur->nxt;
    }
    plstcur = pcur->nxt;
    cout << "Saved:" << pcur->id << ' ' << plstcur->id << endl;
    delete plstcur;
    delete pcur;
    delete Peoplelist;
    
}

int main() {
    Peoplelist = Create();
    Deal();
}

Output：

Kill:3
Kill:6
Kill:9
Kill:12
Kill:15
Kill:18
Kill:21
Kill:24
Kill:27
Kill:30
Kill:33
Kill:36
Kill:39
Kill:1
Kill:5
Kill:10
Kill:14
Kill:19
Kill:23
Kill:28
Kill:32
Kill:37
Kill:41
Kill:7
Kill:13
Kill:20
Kill:26
Kill:34
Kill:40
Kill:8
Kill:17
Kill:29
Kill:38
Kill:11
Kill:25
Kill:2
Kill:22
Kill:4
Kill:35
Saved:16 31

数组：

#include 
using namespace std;
bool alive[41];
int order = 0, total = 41, cur = 1;
void addcur() {
    if (cur == 41) cur = 0;
    cur ++ ;
    while(alive[cur] == 1) {
        cur ++ ;
        if (cur > 41) cur -= 41;
    }
}
void addord() {
    order = (order + 1) % 3;
}
int main() {
    while (total > 2) {
        addord();
        addcur();
        if (order == 2) {
            total --;
            cout << "Kill:" << cur << endl;
            alive[cur] = 1;
        }
    }
    cout << "Saved:";
    for (int i = 1; i <= 41; i ++ ) {
        if (alive[i] == 0) cout << i << ' ';
    }
    return 0;
}

Output：

Kill:3
Kill:6
Kill:9
Kill:12
Kill:15
Kill:18
Kill:21
Kill:24
Kill:27
Kill:30
Kill:33
Kill:36
Kill:39
Kill:1
Kill:5
Kill:10
Kill:14
Kill:19
Kill:23
Kill:28
Kill:32
Kill:37
Kill:41
Kill:7
Kill:13
Kill:20
Kill:26
Kill:34
Kill:40
Kill:8
Kill:17
Kill:29
Kill:38
Kill:11
Kill:25
Kill:2
Kill:22
Kill:4
Kill:35
Saved:16 31

2022/08/09 Class2 面向过程和面向对象的理解 面向过程

面向过程是一种以事件为中心的编程思想。在处理一个问题时，将解决问题的方法逐步分解，并通过函数来实现各个步骤，最终按照顺序完成事件的求解。

例如在编写一个五子棋类的棋牌类程序时，根据面向过程思想，可以分别通过函数实现以下过程：

1.开始游戏	2.绘制画面	3.黑方落子	4.绘制画面	5.判断输赢	6.白方落子	7.绘制画面	8.判断输赢	

并通过按照顺序重复调用这些函数，最终实现这个程序。由此可见，面向过程方法将编程的关注点放在解决问题的步骤当中，依靠的是函数的顺序执行。

面向对象

在日常生活中，当我们面对一些简单的问题，例如去冰箱当中取出一个鸡蛋，那么我们只需要打开冰箱、拿出鸡蛋、关上冰箱这样简单的几步就能完成，而在这种情况下，我们的思维通常是关注在解决问题的步骤上，也就是面向过程的方法。而当我们要布置晚餐，问题变成了去冰箱中取出番茄炒蛋和红烧肉的食材，那么我们就会首先考虑番茄炒蛋和红烧肉需要用到哪些食材，相比于先拿出鸡蛋、关上冰箱、再拿出番茄、关上冰箱的方法，我们更倾向于先想到番茄炒蛋需要番茄和鸡蛋，然后直接把这两种食材一起拿出来。而这个思维方式的不同，也就体现了面向对象的思想在处理具有一定规模的问题时的高效性，而令番茄+鸡蛋=番茄炒蛋这种组合的方式，也就是编程思想中封装的体现。

在面向对象思想当中，我们把所有的个体看做一个包括其本质属性和行为的对象，并用方法将不同的对象相关联，解决问题的中心放在了各个对象上。

回到前面说的五子棋问题，我们可以把所有的玩家和行为归结为三个对象和一个方法：

三个对象：1.玩家（黑白双方的行为是相同的）	2.棋盘	3.规则
方法：由玩家进行数据的输入，并交给棋盘对象进行棋盘的变更并做出显示，同时规则对象会对当前的棋盘进行分析，根据规则判断输赢。

在以上分析后，我们可以看出面向对象方法相比面向过程方法有一系列优点：

• 面向对象方法使复杂程序中的结构清晰，程序是模块化、结构化的，相对于面向过程方法更符合人们的思考方式。
• 面向对象方法更易扩展，类与对象之间可以存在继承关系，方法之间可以存在重用和覆盖关系，同时减轻了代码的冗余，在后续编写过程中更加简单。
• 面向对象方法相对于面向过程方法维护更简单，由于模块化的处理，只需要在要修改的模块中进行维护即可，不需要修改整个程序和主要函数。

STL学习

STL(Standard Template Livrary，标准模板库)，是惠普实验室开发的一些列软件的统称。STL的出现是的程序中代码的复用性得到了进一步的提升。STL建立起了数据结构和算法之间的一套标准，提高了代码的复用性以及两者各自的独立性、单行和交互操作性。

STL从广义上分为三个部分：容器(Container)、算法(Algorithm)、迭代器(Iterator)，容器和算法之间通过迭代器进行操作。而STL中几乎所有代码都是基于模板类和模板函数实现的，大大提升了代码的复用性。

STL共分类六大组件：容器、算法、迭代器、仿函数、适配器和空间配置器，其中容器、算法、迭代器是三个最主要的组件。通过这些组件的配合，STL有了很明显的优点：

• STL内嵌于C++编译器中，可以直接使用。
• STL将数据和操作分离，由容器存储数据，由算法实现操作。
• STL将复杂的实现过程封装为简单的调用和操作，降低了编写程序的难度。
• STL具有高可重用性、高性能等特点。

三大组件 容器

在前面我们说过数据结构是一个程序存储数据的基础，也是算法运行的“轨道”，而STL容器就是将编程当中应用最广泛的一些数据结构进行实现和封装。

在编写程序当中，常用的数据结构有：数组(Array)、链表(List)、树(Tree)、栈(Stack)、队列(Queue)、集合(Set)、映射(Map)，而根据数据在容器中的排列特性，分为序列式容器和关联式容器。

• 序列式容器强调值的排序，序列式容器中的每个元素都有固定的位置。例如Vector容器、Deque容器、List容器等等。
• 关联式容器是非线性的树结构（二叉树）。各个元素之间没有严格的顺序关系，同时在关联式容器的另一个特点是在值中选择一个作为关键字Key，这个关键字可以对值起到索引的作用。例如Set容器、Map容器等等。

算法

算法即问题的解法。通过有限的步骤去解决逻辑上或者数学上的问题。广义上来说，我们编写的每一个程序或者说每一个函数都是一个算法。在STL中收录了一些及其常用切经过数学上的能效分析与证明的算法，例如排序算法、查找算法等等。而算法通常会搭配相应的数据结构，算法与数据结构相辅相成。

同时算法也分为两种，即质变算法与非质变算法。

• 质变算法指的是在运算过程中会对元素内容进行改变的算法，例如替换、删除等。
• 非质变算法指的是在运算过程中不会对元素内容进项改变的算法，例如查找、计数等。

迭代器

迭代器模式的定义：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器内部表示方式。STL的中心思想在于将容器和算法分开独立设计，而迭代器就是将两者相关联的"胶着剂"。

常用容器 String(字符串)容器

C语言中的字符串的实现方式是以空字符结尾的字符数组，实现起来十分复杂，不利于程序编写。所以在C++STL中提供了一种string类，定义在头文件string.h中。

#include 
using namespace std;


string str; // 新建一个名为str的空字符串
string str2(const string& str); // 拷贝构造字符串
string str3(const char *s); // 使用字符数组构造字符串
string str4(int n, char c); // 用n个字符c构造字符串


string& operator = (const char* s); // char*类型字符串 赋值给当前的字符串
string& operator = (const string &s); // 把字符串s赋给当前的字符串
string& operator = (char c); // 字符赋值给当前的字符串
string& assign(const char *s); // 把字符串s赋给当前的字符串
string& assign(const char *s, int n); // 把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s); // 把字符串s赋给当前字符串
string& assign(int n, char c); // 用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n); // 将s从start开始n个字符赋值给字符串


char& operator [] (int n); // 通过[]取字符
char& at(int n); // 通过at取字符


string& operator += (const string& str); // 重载+=操作符
string& operator += (const char* str); // 重载+=操作符
string& operator += (const char c); // 重载+=操作符
string& append(const char *s); // 把字符串s连接到当前字符串结尾
string& append(const char *s, int n); // 把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s); // 同operator+=()
string& append(const string &s, int pos, int n); // 把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c); // 在当前字符串结尾添加n个字符c


int find(const string& str, int pos = 0) const; // 查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const;  // 查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const;  // 从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;  // 查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;// 查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;// 查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;// 从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; // 查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); // 替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); // 替换从pos开始的n个字符为字符串s


//compare函数在>时返回 1，<时返回 -1，==时返回 0。比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。
int compare(const string &s) const; // 与字符串s比较
int compare(const char *s) const; // 与字符串s比较


string substr(int pos = 0, int n = npos) const; // 返回由pos开始的n个字符组成的字符串


string& insert(int pos, const char* s); // 插入字符串
string& insert(int pos, const string& str); // 插入字符串
string& insert(int pos, int n, char c); // 在指定位置插入n个字符c
string& erase(int pos, int n); // 删除从Pos开始的n个字符


//string 转 char*
string str = "it";
const char* cstr = str.c_str();
//char* 转 string 
char* s = "it";
string str(s);

Stack(栈)容器

栈是一种先进后出(First In Last Out,FILO)的数据结构，一个栈只有一个出口，每次操作可以向栈顶新增元素、删除元素或者取得栈顶元素。除了栈顶的元素之外，栈中的其他元素是不允许存取的，也就是栈是不支持遍历的。

#include 
#include 
using namespace std;

stack  ss; // int型栈
stack  s1; // char型栈
stack  s2; // string型栈
stacks3; // 结构Node型栈

int main() {

    
    ss.push(1); // 将元素1压入s栈顶
    ss.push(100);

    
    ss.pop(); // 移除栈顶元素

    
    ss.top(); // 取得栈顶元素(不删除)

    
    ss.empty(); // 为空返回1，否则返回0

    
    ss.size(); // 返回元素个数

}

Queue(队列)容器

队列式一种先进先出(First In First Out,FIFO)的数据结构，一个队列有两个出口，可以从一端增加元素，从另一端移除元素。同样，只有队列队首元素才可以被外界取用，所以queue也不提供遍历功能。

#include	// 引用queue的库
queuea; // 新建一个名称为a格式为int的队列
a.empty(); // 返回1，表示队列为空
a.front(); // 返回队头元素值
a.back(); // 返回对伪元素值
a.pop(); // 删除队头元素
a.push(k); // 在队尾插入元素值为k的元素
a.size(); // 返回队列中的元素个数

在Queue容器下，STL提供了两种特殊的队列容器：Deque双端队列和Priority_queue优先队列。

Deque(双端队列)容器

双端队列即是首尾都可以进行插入操作和删除操作。

#include	// 引用deque的库
#include // 默认打开库
dequea;	// 新建一个名称为a格式为int的双端队列
a.empty(); // 返回1，表示队列为空
a.front(); // 返回队头元素值
a.back(); // 返回队尾元素值
a.pop_front(); // 删除队头元素
a.pop_back(); // 删除队尾元素
a.push_front(k);	// 在队头插入元素值为k的元素
a.push_back(k); // 在队尾插入元素值为k的元素
a.size(); // 返回队列中的元素个数

//双端队列支持排序，如从小到大排序
sort(a.begin(),daend());

Priority_queue(优先队列)容器

优先队列在队列的基础上增加了优先级的概念，保证每次处于队首的元素都是优先级最大的。每次操作队列中的元素都是按照优先级进行排序的。

优先队列的底层实现是一个大根堆(Heap)，同队列相同，优先队列不支持遍历也不提供迭代器。

#include
using namespace std;

int main() {

    priority_queue  pq;
    pq.push(1); // 加入队列
    pq.top(); // 访问堆顶（队首）元素
    pq.pop(); // 删除堆顶（队首）元素
    pq.empty(); // 判断队列是否为空，空返回1
    pq.size(); // 返回队列元素个数

    //优先级设置（默认从大到小）
    priority_queue, cmp >pq; // cmp为比较函数
}

Vector(动态数组)容器

Vector容器数据存储和操作的方式都类似于普通的数组，而相对于普通数组，Vector在空间的运用上更具有灵活性。

• Array(数组)是静态空间，空间一旦被开辟并分配则不能改变，如果想要改变空间大小只能重新开辟空间并移动数组中的元素。
• Vector是动态空间（堆空间），在加入元素的过程当中它的内部机制允许它自动扩充空间来容纳新的元素。

头文件：

#include 

初始化：

vector  num; // 创建一个int型的动态数组
vector  nodes; // 创建一个结构Node类型的动态数组

vector  vec(n); // 创建一个长度为n的动态数组
vector  vec(n, 0); // 创建一个长度为n的动态数组且元素均为0
//若指定了动态数组的长度，那么后续不能使用push_back()操作

vector  nums{1,2,3}; // 动态数组中目前有三个元素

vector  cpynum(num); // 拷贝构造动态数组（类型必须相同）



vector num[5];
// 创建一个行数为5，列数可变的动态数组（一维长度固定）

vector< vector > mul; // 创建一个行列均可变的二维动态数组

方法函数：

vec.front(); // 返回第一个元素
vec.pop_back(); // 删除最后一个元素
vec.push_back(1); // 在数组最后增加一个元素
vec.size(); // 返回元素个数
vec.clear(); // 清空数组
vec.resize(n, v); // 改变数组空间为n个，元素值为v
vec.insert(it, 100); // 向迭代器it插入元素
    vec.insert(vec.begin()+ 2, 200); // 将200插入vec[2]的位置
vec.erase(first, last); // 清除[first, last)区间的所有元素
vec.begin(); // 返回首元素的迭代器（地址）
vec.end(); // 返回最后元素！后一个位置！的迭代器（地址）
vec.empty(); // 判断数组是否为空，为空返回1

排序：

sort(vec.begin(), vec.end(), cmp); // cmp是比较函数

访问方式：

for (int i = 0; i < 5; i ++ ) {
    vec.push_back(i);
}
for (int i = 0; i < vec.size(); i ++ ) {
    cout << vec[i] << endl;
}


vector ::iterator it; // 声明迭代器变量it
//方式一
vector ::iterator it = vec.begin();
for (int i = 0; i < 5; i ++ ) {
    cout << *(it + i) << endl;
}
//方式二
vectoe ::iterator it;
for(it = vec.begin(); it != vec.end(); it ++ ) {
    cout << *it << endl;
}


//智能指针只能遍历完数组，不能仅遍历数组当中的一部分
for(auto i : vec) {
    cout << i << endl;
}

List(链表)容器

如前面所说的链表，在STL中进行了对链表结构的封装，STL中提供的list容器是一个双向的循环链表。

方法函数：

list lstT; // list采用采用模板类实现,对象的默认构造形式：
list(beg,end); // 构造函数将[beg, end)区间中的元素拷贝给本身
list(n,elem); // 构造函数将n个elem拷贝给本身
list(const list &lst); // 拷贝构造函数


push_back(elem); // 在容器尾部加入一个元素
pop_back(); // 删除容器中最后一个元素
push_front(elem); // 在容器开头插入一个元素
pop_front(); // 从容器开头移除第一个元素
insert(pos,elem); // 在pos位置插elem元素的拷贝，返回新数据的位置
insert(pos,n,elem); // 在pos位置插入n个elem数据，无返回值
insert(pos,beg,end); // 在pos位置插入[beg,end)区间的数据，无返回值
clear(); // 移除容器的所有数据
erase(beg,end); // 删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos); // 删除pos位置的数据，返回下一个数据的位置
remove(elem); // 删除容器中所有与elem值匹配的元素


size(); // 返回容器中元素的个数
empty(); // 判断容器是否为空
resize(num); // 重新指定容器的长度为num，若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
resize(num, elem); // 重新指定容器的长度为num，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除


assign(beg, end); // 将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem); // 将n个elem拷贝赋值给本身
list& operator=(const list &lst); // 重载等号操作符
swap(lst); // 将lst与本身的元素互换


front(); // 返回第一个元素
back(); // 返回最后一个元素


reverse(); // 反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素
sort(); // list排序

Set(集合)容器

STL中的Set是以红黑树（Red Black Tree,一种平衡二叉树）为底层所实现的集合容器。在Set中的所有元素都会根据元素的值进行排序（默认从小到大），同时在Set中不允许两个元素有相同的值。

Multiset容器：

multiset容器的特性和用法与set几乎完全相同。两者之间唯一的差别是在multiset中允许两个元素具有相同的值。

方法函数：

#include 
setse;

se.begin(); // 返回set容器的第一个元素的迭代器（地址）
se.end(); // 返回set容器的最后一个元素的迭代器（地址）
se.rbegin(); // 返回逆序迭代器，指向容器元素的最后一个位置
se.rend(); // 返回逆序迭代器，指向容器元素的第一个位置
se.clear(); // 清空set容器中的所有元素
se.empty(); // 判断set是否为空
se.insert(); // 插入一个元素
se.size(); // 返回当前set容器中元素的个数
se.erase(it); // 删除迭代器it指向的值
se.erase(first, last); // 删除[first, last)之间的值
se.erase(key_value); // 删除值为key_value的元素

se.find(val); // 查找set中值为val的元素，有则返回对应迭代器，否则返回结束迭代器
se.lower_bound(val); // 返回大于等于val的第一个元素的迭代器
se.upper_bound(val); // 返回大于val的第一个元素的迭代器
//基于二分查找

访问：

for (set  :: iterator it = se.begin(); it != se.end(); it ++ ) {
    cout << *it << endl;
}


for (auto i : s) {
    cout << i << endl;
}


//第一种
cout << *se.rbegin() << endl;

//第二种
set :: iteraote it = se.end();
it -- ;
cout << (*it) << endl;

//第三种
cout << *(--se.end()) << endl;

Pair对组

Pair将一对值组合为一个值，一对值可以有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。

template  struct pair



//第一种
pair pair1(string("name"), 20);
cout << pair1.first << endl; // 访问pair第一个值
cout << pair1.second << endl; // 访问pair第二个值
//第二种
pair pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;



pair pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;

Map(映射)容器

Map中的所有元素都会根据元素的键值自动排序。且Map中的所有元素都是Pair(对组)，将pair中的第一元素作为键值，第二元素作为实值，在Map中不允许两个元素有相同的键值。Map底层也是通过红黑树实现的。

Multimap容器：

multimap容器的特性和用法与map几乎完全相同。两者之间唯一的差别是在multimap中允许两个元素具有相同的键值。

map mapTT; // map默认构造函数
map(const map &mp); // 拷贝构造函数


map& operator=(const map &mp); // 重载等号操作符
swap(mp); // 交换两个集合容器


size(); // 返回容器中元素的数目
empty(); // 判断容器是否为空


map.insert(...); // 往容器插入元素，返回pair
map mp;
// 第一种 通过pair的方式插入对象
mp.insert(pair(3, "小张"));
// 第二种 通过pair的方式插入对象
mp.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mp.insert(map::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mp[3] = "小刘";
mp[5] = "小王";


clear(); // 删除所有元素
erase(pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end); // 删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem); // 删除容器中key为keyElem的对组。


find(key); // 查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem); // 返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem); // 返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem); // 返回第一个key>keyElem元素的迭代器。
equal_range(keyElem); // 返回容器中key与keyElem相等的上下限的两个迭代器。

总结

STL提供了许多已经封装好的且易于使用的容器，除了容器外STL中也提供了许多常用算法的封装例如排序、全排列等等。在后续学习过程中将会对STL的学习笔记做一个更加系统的总结。

2022/08/10 Class3 我的第一个Qt程序——HelloWorld 新建Qt程序

新建QT程序主要分为五个步骤：选择项目模板、输入项目信息、选择构件套件、输入类信息、设置项目管理。

打开Qt Creater后，进入到软件的欢迎页面，如下：

点击新建项目，选定名称和路径，并选择要是用的编译器和其它设置内容：

设定结束即可进入程序编辑页面，具体页面如图：

在新建程序后，Qt Creater自动生成了如下的项目目录：

对于如上出现的文件有以下的说明：

文件	说明
helloworld.pro	项目文件，包含项目的相关信息
helloworld.pro.user	包含了与本地用户构建信息
hellodialog.h	对话框的头文件
hellodialog.cpp	对话框的源文件
main.cpp	包含程序main函数
hellodialog.ui	QtDesigner生成的界面文件

项目文件helloworld.pro

关于这个文件在一般情况下不需要对文件中内容进行修改。如果需要修改通常是在第一行的位置添加部分Qt模块。

在Qt5中对窗口模块进行了细分，将widgets模块从gui模块中分离。

如果引用了第三方头文件或者一些第三方关键字，则需要在其中添加相应的文件。

源文件main.cpp

应用程序类的库和类调用。

#include 
QApplication a(argc, argv);

在Qt当中使用一个类，则就要包含相应的头文件，通常情况下类的名字和头文件的名字相同。

界面文件mainwindow.ui

头文件mainwindow.h

关于命名空间Ui中的MainWindow类和另外的MainWindow类：

在用普通文本编辑器打开mainwindow.ui后发现其中也有一个mainwindow类，如下。

说明Ui中的mainwindow对应ui文件中的mainwindow。

完成HelloWorld(提示框)

编写main.cpp：

#include 
#include 
int main(int argc, char *argv[]) {
    QApplication app(argc, argv);
    QLabel *label - new QLabel("HelloWorld!");
    label->show();
    return app.exec();
}

编译运行后结果：

完成HelloWorld(窗体程序)

修改UI界面：

编译运行：