数据结构(C语言版)习题及答案第九章(2)

Rtype temp=r.e[i];

r.e[i]=r.e[i+1];

r.e[i+1]=temp;

flag=1;

数据结构(C语言版)习题及答案

}

i+=2;

}

i=2;

while(i<n)

{

if (r.e[i].key> r.e[i+1].key)

{

Rtype temp=r.e[i];

r.e[i]=r.e[i+1];

r.e[i+1]=temp;

flag=1;

}

i+=2;

}

}

}

4 、设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。（作为上机实践题目）

算法为：

struct Rtype

{

KeyType key; //关键字域

┆

};

# define maxlen maxsize // maxsize为分配的存储单元个数

struct ListSq

{

Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放

int len ;

}

void dbubblesort(ListSq r, int n)

{

int i,j,flag;

Rtype temp;

flag=1;

i=0;

while(flag)

{

flag=0;

for(j=n-i;j<i;j--)

{

if (r.e[j].key<r.e[j-1].key)

{

flag=a; temp=r.e[j];

r.e[j]= r.e[j-1];

数据结构(C语言版)习题及答案

r.e[j-1]=temp;

}

}

for(j=i;j<n-1;j++)

{

if (r.e[j].key>r.e[j+1].key)

{

flag=a; temp=r.e[j];

r.e[j]= r.e[j+1];

r.e[j+1]=temp;

}

}

i++;

}

}

5、写出快速排序的非递归算法。

Struct Elemtype

{

int low;

int high;

};

struct Stack

{

Elemtype stack [StackMaxSize] ; //StackMaxSize 确定顺序栈的最大深度 int top ; // 栈顶指针

}；

struct Rtype

{

KeyType key; //关键字域

┆

};

# define maxlen maxsize // maxsize为分配的存储单元个数

struct ListSq

{

Rtype e[ maxlen ] ; // 0号单元空闲，元素从1号单元开始存放

int len ;

}

void quicksort(ListSq *r, int s,int t)

{

Stack x;

Elemtype y,z,q;

Rtype temp;

Initstack(x);

y.low=s;

y.high=t;

push(x,y);

while(!Empty(x))

{

pop(s,y);

数据结构(C语言版)习题及答案

i=y.low; j=y.high;

temp=r.e[i];

do

{

while (j>i && r.e[j].key>=temp.key) j--;

if (i<j) //条件成立时交换r[i]和r[j]的值

{

r.e[i]=r.e[j];

i++;

}

while (i<j && r.e[i].key<=temp.key) i++;

if (i<j)

{

r[j]=r[i];

j--;

}

} while(i==j);//条件成立时继续进行一次划分中的比较和交换 r[i]=temp;

if ((i+1)<y.high)

{

z.low=i+1;

z.high=y.high;

push(x,z);

}

if (y.low<(i-1))

{

q.low=y.low;

q.high=i-1;

push(x,q);

}

}

}