YeeKal

c3

YeeKal • •
"#"

Data Structure and Algorithm

Data Type

intro

对象和操作的总称

Built-in Data Type:

  • Intergers
  • boolean
  • Floating
  • char

Derived Data Type

  • Array
  • List
  • Quene
  • Stack

ADT:

algorithm: method for solving problems

data structure: method to store information

data types

sorting

searching

graphs

strings

性能分析

复杂性理论

complexity theory

空间复杂性：存储空间

时间复杂性：运行时间

程序步：program step

渐进记号

大O

性能测量：performance measurement

//way1
#include<time.h>
start=clock();
stop=clock();
duration=((double)(stop-start))/CLK_TCK
//way2
start=time(NULL);
stop=time(NULL);
duration=(double)difftime(stop-start);

array and struct

correspondence: 对应

mapping: 映射

dereference: 复引用

call-by-value: 传值

self-referential structure: 自引用结构

sparse matrix

稀疏矩阵，包含有很多零元素

ADT SparseMatrix

struce SparseMatrix{
  objects:
    <col,row,val>;
  functions:
    Creat();
    Transpose();
    Output();
    Add();
    Multiply();
}

Linked List

linked list is an obstraction and C pointer is a concrete representation

​ In C, pointers provide a direct and convenient concrete realization of the abstract concept of a linked list, but the essential value of the abstration does not depend on any particular implementation.

types:

  • circular

  • head pointers,null tail

  • dummy head node,null tail

c head=(struct node*)malloc(sizeof(struct node)); head->next=NULL;

  • dummy head and tail nodes

  • doubly-linked list:prev/next

the final node:

  • null link that points to no node
  • dummy node that contains no node
  • refers to the first node, making a circular list

list-processing interface

link newNode(int);
void freeNode(link);
void insertNext(link,link);
link deleteNext(link);
link Next(link);

basic algorithms

typedef struct node* link;
struct node{Item item;link next};
//pointers for links
//structures for nodes

//memory allocation
link x=(link)malloc(sizeof(struct node));

//deletion
x->next=x->next->next;//only remove
t=x->next;x-next=t->next;free(t);//free
//insertion
t->next=x->next;
x->next=t;
/*simplicity of insertion and deletion
not in 'find kth items'*/

//traverse
for(t=x;t!=NULL;t=t->next) visit(t->item);

Josephus problems(约瑟夫问题)

code: 6/22

memory allocation

string

while(*a++=*b++) ;//copy string

Compound Data Types

二维数组内存分配

int **a=malloc2d(m,n);
int **malloc2d(int r,int c){
  int i;
  int **t=(int **)malloc(r*sizeof(int *));
  for(i=0;i<c;i++)
    t[i]=(int *)malloc(c*sizeof(int));  
  return t;
}

graph

a set of objects(called vertices) and a set of connections(called edges)

realization

  • adjacency-matrix
  • adjacency-list

union-find

dynamic connectivity

ADT

pushdown stack(下堆栈)

算术表达式

5*( ( (9+8)*(4*6) )+7)

5 9 8 + 4 6 * * 7 + *

  • 后缀表达式（省去括号）
  • 中缀表达式（正常书写）

实现原理

每个操作数解释为“push”

每个操作符解释为“pop”

realization

  • 数组
  • 链表

#链表

typedef int Item;
typedef struct node* link;
struct node {
    Item item;
    link next;
};

interface

void StackInit();
int StackEmpty();
void StackPush(Item item);
Item StackPop(void);

clients

int main(int argc, char *argv[]) {
    char *a = argv[1];
    int i, n = strlen(a);
    StackInit();
    for (i = 0; i < n; i++) {
        if (a[i] == '+')
            StackPush(StackPop() + StackPop());
        if(a[i]=='*')
            StackPush(StackPop()*StackPop());
        if ((a[i] >= '0') && (a[i] <= '9'))
            StackPush(a[i]);
    }
    printf("result:%d", StackPop());
    return 0;
}

FIFO

frist-in, first-out

recursion

divide and conquer(分治法)

derive max number

hanoi

汉诺塔-分治-递归

自底向上

Dynamic Programming(动态规划)

intro

基本思想：

  • 每次决策依赖于当前状态，又随即引起状态的转移
  • 与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

适用情况

  1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
  2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
  3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

0/1 背包问题

  1. mp[0][y] = 0
  2. mp[x][0] = 0
  3. 当 v[x] > y 时，mp[x][y] = mp[x-1][y]
  4. 当 v[x] <= y 时，mp[x][y] = max{ mp[x-1][y], p[x] + mp[x-1][y-v[x]] }
for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= v; j++) {
            if (ps[i - 1].wei > j)
                maxv[i][j] = maxv[i - 1][j];
            else {
                maxv[i][j] = max(maxv[i - 1][j], ps[i-1].val + maxv[i - 1][j - ps[i-1].wei]);
            }
        }
    }

