資料結構與算法二

1.課程安排表：

1. 線性表

2. 字元串

3. 棧和隊列

4.樹

5.查找

6.排序

7.暴力枚舉法

8.廣度優先搜尋

9.深度優先搜尋

10.分治

11.貪心

12.動态規劃

13.圖

14.數學方法與常見模型

15.大整數運算

16. 基礎功能

2.   程式設計技巧：

1.把較大的數組放在main 函數（全局變量）外，作為全局變量，這樣能夠防止棧溢出，由于棧的大小是有限制的。GCC (C編譯器) 段錯誤

2.假設可以預估棧，隊列的上限，則不要用stack,queue，使用數組來模拟，這樣速度最快。

3.輸入資料一般放在全局變量，且在執行過程中不要改動這些變量。

4.在推斷兩個浮點數a 和b 是否相等時，不要用a==b，應該推斷二者之差的絕對值fabs(a-b) 是否小于某個門檻值，比如1e-9。

5.推斷一個整數是否是為奇數，用x % 2 !=0，不要用x % 2 ==1，由于x 可能是負數。

6.用char 的值作為數組下标（比如，統計字元串中每一個字元出現的次數），要考慮到char 可能是負數。有的人考慮到了，先強制轉型為unsignedint 再用作下标，這仍然是錯的。正确的做法是，先強制轉型為unsignedchar，再用作下标。這涉及C++ 整型

提升的規則，就不詳述了。

3.線性表小結：

題目：高速找到未知長度單連結清單的中間節點。

設定2個指針，一開始同一時候指向頭，第一個指針比第二個指針快2倍

4. 字元串函數的内部實作

1.strlen

描寫叙述：實作strlen，擷取字元串的長度。函數原型例如以下：

int strlen(const char *str)

代碼：

int strlen(const char *str)
{
  const char *s;
  for(s=str; *s; ++s)
    ;
  return (s-str);
}      

2.strcpy

   實作strcpy，字元串拷貝函數，函數原型例如以下：

char*strcpy(char *to, const char *from);

char *strcpy(char *to, const char *from)
{
  assert(to != NULL  && from != NULL);//斷言錯誤
  char *p = to;
  while((*p++ = *from++) != '\0')
  ;
  return to;
}      

5.在排列中實作下一次排列

比如：數字1，2,3

1 2 3       ；    目前序号1

1 3 2       ；    目前序号2

2 1 3       ；    目前序号3

2 3 1       ；    目前序号4

3 1 2       ；    目前序号5

3 2 1       ；    目前序号6

三個數字1,2,3,有6種可能的排序情況，上述分别将序号都列舉了出來。

那麼如今須要解決的問題就是：已知目前排列中的序号 N, 求下一個序列 N+1。

求解過程：

為了便于操作，我們如果5個數字，各自是1,2,3,4,5

測試序列：以目前序列：1,4,3,5,2求出它的下一次排列。

如今将問題分解為4步驟：

1. 從後向前找出第一個不符合降序排列的數的下标，記為 i_pos，在本樣例中那麼就是數字3，下标i_pos 就是2。這裡解釋下何為第一個“不符合降序排列的數”，以樣例來解釋，從後向前找數的過程中，5,2,  是一個降序的排列，而3,5,2, 則破壞了這個降序的排列結構。

2. 在第一步找到的降序隊列中，從當中找出大于下标為i_pos 的數，而且這個數在全部大于下标為i_pos 的數列中是最小的。那麼以樣例來說，這一步找到的數就是5，記錄下标為j_pos;

3. 交換i_pos, 和 j_pos 下标的值。  運作完之後： 1,4,5,3,2

4. 從下标i_pos+1 開始知道末尾，對數列進行升序。樣例中就應該是對 3,2 進行升序，最後的結果就是: 1,4,5,2,3

5. 最後輸出結果。

代碼實作：

#include <iostream>
#define swapData(x,y) {int tmp=x; x = y; y = tmp;}

using namespace std;

int next_permutation(int *num, int n)
{
  int length = n-1;
  int i_pos=-1;

  for(int i=length; i > 0; i --)
  {
    if(num[i]>num[i-1])
    {
      i_pos = i-1;
      break;
    }
  }
  // 推斷是否到了末尾，即所有序列是降序的 
  if(i_pos==-1) return 0;

  int j_pos;
  for(int i=length; i > i_pos; i--)
  {
    if(num[i] > num[i_pos])
    {
      j_pos = i;
      break;
    }
  }

  swapData(num[i_pos], num[j_pos]);


  //冒泡排序 
  for(int i=i_pos+1; i < n; i++)
  {
    for(int j=length;  j > i; j--)
    {
      if(num[j] < num[j-1])
        swapData(num[j], num[j-1]);
    }
  }

  return 1;
}

main()
{
  int num[5]={1,2,3,4,5};
  do
  {
    for(int i=0; i <= 4; i++)
      cout << num[i] << " ";
    cout << endl;
  }while(next_permutation(num, 5));
  return 0;
}