引言

在学习数据结构课程之前,更好的了解我们所使用的语言的一些特性是会帮助我们更好的解决问题的。在这学期的数据结构课程中,我们课堂上使用的是C语言,鉴于之前我已经学习过的C++在数据结构刷题中更加方便,因此我学习数据结构之前先对C/C++相关的一些基础知识做了基本的回顾如下。

事实证明,这些回顾是很有必要的。在我本学期的PTA刷题中,很多地方用到了回顾过程中用到的小技巧,比如sscanf、sprintf、memset等函数可以使我在PTA解题过程中更加高效的处理某些问题(由于诚信守则的原因,我不方便贴出具体的应用场景,读者们可以意会并自行揣摩其独特的使用方式),而qsort等为代表的一系列函数背后孕育的思想,也对我本学期很多问题的快速解决有着重要的启发性作用。

下面,我们就开始数据结构学习开始之前的知识储备与回顾工作。

C/C++查漏补缺

  • 绝对值10^9^以内的数都可以用int表示

  • getchar函数对输入回车敏感(即回车符号\n可以被识别并读入),gets()识别换行符作为输入结束,因此scanf完一个整数后,如果要使用gets,需要先使用getchar接受整数之后的换行符。

  • 常用math函数(#include<math.h>

    • fabs(double x) 对double类型变量取绝对值
    • floor(double x) 对double变量向下取整
    • ceil(double x) 对double变量向上取整
    • log(double x)ln(x) C语言不能求任意底数对数,必须借助换底公式
    • sin(double x) asin(double x) 正弦函数 反正弦函数 cos tan同理
    • round(double x) 将double变量四舍五入(==注==普通的控制输出格式%.md遵循四舍六入五成双规则)
  • 如果数组大小比较大(大概10^6^级别),则需要将其定义放在主函数外面,否则程序会异常退出

    • 原因:函数内部申请的局部变量来自系统栈,允许申请空间较小;

      函数外部申请全局变量来自静态存储区,允许申请空间较大。

  • memset函数——对数组中每一个元素赋相同的值(#include<string.h>

    • memset(数组名,值,sizeof(数组名));
    • 机理上是按字节赋值
    • 建议只用来赋0或-1,赋值为其他数字建议使用fill函数
  • 如果不是使用scanf函数%s格式或gets函数输入字符串(如使用getchar),请一定要在字符串末尾加入’\0’,否则printf和puts输出字符串会因为无法识别字符串末尾而输出一大堆乱码。

  • 常用string函数(#include<string.h>

    • strlen():得到字符数组中第一个’\0’前面的字符个数
    • strcmp():比较两个字符串大小
    • strcpy():把一个字符串复制给另一个字符串
    • strcat():把一个字符串接到另一个字符串后面
  • sscanf与sprintf

    • 两个例程:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      #include<stdio.h>
      int main()
      {
      int n;
      char str[100]="123";
      sscanf(str,"%d",&n);
      printf("%d\n",n);
      return 0;
      }
      //输出结果:123
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      #include<stdio.h>
      int main()
      {
      int n=123;
      char str[100];
      sprintf(str,"%d",n);
      printf("%s\n",str);
      return 0;
      }
      //输出结果233

      还有更多高级功能参见互联网

    • sscanf还支持正则表达式,配合正则表达式可以解决大部分字符串处理问题。

  • 结构体的构造函数

    • 类似于C++中类的构造函数,结构体也支持构造函数

      1
      2
      3
      4
      5
      6
      struct studentInfo{
      int id;
      char gender;
      studentInfo(int _id,char _gender):id(_id),gender(_gender){}
      };
      studentInfo stu=studentInfo(10086,'M');

      ==注意==如果自己重新定义了构造函数,则不能不经初始化就定义结构体变量,也就是说默认生成的构造函数被覆盖了,为此我们可以补上默认构造函数(只要参数个数和类型不完全相同,就可以定义多个构造函数),如下所示。

      1
      2
      3
      4
      5
      6
      7
      struct studentInfo{
      int id;
      char gender;
      studentInfo(int _id,char _gender):id(_id),gender(_gender){}
      studentInfo(){}
      studentInfo(char _gender):gender(_gender){}
      };
  • cin与cout

    • 读入一整行:cin.getline(str,100),可以将一整行读入str[100]中。
    • ==建议==只有在十分必要的场合(如string)时,才用cin与cout,否则都用printf与scanf。
  • 浮点数的比较

    1
    2
    3
    4
    5
    6
    7
    const double eps=1e-8;
    const double Pi=acos(-1.0);
    #define Equ(a,b) ((fabs((a)-(b)))<(eps))
    #define More(a,b) (((a)-(b))>(eps))
    #define Less(a,b) (((a)-(b))<(eps))
    #define MoreEqu(a,b) (((a)-(b))>(-eps))
    #define LessEqu(a,b) (((a)-(b))<(-eps))
    • 0.00输出为-0.00的解决方法:将字符串与-0.00比较,若相等,则输出0.00
    • 经过大量运算后,0可能会变成一个很小的负数,这时sqrt操作会出错,因此需要用eps保证在定义域内
  • 三种OJ输入中的程序组织结构

    • while...EOF

      ==适用条件==题目没有给出输入结束条件,默认读取到结束时使用。

      1
      2
      3
      4
      5
      6
      while(scanf("%d",&n)!=EOF){
      ...
      }
      while(gets(str)!=NULL){
      ...
      }
    • while...break

      ==适用条件==题目给出了输入结束条件如输入数字0时结束,则使用这种结构。

      1
      2
      3
      4
      while(scanf("%d%d",&a,&b),a||b){
      ...
      }
      //程序含义:当a和b中有一个不为零就进行循环
    • while(T--)

      ==适用条件==题目先给出测试数据总量后输入数据时使用。

      1
      2
      3
      4
      scanf("%d",&T);
      while(T--){
      ...
      }
  • 三种输出类型程序组织形式

    • 正常输出

    • 每个数据输出后加空格

    • 两组数据之间有空格,结尾没有空格

      1
      2
      3
      4
      5
      for(int i=0;i<N;i++){
      printf("%d",a[i]);
      if(i<N-1)printf(" ");
      else printf("\n");
      }

算法相关

排序算法

sort()函数(#include<algorithm> using namespace std;)

  • 更推荐使用C++中的sort()函数而非C库中的qsort()函数,因为性能优化更好,而且使用更加简单

  • ==语法==sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(选填))

    如果不填写比较函数,则默认将前面给出的区间进行递增排序。

  • 比较函数cmp的实现

    • 基本数据类型数组的排序

      如果想要把数组从大到小排序,需要使用比较函数cmp,例如,对int型比较,若从大到小排序,cmp函数构造如下:

      1
      2
      3
      bool cmp(int a,int b){
      return a>b; //可以理解为a>b将a放在b的前面
      }

      ==记忆方法==如果要把数据从小到大排列就做用<,若要从大到小排列就用>

    • 结构体数组排序

      对于以下结构体定义:

      1
      2
      3
      struct node{
      int x,y;
      }ssd[10];

      如果想要将ssd按x从大到小排序,可构造cmp函数如下:

      1
      2
      3
      bool cmp(node a,node b){
      return a.x>b.x; //可以理解为a>b将a放在b的前面
      }

      若对x从大到小排序,x相等时对y从小到大排序,那么cmp函数可构造如下:

      1
      2
      3
      4
      bool cmp(node a,node b){
      if(a.x!=b.x) return a.x>b.x; //可以理解为a>b将a放在b的前面
      else return a.y<b.y;
      }
    • 容器的排序

    只有vector,string,deque可以使用sort

    vector的排序(以int型为例):

    1
    2
    3
    bool cmp(int a,int b){
    return a>b; //可以理解为a>b将a放在b的前面
    }

    string的排序(假定要求按照字符串长度从小到大排列):

    1
    2
    3
    bool cmp(string a,string b){
    return a.length()<b.length();
    }
  • 排序题与sort函数的应用——排名的实现

    很多排序题会要求排序之后计算出每个个体的排名,并且规则一般是分数不同排名不同,分数相同排名相同但占用一个排位,对此一般要求在结构体类型定义时加入排名这一项,数组排序完成后有如下两种方法实现排名计算。

    方法1将数组第一个个体排名记为1,然后遍历其余个体:如果当前个体分数等于上一个个体分数,那么当前个体排名等于上一个个体排名,否则当前个体排名等于数组下标加1.

    1
    2
    3
    4
    5
    6
    stu[0].rank=1;
    for(int i=1;i<n;i++){
    if(stu[i].score==stu[i-1].score){
    stu[i].rank=stu[i-1].rank;
    }else stu[i].rank=i+1;
    }

    方法2有时题目不一定需要真的把排名记录下来,而是直接输出即可,那么可令int型变量rank初值为1,然后遍历所有个体:若当前个体不是第一个个体且其分数不等于上一个个体分数,那么令rank等于数组下标加1,这时rank就是当前个体排名,可以直接输出。

    1
    2
    3
    4
    5
    6
    7
    int rank=1;
    for(int i=0;i<n;i++){
    if(i>0&&stu[i].score!=stu[i-1].score){
    rank=i+1;
    }
    //输出当前个体信息,或者令stu[i].rank=rank
    }

    散列

  • ==核心思想==将元素通过一个函数转换为整数,使得这个整数可以尽量唯一的代表这个元素。散列函数$H(key)$

  • $key$为整数的常见散列函数

    • 直接定址法:恒等变换$H(key)=key$或是线性变换$H(key)=a*key+b$

    • 平方取中法:$key$的平方的中间若干位为$hash$值

    • 除留余数法:$H(key)=key%mod$.显然当mod为素数时$H(key)$能尽可能覆盖$[0,mod)$范围内每一个数,因而为了方便起见,我们取$TSize$为一个素数,$mod$取成直接与$TSize$相等。在这种方法中,当$key1$已经把表中位置为$H(key1)$的单元占据时,运算结果相同的$H(key2)$就不能使用这个位置了,这被称为冲突,下面有三种解决冲突的方法:

      • 线性探查法:如果一个地方被占用,那么逐个检查下一个位置是否被占据,依次类推,若找到空位置就使用空位置。若查找到最后也未找到空位置,就返回开头继续寻找。

        ==缺点==这种做法容易导致扎堆,即表中连续若干个位置都被占用,这在一定程度上会影响效率。

      • 平方探查法:当现有位置被占用,则按如下顺序检查表中位置:$H(key)+1^2,H(key)-1^2,H(key)+2^2,H(key)-2^2,H(key)+3^2……$

      • 链地址法:将所有$H(key)$相同的$key$制成单链表。

  • 一般可以直接用map来直接使用hash功能(C++11后可以使用unordered_map速度更快)

  • 二维点散列:$P(x,y)\ for(x,y\ in\ range(0,Range)) →H(key)=x*Range+y$

  • 字符串散列:构造进制转换的方法来实现

递归

  • 全排列问题 示例代码 综合运用递归与散列思想

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #include<cstdio>
    const int maxn=11;
    int n,P[maxn],hashTable[maxn]={false};
    void generateP(int index){
    if(index==n+1){
    for(i=1;i<=n;i++)
    printf("%d",P[i]);
    printf("\n");
    return;
    }
    for(int x=1;x<=n;x++){
    if(!hashTable[x]){
    P[index]=x;
    hashTable[x]=true;
    generateP(index+1);
    hashTable[x]=false;
    }
    }
    }
    int main(){
    n=3;
    generateP(1);
    return 0;
    }
  • n皇后问题——以五皇后问题为例

    • 回溯法的应用

贪心

二分

1
2
3
4
5
6
7
8
9
int binarySearch(int A[], int left, int right, int x) {
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (A[mid] == x)return mid;
else if (A[mid] > x)right = mid - 1;
else left = mid + 1;
}return -1;
}
  • 一类问题:寻找有序序列中第一个满足某条件的元素的位置​,可以用二分思想解决,固定模板如下

    1
    2
    3
    4
    5
    6
    7
    8
    int solve(int left,int right){
    int mid;
    while(left<right){
    mid=(left+right)/2;
    if(条件成立)right=mid;
    else left=mid+1;
    }return left;
    }
  • ==应用==快速幂

幂运算是非常常见的一种运算,求取anan,最容易想到的方法便是通过循环逐个累乘,其复杂度为O(n),这在很多时候是不够快的,所以我们需要一种算法来优化幂运算的过程。

快速幂——反复平方法​

该怎样去加速幂运算的过程呢?既然我们觉得将幂运算分为n步进行太慢,那我们就要想办法减少步骤,把其中的某一部分合成一步来进行。比如,如果n能被2整除,那我们可以先计算一半,得到$a^{n/2}$的值,再把这个值平方得出结果。这样做虽然有优化,但优化的程度很小,仍是线性的复杂度。再比如,如果我们能找到2^k^=n,那我们就能把原来的运算优化成((a^2^)^2^)^2^…,只需要k次运算就可以完成,效率大大提升。可惜的是,这种条件显然太苛刻了,适用范围很小。不过这给了我们一种思路,虽然我们很难找到2^k^=n,但我们能够找到$2^{k_1}+2^{k_2}+2^{k_3}+……+2^{k_m}=n$。这样,我们可以通过递推,在很短的时间内求出各个项的值。
我们都学习过进制与进制的转换,知道一个bb进制数的值可以表示为各个数位的值与权值之积的总和。比如,2进制数1001,它的值可以表示为10进制的1×2^3^+0×2^2^+0×2^1^+1×2^0^,即9。这完美地符合了上面的要求。可以通过2进制来把n转化成$2^{k_m}$的序列之和,而2进制中第i位(从右边开始计数,值为1或是0)则标记了对应的2^i−1^是否存在于序列之中。譬如,13为二进制的1101,他可以表示为2^3^+2^2^+2^0^,其中由于第二位为0,2^1^项被舍去。
如此一来,我们只需要计算a、a^2^、a^4^、a^8^……$a^{2km}$的值(这个序列中的项不一定都存在,由n的二进制决定)并把它们乘起来即可完成整个幂运算。借助位运算的操作,可以很方便地实现这一算法,其复杂度为O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef long long ll;
ll mod;
ll qpow(ll a, ll n)//计算a^n % mod
{
ll re = 1;
while(n)
{
if(n & 1)//判断n的最后一位是否为1
re = (re * a) % mod;
n >>= 1;//舍去n的最后一位
a = (a * a) % mod;//将a平方
}
return re % mod;
}

取模运算一般情况下是需要的,当然也可以省去。

矩阵快速幂​

需要进行幂运算的不仅仅只有整数,比如,在[Fibonacci]中,就需要我们快速地完成方阵的幂运算。知道了如何做快速幂,我们还可以将同样的思想运用在其他地方。除了乘法的规则与普通快速幂不同之外不同,其他的细节并没有什么差别。

实现矩阵快速幂的一种方法如下

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
44
45
46
struct matrix//定义一个结构体,方便传递值
{
int m[maxn][maxn];
};
/*
maxn和mod由全局定义,其中mod根据需要可以省去
*/
matrix mat_multi(matrix a, matrix b)//矩阵求积
{
matrix ans;
for(int i = 0;i < maxn;i++)
{
for(int j = 0;j < maxn;j++)
{
ans.m[i][j] = 0;
for(int k = 0;k < maxn;k++)
{
ans.m[i][j] += (a.m[i][k] % mod * b.m[k][j] % mod) % mod;
ans.m[i][j] %= mod;
}
}
}
return ans;
}
matrix mat_quickpow(matrix a, int n)//矩阵快速幂
{
matrix ans;
for(int i = 0;i < maxn;i++)
{
for(int j = 0;j < maxn;j++)
{
if(i == j)
ans.m[i][j] = 1;
else
ans.m[i][j] = 0;//这里要初始化为单位矩阵,类比普通快速幂这里初始化为1
}
}
while(n != 0)//方法与普通快速幂相同,只有乘法的实现不同
{
if(n & 1)
ans = mat_multi(a, ans);
a = mat_multi(a, a);
n >>= 1;
}
return ans;
}
  • ==应用==two pointers是算法编程中一种非常重要的思想,但是很少会有教材单独拿出来将,其中一个原因是它更倾向于是一种编程技巧,而长得不太像是一个是“算法”的模样。two pointers的思想十分简介,但却提供了非常高的算法效率。

    以一个例子引入:给定一个递增的正整数序列和一个正整数M,求序列中的连个个不同位置的数a和b,使得它们的和恰好为M,输出所有满足条件的方案。例如给定序列{1,2,3,4,5,6}和正整数M=8,就存在2+6=8和3+5=8成立。

      本题的一个最直观的想法是:暴力求解,使用二重循环枚举序列中的整数a和b,判断它们的和是不是M,如果是,输出方案,如果不是,则继续枚举。代码如下:

    1
    2
    3
    4
    5
    6
    7
    for(int i = 0;i < n; i ++){   
    for(int j = i+1; j < n; j++){
    if(a[i]+a[j]==M){
    cout<<a[i]<<" "<<a[j]<<endl;
    }
    }
    }

    显然,这样做的时间复杂度是O(n^2),对n在10^5的规模时是不可承受的。

    那么根据two pointers的思想,代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(i<j){
    if(a[i]+a[j]==M){
    cout<<a[i]<<" "<<a[j]<<endl;
    i++;
    j--;
    }else if(a[i]+a[j]<M){
    i++;
    }else{
    j--;
    }
    }

     明显,此方法的时间复杂度为O(n),可以发现,two poin的思想慧聪分利用了递增序列的性质,以很浅显的思想降低了复杂度。

    快速排序

    是对二分的一种重要体现

    一些高效的技巧与算法

    打表

    一种以空间换时间的策略

    递推的灵活运用

    随机选择算法

    本文主要讨论这样一个问题:如何从一个无序的数组中求出第k大的数。这个问题最直接的想法是对数组排一下序,然后直接取出第k个元素即可,这样做法需要O(nlogn)的时间复杂度。(这个方法比较简单,在运行时间允许的情况下当然选这个方法)下面介绍随机选择算法,它对任何输入都可以达到O(n)的期望时间复杂度。

基本思想:随机选择算法的原理类似于随机快速排序算法。当对A[left,right]执行一次randPartition函数之后,主元左侧的元素个数就是确定的,且它们都小于主元。假设此时主元是A[p],那么A[p]就是A[left,right]中的第一个p-left+1大的数。不妨令M表示p-left+1,那么如果k==M成立,说明第k大的数就是主元A[p];如果k<M成立,就说明第k大的数在主元右侧,即A[(p+1)…right]中的第k-M大,往右侧递归即可。

算法以left==right作为递归边界,返回A[left]。由此可以写出随机选择算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void randSelect(int n[], int left, int right,int k){
if (left == right) return;
int p = randPartition(n, left, right);
int m = p - left + 1;
if (k == m) return;
if (k<m)
{
randSelect(n, left, p - 1, k);
}
else
{
randSelect(n, p + 1, right, k - m);
}
}

可以证明,虽然随机选择算法的最坏时间复杂度是O(n²),但是其对任意输入的期望时间复杂度却是O(n),这意味着不存在一组特定的数据能使这个算法达到最坏情况,是个相当实用和出色的算法。

应用:

给定一个由整数组成的集合,集合中的整数各不相同,现在要将它分为两个子集合,使得这两个子集合的并为原集合,交为空,同时在这两个子集合的元素个数n1和n2之差的绝对值尽可能小的情况下,它们各自的元素之和S1和S2之差的绝对值尽可能大。求|S1-S2|的值。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstdlib>
#include<time.h>
#include<cmath>
#include<algorithm>
using namespace std;
//选取随机主元,对区间[left,right]进行划分
int randPartition(int n[], int left, int right){
//生成[left,right]内的随机数p
int p = round(rand() / RAND_MAX*(right - left) + left);
swap(n[p], n[left]); //交换n[p],n[left];swap函数在头文件algorithm下
//以下为原先(快速排序)中的Partition函数的划分过程
int temp = n[left]; //将n[left]存放在临时变量temp中
while (left<right) //只要left和right不相遇
{
while (left<right&&n[right]>temp) right--;
n[left] = n[right];
while (left < right&&n[left] <= temp) left++;
n[right] = n[left];
}
n[left] = temp; //把temp放在left和right相遇的地方
return left; //返回相遇下标
}
//随机选择算法,从n[left,right]中找到第k大的数,并进行划分
void randSelect(int n[], int left, int right,int k){
if (left == right) return;
int p = randPartition(n, left, right);
int m = p - left + 1;
if (k == m) return;
if (k<m)
{
randSelect(n, left, p - 1, k);
}
else
{
randSelect(n, p + 1, right, k - m);
}
}
int main(){
srand((unsigned)time(NULL)); //初始化随机数种子
int n[] = {1,6,33,18,4,0,10,5,12,7,2,9,3};
int sum = 0;
for (int i = 0; i < 13; i++)
{
sum += n[i];
}
randSelect(n, 0, 13 - 1, 13 / 2);
int sum1 = 0;
for (int i = 0; i < 13/2; i++)
{
printf("%d ", n[i]);
sum1 += n[i];
}
printf("\n%d\n",n[13/2]);
for (int i = 13/2+1; i < 13; i++)
{
printf("%d ", n[i]);
}
printf("\n%d\n", (sum - sum1) - sum1);
return 0;
}