顺序表数据调整

已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分,左边的元素(即排在前面的)均为奇数,右边所有元素(即排在后面的)均为偶数,并要求算法的时间复杂度为O(n),空间复杂度为O(1)。

函数原型如下:
void odd_even(SeqList *L);

相关定义如下:
struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist
SeqList;
提供代码
#include <stdio.h> #include <stdlib.h> #include "list.h" // 请不要删除,否则检查不通过 void
odd_even(SeqList *L) { }
参考代码
/* 顺序表 数据调整 已知顺序表L中的数据元素类型为int。 设计算法将其调整为左右两部分,左边的元素(即排在前面的)均为奇数,
右边所有元素(即排在后面的)均为偶数, 并要求算法的时间复杂度为O(n),空间复杂度为O(1)。 */ /* 算法思路:
空间复杂度为O(1)说明只能使用一个中间临时变量 定义左右两个指针,进行比较,决定是否要交换 */ #include <stdio.h> #include
<stdlib.h> //#include "list.h" // 请不要删除,否则检查不通过 #define ElemType int #define
MAXSIZE 10 struct _seqlist { ElemType elem[MAXSIZE]; int last; }; typedef
struct _seqlist SeqList; //要求左奇数右偶数 void odd_even(SeqList* L) { int* left =
&(L->elem[0]); int* right = &(L->elem[L->last]); int tmp; while (left < right)
{ //左边是偶数 if (*left % 2 == 0) { //右边是奇数 if (*right % 2 == 1) { //交换 tmp =
*left; *left = *right; *right = tmp; left++; right--; } else { right--; } }
else { //左边是奇数 left++; } } } void print(const SeqList* L) { int i = 0; for (i =
0; i <= L->last; i++) { printf("%d ", L->elem[i]); } } int main() { SeqList L =
{ {0,1,2,3,4,5,6,7,8,9},4 };//测试用例 odd_even(&L); print(&L);//打印看是否删除成功 return
0; }

技术
©2019-2020 Toolsou All rights reserved,
在算法研究过程中如何进行算法创新七大排序算法(java代码)MYSQL中的索引与事务———javaweb(8)(面试必考)2022蓝桥杯JavaB组省赛试题网络安全-wifi攻防网络层协议——ICMP协议MySQL查询表中指定条件下的最新记录JavaSE笔记(一)Java基础语法mysql 查询条件之外的数据_mysql 查询符合条件的数据qt使用数据库sqlite