21,【2009統一試験の本題】テーブルヘッダノードを有する単一チェーンテーブルが知られており、ノード構造はdata linkであり、このチェーンテーブルがヘッダポインタlistのみを与えたと仮定する.チェーンテーブルを変更しない前提で、できるだけ効率的なアルゴリズムを設計して、チェーンテーブルの最後からk番目の位置を探してください.

21,【2009統一試験の本題】表頭の結点を持つ単鎖表が知られており、結点構造は
data
link
チェーンテーブルにはヘッダポインタlistのみが与えられていると仮定します.チェーンテーブルを変更しない前提の下で、できるだけ効率的なアルゴリズムを設計して、チェーンテーブルの最後からk番目の位置のノード(kは正の整数)を探して、もし検索に成功したら、アルゴリズムはそのノードのdataドメインの値を出力して、そして1を返します;そうでなければ,0のみを返し,要求:1)アルゴリズムの基本設計思想を記述する.2)アルゴリズムの詳細な実装手順を説明する.3)設計思想と実現手順に従って、プログラム設計言語記述アルゴリズム(C.C+またはJava言語で実現)を採用し、肝心な点は簡単な注釈を与えてください.
回答:
1)2つのポインタを用いて、最初のポインタが先にk個の位置に下がるようにする.このとき、2つのポインタの間の間隔はkである.次に、2つのポインタを一緒に歩かせ、毎回1つの位置を下に移動させ、先に歩いたポインタがチェーンテーブルの尾に着くと、後に歩いたポインタの位置は最後からk番目の位置になります.
2)

は、2つのポインタpおよびqを定義し、いずれもヘッダノードを指す.変数i=0を定義し、pが数歩歩いたことを表す.

pでは空ではなくi

iは、iがkに等しいか否かを判断し、等しくなければ0を返す、そうでなければ、以下のステップ

を実行する.

pは、pがチェーンテーブルの尾

に達するまで、pとqを一緒に後ろに行かせる.

qの位置は逆数k番目の位置

である.
3)

int function(LinkList L, int k){
	Node *p , *q;
	p=q=L;
	int i = 0;
	while(inext;
		i++;	
	}
	//      ，  p k      
	if(i!=k){
		return 0;
	}
	while(p->next){
		p = p->next;
		q = q->next;
	} 
	cout<data;
	return 1;
	
}