Linked List Table Sort、Doubly Linked List Table Sort

typedef struct TreeNode
{
int Data;
int Link, Linkb;
}TreeNode;

小算盤各項功能

1. 按一下 [檢視] 功能表，然後按一下 [工程型]。

2. 鍵入或按一下您的第一頁資料，然後按一下 [Sta] 以開啟 [統計方塊] 對話方塊。

3. 按一下 [RET] 以返回 [小算盤]，然後按一下 [Dat] 以儲存數值。

4. 鍵入或按一下其餘資料，在每次輸入完後按一下 [Dat] 。

5. 按一下 [Ave]、[Sum] 或 [s]。

注意
[Ave] 會計算 [統計方塊] 對話方塊中儲存之值的平均數，[Sum] 會計算值的總和，而 [s] 則會計算標準差。
輸入所有資料之後，您可以按一下 [Sta] 來查看清單。
[統計方塊] 對話方塊的底部會提供您已儲存之值數目的追蹤。您可以按一下 [CD] 來刪除清單中的特定數值，或按一下 [CAD] 來刪除所有值。按一下 [LOAD] 會將 [小算盤] 顯示區的數字，變更為 [統計方塊] 對話方塊中選取的數字。

如何使用儲存在記憶體中的數字？
將數字儲存在記憶體中時，記憶體選項上方的方塊中會出現 [M]。存入其他數字時，目前在記憶體中的數字將被置換。 您可以透過下列方式使用儲存在記憶體中的數字：

‧ 若要儲存顯示的數字，請按一下 [MS]。

‧ 若要恢復儲存的數字，請按一下 [MR]。

‧ 若要清除記憶體，請按一下 [MC]。

‧ 若要將顯示的數字與記憶體中已有的數字相加，請按一下 [M+]。若要查看新數字，請按一下 [MR]。


如何在 [標準型] 和 [工程型] 兩種檢視之間傳送數字？

1. 按一下 [MS] 以儲存顯示的數字。

2. 按一下 [檢視] 功能表，然後按一下所要的檢視。

3. 按一下 [MR] 以恢復儲存的數字。

注意
[小算盤] 在 [標準型] 和 [工程型] 兩種檢視之間做切換時會清除顯示。
以十六進位、八進位或二進位格式所輸入的數字，在從 [工程型] 傳送至 [標準型] 檢視時會轉換成十進位格式。

如何將數值轉換成另一個數字系統？

1. 按一下 [檢視] 功能表，然後按一下 [工程型]。

2. 輸入您要轉換的數字。

3. 按一下您要轉換的目標數字系統。

4. 按一下您要使用的顯示大小。

注意
當您要將某個含小數的十進位數字，轉換為另一個數字系統時，該數字會縮短成一個整數。
從十六進位、八進位或二進位轉換為十進位的數字會顯示為正整數。

執行大型數字計算時會發生什麼？
在十六進位、二進位以及八進位數字系統中，當結果位數比顯示大小所允許的數字位數多時，[小算盤] 在顯示結果時僅會顯示較低的位數。此行為模擬電腦中計算的方式。

針對十六進位數字系統，QWORD 結果可以包含到 16 位數 (64 位元)，DWORD 結果可以包含達 8 位數 (32 位元)；「文字」結果可以包含到 4 位數 (16 位元)；而「位元組」結果可以包含到 2 位數 (8 位元)。

例如， 使用字組所顯示的十六進位數字系統，可以產生的最大結果是 FFFF (在十進位系統中等於 65535)。如果將數字加倍 (FFFFx2)，答案會是 1FFFE。這包含了 5 位數，所以 [小算盤] 將僅會顯示答案的後 4 位數：FFFE。

如何檢視按邏輯群組的數字？
您可以使用數字分位以檢視按邏輯群組的數字。如果要這樣做，請按一下 [檢視] 功能表，然後按一下 [數字分位]。

所有按鈕的功能為何？
下表說明 [小算盤] 的功能：

按鈕
功能

%
以百分比顯示相乘的結果。請輸入一個數字，按一下 [*]，然後輸入第二個數字，再按一下 [%]。例如，50 * 25% 將顯示為 12.5。您也可執行具有百分比符號的運算。請輸入一個數字，按一下運算子 ([+]、[-]、[*] 或 [/])，然後輸入第二個數字，按一下 [%]，再按一下 [=]。例如，50 + 25% (指的是 50 的 25%)= 62.5。

(
開始括弧的新層次。目前的層次數會出現在 [)] 按鈕上方的方塊中。最大的層次數是 25。

)
關閉括弧的目前層次。

*
乘法。

+
加法。

+/-
變更顯示數字的符號。

