第三周项目4（2）-顺序表应用 将所有奇数移到所有偶数前面

问题及代码：

/* copyright （t） 2016，烟台大学计算机学院 *All rights reserved. *文件名称：1.cpp *作者：常锐 *完成日期：2016年9月14日 *版本号：v1.0 *问题描述：将所在奇数移到所有偶数的前面，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。 *输入描述：线性表长度、线性表中各元素 *程序输出：调整顺序后的线性表 */

list.h：

#define Maxsize 100 typedef int Elemtype; //自定义数据类型 typedef struct list { Elemtype data[Maxsize]; //存顺序表元素 int length; //存顺序表长度 } Sqlist; void CreateList(Sqlist *&l,Elemtype a[],int n); //由a中的n个元素建立顺序表 void DispList(Sqlist *l); //输出线性表 void movejs(Sqlist *&l); //移动奇数

fun.cpp：

#include <stdio.h> #include <malloc.h> #include "list.h" 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; } } }

main.cpp：

#include <iostream> #include <malloc.h> #include <cstdio> #include "list.h" using namespace std; 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; }

运行结果：

知识点总结：

        顺序表基本运算的应用

心得体会：

        结合参考解答及课本例题中的内容，对算法的分析能力有所提高，有效巩固了相关知识点。