1． 线性表综合题
（1） 按照输入的顺序建立顺序表
（2） 对顺序表进行排序（直接插入、冒泡、选择、快速、合并）
（3） 按照由大到小的顺序建立一个单链表
（4） 链表逆置
（5） 将顺序表和链表合并成一个有序表。
（6） 结果输出
#include<stdio.h>
#include <stdlib.h>
struct Node{
int data;
Node* link;
};
/****************************************************************************************************/
void insert(int e, int*list, int i) { /* 将e插入已排好序的 list[0],…,list[i]中，
使结果序列也排好序。list至少可容纳i+2个记录。*/
while ((i >= 0) && (e<list[i])) { /* 稳定*/
list[i+1] = list[i];
i--; /* list[i+1] 总是可用于存放记录*/
}
list[i+1] = e;
}
void InsertionSort(int*list, int n) { /*插入排序*/
for (int j = 1; j < n; j++)
insert (list[j], list, j-1);
}
/***************************************************************************************************/
void doitSort(int*a,int n)/*冒泡排序*/
{
int i,j,temp;
for(j=0;j<n;j++)
{
for (i=0;i<n-j-1;i++)
if (a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
/****************************************************************************************************/
void selectSort(int *a, int n)/*选择排序*/
{
int i, j, index, value;
for (i = 0; i < n - 1; i ++)
{
index = i;
value = a[i];
for (j = i + 1; j < n; j ++)
if (value > a[j])
{
index = j;
value = a[j];
}
a[index] = a[i];
a[i] = value;
}
}
/****************************************************************************************************/
void QuickSort (int*list, const int left, const int right) {
/* 排序list[align=left],…,list[align=right]，任选list[align=left]为基准记
录，假设list[align=left]≤list[right+1]。*/
if (left < right) {
int i = left, j = right +1, pivot = list[align=left];
do {
do i++; while (list[i]< pivot);
do j--; while (list[j]> pivot);
if (i < j)
{
int temp=list[i];
list[i]=list[j];
list[j]=temp;
}
} while (i < j);
int temp=list[align=left];
list[align=left]=list[j];
list[j]=temp;
QuickSort(list, left, j-1); /* 排序左子表*/
QuickSort(list, j + 1, right); /* 排序右子表*/
}
}
/**************************************************************************************************/
void merge(int*initList,int*mergedList, const int l, const int m, const int n) {
/*将排好序的两表合并成一个表*/
int i1,i2;
int iResult;
for ( i1 = l, iResult = l, i2 = m +1; i1 <= m && i2 <= n; iResult++)
if ( initList[i1]<= initList[i2]) {
mergedList[iResult] = initList[i1];
i1++;
}
else {
mergedList[iResult] = initList[i2];
i2++;
}
if (i1 > m)
for (int t = i2; t <= n; t++)
mergedList[iResult+t-i2] = initList[t];
else
for (int t = i1; t <= m; t++)
mergedList[iResult+t-i1] = initList[t];
}
void MergePass(int*initList, int*resultList, const int n, const int len) {
/* 一遍归并扫描。将表initList的相邻子表归并到表resultList*/
int i;
for ( i = 0; i <= n-2*len; i += 2*len)
merge(initList, resultList, i, i+len-1, i+2*len-1);
/* 剩下的记录数 < 2len*/
if (i+len-1 < n-1) /* 归并最后两个长短不一的子表*/
merge(initList, resultList, i, i+len-1, n-1);
else for (int t = i; t <= n-1; t++) resultList[t] = initList[t];
}
void MergeSort(int*list, const int n) {
/*合并排序*/
int*tempList = (int*)malloc(n);
for (int l=1; l < n; l*=2) { /* l是当前被归并子表的长度*/
MergePass(list, tempList, n, l);
l*=2;
MergePass(tempList, list, n, l); /* 最后一遍可能只是复制*/
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
void newmerge(int*table,Node* p,int* ntable,int m1,int m2,int n)
/*将一排好序的顺序表和链表合并成一个表*/
{
int i1, iResult ,i2;
for ( i1 = 0, iResult = 0,i2=0; i1<m1 &&i2<m2; iResult++)
/*将两表中的元素逐个比较，直到一表中的全部元素进入新表中*/
{
if ( table[i1]<= p->data) {
ntable[iResult] = table[i1];
i1++;
}
else {
ntable[iResult] =p->data;
p=p->link;
i2++;
}
}
/*处理剩余的元素*/
if (i1>=m1)
for (int t =i2;t<m2;t++)
{
ntable[iResult+t-i2]=p->data;
p=p->link;
}
else
for (int t = i1; t <= m1; t++)
ntable[iResult+t-i1] =table[t];
}
Node* Invert(Node* first )
{ /* 将x = (a1,.., an) 反转为 x = (an,.., a1)*/
Node*p = first, *q = 0; /* q跟在p之后*/
while (p) {
Node* r = q; q = p; /* r跟在q之后*/
p = p->link;
q->link = r; /* 将q前面的结点链到q后*/
}
first = q;
return first;
}
int main()
{
int n1,n2;
/**************************************************************************************************/
printf("顺序表的大小为 :");
scanf("%d",&n1);
int *table=(int*)malloc(n1);
printf("输入元素");
for(int i=0;i<n1;i++)
scanf("%d",&table[i]);
/***************************************************************************************************/
printf("请选择排序方式:\n");
printf("1.直接插入 2.冒泡 3.选择4.快速5.合并\n");
int m,i;
scanf("%d",&m);
switch(m)
{
case 1:
InsertionSort(table,n1);
printf("经过插入排序：\n");
break;
case 2:
doitSort(table,n1);
printf("经过冒泡排序：\n");
break;
case 3:
selectSort(table,n1);
printf("经过选择排序：\n");
break;
case 4:
QuickSort(table,0,n1-1);
printf("经过快速排序：\n");
break;
case 5:
MergeSort(table,n1);
printf("经过合并排序：\n");
break;
}
for(i=0;i<n1;i++)
printf("%d ",table[i]);
printf("\n");
/***************************************************************************************************/
Node *head=(struct Node *)malloc(sizeof(struct Node));
Node*p,*q;
p=head;
printf("链表的大小为 :");
scanf("%d",&n2);
printf("输入元素");
for(i=0;i<n2;i++)
{
q=(struct Node *)malloc(sizeof(struct Node));
scanf("%d",&(q->data));
p->link=q;
p=q;
}
p->link=NULL;
/***************************************************************************************************/
head=Invert(head);
printf("链表逆置\n");
p=head;
for(i=0;i<n2;i++)
{
printf("%d ",p->data);
p=p->link;
}
printf("\n");
/***************************************************************************************************/
int* ntable=(int*)malloc(n1+n2);
newmerge(table,head,ntable,n1,n2,n1+n2);
printf("将顺序表和链表合并成一个有序表\n");
for(i=0;i<n1+n2;i++)
printf("%d ",ntable[i]);
printf("\n");
}
麻烦有空的帮我看下，不甚感激
cMklFIyR.txt
