8-9.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#define K 10;
#define n 10;
typedef int datatype;
typedef struct list{
	datatype data;
	struct list * next;
}LinearList;
void main()
{
	LinearList L;
	int k[n],X[n],A[n],B[n],C[n];
	int r = K/2; /* 上半部分需要的交叉数,从右至左扫描线路*/
	int w = n; /* w 是当前线路*/
	while (r) 
	{ /* 上半部分需要更多的交叉*/
		if (k[w] < r) 
		{/* 使用w的所有交叉Insert(k[w], w);*/
			r -= k[w];
		}
		else 
		{/* 仅使用w的r个交叉*/
			//Insert (L,r,w);
			r = 0;
		}
		w--; 
	}
	/* 在中线上确定线路排列前w条线的排列次序不变*/
	for (int i = 1; i <= w; i++)
		X[i] = i;
	/* 其余线路的排列次序来自L*/
	for (i = w+1; i <= n; i++)
		//Delete(L,1, X[i]);
	/*计算上半部分的排列*/
	for (i = 1; i <= n; i++)
		A[X[i]] = i;
	/* 计算下半部分的排列*/
	for (i=1; i <= n; i++)
		B[i]=C[X[i]];
}