单纯形算法的c语言源代码

     关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。下面我们着重谈谈几个有代表性的组合算法： 
单纯形法： 
这是一种线性规划算法，由G.B.Dantzig在1947年提出，后来由他和其他的学者又提出了单纯形法的变形和改进。这些被实践证明都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集（即满足约束条件的点的全体）是一个超多面体。如果它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后来的椭球算法和投影算法都很好的解决了这个问题。 
排序和检索： 
   这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下面我们专门谈谈排序算法（sorting algorithm） 
在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录{R1,R2,…,Rn}及其相应的键码的集合{K1,K2,…,Kn}。所谓排序算法就是数据处理中将文件中的记录按键码的一定次序要求排列起来的算法。若代排序的文件能够同时装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，如果经过排序后这些相同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。如果排序算法设计成单处理机完成的，则此排序算法称为串行（或顺序）排序算法；如果排序算法时设计成多处理机实现的，则称为并行排序算法。 
首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。 
使有序区中记录的数目增加一个或几个的操作称为一趟排序。 
   逐步扩大记录有序序列长度的方法大致有下列几类： 
一． 插入排序 
假设在排序过程中，记录序列R[1..n]的状态为： 
则一趟直接插入排序的基本思想为：将记录R插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。 
显然，完成这个“插入”需分三步进行： 
1．查找R的插入位置j+1； 
2．将R[j+1..i-1]中的记录后移一个位置； 
3．将R复制到R[j+1]的位置上。 
[I]直接插入排序 
 利用顺序查找实现“在R[1..i-1]中查找R的插入位置”的插入排序。 
 注意直接插入排序算法的三个要点： 
1．从R[i-1]起向前进行顺序查找，监视哨设置在R[0]； 
 R[0] = R;    // 设置“哨兵” 
 for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找 
 return j+1;     // 返回R的插入位置为j+1 
2．对于在查找过程中找到的那些关键字不小于R.key的记录，可以在查找的同时实现向后移动； 
 for (j=i-1; R[0].key<R[j].key; --j);    
    R[j+1] = R[j] 
3．i = 2，3，…, n, 实现整个序列的排序。 
template<class Elem> 
void InsertionSort ( Elem R[ ],  int n) 
{ 
 // 对记录序列R[1..n]作直接插入排序。 
 for ( i=2; i<=n; ++i ) 
 { 
   R[0] = R;            // 复制为监视哨 
   for ( j=i-1; R[0].key < R[j].key;  --j ) 
     R[j+1] = R[j];        // 记录后移 
   R[j+1] = R[0];        // 插入到正确位置 
 } 
} // InsertSort 
时间分析： 
实现排序的基本操作有两个： 
（1）“比较”序列中两个关键字的大小； 
（2）“移动”记录。 
对于直接插入排序： 
[II]折半插入排序 
 因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R的插入位置”，如此实现的插入排序为折半插入排序。其算法如下： 
template<class Elem> 
void BiInsertionSort (Elem R[ ]， int n) 
{ 
 // 对记录序列R[1..n]作折半插入排序。 
 for ( i=2; i<=L.length; ++i ) 
 { 
   R[0] = R;      // 将R暂存到R[0] 
   low = 1;   high = i-1; 
while (low<=high) 
{ //在R[low..high]中折半查找插入的位置 
      m = (low+high)/2;           // 折半 
      if (R[0].key < R[m].key)) 
        high = m-1;   // 插入点在低半区 
      else  low = m+1; // 插入点在高半区 
    } 
    for ( j=i-1; j>=high+1; --j ) 
      R[j+1] = R[j];      // 记录后移 
    R[high+1] = R[0];  // 插入 
 } 
} // BInsertSort 
折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。 
[III]表插入排序 
  为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。 
