数据结构知识点
文章中所有的数据结构都是用伪C,数据结构用C语言实现的，如果有文章有什么错误，请及时联系我(QQ:2567919800)
排序
排序中用到的结构
# define MAXSIZE 10 // 用于要排序数组个数的最大值，可根据需要修改
typedef struct
{
int r[MAXSIZE+1]; // 用于存储要排序的数组，r[0] 用作哨兵或临时变量
int length; // 用于记录顺序表的长度
}SqList;
冒泡排序
1.最简单的排序实现思想:
两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
数据结构
void BubbleSort(SqList *L)
{
int i,j;
// 这里的下标是从 1 开始的，按照人的现实逻辑
for( i=1; i<L->length; i++)
for( j=i+1; j<=L->length-i;j++)
if( L->r[j] > L->r[j+1])
{
int temp = L->r[j];
L->r[j] = L->r[j+1];
L->r[j] = temp;
}
}
C语言实现
# include <stdio.h>
# define N 10
int main()
{
int a[N],i,j,t;
printf("请输入%d个数组的元素：",N);
for( i=0; i<N; i++)
scanf("%d",&a[i]);
// 最简单冒泡排序核心代码
for( i=0; i<N-1; i++)
for( j=i+1; j<=N-i-1; j++)
if( a[j] > a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
printf("排序后的数组的元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
return 0;
}
这种算法是由缺陷的，只对前两个位置的元素有效，对其余的没有什么帮助
2.正宗的冒泡算法(考试写这种)
从数组的最后一个元素开始，两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
数据结构
void BubbleSort(SqList *L)
{
int i,j;
for( i=1; i<L->length; i++)
for( j=L->length;j>=i;j--)
if( L->r[j] > L->r[j+1])
{
int temp = L->r[j];
L->r[j] = L->r[j+1];
L->r[j] = temp;
}
}
C语言实现
# include <stdio.h>
# define N 10
int main()
{
int a[N]={11,233,78,56,2,24,23,6,90,3};
int i,j,t;
printf("原数组元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
printf("\n");
// 正宗冒泡的核心思想, 从小到大，结果是正确的
/* 写法一
for( i=0; i<N-1; i++)
for(j=N-2;j>=i;j--)
if(a[j]>a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
*/
// 写法二
for(i=0;i<N-1;i++)
for(j=0;j<N-1-i;j++)
if(a[j]>a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
printf("排序完数组元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
这种结果是正确的
3.冒泡排序的优化
优化外层循环若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个标签flag，在每趟排序开始前，先将其置为0。若排序过程中发生了交换，则将其置为1。各趟排序结束时检查flag，若未曾发生过交换则终止算法，不再进行下一趟排序。
优化内层循环记住最后一次交换发生位置n的冒泡排序在每趟扫描中，记住最后一次交换发生的位置n，（该位置之后的相邻记录均已有序）。下一趟排序开始时，L[1..n-1]是无序区，R[n..length]是有序区。这样，一趟排序可能使当前无序区扩充多个记录，因此记住最后一次交换发生的位置n，从而减少排序的趟数。
数据结构
// 优化外层循环
void BubbleSort(SqList *L)
{
int i,j;
Status flag = TRUE; // flag 用来标识
for(i=1;i<L->length && flag;i++)
{
flag = FlASE; // 初始为flase
for(j=L->length;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
{
int temp = L->r[j];
L->r[j] = L->r[j+1];
L->r[j] = temp;
flag = TRUE; // 如果有数据交换，则 flag 为true
}
}
}
}
// 优化内层循环
void BubbleSort(SqList *L)
{
int i,j,n=0;
int k = L->length;
for(i=1;i<L->length;i++)
{
int flag = 1; // 假定每次进入都是有序的 flag 为 1
n= 0;
for(j=1;j<=k;j++)
{
if(L->r[j]>L->r[j+1])
{
int temp = L->r[j];
L->r[j] = L->r[j+1];
L->r[j] = temp;
flag = 0; // 如果发生交换，则 flag 置为 0
n = j; // 保留最后一次交换的下标
}
}
if(flag == 1) // 如果这趟走完，没有发生交换，则原数组有序
break;
K == n; // 最后一次交换的位置给K，减少比较的次数
}
}
C语言实现
// 优化外层循环
# include <stdio.h>
# define N 10
int main()
{
int a[N] = {2,1,3,5,4,6,8,7,9,20};
int i,j,t,flag = 1;
printf("原数组元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
printf("\n");
for(i=0;i<N-1 && flag;i++)
{
flag = 0;
for(j=N-2;j>=i;j--)
{
if(a[j]>a[j+1])
{
t =a[j];
a[j]=a[j+1];
a[j+1]=t;
flag = 1;
}
}
}
printf("排序完数组元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
// 优化内层循环
# include <stdio.h>
# define N 10
int main()
{
int a[N] = {2,1,3,5,4,6,8,7,9,20};
int i=0;
int j=0;
int t;
int k=N-1; // 控制内部比较循环
int n = 0;
printf("原数组元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
printf("\n");
for(i=0;i<N-1;i++)
{
int flag = 1;
n= 0;
// 假定每次进入都是有序的 flag 为 1
for(j=0;j<k;j++)
{
if(a[j]>a[j+1])
{
t =a[j];
a[j]=a[j+1];
a[j+1]=t;
flag = 0; // 如果发生交换，则 flag 置为 0
n=j; // 保留最后一次交换的下标
}
}
if(flag == 1) // 如果这趟走完，没有发生交换，则原数组有序
break;
k = n; // 最后一次交换的位置给K，减少比较的次数
}
printf("排序完数组元素：");
for( i=0; i<N; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
冒泡排序优化比较难掌握，考试不大考
直接插入排序
思想
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
(从小到大)如果当前i位置的元素小于第i+1位置的元素，设置哨兵为i位置的元素，将从0到i位置的元素进行排序交互位置。
数据结构
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if(L->r[i]<L->r[i-1])
{
L->r[0] = L->r[i]; // 设置哨兵
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1] = L->r[j]; // 记录后移
L->r[j+1] = l->r[0]; // 插入到正确的位置
}
}
}
C语言实现
# include <stdio.h>
int main()
{
int a[6]={0,5,3,4,6,2};
int i,j,t;
// a[0] 设置为哨兵,实现从小到大
for(i=1;i<=5;i++)
{
if(a[i] < a[i-1])
{
a[0] = a[i];
for(j=i-1;a[j]>a[0];j--)
{
t= a[j];
a[j]=a[j+1];
a[j+1]=t;
}
a[j+1] = a[0];
}
}
for(i=1;i<6;i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
简单选择排序
思想
设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。
数据结构
void SelectSort(SqList * L)
{
int i,j,min;
for(i=1;i<L->length;i++)
{
min = i;
for(j=i+1;j<=L->length;j++)
{
if(L->r[min]>L->r[j])
min = j;
}
if(i!=min)
{
t = a[min];
a[min]=a[i];
a[t]=t;
}
}
}
C语言实现
# include <stdio.h>
int main()
{
int i,j,t,index;
int a[10]={55,3,90,56,233,67,34,23,546,89};
// 使用简单选择进行从小到大排序
for(i=0;i<9;i++)
{
index = i;
for(j=i+1;j<10;j++)
{
if(a[index] > a[j])
index = j;
}
if(i!=index)
{
t= a[i];
a[i]=a[index];
a[index]=t;
}
}
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
网友评论