dsa基础

0.概念

数据结构

逻辑结构

• 集合
• 线性
• 树
• 图

物理结构 (存储结构)

• 线性存储 ： 元素存储必须是连续的
• 链式存储 ：指针地址
• 索引存储 ：索引表（关键字 地址）
• 散列存储 （哈希存储）：（关键字 直接计算出内存地址)

复杂度

时间复杂度

事前预估 时间开销$T(n)$与问题规模n的关系
执行次数$x$，$x=f(n)$,复杂度与$f(n)$的数量级$T(n)$
$1<logn<n<nlogn<n^2<n^3<2^n$

估算策略

• 忽略顺序执行语句
• 只关注循环部分，且关注其中的一个循序语句
• 只关注嵌套循环中最深层中的执行语句

空间复杂度

与内存空间(通常与字节为单位)

估算策略

找到所占空间与问题规模相关的变量

1. 线性表

数据元素的数据类型相同
有序
数量有限

索引：–> 位序
第一个元素：表头
前一个元素：直接前驱
后一个元素：直接后继

顺序表(数组)

顺序(连续)存储

• 随机访问(随机存取)

O(1)

• 插入、删除

O(n)

• 查找

按位查找： O(1) ，因为是随机存取的
按值查找： O(n)

链表

链式存储

单链表

• 带头结点

• 不带头结点 -建议使用

• 插入、删除 (按位序) ???

O(n) 相当于查找耗时

• 查找

O(n)

• 尾插法

普通尾插法$O(n^2)$ – 见例子 ‘dsa-cpp’

双链表

在单链表的基础上，加上一个指向prior的前向指针

循环链表

在单链表的基础上，最后的一个尾结点指向了头结点
给定一个节点，可以找到链表中的任意其他节点（单链表只能找到该节点的后继节点）

静态链表

单链表在内存中是随机存储的
静态链表在内存中是连续存储（注意：不是顺序存储）的
头结点的地址+游标*字节大小

顺序表/链表

• 顺序表

顺序存储、随机存取
连续内存分配不方便，插入删除不方便

• 链表

链式存储，不能顺序存取
离散空间分配方便，插入删除方便

栈

只允许在一端进行插入或删除操作的线性表
后进先出(LIFO)

顺序栈

增删改查 O(1)

链式栈

一般使用头插法

队列

只允许在一端进行插入，在另一端删除的线性表
先进先出(FIFO)

这里讨论的循环队列

顺序循环队列

利用数组实现

第一种实现方法 – 见例子
在某些情况下会浪费一个存储空间

链表队列

利用链表实现

双端队列

运算两端插入、两端删除

2. 递归

见C语言教程文档
实际上是 函数调用栈
函数调用

调用返回地址
实参
局部变量

void main()
{
    int a,b,c;
    func1(a,b);
    c=a+b;
}

void func1(int a,int b)
{
    int x;
    func2(x);
}

void func2(int x)
{
    int m,n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

func1()的地址，func1() 函数中的局部变量a,b
main() 函数中的局部变量 a,b
main()

---

递归与栈

阶乘例子

#include 
using namespace std;

int factorial(int n)
{
    if (n==0 || n==1)
    {
        return 1;
    }
    else
    {
        return n*factorial(n-1);
    }
}

int main()
{
    int x=factorial(10);
    cout<<x<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

3. 矩阵

对称矩阵

行优先存储下
一维数组下标与对称矩阵数据下标的映射函数
eg1：假设一维数组是从0开始；二维数组（不是下图所示）也是从0开始的：
$a[i][j]-->a[i\ast \frac{i+1}{2}+j]$
$1+2+...+(i)+(j+1)-1=i\ast \frac{i+1}{2}+j$

eg2：假设一维数组是从0开始；二维数组（如下图所示）也是从1开始的：
$a[i][j]-->a[(i-1)\ast \frac{i}{2}+j-1]$
$1+2+...+(i-1)+j-1=(i-1)\ast \frac{i}{2}+j-1$

三角矩阵

• 上三角
• 下三角

见王道视频

稀疏矩阵

• 方法1

顺序存储： 三元组<行，列，值>
结构体数组

• 方法2

链式存储：十字链表法

4. 字符串

索引从0开始
位序/位置从1开始

字符串是一种特殊的线性表

数组形式

• 静态存储

char ch[]

• 动态存储

char *ch=(char *)malloc(length*sizeof(char))

链表形式

链表形式存储