编辑代码

/*------------------------------------------------------------
---------例3.1（第70页）线性表按奇偶拆分----------------
将线性表A按元素值奇偶拆分成两个表，A表存放奇数，B表
存放偶数。
------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

/*---------顺序表类型定义（第71页） -------*/
#define maxsize 1024
typedef int datatype;

typedef struct {
	datatype data[maxsize]; //采用向量存储线性表，data[0]不用，从下标为1的data[1]开始使用
	int last;  //last是顺序表当前的长度
} sequenlist;

//声明函数原型
sequenlist *InitList();
int Insert(sequenlist *, datatype, int);
int Delete(sequenlist *L, int i);
void separate(sequenlist *La, sequenlist *Lb);
void PrintList(sequenlist *);

int main() {
	int len_a = 10;
	int a[10] = {1, 1, 4, 6, 5, 2, 6, 3, 8, 9};

	sequenlist *La, *Lb;
	La = InitList();
	Lb = InitList();

	int i, j;
	for (i = 0; i < len_a; i++) {
		La->data[i + 1] = a[i];
	}
	La->last = len_a;


	printf("顺序表La为：\n");
	PrintList(La);
	separate(La, Lb);
	printf("拆分后的顺序表La为：\n");
	PrintList(La);
	printf("拆分后的顺序表Lb为：\n");
	PrintList(Lb);

	return 0;
}

/*------------------------------------------------------------
---------算法3.2 建立一个空顺序表（第72页）----------------
通过函数返回值将结果带回到主调函数
------------------------------------------------------------*/
sequenlist *InitList() {
//分配顺序表的动态存储空间，将表的长度置为0
	sequenlist *L = (sequenlist *)malloc(sizeof(sequenlist));
	L->last = 0;
	return L;
}

/*------------------------------------------------------------
---------算法3.3 顺序表中插入结点（第72页）----------------
在顺序表的第i个位置上插入一个新结点x
------------------------------------------------------------*/
int Insert(sequenlist *L, datatype x, int i) {
//将新结点插入顺序表的第i个位置。插入成功返回1；不成功返回0.
	int k;
	if (L->last >= maxsize - 1) {
		printf("表已满.\n");    //插入不成功返回0
		return 0;
	}

	if (i < 1 || i > L->last + 1) {
		printf("非法插入位置.\n");
		return 0;
	}

	for (k = L->last; k >= i; k--) {
		L->data[k + 1] = L->data[k]; //结点后移
	}
	L->data[i] = x; //插入到L->data[i]中。从data[1]开始存放，data[0]不用
	L->last++;   //表长度加1
	return 1;   //插入成功返回1
}

/*------------------------------------------------------------
---------算法3.4（第74页）顺序表中删除结点----------------
删除顺序表的第i个结点
------------------------------------------------------------*/
int Delete(sequenlist *L, int i) {
//删除顺序表的第i个结点。删除成功返回1；不成功返回0.
	int j;
	if (i < 1 || i > L->last) {
		printf("非法删除位置.\n");
		return 0;   //删除不成功返回0
	}

	for (j = i; j <= L->last - 1; j++) {
		L->data[j] = L->data[j + 1]; //结点前移
	}
	L->last--;  //表长度减1
	return 1;   //删除成功返回1
}

//将偶数插入到B表中，A表只保留奇数
void separate(sequenlist *La, sequenlist *Lb) {
	int i = 1, j = 1;
	datatype x;
	while (i <= La->last) {
		x = La->data[i];       //取ai
		if (La->data[i] % 2 == 0) {
			Insert(Lb, x, j);
			j++;
			Delete(La, i);   //ai是偶数，插入到B表末尾，并从A表中删除
		} else
			i++;    //ai是奇数，仍放在A表中
	}
}


void PrintList(sequenlist *L) { //输出顺序表
	int i;
	for (i = 1; i <= L->last; i++)
		printf("%5d", L->data[i]);
	printf("\n");
}