1、插入排序
每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
1.1 直接插入排序
原理：将数组分为无序区和有序两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序的都移动到有序区完场排序。
要点：设立哨兵，作为临时存储和判断数组边界使用。
voidInsertSort(int*L,int length)
for(i =1;i{
if(L[j]& L[i])
L[0]= L[j];//存储待排序元素
while(L[0]& L[i])//在有序区找位置插入
L[i+1]= L[i];//移动
L[i+1]= L[0];
i = j-1;//还原有序区指针
当插入第i (i & 1) 个对象时，前面的V[0], V[1], &, v[i-1]已经排好序。这时，用v[i]的关键码与v[i-1], v[i-2], &的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。
最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较 1 次，移动 2 次对象，总的关键码比较次数为 n-1，对象移动次数为 2(n-1)。
最坏情况下，第 i 趟时第 i 个对象必须与前面 i 个对象都做关键码比较，并且每做 1 次比较就要做 1 次数据移动。则总的关键码比较次数KCN和对象移动次数RMN分别为n2/2。
1.2折半插入
原理：设在顺序表中的对象序列V[0],[1],[2].....。其中前i个是已经排序好的对象，再插入v[i]时，用折半搜索的方式查找。
voidBinaryInsert( datalist&list,int i )
int left =0,Right= i-1;
Element temp =list.Vector[i];
while( left &=Right)
int middle =( left +Right)/2;
if( temp.getKey ()Right= middle -1;
left = middle +1;
for(int k = i-1; k &= k--)
list.Vector[k+1]=list.Vector[k];
list.vector[left] =
算法分析：对分查找比顺序查找快，所以对分插入排序就平均性能来说比直接插入排序要快。
它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。因此，将 n 个对象（为推导方便，设为 n=2k )用对分插入排序所进行的关键码比较次数为：
当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。
在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比对分插入排序执行的关键码比较次数要少。对分插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。
对分插入排序是一个稳定的排序方法
1.3链表插入
原理：在每个对象的结点中增加一个链表指针数据成员LINK
算法分析：使用链表插入排序，每插入一个对象，最大关键码比较次数等于链表中已排好序的对象个数，最小关键码比较次数为1。故总的关键码比较次数最小为 n-1，最大为n（n-1)/2
用链表插入排序时，对象移动次数为0。但为 了实现链表插入，在每个对象中增加了一个链域 link，并使用了vector[0]作为链表的表头结点，总共用了 n 个附加域和一个附加对象。
算法从 i = 2 开始，从前向后插入。并且在vector[current].Key == vector[i].Key时，current还要向前走一步，pre跟到current原来的位置，此时， vector[pre].Key == vector[i].Key。将vector[i]插在vector[pre]的后面，所以，链表插入排序方法是稳定的。
1.4希尔排序
基本思想：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。
要点：增量的选择以及排序最终以1为增量进行排序结束。
void shellsort(datalist&list)
int gap = list.currentsize/2;
while(gap)
shellInsert(list,gap);
gap = gap == 2?1:(int)(gap/2.2);
shellInsert ( datalist & const int gep ) {
//一趟希尔排序,按间隔gap划分子序列 for ( int i = i & list.CurrentS i++) { Element temp = list.Vector[i]; int j = while ( j &= gap && temp.getKey ( ) & list.Vector[j-gap].getKey ( ) ) { list.Vector[j] = list.Vector[j-gap]; j -= } list.Vector[j] = } }
算法分析：
开始时 gap 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。
2、交换排序
两两比较待排序对象的关键码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有对象都排好序为止。
2.1冒泡排序(从后面到前面有序)
思想：设待排序对象序列中的对象个数为 n。最多作 n-1 趟，i = 1, 2, 。。。, n-2 。在第 i 趟中顺次两两比较v[n-j-1].Key和v[n-j].Key，j = n-1, n-2, 。。, i。如果发生逆序，则交换v[n -j-1]和v[n-j]。
int arr[10]={7,6,4,3,5,1,2,9,10,8};
for(int i=0;i<length-1;i++){</length-1;i++)
for(int j=0;j<length-i-1;j++){</length-i-1;j++)
if(arr[j]&arr[j+1])
swap(&arr[j],&arr[j+1]);
//冒泡排序优化版本
bool flag =
for(int i=0;i{
flag =//若是有序，就不用比了
for(int j=0;j<length-i-1;j++){</length-i-1;j++)
if(arr[j]&arr[j+1])
swap(&arr[j],&arr[j+1]);
3.选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
是所有 sorting 里面 swap 次数最少的，当 swap 代价很高的时候，选择使用选择排序。
通过n-i次比较，从n-i+1个数据中找到最小的数据，并和第i个数据交换。
int min =0;
for(int i=0; i{
min =//定义当前下标为最小值
for(int j=i+1;j<j++){</j++)
if(arr[min]& arr[j])//如果存在更小的值
min =//调整min下标
if(i != min)//若i不为最小值，交换
swap(&arr[min],&arr[i]);
任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子序列：
左侧子序列中所有对象的关键码都小于或等于基准对象的关键码
右侧子序列中所有对象的关键码都大于基准对象的关键码
int partation(keytype ar[],int left,int right)
int i= left,j =
ar[0]= ar[i];
while(i<j){</j)
while(i ar[i] = ar[j];
while(i ar[j] = ar[i];
ar[i] = ar[0];
void quick(int ar[],int left,int right)
if(left & right)
int pos = partation(ar,left,right);
quick(ar,left,pos-1);
quick(ar,pos+1,right);
void quicksort（int ar[],int n）
quick(ar,1,n);
voidquick_sort_loop(int*arr,intlen)
int*stack=(int*)malloc(len*sizeof(int)*20);//借助空间
assert(stack!=NULL);
stack[top++]=0;
stack[top++]=len-1;
while(top!=0)
high=stack[--top];//len-1
low=stack[--top];//0
//不断循环排列
part=partition(arr,low,high);
if(low<part-1)
stack[top++]=
stack[top++]=part-1;
if(part+1<high)
stack[top++]=part+1;
stack[top++]=
free(stack);
算法分析：
从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。
如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。
在n个元素的序列中，对一个对象定位所需时间为 O(n)。若设 t(n) 是对 n 个元素的序列进行排序所需的时间，而且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：o(n log2n )
要求存储开销为 o(log2n)。
可以证明，函数quicksort的平均计算时间也是o(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
5、锦标旗排序
首先取得 n 个对象的关键码，进行两两比较，得到 【n/2】 个比较的优胜者(关键码小者)，作为第一步比较的结果保留下来。然后对这 【n/2】 个对象再进行关键码的两两比较，&，如此重复，直到选出一个关键码最小的对象为止。
如果n不是2的K次幂，则让叶结点数补足到2的k次方个。叶结点上面一层的非叶结点是叶结点的关键码俩俩比较的结果。
每个结点除了存放对象的关键码 data 外，还存放了此对象是否要参选的标志 Active 和此对象在满二叉树中的序号index。
算法分析：
锦标赛排序构成的树是满的完全二叉树，其深度为 log2(n+1)，其中 n 为待排序元素个数。
除第一次选择具有最小关键码的对象需要进行 n-1 次关键码比较外，重构胜者树选择具有次小、再次小关键码对象所需的关键码比较次数均为 O(log2n)。总关键码比较次数为O(nlog2n)。
对象的移动次数不超过关键码的比较次数，所以锦标赛排序总的时间复杂度为O(nlog2n)。
多了附加存储。如果有 n 个对象，必须使用至少 2n-1 个结点来存放胜者树。
堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法 FilterDown( ) 形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。
void heap_adjust(int*arr,int start,int end)
int tmp = arr[start];
for(int i=2*start+1;i&=i=i*2+1)
if(i+1&=end && arr[i]& arr[i+1])
if(tmp & arr[i])
arr[start]= arr[i];
arr[start]=
void heap_sort(int*arr,int len)
{//12,3,5,7,9,0,23,16,90,20,30
for(int i=len/2-1;i&=0;i--)//n/2 * log2N
heap_adjust(arr, i, len-1);
swap(&arr[0],&arr[len-1]);
for(int i=len-2;i&0;i--)// n log2N
heap_adjust(arr,0,i);
swap(&arr[0],&arr[i]);
}//1.5N * log2N
}// 稳定性？？？？？？ 递归版本
int main()
int arr[]={12,3,5,7,9,0,23,16,90,20,30};
int len =sizeof(arr)/sizeof(arr[0]);
heap_sort(arr, len);
show(arr, len);
初始化大根堆，交换arr[0] = arr[n-1]，从0号到n-1号，重新调整为大根堆，交换arr[0] = arr[n-2],,,,,,直至交换0号与1号。
算法分析：
堆排序的时间复杂性为O(nlog2n)。
算法的空间复杂性为O(1)。
堆排序是一个不稳定的排序方法。
7、归并排序
设两个有序表A和B的对象个数(表长)分别为 al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。
当 i 和 j 都在两个表的表长内变化时，根据A[i]与B[j]的关键码的大小，依次把关键码小的对象排放到新表C[k]中；
当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表C[k]中。
void merge(int*arr,int len,int gap)
int*crr =(int*)malloc(sizeof(int)* len);
assert(crr != NULL);
int L1 =0;
int H1 = L1+gap-1;
int L2 = H1+1;
int H2 =(L2+gap-1)&=(len-1)?(L2+gap-1):(len-1);/////?????
while(L2&=len-1)/////?????
while(L1&=H1 && L2&=H2)
if(arr[L1]&= arr[L2])
crr[i++]= arr[L1++];
crr[i++]= arr[L2++];
while(L1&=H1)
crr[i++]= arr[L1++];
while(L2&=H2)
crr[i++]= arr[L2++];
L1 = H2+1;
H1 = L1+gap-1;
L2 = H1+1;
H2 =(L2+gap-1)&=(len-1)?(L2+gap-1):(len-1);/////?????
while(L1&=len-1)/////?????
crr[i++]= arr[L1++];
for(int i=0;i<i++)</i++)
arr[i]= crr[i];
free(crr);
void merge_sort(int*arr,int len)///空间复杂0(n)
for(int i=1;i
merge(arr, len, i);//2N
template void merge ( datalist & initList, datalist
& mergedList, const int l, const int m, const int n ) { int i = 0, j = m+1, k = 0; while ( i &= m && j &= n ) //两两比较 if ( initList.Vector[i].getKey ( ) &=initList.Vector[j].getKey ( ) )
{ mergedList.Vector[k] = initList.Vector[i]； i++; k++; } else {
mergedList.Vector[k] = initList.Vector[j]; j++; k++; } if ( i &= m ) for ( int n1 = k, n2 = n1 &= n && n2 &=n1++, n2++ ) mergedList.Vector[n1] = initList.Vector[n2]; else for ( int n1 = k, n2 = n1 &= n && n2 &=n1++, n2++) mergedList.Vector[n1] = initList.Vector[n2];}
void MergePass ( datalist & initList,datalist & mergedList, const int len ) { int i =0; while ( i+2*len &= initList.CurrentSize-1 ){ merge ( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * } if ( i+len &= initList.CurrentSize-1 ) merge ( initList, mergedList, i, i+len-1, initList.CurrentSize-1 ); else for ( int j=i; j &= initList.CurrentSize-1; j++ ) mergedList.Vector[j] = initList.Vector[j];}
（两路)归并排序的主算法
voidMergeSort( datalist&list){
//按对象关键码非递减的顺序对表list中对象排序
datalist& tempList (list.MaxSize);
int len =1;
while( len <list.currentsize){MergePass(list, tempList, len ); len *=2;</list.currentsize){
MergePass( tempList,list, len ); len *=2;
delete[]tempL
函数 MergePass( ) 做一趟两路归并排序，要调用merge ( )函数 n/(2*len)  O(n/len) 次，函数MergeSort( )调用MergePass( )正好log2n 次，而每次merge( )要执行比较O(len)次，所以算法总的时间复杂度为O(nlog2n)。
8、基数排序
(1)基数排序是采用&分配&与&收集&的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。
(2)最高位优先MSD (Most Significant Digit first)
最高位优先法通常是一个递归的过程：
先根据最高位关键码K1排序,得到若干对象组，对象组中每个对象都有相同关键码K1。
再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。
依此重复，直到对关键码Kd完成排序为止。
最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。
(3)最低位优先LSD (Least Significant Digit first)
首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。
(4)为了有效地存储和重排 n 个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。
voidRadixSort(staticlinklist&list,constint d,constint radix)
int rear[radix],front[radix];
for(int i =1;i<list.i++)}</list.i++)
//queue中存数据
voidbase_stor(int*arr,intlen,intwide)
LOOP_QUEUEbase[10];
for(i=0;i&10;i++)
InitQueue(&base[i]);
for(j=0;j<j++)
for(k=0;k&10;k++)
n=arr[k]/(int)pow(10,(double)j);//计算^y
Push(&base[m],arr[k]);
for(k=0;k&10;k++)
while(!IsEmpty(&base[k]))
Pop(&base[k],tmp);
}</j++)
(5)算法分析：
则称radix为基数。例如，关键码984可以看成是一个3元组(9, 8, 4)，每一位有0, 1, &, 9等10种取值，基数radix = 10。关键码&data&可以看成是一个4元组(d, a, t, a)，每一位有&a&, &b&, &, &z&等26种取值，radix = 26。
若每个关键码有d 位，需要重复执行d 趟&分配&与&收集&。每趟对 n 个对象进行&分配&，对radix个队列进行&收集&。总时间复杂度为O ( d ( n+radix ) )。
若基数radix相同，对于对象个数较多而关键码位数较少的情况，使用链式基数排序较好。
基数排序需要增加n+2radix个附加链接指针。
基数排序是稳定的排序方法。
9、归并排序
当待排序的对象数目特别多时，在内存中不能一次处理。必须把它们以文件的形式存放于外存，排序时再把它们一部分一部分调入内存进行处理。这样，在排序过程中必须不断地在内存与外存之间传送数据。这种基于外部存储设备（或文件）的排序技术就是外排序。
void showex(int*arr,int len)
{for(int i=0;i<i++){</i++)
printf(&%5d &,arr[i]);
if(i%5==4)
printf(&\n&);
printf(&\n&);
void swap(int*p1,int*p2)
char*arr_path =&f:\\arr.dat&;
voidCreateArrFile(unsignedlonglong n)
FILE*fw = fopen(arr_path,&wb&);
assert(fw != NULL);
srand(100);
for(unsignedlonglong i =0;i &++i)
int tmp = rand();
fwrite(&tmp,sizeof(int),1,fw);
fclose(fw);
void showArrFile()
FILE*fr = fopen(arr_path,&rb&);
assert(fr != NULL);
while(fread(&tmp,sizeof(int),1,fr)!=0)
printf(&%8d&,tmp);
if(i%5==0)
printf(&\n&);
printf(&\n&);
fclose(fr);
void bubble_sort(int*arr,int len)
for(int i=0;i<len-1;i++){</len-1;i++)
for(int j=0;j<len-1-i;j++){</len-1-i;j++)
if(arr[j]& arr[j+1])
swap(&arr[j],&arr[j+1]);
char*tmp_path =&f:\\tmp.dat&;
voidHandlerArrFile()
int arr[2000];
FILE* fr = fopen(arr_path,&rb&);
assert(fr != NULL);
FILE* fw = fopen(tmp_path,&wb&);
assert(fw != NULL);
int count =0;
while((count = fread(arr,sizeof(int),2000,fr))!=0)
bubble_sort(arr,count);
fwrite(arr,sizeof(int),count,fw);
fclose(fr);
fclose(fw);
remove(arr_path);
rename(tmp_path,arr_path);
#define LEN 30000
#define SIZE 1000
voidMergeArrFile(int gap)
FILE*fr = fopen(arr_path,&rb&);
FILE*fw = fopen(tmp_path,&wb&);
assert(fw != NULL && fr != NULL);
int L1 =0;
int H1 = L1 +gap-1;
int L2 = H1+1;
int H2 = L2+gap-1<len-1?l2+gap-1:len-1;int arr[1000],brr[1000],crr[2000];</len-1?l2+gap-1:len-1;
int i=1000,j=1000,k=0;
//归并过程
while(L2 &= LEN-1)
while(L1 &= H1 && L2&= H2)
if(i ==1000)
fseek(fr,L1*sizeof(int),SEEK_SET);//读数据1
fread(arr,sizeof(int),1000,fr);
if(j ==1000)
fseek(fr,L2*sizeof(int),SEEK_SET);//读数据2
fread(brr,sizeof(int),1000,fr);
if(arr[i]&=brr[i])
crr[++k]= arr[++i];
crr[++k]= brr[++j];
if(k ==1000)
fwrite(crr,sizeof(int),1000,fw);
fwrite(crr,sizeof(int),k,fw);
while(L1&=H1)
fseek(fr,L1*sizeof(int),SEEK_SET);
fread(crr,sizeof(int),1,fr);
fwrite(crr,sizeof(int),1,fw);
while(L2&=H2)
fseek(fr,L2*sizeof(int),SEEK_SET);
fread(crr,sizeof(int),1,fr);
fwrite(crr,sizeof(int),1,fw);
L1 = H2+1;
H1= L1+gap-1;
L2 = H1+1;
H2 = L2+gap-1<len-1?l2+gap-1:len-1;}</len-1?l2+gap-1:len-1;
while(L1&=LEN-1)
fseek(fr,L1*sizeof(int),SEEK_SET);
fread(crr,sizeof(int),1,fr);
fwrite(crr,sizeof(int),1,fw);
fclose(fr);
fclose(fw);
remove(arr_path);
rename(tmp_path,arr_path);
voidFileSort(int num)
HandlerArrFile();
for(int i =2000;i{
MergeArrFile(i);
int main()
CreateArrFile(30000);
//showArrFile();
FileSort(30000);
//showArrFile();
//HandlerArrFile();
showArrFile();班卓｜LOFTER（乐乎） - 让兴趣，更有趣
LOFTER for ipad —— 让兴趣，更有趣
下载移动端
关注最新消息
  被喜欢
  被喜欢
{list posts as post}
{if post.type==1 || post.type == 5}
{if !!post.title}${post.title|escape}{/if}
{if !!post.digest}${post.digest}{/if}
{if post.type==2}
{if post.type == 3}
{if !!post.image}
{if post.type == 4}
{if !!post.image}
{if !!photo.labels && photo.labels.length>0}
{var wrapwidth = photo.ow < 500?photo.ow:500}
{list photo.labels as labs}
{var lbtxtwidth = Math.floor(wrapwidth*(labs.ort==1?labs.x:(100-labs.x))/100)-62}
{if lbtxtwidth>12}
{if !!labs.icon}
{list photos as photo}
{if photo_index==0}{break}{/if}
品牌${make||'-'}
型号${model||'-'}
焦距${focalLength||'-'}
光圈${apertureValue||'-'}
快门速度${exposureTime||'-'}
ISO${isoSpeedRatings||'-'}
曝光补偿${exposureBiasValue||'-'}
镜头${lens||'-'}
{if data.msgRank == 1}{/if}
{if data.askSetting == 1}{/if}
{if defined('posts')&&posts.length>0}
{list posts as post}
{if post_index < 3}
{if post.type == 1 || post.type == 5}
{if !!post.title}${post.title|escape}{/if}
{if !!post.digest}${post.digest}{/if}
{if post.type == 2}
{if post.type == 3}
{if post.type == 4}
{if post.type == 6}
{if drlist.length>0}
更多相似达人：
{list drlist as dr}{if drlist.length === 3 && dr_index === 0}、{/if}{if drlist.length === 3 && dr_index === 1}、{/if}{if drlist.length === 2 && dr_index === 0}、{/if}{/list}
暂无相似达人，
{if defined('posts')&&posts.length>0}
{list posts as post}
{if post.type == 2}
{if post.type == 3}
{if post.type == 4}
{if post.type == 6}
this.p={ currentPage:1,pageNewMode:true,isgooglead3:false,ishotrecompost:false,visitorId:0, first:'',tag:'班卓',recommType:'new',recommenderRole:0,offset:4,type:0,isUserEditor:0,};博客访问： 2619234
博文数量： 412
博客积分： 10227
博客等级： 上将
技术积分： 9629
注册时间：
认证徽章：
非淡泊无以明志，非宁静无以致远
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
1. 顺序表的定义 用把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法存储的线性表简称为顺序表。 顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。2. 顺序表存储结构&&& 在计算机内，可以用不同的方法来存储数据信息，最常用的方法是顺序存储。顺序存储结构也称为向量存储。&&& 假设每个元素占用的空间大小为L个字节，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：&&&&&&&&&&& LOC（ai）= LOC（a1）+L*（i-1）&& 1≤i≤n&注意：&&& 在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。
3. 顺序表的类定义
&typedef int ElemT&&&&&&&&&&&&&&&&&&//定义数据元素的类型，类型可根据实际情况而定，这里假设为int&&&&&&&&&const int MAXSIZE=100;&&&&&&&&&&&&&&&&&&//表空间的大小可根据实际需要而定，这里假设为100&&&&&&&&&class Sqlist&&&&&&&&&{&&&private:&&&&&&&&&&&&&&&&&&ElemType elem[MAXSIZE];&&&&&&&&&&&//数组，用于存放表结点 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//线性表的长度&&&&&&&&&&&&&&public:&&&&&&&&&&&&&&&&&&Sqlist(void);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//构造函数&&&&&&&&&&&&&&&&&&~Sqlist(){};&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//析构函数&&&&&&&&&&&&&&&&&&void SetData();&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//初建一个简表函数&&&&&&&&&&&&&&&&&&&void PrintOut();&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//输出线性表函数&&&&&&&&&&&&&&&&&&void Insert(int i,ElemType e);&&&&&&&&&//插入函数&&&&&&&&&&&&&&&&&&ElemType Delet(int i);&&&&&&&&&&&&&&&&&&&//删除函数&&&&&&&&&&};
&&&用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。存放线性表结点的向量空间的大小MAXSIZE应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。
&&&&&&&&& a1ai-1aian
&&&&&&&&& a1ai-1xaian
L-lengthListSize
n n-1in+1ni+1ixi=n+1x
void Sqlist::Insert(int i,ElemType e)
& i--;&&&&&&&&&&&& //C++
& if ( i&0 || i&length )&&&&&&&&&&&& //
& cout&&"i Error!"&&
for(j=j&1;j--)
elem[j]=elem[j-1];&&&&&&&&&&&& &&&&&&//
elem[i]=e;&&&&&&&&&&&&&&&&&&&&&&&&& //
&length++;&&&&&&&&&&&&&&&&&&&&&&&&& //1
&&& L-lengthn
&i=n+100(1)
&&& in-i+1
&&& pii1in+1
&&&&&&&&&&& &p1=p2=…=pn+1=1/(n+1)
5.程序实例：
#include &iostream&
#define Max& 100
/*线性表结构*/
typedef struct SeqList{
&&& datatype data[Max];
/*初始化*/
SeqList * init_SeqList()
&&&&& SeqList *L;&
&&&&& L=new SeqL
&&&&& cout&&"请输入顺序表的长度"&&
&&&&& cin&&L-&
&&&&& L-&last--;
&&&&& cout&&"请输入顺序表的内容"&&
&&&&& for(i=0;i&=L-&i++)
&&&&&&&&&&&& cin&&L-&data[i];
&&&&& return L;
void Print(SeqList *L)
&&&&& cout&&"顺序表内容为："&&
&&&&& for(i=0;i&=L-&i++)
&&&&&&&&&&&& cout&&L-&data[i]&&
/*从小到大排序*/
void Sort(SeqList *L)
&&&&& int i,j;
&&&&& for(j=0;j&=L-&j++)
&&&&& &&&&&& for (i=0;i&L-&last-j;i++)
&&& if (L-&data[i]&L-&data[i+1])
&&&&&&&&&&&& t=L-&data[i];
&&& L-&data[i]=L-&data[i+1];
&&& L-&data[i+1]=t;}
int Insert(SeqList *L,int i,datatype x){
&&& if(L-&last&Max-1){
&&&&&&&&&&&& cout&&"表满"&&
&&&&&&&&&&&& return -1;
&&& if(i&1||i&L-&last+2){
&&&&&&&&&&&& cout&&"插入位置错误!插入失败"&&
&&&&&&&&&&&& return 0;
&&& for(j=L-&j&=i-1;j--)
&&&&&&&&&&&& L-&data[j+1]=L-&data[j];
&&&&& L-&data[i-1]=x;
&&&&& L-&last++;
&&&&& return 1;
int Delete(SeqList *L,int i){
&&& if(i&1||i&L-&last+1){
&&&&&&&&&&&& cout&&"不存在第i个元素"&&
&&&&&&&&&&&& return 0;
&&& for(j=i;j&=L-&j++)
&&&&&&&&&&&& L-&data[j-1]=L-&data[j];
&&& L-&last--;
&&& return 0;
/*按值查找*/
int Location(SeqList *L,datatype x){
&&& while(i&=L-&last&&L-&data[i]!=x){
&&&&&&&&&&&& i++;
&&&&&&&&&&&& if(i&L-&last){
&&&&&&&&&&&&&&&&&&& return -1;
&&&&&&&&&&&& }
&&& return i+1;
/*线性表合并*/
void Merge(SeqList *A,SeqList *B,SeqList *C){
&&&&& int i,j,k;
&&&&& i=0;
&&&&& j=0;
&&&&& k=0;
//&&& C = new SeqList[A-&last+B-&last];
&&&&& //C = (SeqList*)malloc(sizeof(SeqList *)*200);
//&&& C=new SeqL
&&&&& while(i&=A-&last && j&=B-&last)
&&&&&&&&&&&& if(A-&data[i]&B-&data[j])
&&&&&&&&&&&&&&&&&&& C-&data[k++]=A-&data[i++];
&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&& C-&data[k++]=B-&data[j++];
&&&&&&&&&&&& while(i&=A-&last)
&&&&&&&&&&&&&&&&&&& C-&data[k++]=A-&data[i++];
&&&&&&&&&&&& while(j&=B-&last)
&&&&&&&&&&&&&&&&&&& C-&data[k++]=B-&data[j++];
&&&&&&&&&&&& C-&last=k-1;
/*两个线性表的比较*/
int Compare(int A[],int B[],int m,int n){
&&& int i,j,AS[100],BS[100],ms,
&&& ms=ns=0;
&&& while(i&=m && i&=n && A[i]==B[i])
&&&&&&&&&&&& i++;
&&& for(j=i;j&m;j++){
&&&&&&&&&&&& AS[j=i]=A[j];
&&&&&&&&&&&& ms++;
&&& for(j=i;j&n;j++){
&&&&&&&&&&&& BS[j-i]=B[j];
&&&&&&&&&&&& ns++;
&&& if(ms==ns&&ms==0)
&&&&&&&&&&&& return 0;
&&&&& &&&&&& if(ms==0&&ns&0||ms&0&&ns&0&&AS[0]&BS[0])
&&&&&&&&&&&&&&&&&&& return -1;
&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&& return 1;
/*线性表转化成数组*/
int Change(SeqList *L){
&&&&& int *a= new int[L-&last];
&&&&& //int a[L-&last];
&&&&& for(i=0; i&L-& i++){
&&&&&&&&&&&& a[i]=L-&data[i];
&&&&&&&&&&&& return a[L-&last];
/*主函数*/
int main()
&&&&& int a[100];
&&&&& int b[100];
&&&&& SeqList *L;
&&&&& SeqList *L2;
&&&&& SeqList *L3;
&&&&& L3 = new SeqL
&&&&& L=init_SeqList();
&&&&& cout&&"您输入的";
&&&&& Print(L);
&&& Sort(L);
&&&&& cout&&"从小到大排序后的";
&&&&& Print(L);
&&&&& cout&&"请输入您要插入的数："&&
&&&&& cin&&
&&&&& cout&&"请输入您要插入的位置："&&
&&&&& cin&&
&&&&& Insert(L,into,num);
&&&&& cout&&"插入后的";
&&&&& Print(L);
&&&&& cout&&"请输入您要删除的元素位置："&&
&&&&& cin&&
&&&&& Delete(L,del);
&&&&& Print(L);
&&&&& cout&&"请输入您要查找的数"&&
&&&&& cin&&
&&&&& cout&&"您查找的数在第"&&Location(L,find)&&"位"&&
&&&&& cout&&"输入第二个线性表："&&
&&&&& L2=init_SeqList();
&&&&& cout&&"您输入的";
&&&&& Print(L2);
&&& Sort(L);
&&&&& Sort(L2);
&&&&& Merge(L,L2,L3);
&&&&& cout&&"两个从小到大线性表合并后的";
&&&&& Print(L3);
&&&&& cout&&"线性表转化成数组"&&
&&&&& a[100]=Change(L);
&&&&& b[100]=Change(L2);
&&&&& int *x;
&&&&& int *y;
&&&&& x=&a[100];
&&&&& y=&b[100];
&&&&& cout&&"两个线性表的比较"&&
&&&&& result=Compare(x,y,L-&last,L2-&last);
&&&&& if(result=1){
&&&&&&&&&&&& cout&&"A线性表大于B线性表"&&
&&&&& }else if(result=0){
&&&&&&&&&&&& cout&&"A线性表等于B线性表"&&
&&&&& }else if(result=-1){
&&&&&&&&&&&& cout&&"A线性表小于B线性表"&&
&&&&& return 0;
阅读(669) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。
