算法题——Cantor表

题目介绍

描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的:

1/1, 1/2 , 1/3, 1/4, 1/5, …

2/1, 2/2, 2/3, 2/4, …

3/1, 3/2, 3/3, …

4/1, 4/2, …

5/1, …

我们以Z字形给表上每一项编号。第一项是1/1,然后是1/2, 2/1, 3/1, 2/2, …

输入格式

整数N(1<= N <=10^7)

输出格式

表中的第N项

样例

输入:

1
7

输出:

1
1/4

分析

规律

我们通过题目可知,在Cantor表中走法为Z字形

不妨将Cantor表转化为下图

Cantor

从左往右数

奇数行分母依次递增,分子依次递减

偶数行分母依次递减,分子依次递增

可知奇偶数行分子分母规律正好相反

所以为使奇偶数行变化规律一致并且符合题中所给的项数规律,我们可以规定

在上图中,奇数行从左往右数,偶数行从右往左数

找查

例如我们要找查第7项,前三行一共有6项,前4行一共有10项

很显然 6 < 7 < 10

所以我们可以很方便地确定第7项在第4行

前几行项数 - 所要找的项数 = 所要找的项所在行的最后一项分子 - 所找项分子

同理

前几行项数 - 所要找的项数 = 所找项分母 - 所找项所在行最后一项分母

这两个等式中我们分别知道任意三个量就可以求其中的第四个量

然后,我们继续根据规律确定第7项的具体的值为 1/4

最后,我们可以轻易得出求任意项的算法如下

解法

以下是笔者的解题方法

先上代码

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
#include <iostream>
using namespace std;

int main()
{
int n = 0, sum = 0, i = 1;
cin >> n;

while(sum < n)
{
++i; //这里一定要让i先自增再求和,否则求出来的和少一项(此处的项指的是等差数列的项)
sum = i*(i - 1)/2; //首项公差均为1的等差数列求和,此处的和为第i行为止的Cantor表的总项数
}

//总项数与所找项的项数的差
int dif = sum - n;

if((i - 1) % 2 != 0)
//如果i-1行为奇数,那么i行为偶数行,偶数行从右开始数(这里在写的时候绕了个弯)
cout << 1 + dif << "/" << i - 1 - dif;
else
//第i行为奇数行,从左边数
cout << i - 1 -dif << "/" << 1 + dif;

}

链表的定义

链表

链表的概念

定义链表是一种物理存储单元上非连续、非顺序的存储结构,由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

在链表的储存上,每个结点不仅包含所存的元素信息,还包含元素间的逻辑信息

链表的特性

  • 不支持随机访问不能通过知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。
  • 节点的储存空间利用率相对顺序表较低:链表中的每分一个结点需要划出一部分空间来储存指向下一个结点位置指针
  • 支持储存空间的动态分配:链表中当前结点的位置是由其前驱结点中的地址信息所指示的。其结点可以散落在内存中的任意位置,且不需要一次性地划分所有结点所需的空间给它。
  • 在链表中进行插入操作无需移动元素(而顺序表需要)

链表的形式

单链表

在每个结点除了包含的数据域外,还包含一个指针域,用以指向其后继结点。

  • 带头结点的单链表

带头结点的单链表中,头指针head指向头结点,头结点的值域不含任何信息,从头结点的后继结点开始储存信息。头指针head 始终不等于NULLhead->next等于NULL的时候,链表为空。

带头节点的单链表(图片来自网络)

  • 不带头结点的单链表

不带头结点的单链表中的头指针head直接指向开始结点,当head等于NULL时,链表为空。

不带头节点的单链表

双链表

双链表就是在单链表结点上增添了一个指针域,指向当前节点的前驱

相比于单链表,双链表能够从终端结点反向走到开始结点

双链表(图片源自网络)

循环链表

  • 循环单链表

只需要将单链表最后一个指针域(空指针)指向链表中的第一个结点即可。(如果循环单链表带头结点,则指向头结点;不带头结点,则指向开始结点)。

