设有一个线性表采用顺序存储结构,表中的数据元素值为正整数(n个).设在O(n) 时间内,将线性表分成两为两部分,其中左半部分每个元素都小于原表的第一个元素,而右半部分则相反.

问题描述:

设有一个线性表采用顺序存储结构,表中的数据元素值为正整数(n个).设在O(n) 时间内,将线性表分成两为两部分,其中左半部分每个元素都小于原表的第一个元素,而右半部分则相反.

不知道你是否学过快速排序算法,在算法中有划分算法,实现的就是你说的这个操作.思想是:以第一个元素为轴,开始时设置2个指针(一个在最左端【不包括第一个元素】,一个在最右端)若两个指针没有重合,从右向左扫描每个...#include "数据操作.h"void main(){ printf("请输入数据表中关键字个数:\n"); int len;//数据表中关键字个数 scanf("%d",&len); SeqList SL;//声明数据表类型变量 if(CreateList(&SL,len)) //创建数据表 {printf("数据表创建成功,划分前关键字如下:\n");PrintList(SL);//输出数据表int pivot; //枢纽pivot=(int)rand()%1000;//随机生成枢纽printf("枢纽为:%d\n",pivot); int partionIdx=Partion(&SL,cmp,swp,1,SL.len,pivot);//划分printf("划分位置:%d\n",partionIdx-1); //输出划分位置printf("划分后关键字如下:\n"); PrintList(SL);//输出数据表 } elseprintf("数据表无元素,数据表创建失败!\n");}#ifndef _TBOPP_H_#define _TBOPP_H_#include #include #include //数据表存储结构类型//数据表中记录的关键字类型typedef int KeyDT;//数据表记录类型typedef struct{ KeyDT key;//关键字 //为简化程序,省略其余记录项}RecType;//数据表类型,采用定长顺序存储结构typedef struct { RecType * List;//数据表头指针 int len ; //数据表长度}SeqList;//声明布尔类型typedef enum {TRUE=1,FALSE=0} BOOL;//函数声明BOOL CreateList(SeqList * PL,int n);void PrintList(SeqList SL);intPartion(SeqList * PL,int(*cmp)(KeyDT,KeyDT),void(*swp)(KeyDT *,KeyDT *),int leftptr,int rightptr,int pivot);int cmp(KeyDT,KeyDT);void swp(KeyDT *,KeyDT *);#endif