/* copyright （t） ，烟台大学计算机学院 *All rights reserved. *文件名称：1.cpp *作者：邵雪源*完成日期：9月19日 *版本号：v1.0 *问题描述：将所在奇数移到所有偶数的前面，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。 *输入描述：线性表长度、线性表中各元素 *程序输出：调整顺序后的线性表 */ #include <iostream>#include <malloc.h>#include <cstdio>using namespace std;#define Maxsize 100typedef int Elemtype;//自定义数据类型typedef struct list{Elemtype data[Maxsize]; //存顺序表元素int length;//存顺序表长度} Sqlist;void CreateList(Sqlist *&l,Elemtype a[],int n) //由a中的n个元素建立顺序表{int i;l=(Sqlist *)malloc(sizeof(Sqlist)); //分配存储空间for(i=0;i<n;i++)l->data[i]=a[i];//存放元素l->length=n; //设置长度}void DispList(Sqlist *l)//输出线性表{int i;for(i=0;i<l->length;i++)printf("%d ",l->data[i]);printf("\n");}void movejs(Sqlist *&l) //移动奇数{int i=0,j=l->length-1;Elemtype t;while (i<j){while ((i<j) && (l->data[j]%2==0)) //从右往左遍历找第一个奇数j--;while ((i<j) && (l->data[i]%2==1)) //从左往右遍历找第一个偶数i++;if (i<j)//如果未到达“分界线”，将上述循环中找到的奇数和偶数交换{t=l->data[i];l->data[i]=l->data[j];l->data[j]=t;}}}int main(){int i,Llength;Sqlist *l;Elemtype a[Maxsize];printf("请输入线性表长度：\n");scanf("%d",&Llength);printf("请输入线性表中各元素：\n");for(i=0;i<Llength;i++)scanf("%d",&a[i]);CreateList(l,a,Llength);movejs(l);DispList(l);return 0;} //移动奇数
