缥缈峰

压缩包下载：

●《盗墓贼》
●《白猫黑猫》


注：经古月先生书面同意，由缥缈峰网站作为其油画、小说发布的合法媒体，其他媒体需要转载请事先征求古月先生(guyue523@21cn.com)的同意。

     “缥缈峰”转介“画家古月用一个指头敲出七十万字小说”一文，收到不少信息。有人说：现在的老画家为了写作，竟去请年轻的学生做“家教”做朋友，以听取实在的意见，这真诚倒是难能可贵的。有人说：画家写的小说很有特点，就好像是看电视片，能看到活动的画面。有人说：曾经看过他不少绘画，现在又看了他的长篇小说《微尘》，除了好奇，还让人感动。有人说：画家古月画了不少画，写了不少小说，可我们看到的很少，请“缥缈峰”能多做一些介绍。

     在联系过后，“缥缈峰”将开辟一个专栏，以陆续刊出他的绘画和小说。以下请了他的好朋友画家武辉夏先生写了一个简介“古月其人”：


古月画册：
http://www.turbozv.com/blog.php?job=gallery&a=f&fid=guyue

     感谢Knife撰写串，Knife是我教研室的同学，签华为成研所。
大家有任何问题可以联系他：knife028_AT_126_DOT_com

---

作者：Knife(knife028_AT_126_DOT_com)


     有关串的定义和操作是大家在找工作时被问及较多的咚咚，在此和大家一起回顾和总结一下，达到共同学习的目的哈

一、串的基本概念
     串（或字符串），是由零个或多个字符组成的有限序列。串中字符的数目称为串的长度。零个字符的串称为空串，它的长度为零。
     串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
串相等的充要条件：长度相等，且各个对应位置上的字符都相等。
     空格串是指由一个或多个空格字符组成的串，其长度等于它包含的空格个数；空串是零个字符的串，其长度为零。


S1和S2为串，给出使S1||S2=S2||S1成立的所有可能条件如下：(||为连接符号)
1、S1和S2都为空串；
2、S1或S2其中之一为空串；
3、S1和S2为相同的串；
4、若两串长度不等，则长串由整数个短串组成。


串有三种机内表示方法
1、定长顺序存储表示；
2、堆分配存储表示；
3、块链存储表示。


随便提醒一下笔试者：C规定以字符'\0'作为字符串结束标志(考点哦)。


二、重要的串操作
     以下函数中串采用定长顺序存储结构（类似于线性表的顺序存储结构）,用一组地址连续的存储单元存储串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1]  //0号单元存放串长

     串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
     串长用下标为0的数组元素存储。

定位函数



串的置换操作


     
模式匹配的改进算法（KMP）

三、有关串的函数（C实现）

字符串逆序存储的递归算法
void InvertStore(char A[])
//字符串逆序存储的递归算法。
{ char ch;
static int i = 0;//需要使用静态变量
scanf ("%c",&ch);
if (ch!= '.')    //规定'.'是字符串输入结束标志
   {InvertStore(A);
    A[i++] = ch;//字符串逆序存储
   }
A[i] = '';  //字符串结尾标记
}//结束算法InvertStore。