循环单链表可以实现从任何一个结点出发,访问链表中任何结点。(注意:此处应该区分与顺序表随机访问的特点。循环单链表指的是从一个结点出发,而不是知道一个结点从而迅速找到任何一个结点,因此循环单链表不具有随机访问特性。)

带头结点的循环单链表,当head等于head->next时,链表为空;不带头结点的循环单链表,当head等于NULL时,链表为空。

  • 循环双链表

双链表终端节点的next指针指向链表中第一个结点,将链表中的第一个结点的prior指针指向终端结点。

不带头结点的循环双链表,head等于NULL,链表为空

带头结点的循环双链表是没有空指针的,其为空状态下,head->nexthead->prior必然都等于head,故一下四种语句都可判断为空

1
2
3
4
head->next == head;
head->prior == head;
head->next == head && head->prior == head;
head->next == head || head->prior == head;

静态链表

静态链表借助一维数组表示。

静态链表结点空间来自于一个结构体数组(一般链表结点空间来自整个内存),数组中每个结点含两个分量:

  • 数据元素分量data
  • 指针分量(指示了当前结点直接后继节点在数组中的位置)

注意:静态链表的指针不是通常所说储存内存地址的指针型变量,而是储存数组下标的整型变量,其功能类似于指针,故在此称为指针

顺序表与链表区别

基于空间比较

  • 储存的分配方式

顺序表储存空间时一次性分配的,链表的是多次分配的

  • 存储密度

