数据结构与算法-REVIEW

Chapter 1: Introduction

数据结构的定义（最多出现选择题/填空题）

What is Data Structure

1. Data
   • is the carrier of information
   • is a set of numbers, characters and other symbols
   • Data can be divided into two classes：
     numerical data：int, float, complex…
     non-numerical data：character, string, graph, voice…
2. Data Structure
   • A data structure is a data object together with the relationships among the data members that compose the object.
   • Data Structure = {D, R}
     D：a data object
     R：a limited set of relationships of all the data members in D
   • linear structure / non-linear structure

数据结构分层

• 数据的逻辑结构：从用户视图看，是面向问题的
• 数据的物理结构：从具体实现视图看，是面向计算机的
• 相关的操作及其实现
• Example：学生表
  逻辑结构：线性表
  物理结构：数组 / 链表
  操作：插入 / 删除 / 查找

Algorithm Definition（很少考，曾考过大题）

Algorithm：an operation sequence of soluting a problem
Properties：

1. Input Specified
2. Output Specified
3. Definiteness
4. Effectiveness
5. Finiteness

递归算法（物理层是重点）

two fundamental rules of recursion：1. base cases；2. making progress

1. direct recursion 自递归
2. indirect recursion 互递归

static long factorial(int n) {
    if(n <= 1) return 1;
	else return n * factorial(n-1);
}

// permutation 全排列
public static void perm(char[] list, int k, int m) {
    if(k == m) {
        for(int i=0; i<=m; i++) cout << list[i];
        cout << endl;   
    }
    else {
        for(int i=k; i<=m; i++) {
            swap(list[k], list[i]);
            perm(list, k+1, m);
            swap(list[k], list[i]);
        }
    }
}
// m 是数组最后一个元素的下标, k 是把数组分为两个部分的指标
// 递归到 m-1 个元素的全排列和 m 个元素全排列的递推关系
// 用循环找递推关系：每次把单独拿出来的元素跟后面全排列中的某一个元素交换顺序

// hanoi tower problem
public void moveDISKs(int n, char fromTower, char toTower, char auxTower) {
    if (n == 1) Move disk 1 from the fromTower to the toTower;
    else {
        moveDISKs(n-1, fromTower, auxTower, toTower);
		Move disk n from the fromTower to the toTower;
		moveDISKs(n-1, auxTower, toTower, fromTower);
    }
}

C语言不断调用函数就是不断压栈的过程，每调用一个新函数则新创建一个栈空间（调用构成回路即构成递归）

ADT and OO

• ADT：Abstract Data Types
  是将类型和与这个类型有关的操作封装在一起的数据模型
• OO：
  1. object-oriented = object + class + inherit + communicate
  2. object：attribute values + operates

程序和算法的不同点

• Program：is written by languages that can be performed by machine.
  can not satisfy the finiteness. For example, OS.
• Algorithm：has multiple descriptive methods, such as language, graph, table.

Chapter 2

Space Complexity and Time Complexity

1. Space Complexity：the amount of memory a program needs to run to completion
2. Time Complexity：the amount of time a program needs to run to completion

Space Complexity

// Sequential Search
public static int SequentialSearch(int[] a, int x) {
    int i;
    for(i=0; i<a.length&&a[i]!=x; i++);
    if(i == a.length) return -1;
    return i;
}

• 0 / -1 放不放栈内存？ –> 取决于编译器。
• total data space：x, i, a[i], 0, -1, a.length –> 6*int [each of them costs 2 bytes]
• a数组中数据增加？ –> 实际传入的是引用，数据增加并不影响。
• S(n) = 0
• The best comparison count is one, the worst is n.
• The average count for a successful search is：（隐含假设：等概率）

  // recursive code to add a[0: n-1]
  public static float Rsum(float[] a, int n) {
      if(n > 0) return Rsum(a, n-1) + a[n-1];
      return 0;
  }

• recursion stack space：a, n, 0
• depth of recursion：n+1
• S(n) = 6(n+1) [6? each of them costs 2 bytes]

PPT上的计算方法：

Time Complexity

// finding the largest number in a[0: n-1]
public static int Max(int[] a, int n) {
    // locate the largest element in a[0: n-1]
    int pos = 0;
    for(int i=1; i<n; i++) {
        if(a[pos] < a[i]) pos = i;  // key operation
    }
    return pos;
}

• i < n：n次
• i++：n-1次
• compare time：n-1次

排序算法

选择排序

• the number of element move is 3(n-1)
• the total number of comparisons is (n-1)+(n-2)+…+3+2+1=n*(n-1)/2

（swap：需要临时存储空间 移动次数按三次计）

public static void SelectionSort(int[] a, int n) {
    // sort the n numbers in a[0: n-1]
    for(int size=n; size>1; size--) {
        int j = Max(a, size);
        swap(a[j], a[size-1]);
    }
}

