数据结构的C语⾔实现-线性表的合并与排序
⼀、线性表简介：
1、线性表是最基本、最简单、也是最常⽤的⼀种数据结构。线性表（linear list）是数据结构的⼀种，⼀个线性表是n个具有相同特性的数据元素的有限序列
2、线性表中数据元素之间的关系是⼀对⼀的关系，即除了第⼀个和最后⼀个数据元素之外，其它数据元素都是⾸尾相接的（注意，这句话只适⽤⼤部分线性表，⽽不是全部。⽐如，循环链表逻辑层次上也是⼀种线性表（存储层次上属于链式存储，但是把最后⼀个数据元素的尾指针指向了⾸位结点）
⼆、线性表的⼀般操作：
（1）InitList(& L)
//构造⼀个空的线性表
（2）DestroyList(& L)
//线性表存在了，消耗⼀个线性表
（3） ClearList（&L ）
//清空线性表中的内容
（4） ListEmpty（L）
//判断线性表是否为空
（5） ListLength（L）eclipse快捷键复制当前行到下一行
format命令进行高级格式化//返回线性表的长度
（6） GetElem（L，i，& e）
//返回线性表i位置上的元素值，通过e返回
（7） PriorElem（L，cur_e,&pre_e）
//若cur_e是线性表中的元素，且不是第⼀个，则返回该元素前⼀个元素的值
（8） NextElem（L，cur_e,&next_e）
/
/如果cur_e是线性表中的元素，⽽且不是最后⼀个，返回它下⼀个元素的值
（9）Listinsert(&L,i,e)
//如果线性表存在了，⽽且i符合条件，则在i位置插⼊⼀个元素
（10）ListDelete（&L,i）
//删除i位置上的元素
（11）ListDelete_data(&L,e,order)
//删除指定的元素e，order决定是删除⼀个，还是全部。
（12）Connect_two_List(L_a,L_b,& L_c)
//连接两个线性表，除去重复的内容
（13）print(L)
//打印线性表
冒泡排序代码c语言
三、线性表的合并与排序问题分析：
1、算法简介：
本⽂算法采⽤的是冒泡排序法，它的基本思想是⽐较相邻的两个数，如果前者⽐后者⼤，则进⾏交换。每⼀轮排序结束，选出⼀个未排序中最⼤的数放到数组后⾯，冒泡排序法是属于交换排序的，交换排序的基本思想都为通过⽐较两个数的⼤⼩，当满⾜某些条件时对它进⾏交换从⽽达到排序的⽬的
2、时间复杂度：
3、算法稳定性：
0是偶数吗北师版
冒泡排序就是把⼩的元素往前调或者把⼤的元素往后调。⽐较是相邻的两个元素⽐较，交换也发⽣在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前⾯的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是⼀种稳定排序算法。
四、附上合并排序的C语⾔源代码：
（附带保姆级注释，供初学者参考）
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node{//定义顺序表
int*elem;
int len;
};
void Init_arr(int len,struct node &arr)//1、初始化顺序表
{
int i=0,j=0,k=0;//2、定义i，j，k值均为0
int t;
arr.elem=(int*)malloc(len*sizeof(int));
//3、为该arr顺序表分配内存空间
if(arr.elem!=NULL)
//4、内存分配是否成功的判断
{
for(i=0;i<len;i++)
//5、进⼊for循环，当i不⼤于顺序表长度时，进⾏+1操作
scanf_s("%d",&arr.elem[i]);
//6、这⾥⼿动输⼊顺序表的元素（可⽆序）
arr.len=len;
//冒泡排序
for(j=0;j<len-1;j++)
//1、外层for循环表⽰arr中有len个数，⽐较次数为len-1
{
for(k=0;k<len-j-1;k++)
//2、内层for循环表⽰若第⼆个数⽐第⼀个数⼩进⾏两两交换的次数
{
if(arr.elem[k]>arr.elem[k+1])
//3、if判断前⼀个数⼤⼩是否⼤于后⼀个
{
t=arr.elem[k];
//4、若是，进⾏交换操作，其中t为交换的中间量
arr.elem[k]=arr.elem[k+1];
arr.elem[k+1]=t;
//5、完成位置交换
}
}
}
}
else{printf("内存分配失败！");
exit(0);
//6、else错误操作直接退出
}
}
void Combine_arr(struct node &arr1,struct node &arr2,struct node &arr)//归并顺序表，三个接⼝分别为表1，表2和合并完成的表
{
int i=0,j=0,k=0;
//1、创建第⼆个顺序表，步骤和第⼀个类似
arr.elem=(int*)malloc(1000*sizeof(int));
//2、为第⼆个顺序表申请空间
if(arr.elem!=NULL)
//3、若顺序表不空
{
while(i<arr1.len&&j<arr2.len)
//4、i表⽰第⼀个顺序表的下标，j表⽰第⼆个顺序表的下标
{
if(arr1.elem[i]>arr2.elem[j]){
//5、两两⽐较，若表1的i⼤于表2的j
arr.elem[k++]=arr2.elem[j];
/
/6、合并后的总表的第⼀个数就是第⼆个表中的j
j++;
plsql表编辑界面列选项不能编辑//7、j执⾏加1操作继续与第⼀个表中的i进⾏⽐较
}
else{
arr.elem[k++]=arr1.elem[i];
//8、如果i为较⼩的那个，则合并后总表的第⼀个数为i
i++;
//9、执⾏i加1操作，继续与第⼆个表中的j进⾏⽐较
}
}
if(i>=arr1.len)
//10、只剩⼀个表还未归并⼊新表（即通过i++，数组下标已经达到了第⼀个表的最后⼀个，即第⼀个表最⼤元素⼩于第⼆个表的最⼩元素，此时第⼀个表全体⼊新表）python新手入门图解
for(j;j<arr2.len;j++)
//11、此时只剩第⼆张表，进for循环
{
arr.elem[k++]=arr2.elem[j];
//12、下标为j的⼆表元素依次进⼊新表
}
else
{
for(i;i<arr1.len;i++)
//13、如果⼆表最⼤元素⼩于⼀表最⼩元素，即⼆表全部进⼊新表，⼀表没有元素进新表
arr.elem[k++]=arr1.elem[i];
//14、下标为i的⼀表元素进⼊新表
}
arr.len=k;
//15、新顺序表长度为最终的k
}
else
{
printf("内存分配失败！");
exit(0);
}
}
void traverse_arr(struct node &arr)
//1、遍历显⽰出顺序表
{
int i=0;
for(i=0;i<arr.len;i++)
//2、不超出范围的前提下，分别通过下标打印出新表元素printf("%d ",arr.elem[i]);
printf("\n");
}
int main(void)
{
int p,q;
struct node arr1,arr2,arr;
printf("顺序表1的元素个数为：");scanf_s("%d",&p);
printf("请输⼊第1个顺序表元素：");Init_arr(p,arr1); traverse_arr(arr1);
printf("顺序表2的元素个数为：");scanf_s("%d",&q);
printf("请输⼊第2个顺序表元素：");Init_arr(q,arr2); traverse_arr(arr2);
Combine_arr(arr1,arr2,arr);
//对表⼀表⼆进⾏归并
traverse_arr(arr);
//再次遍历并输出总表
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。