(注: 存储密度 = 结点值域所占存储量/结点结构所占存储总量

顺序表存储密度 = 1

链表存储密度 < 1

基于时间的比较

  • 存取方式

顺序表可以随机存取,也可以顺序存取

链表只能顺序存取

  • 插入/删除时移动元素个数

顺序表平均需要移动一半元素

链表不需要移动元素,仅需修改指针

顺序表的操作

顺序表的操作

这里先定义个顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

#define MAXSIZE 100

typedef struct{
int *elems;
int length;
int size;
}Sqlist;

Sqlist list;

顺序表初始化

  • 定义bool类型函数 initList() ,初始化成功为true,失败为false
1
2
3
4
5
6
7
8
9
10
11
//初始化顺序表,创建一个空表
bool initList(Sqlist &L) //L本身要改变所以为引用型
{
L.elems = new int[MAXSIZE]; //为顺序表分配内存空间
if(!L.elems) return false; //存储分配失败返回false

//分配成功则初始化
L.length = 0;
L.size = MAXSIZE;
return true; //成功并返回true
}
  • 定义函数 outputInfoList() 用于输出顺序表信息
1
2
3
4
5
6
7
8
9
//输出数据表信息
void outputInfoList(Sqlist &L)
{
cout << "顺序表储存空间" << L.size << ",已经保存元素个数" << L.length << endl;
for(int i = 0; i <= L.length - 1;i++){
cout << L.elems[i] << " ";
}
cout << endl;
}

找查元素

  • 定义函数 findElem() 在顺序表中找查一个等于e的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 用于找查顺序表中的元素
* 参数e为要找查的元素
* 若找到则返回元素下标
* 若没找到则返回-1
*/
int findElem(Sqlist L, int e) //这里我们不改变L,所以不用引用类型
{
for(int i = 0; i < L.length; i++){
if(e == L.elems[i])
return i; //若找到则返回元素下标
}
return -1; //若没找到则返回-1
}

插入元素

尾部添加元素

在尾部添加元素要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 故定义函数 listAppend()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 在顺序表尾部插入元素
* 参数e为要插入到尾部的元素
* 若成功则返回true,失败(顺序表已经满了)则返回false
*/
bool listAppend(Sqlist &L, int e)
{
if(L.length == L.size)
//顺序表满了
return false;
//没满则尾部插入元素并返回true
L.elems[L.length] = e;
L.length++;
return true;
}

在特定位置插入元素

在特定位置插入要考虑以下几点

  • 顺序表是否已满
  • 添加成功后长度要加1
  • 要移动后面的元素而不能移动前面的元素,否则后面的元素会被前面的覆盖

定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//在顺序表p位置(0 <= p <= length)上插入元素e
bool insertElem(Sqlist &L, int p, int e)
{
if(p < 0 || p > L.length || L.length == MAXSIZE)
/*
* 如果位置错误
* 或者表长已经达到最大允许值
* 此时插入不成功并返回false
*/
return false;
for(int i = L.length - 1; i >= p; --i)
//从后往前将元素相后方移动一个位置
L.elems[i+1] = L.elems[i];
L.elems[p] = e; //插入元素e到p位置
L.length++;

return true; //成功返回true
}

删除元素

删除元素要考虑以下几点

  • 顺序表位置是否正确
  • 成功后长度要减去1
  • 后方元素向前移动一个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除p位置的元素
bool delElem(Sqlist &L, int p, int &e)
{
//位置错误返回false
if(p < 0 || p > L.length - 1) return false;
e = L.elems[p]; //将被删除的元素赋值给e
for(int i = p; i < L.length - 1; i++)
{
//从p开始后方元素向前移动一个位置
L.elems[i] = L.elems[i+1];
}

L.length--; //长度减去1
return true; //成功返回true

}

顺序表的销毁

  • 在初始化函数中,用了new来分配内存,所以在销毁时要释放内存
1
2
3
4
5
6
7
void destroy(Sqlist &L)
{
//内存存在则释放内存
if(L.elems) delete []L.elems;
L.length = 0;
L.size = 0;
}

顺序表的概念及定义

顺序表

结点的概念

结点 :结点是内存中一片由用户分配的储存空间,只有一个地址来表示它的存在,没有显式名称。

在学习顺序表时,一般不会去特别强调结点的概念,此概念往往在链表学习中涉及,但并不代表结点与顺序表无关,所以我特意把结点的概念放在此处以加深对顺序表的理解。

顺序表的概念

定义:把逻辑上相邻的结点储存在物理位置上的相邻储存单元中,结点的逻辑关系由储存单元的邻接关系来体现

通俗来讲,顺序表就是把线性表中的所有元素按照其逻辑顺序,依次储存到从指定的储存位置开始的一块连续的储存空间中。

第一个元素的储存位置就是指定的储存位置,第 i+1 个元素的储存位置在第 i 个元素后面

顺序表的特性

  • 占用连续的储存空间:由定义可知顺序表的储存空间必然连续,并且存储分配只能预先进行,一旦分配完毕,在操作过程中始终不变。
  • 随机访问特性:因为储存空间是连续的,知道第一个元素的地址(即储存空间的首地址)可以轻松访问储存的所有数据。每一个结点对应一个序号,由该序号可以直接算出结点的储存地址。

顺序表三要素

  • 顺序表基地址
  • 顺序表长度
  • 顺序表总空间大小

顺序表结构体定义

1
2
3
4
5
6
typedef struct _Sqlist Sqlist;
struct _Sqlist {
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小
};

当然C语言提供了一种简单的写法(如下,以后以简单写法为例)。

1
2
3
4
5
6
typedef struct{
int *elems; //顺序表基地址
int length; //顺序表长度
int size; //顺序表总空间大小

}Sqlist;

在某些书籍上,有这样定义顺序表的

1
#define MAXSIZE 100
1
2
3
4
typedef struct {
int data[MAXSIZE]; //存放顺序表元素的数组
int length; //存放顺序表的长度
}Sqlist;
  • 实际上这种定义已经为顺序表开辟了一部分内存空间,而前者需要使用函数来顺序表初始化。
  • 但实际上两种代码本质上是一样的,因为前者在顺序表的操作——初始化顺序表中的函数定义中,我们仍需要分配一片储存空间并且定义一个存放顺序表元素的数组;而后者相当于把这一步合并到了定义中。
  • 在学习过程而非实际开发中,我更倾向于前者,因为这更能反应顺序表的三要素,并且与链表代码书写风格相似,有利于感受线性表思想的共性。

结束

我们现在已经成功定义顺序表了,但更重要的是它的操作,所以下一篇文章就来写这部分内容。