冒泡排序

• the number of comparisons is n*(n-1)/2

public static void Bubble(int[] a, int n) {
    // bubble largest element in a[0: n-1] to right
    for(int i=0; i<n-1; i++)
        if(a[i] > a[i+1]) swap(a[i], a[i+1]);
}
public static void BubbleSort(int[] a, int n) {
    // sort a[0: n-1] using a bubble sort
    for(int i=n; i>1; i--)
        Bubble(a, i);
}

秩排序

• the number of element comparison is n*(n-1)/2
• the number of element swap is 2n

public static void Rank(int[] a, int n, int[] r) {
    // rank the n elements a[0: n-1]
    for(int i=0; i<n; i++) r[i] = 0;
    for(int i=1; i<n; i++) {
        for(int j=0; j<i; j++) {
            if(a[j] < a[i]) r[i]++;
            else r[j]++;
        }
    }
}
public static void Rearrange(int[] a, int n, int[] r) {
    // in-place rearrangement into sorted order
    for(int i=0; i<n; i++) {
        while(r[i] != i) {
            int t = r[i];
            swap(a[i], a[t]);
            swap(r[i], r[t]);
        }
    }
}

插入排序

• the number of comparisons
  • the best case is n-1
  • the worst case is (n-1)*n/2
• move number
  • the best case is 2*(n-1)
  • the worst case is
    (1+2) + (2+2) + … + (n-2+2) + (n-1+2) = (n-1)*n/2 + 2*(n-1) =

public static void Insert(int[] a, int n, int[] x) {
    // insert x into the sorted array a[0: n-1]
    int i;
    for(i=n-1; i>=0&&x<a[i]; i--)
        a[i+1] = a[i];
    a[i+1] = x;
}
public static void InsertionSort(int[] a, int n) {
    for(int i=1; i<n; i++) { // 此处可以从i=1开始
        int t = a[i];
        Insert(a, i, t);
    }
}

Asymptotic Notation（）

1. 给出上界（不可以到达上界）
2. 给出上界（可以到达上界）
3. 给出下界
4. 相同量级

Selection Sort

for(int i=0; i<n-1; i++) {        // n
    int k = i;                    // n-1
    for(int j=i+1; j<n; j++)      // (n+2)(n-1)/2
        if(a[j] < a[k]) k = j;    // <=n(n-1)/2
    swap(a[i], a[k]);             // 3(n-1)
}
// T(n) = O(n^2)

Binary Search

• best：1
• worst：
• average：

  public static int BinarySearch(Comparable[] a, Comparable x) {
      int low = 0, high = a.length-1;
      while(low <= high) {
          int mid = (low + high) / 2;
          if(a[mid].compareTo(x) < 0) low = mid+1;
          else if(a[mid].compareTo(x) > 0) high = mid-1;
          else return mid;
      }
      return NOT-FOUND;
  }

MAXIMUM SUBSEQUNCE SUM PROBLEM

Algorithm 1 穷举法：

public static int maxSubSum1(int[] a) {
    int maxSum = 0;
    for(int i=0; i<a.length; i++) {
        for(int j=i; j<a.length; j++) {
            int thisSum = 0;
            for(int k=i; k<=j; k++) thisSum += a[k];
            if(thisSum > maxSum) maxSum = thisSum;
        }
    }
    return maxSum;
}
// O(n^3)

Algorithm 2：

public static int maxSubSum1(int[] a) {
    int maxSum = 0;
    for(int i=0; i<a.length; i++) {
        int thisSum = 0;
        for(int j=i; j<a.length; j++) {
            thisSum += a[j];
            if(thisSum > maxSum) maxSum = thisSum;
        }
    }
    return maxSum;
}
// O(n^2)

Algorithm 3 分治法：

private static int maxSumRec(int[] a, int left, int right) { 
	if (left == right)
        if (a[left] > 0) return a[left];
    	else return 0;
    int center = (left + right) / 2;
    int maxLeftSum = maxSumRec(a, left, center);
    int maxRightSum = maxSumRec(a, center+1, right);
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for(int i=center; i>=left; i--) { 
        leftBorderSum += a[i];
        if(leftBordersum > maxLeftBorderSum)
        maxLeftBorderSum = leftBorderSum;
    } 
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for(int i=center+1; i<=right; i++) {
        rightBorderSum += a[i];
        if(rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum;
    }
    return max3( maxLeftSum, maxRightSun, maxLeftBorderSum + maxRightBorderSum );
}
public static int maxSubSum3(int[] a) { 
    return maxSumRec(a, 0, a.length – 1);
}
// O(nlogn)

Euclid’s Algorithm 辗转相除法

// 计算最大公因数
public static long gcd(long m, long n) { 
    while( n != 0 ) { 
        long rem = m % n;
        m = n;
        n = rem;
    }
    return m;
}
// O(logn)