-
減法。

.
插入小數點。

/
除法。

0–9
將這個數字放在小算盤顯示畫面。

1/x
計算顯示數字的倒數。

=
在前兩個數字執行任何運算。若要重複上個運算，請再按一下 [=]。

A–F
在數值中輸入選取的字母。 只有在開啟十六進位模式時才可使用此按鈕。

And
計算逐位元 AND。 除非輸入整數，否則無法定義邏輯運算子的行為。

Ave
計算 [統計方塊] 中顯示之值的平均數。若要計算平方的平均數，請使用 [Inv] + [Ave]。 必須先按一下 [Sta] 才能使用這個按鈕。

backspace
刪除顯示數字的最後一位數。

Bin
將顯示數字轉換成二進位數字系統。最大的不帶正負號的二進位數字是一個 64 位元的表示式，全都設為 1。

C
清除目前的計算。

CE
清除顯示的數字。

cos
計算所顯示數字的餘弦函數。若要計算反餘弦，請使用 [Inv] + [cos]。若要計算雙曲線餘弦，請使用 [Hyp] + [cos]。若要計算反雙曲線餘弦，請使用 [Inv] + [Hyp] + [cos]。[cos] 只可用於十進位系統。

Dat
在 [統計方塊] 對話方塊中輸入顯示的數字。 必須先按一下 [Sta] 才能使用這個按鈕。

十進位
將顯示數字轉換成十進位數字系統。

Degrees
在十進位模式中將三角函數輸入設定為度數。

dms
將顯示的數字轉換成「度-分-秒」的格式 (假設顯示的數字為角度)。若要將顯示的數字轉換為度 (假定顯示的數字為度-分-秒格式)，請使用 [Inv] + [dms]。[dms] 只能用於十進位系統。

Exp
讓您可以輸入以工程記號表示法的數值。指數最多可為四位數。指數中只可使用十進位數字 (鍵 0-9)。[Exp] 只能用於十進位數字系統。

F-E
開啟及關閉工程記號表示法。大於 10^32 的數字一定是以指數型式表示。[F-E] 只能用於十進位系統。

Grads
在十進位模式中將三角函數輸入設定為斜率。

十六進位
將顯示數字轉換成十六進位數字系統。無正負符號的十六進位數值的最大值是 64 位元，全部設定為 1。

Hyp
設定 [sin]、[cos] 以及 [tan] 的雙曲線函數。 這些函數會在計算完畢之後，自動關閉雙曲線函數。

Int
顯示十進位數的整數部分。若要顯示十進位數的分數部分，請使用 [Inv] + [Int]。

Inv
設定 [sin]、[cos]、[tan]、[PI]、[x^y]、[x^2]、[x^3]、[ln]、[log]、[Ave]、[Sum] 以及 [s] 的反函數。 這些函數會在計算完畢之後，自動關閉反函數。

ln
計算自然對數 (以 e 為底)。若要計算 e 的 x 次方 (其中 x 是目前的數字)，請使用 [Inv] + [ln]。

log
計算常用對數 (以 10 為底)。若要計算 10 的 x 次方，請使用 [Inv] + [log]。

Lsh
向左移位。若要向右移位，請使用 [Inv] + [Lsh]。按一下這個按鈕以後，您必須指定 (以二進位) 要將顯示區中的數字向左移幾位或向右移幾位，再按 [=]。 除非輸入整數，否則無法定義邏輯運算子的行為。

M+
將顯示的數字新增到已存在記憶體中的任何數字，但不顯示這些數字的總和。

MC
清除儲存在記憶體中的全部數字。

Mod
顯示 x/y 的模數或餘數。請將此按鈕當作二元運算子來使用。例如，若要計算 5 除以 3 的模數，請按一下 [5] [MOD] [3] [=]，結果會等於 2。

MR
喚回儲存在記憶體中的數字。數字仍會保留在記憶體中。

MS
將顯示數字存放在記憶體中。

n!
計算所顯示數字的階乘。

Not
計算反逐位元。 除非輸入整數，否則無法定義邏輯運算子的行為。

八進位
將顯示數字轉換成八進位數字系統。最大的無正負符號八進位值是 64 位元，全部設定為 1。

Or
計算逐位元 OR。 除非輸入整數，否則無法定義邏輯運算子的行為。

pi
顯示 pi (3.1415...) 的值。若要顯示 2 * pi (6.28...)，請使用 [Inv] + [pi]。[pi] 只能用於十進位數字系統。

Radians
在十進位模式中將三角函數輸入設定為徑度。

s
計算總體參數為 –1 的標準差。若要計算總體參數為 n 的標準差，請使用 [Inv] + [s]。 必須先按一下 [Sta] 才能使用這個按鈕。

