缥缈峰

     感谢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:<>

感谢Faust撰写C函数调用，Faust是我教研室的同学，签南京中兴。
-------------------------------------------------------------------------------------------------
作者：Faust ( wsgfaust_AT_163_DOT_com )

   C中采用了不同的调用方式来调用函数，这里的函数调用概念可能与我们通常所理解的函数调用有所不同，它们指的是处理器在处理函数上的差异。理解这些不同的方式有助于我们来调试程序和链接我们的代码。在此我想讨论一下主要的四种函数调用方法以及之间的区别，它们是__stdcall、__cdecl、__fastcall、thiscall。当然，还有一些更加不常用的函数调用方法比如naked call我也将顺便提及。


   不同的函数调用方法之间的主要有以下一些区别：
① 当参数个数多于一个时，按照什么顺序把参数压入堆栈函数调用后
② 谁来恢复堆栈
③ 编译后的修饰名规则


__stdcall：将参数压栈是按PASCAL语言的顺序（从右到左），通常用于WINAPI中。它是由被调用者将参数从栈中清除的,所以它的编译文件比__cdecl小。__stdcall是Windows API函数中默认的调用约定，被调函数自己在退出时清空堆栈。这种调用方式不能实现变参函数，因为被调函数不能事先知道弹栈数量，但在主调函数中是可以做到的，因为参数数量由主调函数确定。VC将函数编译后会在函数名前面加上下划线前缀，在函数名后加上"@"和参数的字节数。如函数int func(int a,  double b)的修饰名是_func@12。
编译选项/Gz。


注意：在创建DLL时，一般使用__stdcall调用（Win32 Api方式），采用__functionname@number命名规则，因而各种语言间的DLL能互相调用。也就是说，DLL的编制与具体的编程语言及编译器无关，只要遵守DLL的开发规范和编程策略，并安排正确的调用接口，不管用何种编程语言编制的DLL都具有通用性。


__cdecl：是C语言采用的默认调用方法，参数按从右到左的顺序压入栈，由调用者把参数弹出栈,它的优点是支持printf这样的可变参数调用。一般可变参数函数的调用都采用这种方式，比如int __cdecl scanf (const char *format,…)。对于"C"，修饰名是在函数名前加下划线,如函数void test(void)的修饰名是__test。除非声明为 extern "C"，否则 C++ 函数将使用不同的名称修饰方案。
    编译选项/Gd。


   注意：CC++中的main(或wmain)函数的调用约定必须是__cdecl,不允许更改。


__fastcall：__fastcall调用较快，它通过CPU内部寄存器传递参数。头两个DWORD类型或者占更少字节的参数被放入ECX和EDX寄存器，其他剩下的参数按从右到左的顺序压入栈。由被调用者把参数弹出栈，对于“C”函数或者变量，修饰名以“@”为前缀，然后是函数名，接着是符号“@”及参数的字节数，如函数int func(int  a, double b)的修饰名是@func@12。
编译选项/Gr，通常减少执行时间。


   注意：在对用内联程序集语言编写的任意函数使用__fastcall 调用约定时，一定要小心。您对寄存器的使用可能与编译器对它们的使用发生冲突。Microsoft 不保证不同编译器版本之间的 __fastcall 调用约定的实现相同。例如，16 位编译器与 32 位编译器的实现就不同。因此当使用 __fastcall 命名约定时，请使用标准包含文件。否则将获取无法解析的外部引用。


   thiscall： 函数体 this指针默认通过ECX传递,其它参数从右到左入栈。thiscall是唯一一个不能明确指明的函数修饰，因为thiscall不是关键字。它是C++类成员函数缺省的调用约定。由于成员函数调用还有一个this指针，因此必须特殊处理。3
thiscall意味着：参数从右向左入栈，如果参数个数确定，this指针通过ecx传递给被调用者；如果参数个数不确定，this指针在所有参数压栈后被压入堆栈。对参数个数不定的，调用者清理堆栈，否则函数自己清理堆栈。


   nakedcall：
这是一个很少见的调用约定，一般程序设计者建议不要使用。编译器不会给这种函数增加初始化和清理代码，更特殊的是，你不能用return返回返回值，只能用插入汇编返回结果。这一般用于实模式驱动程序设计。
讲到自右至左我想到了一个关于求值顺序的问题，巧合（？？?）的是，在C中求值顺序也是从右至左（不知道和压栈顺序是怎样的关系？）。我找到一个小例子。
void main()
{
int i=8;
printf("%dn%dn%dn%dn",++i,--i,i++,i--);
}
如按照从右至左的顺序求值。运行结果应为：
8
7
7
8
如对printf语句中的++i，--i，i++，i--从左至右求值，结果应为：
9
8
8
9
   应特别注意的是，无论是从左至右求值， 还是自右至左求值，其输出顺序都是不变的， 即输出顺序总是和实参表中实参的顺序相同。由于Turbo C现定是自右至左求值，所以结果为8，7，7，8。