tree

定义

  • 节点
  • 两节点路径唯一
  • 根节点(root node)
  • 父节点(parent)
  • 子节点(children)
  • 兄弟节点(sibling)
  • 叶节点/终结点(leave/terminal node)
  • 深度，depth

types

  • binary tree 二叉树
  • m叉树
  • 有序树

vs 图

树是图的一种

树的数学性质

  1. 一颗有n个内部节点的二叉树有（n+1）个外部节点
  2. 妈的，好烦

初始化

树的遍历

递归算法（preorder,inorder,postorder）

非递归（层序，栈与队列）

树参数

  • countNode()
  • countHeight()

图

深度优先搜索

排序

​ 如果排序后文件中具有相同关键字的相对位置保持不变，称一个排序方法是稳定的。

选择排序

插入排序

冒泡排序

希尔排序(Shell Sort)

插入排序的改进版本。不是一个元素一个元素的比较，而是初期选用大跨度比较，然后缩小增量直至为1.

快速排序

重点在分治算法上。第一个是参考值的选择，第二个是以参考值排序的单边和双边算法。

void quickSort(int *numP, int s, int e) {
    int i;
    if (e > s) {
        i = partion2(numP, s, e);
        quickSort(numP, s, i - 1);
        quickSort(numP, i + 1, e);
    }
}
int partion1(int *numP, int s, int e) {
    //choose the referance num
    //ways to interchange two nums
    //two sides to find 
    int val;
    val = numP[e];
    int left=s-1, right=e;
    while (1) {
        while (numP[++left] < val);
        while (numP[--right] >= val)
            if (right == s)
                break;
        if (left >= right)
            break;
        swap(numP, left, right);
    }
    swap(numP, left, e);
    return left;
}
int partion2(int *numP, int s, int e) {
    //choose the referance num
    //ways to interchange two nums
    //one side to find 
    int val, num;
    val = numP[e];
    num = s;
    for (int i = s; i < e; i++) {
        if (numP[i] < val)
        {
            swap(numP, num, i);
            num++;
        }
    }
    swap(numP, num, e);
    return num;
}

归并排序

稳定的排序算法

堆(heap)

堆操作

优先队列(priority quene)，但不是队列。按照优先级取出元素。（一堆堆）

堆的一个经典实现是完全二叉树(omplete binary tree), 该堆又叫做二叉堆(binary heap).完全二叉树是指上层必须填满，最底层从左到右填满。完全二叉树中若任意节点的优先级不小于（不大于）子节点就是堆。最大堆与最小堆（max heap/min heap）

adt

  • maxHeap create(max_size); //创建空堆
  • maxHeap insert(heap,item ,n); //插入元素
  • item delete(heap,n); //删除最大元素

由于需要对堆有频繁的插入与删除操作，大部分堆的底层通过数组实现，即按照完全二叉树的结构顺序排列。完全树是保证数组表示堆的方便性而加的条件。这样每一个处于顺序位置为n的子节点，其父节点顺序位置是n/2

堆实现

create

倘若用指针动态分配内存，则数组数据不便删除，并且动态分配之后需要删除数据时每次都需要重新创建。或者就把数据放在最后，第一位记录个数的方式隐世删除，但这种方式依然不能绝对自由的动态添加元素。

insert

新插入的元素先放在最后的位置，之后再跟父节点比较，直到恢复有序结构。

delete

删除根节点，将堆的最后一个元素放到跟节点，之后与子节点比较，两个节点都要比较，直到形成稳定结构。

堆排序

  • 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
  • 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
void heapSort(int *heap, int size) { //sort
    createHeap(heap, size);
    for (; size >1;) {
        swap(heap, 0, size - 1);
        size--;
        maxHeapify(heap, size, 1);
    }
}
void createHeap(int *heap,int size) {//create from array
    int t = size / 2;
    for (; t>0; t--) {
        maxHeapify(heap, size, t);//from bottom to top
    }
}
void maxHeapify(int *heap, int size, int s) {//adjust
    int index_father = s;
    int index_child = 2 * index_father;
    int index_child2 = index_child + 1;
    int index_mid;
    while (1) {
        if (index_child > size)
            return;
        else if (index_child2 > size)
            index_mid = index_child;
        else {
            if (heap[index_child - 1] > heap[index_child2 - 1])
                index_mid = index_child;
            else
                index_mid = index_child2;
        }
        if (heap[index_mid - 1] > heap[index_father - 1])
            swap(heap, index_mid - 1, index_father - 1);
        else
            return;
        index_father = index_mid;
        index_child = 2 * index_father;
        index_child2 = index_child + 1;
    }
}
← Back to cpp