tags: school class

資料結構

1. 演算法五個條件

輸入input
輸出output
明確性definiteness
有效性finiteness
有限性effectiveness

2. 複雜度

• 時間複雜度 運行花費的時間長短
• 空間複雜度 占用記憶體的程度

big O 代表f(n)的上限

• O(1)
• O(logN)
• O(N)
• O(NlogN)
• O(2N)
• O(N^2)
• O(N^3)
  omega 代表f(n)的下限
  theta 代表f(n)的上限與下限，較精確

3. 排序法

氣泡排序

• 每一回合逐一比較相臨資料，依排序之順序交換位置。
• 每回合至少會有一次交換位置，至沒交換位置則停止。

BubSort(int A[], int n)  //氣泡排序法之副程式
  {
    int i, j , k,t=1, Temp,sp;
    for (i=n-1; i>0; i--)
       {
        sp=1;
        for (j =0; j <=i; j++)
          if (A[j] > A[j+1])
             {  //兩數交換位置
               Temp = A[j];
               A[j] = A[j+1];
               A[j+1] = Temp;
               sp=0;
             }
             if (sp==1) break;          
       }
  }

選擇排序

• 未排序前之第一筆資料可視為已排序好之資料
• 每一回合逐一比較相臨資料，依排序之順序交換位置。

SelSort(int A[], int n)  //選擇排序法之副程式
 {
   int i, j, Temp, NP = 0;
   for (i = 1; i <= n - 1; i++)
    {
       NP = i;
       for (j = i + 1; j <= n; j++)
          if (A[j] > A[NP])  NP = j;
      {//相鄰兩個的資料交換位置
       Temp = A[i];
       A[i] = A[NP];
       A[NP] = Temp;
      }
    }
 }

插入排序

• 將待排序之資料逐一與已排序後之資料比較，再將資料放入適當位置。
• 由最大(最小)逐回合比較至最小(最大)。

InSort(int A[], int n)  //插入排序法之副程式
 {
   int i, j, Temp;
   for (i = 1; i <= n; i++)
    {
     Temp=A[i];
     j=i-1;
     while (Temp<A[j])
      {
        A[j+1]=A[j];
        j--;
        if(j==-1) break;
      }
      A[j+1]=Temp;
    }
 }

快速排序

• 取第一個記錄為鍵值K0，當中間值。
  -由左而右找第一個Ki，使得Ki≧K0。由右而左找第一個Kj，使得Kj≦K0。也就是說，從左邊找比K0大，從右邊找比K0小。
• 若i<j則Ki與Kj對調位置繼續步驟2；否則K0與Kj對調位置，並以j為基準，分為兩個未排序之序列。以遞迴呼叫方式對左右兩邊進行排序，直道完成排序。
• 由最大(最小)逐回合比較至最小(最大)。

QuickSort(int A[], int left, int right)
{
    int i, j, s , Temp;
    if(left < right) {
        s = A[(left+right)/2];
        i = left - 1;
        j = right + 1;
        while(1) {
            while(A[++i] < s) ;  // 向右找
            while(A[--j] > s) ;  // 向左找
            if(i >= j) break;
               Temp = A[i];
               A[i] = A[j];
               A[j] = Temp;
        }
        QuickSort(A, left, i-1);   // 對左邊進行遞迴
        QuickSort(A, j+1, right);  // 對右邊進行遞迴
    }
}

堆積排序

Heapsort(int A[]) {
    int i, m, p, s,t=1;
    m = MAX;
    while(m > 1) {
        SWAP(A[1], A[m]);
        m--;
        p = 1;
        s = 2 * p;
        while(s <= m) {
            if(s < m && A[s+1] < A[s])  s++;
            if(A[p] <= A[s])  break;
            SWAP(A[p], A[s]);
            p = s;
            s = 2 * p;
        }
    }
}

薛爾排序

Shellsort(int A[])
{
    int i, j, k, Gap, t;
    Gap = MAX / 2;
    while(Gap > 0)
     {
        for(k = 0; k < Gap; k++)
        {
            for(i = k+Gap; i < MAX; i+=Gap)
            {
                for(j = i - Gap; j >= k; j-=Gap)
                {
                    if(A[j] > A[j+Gap])
                    {
                        SWAP(A[j], A[j+Gap]);
                    }
                    else  break;
                }
            }
        }
        printf("\nGap = %d：", Gap);
        for(i = 0; i < MAX; i++)
            printf("%d ", A[i]);
        Gap /= 2;
    }
}

合併排序

Mergesort(int A[], int M, int B[],int N, int C[])
 {
    int i = 0, j = 0, k = 0;
    while(i < M && j < N)
    {
        if(A[i] <= B[j])  C[k++] = A[i++];
        else  C[k++] = B[j++];
    }
    while(i < M)  C[k++] = A[i++];
    while(j < N)  C[k++] = B[j++];
}

基數排序

Radix(int data[],int n) 
{   int t=1;
    while(n <= 10)
     {
        for(i = 0; i < 10; i++)
        {
            lsd = ((data[i] / n) % 10);
            temp[lsd][order[lsd]] = data[i];
            order[lsd]++;
        }
        if (t==1)  printf("\n「個位數」為主排序：");
        else   printf("\n「十位數」為主排序：");
        for(i = 0; i < 10; i++)
         {
            if(order[i] != 0)
                for(j = 0; j < order[i]; j++)
                {
                    data[k] = temp[i][j];
                    printf("%d ", data[k]);
                    k++;
                }
            order[i] = 0;
        }
        n *= 10;
        k = 0;
        t+=1;
    }
  }

樹

一個有限的集合，有一或多個節點
分支度-每個節點下分出幾個節點
轉二元樹 左子右兄弟

陣列

連續的空間
資料好尋找
新增資料需要空出位置並移動
移除資料需要移動資料

鏈結串鍊

節省新增移除資料的時間
資料不好尋找