sin
計算所顯示數字的正弦。若要計算反正弦，請使用 [Inv] + [sin]。若要計算雙曲線正弦，請使用 [Hyp] + [sin]。若要計算反雙曲線正弦，請使用 [Inv] + [Hyp] + [sin]。[sin] 只能用於十進位系統。

sqrt
計算顯示數字的平方根。

Sta
顯示 [統計方塊] 對話方塊，並啟動 [Ave]、[Sum]、[s] 以及 [Dat]。

Sum
計算 [統計方塊] 對話方塊中顯示之值的總和。若要計算平方的總和，請使用 [Inv] + [Sum]。 必須先按一下 [Sta] 才能使用這個按鈕。

tan
計算所顯示數字的正切函數。若要計算反正切，請使用 [Inv] + [tan]。若要計算雙曲線正切，請使用 [Hyp] + [tan]。若要計算反雙曲線正切，請使用 [Inv] + [Hyp] + [tan]。[tan] 只可用於十進位數字系統。

Xor
計算互斥逐位元 OR。 除非輸入整數，否則無法定義邏輯運算子的行為。

x^2
計算所顯示數字的平方。若要計算平方根，請使用 [Inv] + [x^2]。

x^3
計算所顯示數字的立方。若要計算立方根，請使用 [Inv] + [x^3]。

x^y
計算 x 的 y 次方。此按鈕為二元運算子。例如，若要計算 2 的 4 次方，請按 2 x^y 4 =，結果為 16。若要計算 x 的開 y 次方根，請使用 Inv+x^y。

Quick Sort

Quick Sort 是將陣列依某個 key，分成較大的部份和較小的部份，再將兩部份分別排序即可。因此，排序時會出現兩個集團，分別是較大和較小的部分。集團會再分成更小的集團。當集團小到某個程度時，是以 insertion sort 排序，就不再分成更小的集團了。

public class QuickSortApplet extends SortApplet {

    public void run() {
        int l = 0, r = number - 1;
        int[] stack = new int[50];
        int top = 0;
        int i;

        while(true) {
            while(r > l) {
                if(r - l <= 10) {
                    insertion(l, r);
                    break;
                }

                i = partition(l, r);
                if(i - l > r - i) {
                    stack[top++] = l;
                    stack[top++] = i - 1;
                    l = i + 1;
                }
                else {
                    stack[top++] = i + 1;
                    stack[top++] = r;
                    r = i - 1;
                }
            }
            if(top == 0)
                break;
            r = stack[--top];
            l = stack[--top];
        }
    }

    private int partition(int l, int r) {
        int m = (l + r) / 2;
        if(getData(l) > getData(m))
            swapData(l, m);
        if(getData(l) > getData(r))
            swapData(l, r);
        if(getData(m) > getData(r))
            swapData(m, r);
        swapData(m, r - 1);

        m = r - 1;
        int v = getData(m);

        l++;
        r -= 2;

        while(true) {
            while(getData(l) < v)
                l++;
            while(getData(r) > v)
                r--;
            if(l >= r)
                break;
            swapData(l, r);
            l++;
            r--;
        }
        swapData(l, m);

        return l;
    }

    private void insertion(int l, int r) {
        int i, j, v;

        for(i = l + 1; i <= r; i++) {
            v = getData(i);
            j = i;
            while(j > l && getData(j-1) > v) {
                copyData(j, j-1);
                j--;
            }
            setData(j, v);
        }
    }
}

Binary Search Tree by Rank (Insert, Delete)

typedef struct Node
{
   int data;
   int leftsize;
   struct Node *left;
   struct Node *right;
} NODE;

Max Heap 排序法

轉錄自 From Gossip@caterpillar
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HeapSort.htm

說明
選擇排序法的概念簡單，每次從未排序部份選一最小值，插入已排序部份的後端，其時間主要花費於在整個未排序部份尋找最小值，如果能讓搜尋最小值的方式加快，選擇排序法的速率也就可以加快，Heap排序法讓搜尋的路徑由樹根至最後一個樹葉，而不是整個未排序部份，因而稱之為改良的選擇排序法。

解法
Heap排序法使用Heap Tree（堆積樹），樹是一種資料結構，而堆積樹是一個二元樹，也就是每一個父節點最多只有兩個子節點（關於樹的詳細定義還請見資料結構書籍），堆積樹的父節點若小於子節點，則稱之為最小堆積（Min Heap），父節點若大於子節點，則稱之為最大堆積（Max Heap），而同一層的子節點則無需理會其大小關係。

