ヘッダ付きの単一チェーンテーブルが知られており、ノード構造はdata-linkであり、このチェーンテーブルがヘッダポインタlistのみを与えていると仮定します.チェーンテーブルを変更しない前提で、できるだけ効率的なアルゴリズムを設計し、チェーンテーブルの最後からk番目の位置のノード(kは正の整数)を検索します.

今日、2009年のコード408の本題を皆さんと共有します.ヘッダー付きの単一チェーンテーブルが知られています.ノード構造はdata-linkで、チェーンテーブルがヘッダーポインタlistしか与えられていないと仮定します.チェーンテーブルを変更しない前提で、できるだけ効率的なアルゴリズムを設計し、チェーンテーブルの最後からk番目の位置のノード(kは正の整数)を検索します.検索に成功すると、アルゴリズムはそのノードのdataドメインの値を出力し、1を返します.そうしないと、0だけを返します.採点基準:kを1回で見つけることができれば、15点満点で、1回を超えると最高10点になります.次はコードを直接見てみましょう.

struct LinkNode{
	int data;
	LinkNode *link;
} *LinkList;
int Search_k(LinkList list,int k){
	//    list   k   ，      data   
	LinkList p=list->link;//  p,q           
	LinkList q=list->link;
	int count=0;//       0 
	while(p!=NULL){//  p               
		if(countlink;
		p=p->link;
	} //while
	/*
	               ，      
	         ，p  ， q  
	  p     k ，  k count  ，   p q      
	  k       ，   q         
	*/
	if(countdata<

この問題は2つの変数でこの難題を解決し,同期の思想があちこちに見られる.以前、ある会社が面接問題を出したことを覚えています.簡単そうに見えますが、多くの人が歩きにくいです.この面接問題は主に2つの変数の値を交換することを言っていますが、3番目の変数を導入できないことを前提にしています.具体的なコードを見てみましょう.

void swap(int &a,int &b){
	a=a+b;
	b=a-b;
	a=a-b;
} 

今日は長い間書いていたので,ちょっと休んでください.