long atoi(char X[])
//一数字字符串存于字符数组X中，本算法将其转换成数
{long num=0;
long htemp=1;
int j,i=1; //i 为数组下标
while (X[i]!= '') num=10*num+(X[i++]-'0');//当字符串未到尾，进行数的转换
if(X[0]=='-') return (-num);     //返回负数
else
{ for (j=1;j    htemp*=10;
 return ((X[0]-'0')*htemp+num); //返回正数，第一位若不是负号，则是数字
}
}//算法atoi结束



实现字符串拷贝的函数 strcpy为：

void strcpy(char *s , char *t) /*copy t to s*/

{ while  (*s++=*t++);

}


求两字符串中最大公共子串
// index存放子串在串s中的位置，length存放子串的长度
void  maxcomstr(orderstring *s,*t; int index, length)
{int i,j,k,length1,con;
 index=0;length=0;i=0;
 while (i {j=0;
 while(j   { if (s[i]= =t[j])
    { k=1;length1=1;con=1;
         while(con)
            if (i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] ) { length1=length1+1;k=k+1; }  else con=0;
         if (length1>length) { index=i;  length=length1; }
         j+=k;
    }
    else j++;
  }
 i++;
}
}

????? Yamir是我的师弟，也是我师弟Parvel的师弟，所以师弟关系具有传递性:P 他帮我完成了排序一章节，大家有任何问题可以联系他： http://www.sinklow.com/blog/

---

一、排序的概念
所谓排序，就是要让所有元素按递增或递减的顺序排列。

二、排序的分类
内部排序：只在主存中完成的排序(由于主存有限，所以内部排序的元素是有上限的)。
外部排序：利用磁盘等外存进行排序。

三、排序的稳定性
在待排序的元素中，存在多个相同的元素，经过排序后，这些元素的相对位置不变，该排序法就为稳定排序，否则为不稳定排序。

四、内部排序法
-----------------------------------------------------------
1.插入排序

算法思想
假设待排序的元素存放在数组A[N]中。初始时，A[0]自成1个有序区，无序区为A[1]~A[N-1]。从i=1起直至i=N-1为止，依次将A[i]插入当前的有序区A[0]~A[i-1]中。排序结束后为含N个元素的有序区。算法的平均时间复杂度为O(N^2)。

程序实现

--------------------------------------------------------
2.希尔排序

算法思想
假设有N个待排序的元素，先取一个小于N的整数d1作为第一个增量，把所有距离为d1的倍数的元素放在同一个组中，在各组内进行插人排序；然后取第二个增量d2
程序实现

void
Shellsort( ElementType A[], int N )
{
??int i, j, Increment;
??ElementType Tmp;
??for( Increment = N / 2; Increment > 0; Increment /= 2 )
????for( i = Icrement; i < N; i++ )
????{
??????Tmp = A[ i ];
??????for( j = i; j >= Increment; j -= Increment )
????????if( Tmp < A[ j - Increment ] )
??????????A[ j ] = A[ j -Increment ];
????????else
??????????break;
??????A[ j ] = Tmp
????}
}

注：程序实现中采用的是希尔增量，采用不同的增量会影响到希尔排序的时间复杂度。效率比较高的增量有Sedgewick增量。
Sedgewick增量序列：9*4^i-9*2^i+1 或者 4^i-3*2^i+1

--------------------------------------------------------
3.堆排序

算法思想
将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(NlogN)。

程序实现

#define LeftChild( i ) ( 2 * ( i ) + 1 )

void
PrecDown( ElementType A[ ], int i, int N )
{
??int Child;
??ElementType Tmp;

??for( Tmp = A[ i ]; LeftChild( i ) < N; i = Child )
??{
????Child = LeftChild( i );
????if( Child != N - 1 && A[ Child + 1 ] > A[ Child ] )
??????Child++;
????if( Tmp < A[ Child ] )
??????A[ i ] = A[ Child ];
????else
??????break;
??}
??A[ i ] = Tmp;
}

void
Heapsort( ElementType A[ ], int N )
{
??int i;
??
??for( i = N / 2; i >= 0; i-- )
????PrecDown( A, i, N )
??for( i = N - 1; i > 0; i-- )
??{
????Swap( &A[ 0 ], &A[ i ] );
????PercDown( A, 0, i )
??}
}

--------------------------------------------------------------
4.直接选择排序

算法思想
每一趟从待排序的元素中选出最小的元素，顺序放在已排好序的子元素集的最后，直到全部元素排序完毕。算法的平均时间复杂度为O(N^2)。

程序实现

void
SelectSort( ElementType A[ ], int N )
{
??int i, j, k;
??ElementType Tmp;

??for( i = 0; i < N; i++ )
??{
????k = i;
????for( j = i+1; j <= N; j++ )
??????if( A[j] < A[k] )
????????k = j;
????if( k != i )
????{
??????Tmp = R[i];
??????R[i] = R[k];
??????R[k] = Tmp;
????}
??}
}

----------------------------------------------------------------
5.归并排序

算法思想
归并排序是将若干个已排序的表合并成一个有序的表。

程序实现(递归历程)

void
MSort( ElementType A[ ], ElementType TmpArray[ ], int Left, int Right )
{
??int Center;
??if( Left < Right )
??{
????Center = ( Left + Right ) / 2;
????MSort( A, TmpArray, Left, Center );
????MSort( A, TmpArray, Center + 1, Right );
????Merge( A, TmpArray, Left, Center + 1, Right );
??}
}

void
Mergesort( ElementType A[ ], int N )
{
??ElementType *TmpArray;
??TmpArray = malloc( N * sizeof( ElementType ) );
??if( TmpArray != NULL )
??{
????MSort( A, TmpArray, 0, N - 1 );
????free( TmpArray );
??}
??else
????FatalError( "No space for tmp array!!!" );
}

程序实现(Merge例程)

/* Lpos = start of left half, Rpos = start of right half */

void
Merge( ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd )
{
??int i, LeftEnd, NumElements, TmpPos;
??
??LeftEnd = Rpos - 1;
??TmpPos = Lpos;
??NumElements = RightEnd - Lpos + 1;

??/* main loop */
??while( Lpos <= LeftEnd && Rpos <= RightEnd )
????if( A[ Lpos ] <= A[ Rpos ] )
??????TmpArray[ TmpPos++ ] = A[ Lpos++ ];
????else
??????TmpArray[ TmpPos++ ] = A[ Rpos++ ];
??
??while( Lpos <= LeftEnd ) /* Copy rest of first half */
????TmpArray[ TmpPos++ ] = A[ Lpos++ ];
??while( Rpos <= RightEnd ) /* Copy rest of second half */
????TmpArray[ TmpPos++ ] = A[ Rpos++ ];

??/* Copy TmpArray back */
??for( i = 0; i < NumElements; i++, RightEnd-- )
????A[ RightEnd ] = TmpArray[ RightEnd ];
}

------------------------------------------------------------------
6.冒泡排序

算法思想
两两比较待排序的元素，发现两个元素的次序相反时即进行交换。算法的平均时间复杂度为O(N^2)。

程序实现

void
BubbleSort( ElementType A[], int N )
{
??int i, j;
??ElementType Tmp;
??
??for( i=0; i??{
????for( j=N-1; j>i; j--)
??????if( A[j] < A[j-1] )
??????{
????????Tmp = A[j];
????????A[j] = A[j-1];
????????A[j] = Tmp;
??????}
??}
}

------------------------------------------------------
7.快速排序

算法思想
快速排序是是一种分治的递归算法。分治法的基本思想是：将元素集分解为若干个子集合。递归地解这些子集合，然后将这些子集合问题的解组合为原元素集。快速排序算法被认为是理论上高度优化的一种排序算法。平均时间复杂度为O(NlogN)。

程序实现

/* Return median of Left, Center, and Right */
/* Order these and hide the pivot */
ElementType
Median3( ElementType A[ ], int Left, int Right )
{
??int Center = ( Left + Right ) / 2;
??if( A[ Left ] > A[ Center ] )
????Swap( &A[ Left ], &A[ Center ] );
??if( A[ Left ] > A[ Right ] )
????Swap( &A[ Left ], &A[ Right ] );
??if( A[ Center ] > A[ Right ] )
????Swap( &A[ Center ], &A[ Right ] );
??/* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */
??Swap( &A[ Center ], &A[ Right - 1 ] );??/* Hide pivot */
??return A[ Right - 1 ];??/* Return pivot */
}

#define Cutoff ( 3 )
void
Qsort( ElementType A[ ], int Left, int Right )
{
??int i, j;
??ElementType Pivot;
??if( Left + Cutoff <= Right )
??{
????Pivot = Median3( A, Left, Right );
????i = Left; j = Right - 1;
????for( ; ; )
????{
??????while( A[ ++i ] < Pivot ){ }
??????while( A[ --j ] > Pivot ){ }
??????if( i < j )
????????Swap( &A[ i ], &A[ j ] );
??????else
????????break;
????}
????Swap( &A[ i ], &A[ Right - 1 ] );??/* Restore pivot */
????Qsort( A, Left, i - 1 );
????Qsort( A, i + 1, Right );
??}
??else??/* Do an insertion sort on the subarray */
????InsertionSort( A + Left, Right - Left + 1 );
}

void
Quicksort( ElementType A[ ], int N )
{
??Qsort( A, 0 , N-1 );
}

-----------------------------------------------------------------

8.其他排序还有一些，诸如快速选择排序,桶式排序,基数排序等等。

---------------------------------------------------------------
五、外部排序法
基本的外部排序算法使用归并排序中的Merge例程。

六、排序算法的上下界证明
这个都是数学证明了，Job Hunting中应该不用写了^^。

<转载请注明出处，谢谢>
Reference:<>