转载请注明出处，谢谢！

     感谢Chris写的这个章节，另外更多的热心人正在帮助我完成Job Hunting系列技术文章的编写，再次对大家表示深深的感谢。
     如果您对我们写的文章有什么意见和建议，请告诉我们，谢谢。
-------------------------------------------------------------------------------------------------
作者：Chris. LGH (Blog: http://chris.turbozv.com)


     在一般的C教科书中，可以见到6种类型修饰符，分别是: auto, const, register, static, volatile, extern.
     局部变量除非显式指明为static, 否则默认为auto，所以一般不会在代码中使用类型修饰符auto.
     在后编译器时代，优化器可以合理的分配寄存器，所以一般不会在代码中使用类型修饰符register.
     extern只用于声明全局变量，用法单一。
     本节将主要介绍const, static和volatile.


1. const
     首先需要注意的是，const修饰的是在它前面的类型，如果它前面没有类型，那它修饰的是紧跟着它的那个类型。
例如：
(a)const int i = 0; 和 (b)int const i = 0; 是完全一样的。
在(a)中，const前面没有类型，它就修饰它后面的那个int类型。在(b)中，const修饰它前面的int类型，两者没有任何区别。
再看另一个稍复杂一点的例子，下面两条语句却不相同：
(c)const int *pi = 0;
/* 相当于int const *pi = 0; pi是一个指向const int的指针，复引用此运算符为得到一个const int的类型，该类型不能作为左值，在该语句后使用类似于*pi = 1的操作将导致编译错误。但该变量本身并不具备const属性，可以使用pi = &i的操作。可用于访问只读存储器。*/
(d)int* const pi = 0;
/* pi是一个指向int类型的const指针，复引用此运算符为得到一个int类型，该类型可以作为左值，在该语句可以使用类似于*pi = 1的操作，但该变量本身具备const属性，使用pi = &i的操作将导致编译错误。可用于访问固定位置的存储器。*/
再看一个更复杂的例子：
(e)const int* const pi = 0;
/* pi和*pi均不能作为左值。它只适合于读取某个固定位置的只读存储器 */

const还有下列典型用法:
     * 用于参数列表，通常修饰的是指针类型，表明该函数不会试图对传入的地址进行写操作。例如：
void *memcpy(void *, const void *, size_t);
     * 用于返回值，通常是一个指向只读区域的指针。例如：
const datatype_t *get_fixed_item(int index);
     * 给固定不变的数据(例如码表)加上只读属性，在某些情况下可以减小ram的开销。


2.static
     static用于全局变量声明和局部变量声明具有完全不同的语义，不得不说，这是C语言设计中的一个不合理之处。当static用于修饰全局变量声明(或函数声明，可以认为函数声明就是声明一个指向代码段的指针，该指针的值最后由链接时决定，从这个意义上说，函数声明也是一种全局变量声明)，它表示该变量具有文件作用域，只能被该源文件的代码引用，不能被其他源文件中的代码访问。在编译时引起的实际变化是被static修饰的变量不会被写入目标文件的输出节，在链接时解析其他模块中的未定义符号时不会被引用到。它的反义词是extern。
例如：
------main.c---
extern int a(void);
int main(){ return a(); }
------a.c------
/* link will fail unless remove “static” modifier */
static int a(void) { return 0; }



     当static用于修饰局部变量声明，它表示该变量不是分配在该函数的活动记录中，而是分配在全局的数据段(或bss段)中。简单的说，就是被static修饰的局部变量实际上并不是局部变量，而是具有函数作用域的全局变量，除了只能在定义它的函数内访问外(这是由C语法决定的)，它的运行时特征和全局变量完全一样，函数返回不会影响它的状态，它的初始化仅有一次，发生在程序的装载时，而不是在每次函数调用的时候初始化。它的反义词是auto。
例如, 下面这段函数返回自己被调用了多少次：
int callee(void) {
 static int times_called = 0;
 return (++ times_called);
}


3.volatile
     volatile修饰符的作用是告诉优化器不能优化这个变量的读写操作，一定要为这个变量的读写操作生成代码。
例如：
/* 延时操作 */
int foo(void) {
 /* 100次减法后返回 */
 volatile int i = 100; /*(a)*/
 while (i > 0) i--;  /*(b)*/
 return 0;
}
     在无volatile修饰的情况下，因为变量i的变化对上下文无影响，所以优化器很可能会省略掉对i操作的代码，而只生成return 0的代码，加上volatile可以保证编译器一定为语句(a)和(b)生成代码，达到延时的目的。

/* 设备状态判定 */
int uart_write_char(int c) {
 /* 向串口发送寄存器写入待发送字符 */
 *(volatile unsigned int *)UART_TX_REG = c;
 /* 判断是否已发送*/
 while ( (*(volatile unsigned int *)UART_STATUS_REG & TX_BIT) != 0); /*(c)*/
 return 0;
}
     在语句(c)中，如果不使用volatile，优化器可能会因为在两次读取UART_STATUS_REG之间没有对UART_STATUS_REG的写操作而将读取操作外提到循环体外而导致死循环。


转载请注明出处，谢谢！