単一チェーンテーブルの最後からk番目の要素を取る


【著作権声明:転載は出典:blog.csdn.net/algorithm_onlyを保留してください.メールアドレス:[email protected]
1.アルゴリズム要求
テーブルヘッダノードを有する単一チェーンテーブルが知られており、ノード構造は
typedef struct lnode {
	elemtype data;
	struct lnode *next;
}lnode, *linklist;
このチェーンテーブルにはヘッダポインタlしか与えられていないと仮定します.チェーンテーブルを変更しない前提で、できるだけ効率的なアルゴリズムを設計して、チェーンテーブルの最下位を検索してください.
k個の位置におけるノード(kは正の整数)である.検索に成功すると、アルゴリズムはノードのdata値を出力します.
2.アルゴリズムの基本思想
単一チェーンテーブルを最初から最後まで巡回し、ポインタPで現在のノードの前K個のノードを指す.チェーンテーブルの最後のノードを巡回すると、ポインタPが指すノードが検索されたノードとなる. 
3.詳細な実装手順
2つのポインタ変数と1つの整数変数を追加し、チェーンヘッダから後方に遍歴し、ポインタP 1が現在遍歴しているノードを指し、ポインタPがP 1がノードを指している前のKノードを指し、P 1が前にK個のノードがなかった場合、Pはヘッダノードを指す.整数変数iで現在どれだけのノードが遍歴しているかを表し、i>kのとき、ポインタpは遍歴するたびに1つのノードを前に移動する.遍歴が完了すると、pは、テーブルヘッダがノードであるか、チェーンテーブルの最後からK番目の位置にあるノードを指す.
4.アルゴリズム実装
int get_node(linklist l, int k)
{
	linklist	p, q;
	int		i = 1;

	p = l->next;
	q = l;

	while (p) {
		p = p->next;
		++i;
		if (i > k)     /*  i  k ,    ,   q         k    */
			q = q->next;
	}
	if (q == l)            /* q     ,        k    */
		return ERROR;
	return q->data;
}
ソースのダウンロード:http://download.csdn.net/detail/algorithm_only/3890784