可以使用一維陣列來儲存堆積樹的所有元素與其順序，為了計算方便，使用的起始索引是1而不是0，索引1是樹根位置，如果左子節點儲存在陣列中的索引為s，則其父節點的索引為s/2，而右子節點為s+1。

由於使用一維陣列來儲存堆積樹，每一次將樹葉與樹根交換的動作就是將最小值放至後端的陣列，所以最後陣列就是變為已排序的狀態。

其實堆積在調整的過程中，就是一個選擇的行為，每次將最小值選至樹根，而選擇的路徑並不是所有的元素，而是由樹根至樹葉的路徑，因而可以加快選擇的過程，所以Heap排序法才會被稱之為改良的選擇排序法。

【C Language】

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void createheap(int[]);
void heapsort(int[]);

int main(void) {
    int number[MAX+1] = {-1};
    int i, num;

    srand(time(NULL));

    printf("排序前：");
    for(i = 1; i <= MAX; i++) {
        number[i] = rand() % 100;
        printf("%d ", number[i]);
    }

    printf("\n建立堆積樹：");
    createheap(number);
    for(i = 1; i <= MAX; i++)
        printf("%d ", number[i]);
    printf("\n");

    heapsort(number);

    printf("\n");

    return 0;
}

void createheap(int number[]) {
    int i, s, p;
    int heap[MAX+1] = {-1};

    for(i = 1; i <= MAX; i++) {
        heap[i] = number[i];
        s = i;
        p = i / 2;
        while(s >= 2 && heap[p] > heap[s]) {
            SWAP(heap[p], heap[s]);
            s = p;
            p = s / 2;
        }
    }

    for(i = 1; i <= MAX; i++)
        number[i] = heap[i];

}

void heapsort(int number[]) {
    int i, m, p, s;

    m = MAX;
    while(m > 1) {
        SWAP(number[1], number[m]);
        m--;

        p = 1;
        s = 2 * p;

        while(s <= m) {
            if(s < m && number[s+1] < number[s])
                s++;
            if(number[p] <= number[s])
                break;
            SWAP(number[p], number[s]);
            p = s;
            s = 2 * p;
        }

        printf("\n排序中：");
        for(i = MAX; i > 0; i--)
            printf("%d ", number[i]);
    }
}

【Java】

public class HeapSort {
    public static void sort(int[] number) {
        int[] tmp = new int[number.length + 1];
        for(int i = 1; i < tmp.length; i++) {
            tmp[i] = number[i-1];
        }

        createHeap(tmp);

        int m = number.length;
        while(m > 1) {
            swap(tmp, 1, m);
            m--;

            int p = 1;
            int s = 2 * p;

            while(s <= m) {
                if(s < m && tmp[s+1] < tmp[s])
                    s++;
                if(tmp[p] <= tmp[s])
                    break;
                swap(tmp, p, s);
                p = s;
                s = 2 * p;
            }
        }
        for(int i = 0; i < number.length; i++) {
            number[i] = tmp[i+1];
        }
    }

    private static void createHeap(int[] tmp) {
        int[] heap = new int[tmp.length];

        for(int i = 0; i < heap.length; i++)
            heap[i] = -1;

        for(int i = 1; i < heap.length; i++) {
            heap[i] = tmp[i];
            int s = i;
            int p = i / 2;
            while(s >= 2 && heap[p] > heap[s]) {
                swap(heap, p, s);
                s = p;
                p = s / 2;
            }
        }

        for(int i = 1; i < tmp.length; i++)
            tmp[i] = heap[i];

    }

    private static void swap(int[] number, int i, int j) {
        int t;
        t = number[i];
        number[i] = number[j];
        number[j] = t;
    }
}

Inorder、Preorder、Postorder

1. Create Binary Tree (stack)
(1)Inorder
(2)Preorder
(3)Postorder
2. Parent Binary Tree (linked list 使用 parent field)
(1)Inorder
(2)Preorder
(3)Postorder
3. Thread Binary Tree (linked list 使用 引線)
(1)Inorder
(2)Preorder
4. Universal Binary Tree (stack)
(1)Inorder
(2)Preorder

Doubly Linked List

功能：
1. Inverse
2. Doubly Linked list

若有須要，請在2009/04/06 23:59之前Mail給我，逾期不候。

Linked List

我也應景寫了一篇Linked List，若有須要請Mail給我。

功能要求
1 InsertAfter (find address)
2 InsertAfter (find number)
3 InsertAfter (find data)
4 InsertAfter (find final data)
5 Delete (find address)
6 Delete (find number)
7 Delete (find data)
8 Delete (find final data)

結構

struct Node
{   
    char data[20];
    struct Node *link;
};