题目描述
设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。
输入
1 4 6 23 45 14 34 78 45 9
输出
1 4 6 9 23 45 14 34 78 45
样例输入
11 44 63 23 45 14 34 78 45 19
样例输出
11 14 19 44 63 23 45 34 78 45
参考代码
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)
int t;
struct date
{
int num;
struct date *next;
}
;
struct date * creat(int *p)
{
struct date *head;
struct date *p1,*p2;
int t1=0,flog=0;
char ch;
t=0;
t1++;
p1=p2=(struct date *)malloc(LEN);
head=NULL;
while(scanf("%d",&p1->num))
{
scanf("%c",&ch);
if(ch=='n')
flog=1;
t1++;
t++;
if(t==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(struct date *)malloc(LEN);
if(flog==1)
break;
}
p2->next=NULL;
*p=t1;
return (head);
}
void print(struct date *head)
{
struct date *p;
p=head;
if(head!=NULL)
do
{
printf("%d ",p->num);
p=p->next;
}while(p!=NULL);
printf("n");
}
int main()
{
struct date *p,*p1,*p2,*p3,*p4,*p5;
int m,a,t1=0;
p=creat(&m);
p1=p;
while(p1)
{
p2=p1;
p1=p1->next;
}
a=p2->num;
m-=3;
p1=p;
while(m--)
p1=p1->next;
p1->next=NULL;
p1=p;
p3=p2;
p4=p2;
while(p)
{
if(p->num>a)
{
p=p->next;
p3->next=p1;
p1->next=NULL;
p1=p;
p3=p3->next;
}
else
{
t1++;
if(t1==1)
{
p=p->next;
p1->next=p2;
p2=p1;
p1=p;
p5=p2;
}
else
{
p=p->next;
p1->next=p4;
p5->next=p1;
p1=p;
p5=p5->next;
}
}
}
print(p2);
return 0;
}
解析
暂无