算法描述如下： 
template<class Elem> 
void LInsertionSort (Elem SL[ ]， int n) 
{ 
 // 对记录序列SL[1..n]作表插入排序。 
 SL[0].key = MAXINT ; 
 SL[0].next = 1;  SL[1].next = 0; 
 for ( i=2; i<=n; ++i ) 
for ( j=0, k = SL[0].next; 
 SL[k].key<=SL.key ; j=k, k=SL[k].next ) 
     { SL[j].next = i;  SL.next = k; } 
       // 结点i插入在结点j和结点k之间 
}// LinsertionSort 
关于如在排序之后调整记录序列： 
算法中使用了三个指针: 
其中：p指示第i个记录的当前位置； 
     i指示第i个记录应在的位置； 
     q指示第i+1个记录的当前位置 
template<class Elem> 
void Arrange ( SLinkListType SL[ ], int n ) { 
 // 根据静态链表SL中各结点的指针值调整 
 // 记录位置，使得SL中记录按关键字非递减 
 // 有序顺序排列 
 p = SL[0].next;// p指示第一个记录的当前位置 
 for ( i=1; i<n; ++i ) {        
  // SL[1..i-1]中记录已按关键字有序排列， 
  // 第i个记录在SL中的当前位置应不小于i 
  while (p<i)  p = SL[p].next; 
            // 找到第i个记录，并用p指示 
            // 其在SL中当前位置 
  q = SL[p].next;     // q指示尚未调整的表尾 
  if ( p!= i ) { 
SL[p]←→SL;   // 交换记录，使第i个 
               // 记录到位 
SL.next = p;    // 指向被移走的记录， 
         // 使得以后可由while循环找回 
  } 
  p = q;         // p指示尚未调整的表尾， 
               // 为找第i+1个记录作准备 
 } 
} // Arrange 

二． 交换排序：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度; 
[I]起泡排序 
 假设在排序过程中，记录序列R[1..n]的状态为：n-i+1 
则第i趟起泡插入排序的基本思想为：借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。 
算法描述： 
template <class Elem> 
void BubbleSort(Elem R[], int n) 
{ 
  // i 指示无序序列中最后一个记录的位置 
  i = n; 
  while (i >1) { 
    lastExchangeIndex = 1; 
    for (j = 1; j < i; j++) 
      if (A[j+1] < A[j]) { 
         Swap(A[j],A[j+1]); 
         lastExchangeIndex = j; 
      } //if 
     i = lastExchangeIndex; 
  } // while 
} // BubbleSort 
起泡排序的结束条件为：最后一趟没有进行“交换”。 
从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。我们可以设想，若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。 
[II]一趟快速排序 
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且     R[j].key≤ R.key ≤ R[j].key 
      (s≤j≤i-1)   枢轴     (i+1≤j≤t) 
例如:关键字序列 
        52, 49, 80, 36, 14, 58, 61, 97, 23, 75    
调整为:  23, 49, 14, 36, (52) 58, 61, 97, 80, 75 
其中(52)为枢轴，在调整过程中，需设立两个指针:low和high，它们的初值分别为:s和t, 之后逐渐减小high，增加low，并保证R[high].key≥52，而R[low].key≤52,否则进行记录的“交换”。 
算法描述如下: 
template<class Elem> 
int Partition (Elem R[], int low, int high) { 
// 交换记录子序列R[low..high]中的记录，使 
// 枢轴记录到位，并返回其所在位置，此时， 
// 在它之前（后）的记录均不大（小）于它 
 pivotkey = R[low].key; 
          // 用子表的第一个记录作枢轴记录 
 while (low<high) { 
          // 从表的两端交替地向中间扫描 
   while (low<high && R[high].key>=pivotkey)      
      --high; 
   R[low]←→R[high];    
        // 将比枢轴记录小的记录交换到低端 
   while (low<high && R[low].key<=pivotkey) 
      ++low; 
   R[low]←→R[high]; 
        // 将比枢轴记录大的记录交换到高端 
 } 
 return low;          // 返回枢轴所在位置 
} // Partition 
容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。 
将上述“一次划分”的算法改写如下：