408复习暨面试复习---数据结构

按理来说,应该先夯实数学的基础,但是,李老师说的一句话很对,研究生什么时候都能考,但是校招在本科阶段就那么一次,说实话,我很摇摆不定,但是我真的不是很想读了,三年的时间成本过于巨大了,国内研究生教育又没有那么有含金量,镀金什么时候都可以镀,这样盲目的跟大流,真的能知道自己想要什么吗?怕不是研究生读完,还是像现在一样盲目。

所以先开启408,反正不亏。

增删查改

线性表

顺序表示

插入 O(n)
删除 O(n)
查询 O(1)

链表表示

插入 O(1)
删除 O(1)
查询 O(n)

单链表
循环链表

应用

多项式运算?
不是用set就解决了吗?

一些话

线性表只是逻辑结构,使用不同的物理结构会导致复杂度的不同,线性表只是抽象的一类东西。

栈、队列(递归)

很奇怪,面试中,会有这类的题,就我的经验来看,栈、队列都是数组的严格化,复杂度不变,但常数小了,所以快了,面试的时候就会搞你,这时候注意一下吧。

顺序栈
链式栈

应用

表达式求值

这倒是要和编译原理扯上了
后缀表达式(逆波兰式)
简单来讲就是 操作数,紧跟操作符(根据操作符性质取操作数)
(32-26)*5+28/4

32 26 - 5 * 28 4 / +

栈和卡特兰数
对于一个{1,2,...,n}入栈序列,它有几种出栈序列呢?
卡特兰数,可以开专题了...
简单dp问题 $dp_{xy}$: x次入栈,y次出栈时的序列数

#include<iostream>
#include<string.h>
using namespace std;
int dp[10][10];
int dfs(int x,int y){
    if(dp[x][y]!=-1) return dp[x][y];
    if(x>y) return -2;
    int x1=x-1,y2=y-1;
    int &val = dp[x][y];
    val = 0;
    if(x1<=y) val+=dfs(x1,y);
    if(x<=y2) val+=dfs(x,y2);
    return val;
}

int main()
{
    memset(dp,-1,sizeof dp);
    dp[0][0]=1;
    dfs(9,9);
    for(int i=0;i<9;i++)
    printf("%d\n",dp[i][i]);
    return 0;
}

队列....

递归....

字符串、数组、广义表

kmp
给个板子,慢慢啃

基本概念:堂兄弟。

二叉树

满二叉树:h = $log_2(n+1)$ 或者说反过来:n = $2^h-1$
完全二叉树:努力向满二叉树奋斗,但还是差一点,差在哪里呢? 最右侧的几个树叶节点没了。 $2^{n-1}<n+1<2^{h}$

$$分支数 = 度为0节点(数量)+度为1节点(数量)+度为2节点(数量)-1$$

$$0*d_0+1*d_1+2*d_2 = d_0 + d_1 + d_2 -1$$

$$d_2 = d_0 - 1$$

顺序二叉树和链式二叉树
数组的二叉树:

  • 根结点为0 lr——son$2*n+1$ 和 $2*n+2$ father$\left \lceil i/2 \right \rceil -1$
  • 根结点为1 lr——son$2*n$ 和 $2*n+1$ father$\left \lfloor i/2 \right \rfloor$

先序遍历:访问到就出栈
中序遍历:左,中,右
后序遍历:左,右,中

三者得二,可得二叉树

线索二叉树:把树叶节点闲置的null指针指个地方,前驱或后继,看是怎么遍历的。

这些就是二叉树:堆,哈夫曼树

//用数组模拟堆
//1-把无序的数组调整为最小堆
//2-插入 调整
//3-删除
#include<bits/stdc++.h>
using namespace std;
int heap[100];
int a[10];
int cursize=10;
void pre()
{
    for(int i=0;i<10;i++){
        a[i] = rand()%100;
        heap[i] = a[i];
    }
}
int fa(int leaf){
    return (leaf-1)/2;
}

void filterdown(int v){
    int son = 2*v+1;
    while(son<cursize){ //从0开始
        if(son+1<cursize && heap[son+1]<heap[son])
            son++;
        if(heap[v]<=heap[son]) break; 
        else{
            swap(heap[v],heap[son]);
            v = son;
            son = v*2+1;
        }
    }
}
void shifttoheap(){
    int st=(cursize-1)/2;
    for(int i=st;i>=0;i--)
        filterdown(i);
}

void filterup(int u){
    int v=fa(u);
    while(u>0){
        if(heap[u]>=heap[v]) break;
        else{
            swap(heap[u],heap[v]);
            u = v;
            v = fa(u);
        }
    }
}
void insert(int val){
    heap[cursize++] = val;
    filterup(cursize-1);
}

void Delete(int pos){
    heap[pos] = heap[cursize-1];
    cursize--;
    filterdown(pos);
}
void showa()
{
    for(int i=0;i<cursize;i++) printf("%d ",a[i]); puts("");
}
void showheap()
{
    for(int i=0;i<cursize;i++) printf("%d ",heap[i]); puts("");
}
int main()
{
    pre();
    showa();
    shifttoheap();
    showheap();
    insert(-1);
    showheap();
    Delete(0);
    showheap();
    return 0;
}

添加新评论