単一チェーンテーブルの最後からk番目の要素を取る
【著作権声明:転載は出典:blog.csdn.net/algorithm_onlyを保留してください.メールアドレス:[email protected]】
1.アルゴリズム要求
テーブルヘッダノードを有する単一チェーンテーブルが知られており、ノード構造は
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.アルゴリズム実装
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