つの面白いシングルチェーンの表面試験問題(シングルチェーン表の逆順、チェーン表の中間元素、チェーン表の並べ替え、シングルチェーン表のリングがあるかどうかを判断する)

3692 ワード

チェーンの接続点のデータ構造を以下に示します.

typedef struct _list_node
{
	double keyVal;
	_list_node *next;
}ListNode;

Q 1シングルチェーン表の逆順

ListNode* reverseList(ListNode* head)
{
	ListNode *p1, *p2 , *p3;
	//    ，              
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	p1 = head;
	p2 = head->next;
	while (p2 != NULL)
	{
		p3 = p2->next;
		p2->next = p1;
		p1 = p2;
		p2 = p3;
	}
	head->next = NULL;
	head = p1;
	return head;
}

Q 2チェーンの中間要素を見つける

ListNode* find_midlist(ListNode* head)
{
	ListNode *p1, *p2;
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	p1 = p2 = head;
	while (1)
	{
		if (p2->next != NULL && p2->next->next != NULL)
		{
			p2 = p2->next->next;
			p1 = p1->next;
		}
		else
		{
			break;
		}
	}
	return p1;
}

考え方の分析:
シングルチェーンの表の大きな特徴は、広告用語で「振り返らない」ということです.ランダムアクセスができません.配列aの中間要素を探したいなら、直接a[len/2]でいいですが、チェーンはだめです.a[len/2-1]だけがa[len/2]がどこにあるかを知っていますので、他の人は分かりません.そのため、配列のやり方によってヒョウタンを描くなら、チェーンの中点を見つけるには、チェーンの長さの半分の位置まで、どのぐらいの長さ(2)を知る必要があります.これは1.5 n(nはチェーンの長さ)の時間の複雑さが必要です.もっといい方法がありますか?あります.考え方は簡単です.二人は競走します.Aの速度がBの二倍なら、Aが終点に着いた時、Bは中点に来たばかりです.これはチェーンを巡回するだけでいいです.チェーンの長さを計算する必要はありません.
上のコードはこの考えを表しています.

Q 3 チェーンの並べ替え

double cmp(ListNode *p ,ListNode *q)
{
	return (p->keyVal - q->keyVal);
}

ListNode* mergeSortList(ListNode *head)
{
	ListNode *p, *q, *tail, *e;
	int nstep = 1;
	int nmerges = 0;
	int i;
	int psize, qsize;
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	while (1)
	{
		p = head;
		tail = NULL;
		nmerges = 0;
		while (p)
		{
			nmerges++;  q = p;  psize = 0;
			for (i = 0; i < nstep; i++){
				psize++;
				q = q->next;
				if (q == NULL)break;
			}
			qsize = nstep;
			while (psize >0 || (qsize >0 && q))
			{
				if (psize == 0 )
				{
					e = q;
					q = q->next;
					qsize--;
				}
				else if (q == NULL || qsize == 0)
				{
					e = p;
					p = p->next;
					psize--;
				}
				else if (cmp(p,q) <= 0)
				{
					e = p;
					p = p->next;
					psize--;
				}
				else
				{
					e = q;
					q = q->next;
					qsize--;
				}
				if (tail != NULL)
				{
					tail->next = e;
				}
				else
				{
					head = e;
				}
				tail = e;
			}
			p = q;
		}
		tail->next = NULL;
		if (nmerges <= 1)
		{
			return head;
		}
		else
		{
			nstep <<= 1;
		}
	}
}

考え方の分析:
チェーンの並べ替えは、正規の並べ替えアルゴリズムを使用したほうがいいです.積み上げ秩序化、高速秩序化、これらは配列の順序付け時に性能が非常に良いアルゴリズムで、チェーンテーブルでは「順番訪問」しかできない魔法の下で能力を発揮できません.しかし、並べ替えは魚が水を得たように、O(nlogn)の時間の複雑さを維持するだけでなく、配列の順序において非難される空間の複雑さはチェーンの順序においてもO(n)からO(1)に減少した.本当に素晴らしいですね.ハハ.上記の手順はデリバリーのプログラムです.また、その複雑さを見ると、ちょっと見覚えがありますか?はいこれは分治法の時間の複雑さで、整理して並べ替えるのはまたdivide and conquerです.

Q 4 チェーンテーブルにループがあるかどうかを判断します.

int is_looplist (ListNode *head)
{
	ListNode *p1, *p2;
	p1 = p2 = head;
	if (head == NULL || head->next == NULL)
	{
		return 0;
	}
	while (p2->next != NULL && p2->next->next != NULL)
	{
		p1 = p1->next;
		p2 = p2->next->next;
		if (p1 == p2)
		{
			return 1;
		}
	}
	return 0;
}

考え方の分析:
この問題は「C専門家プログラミング」の問題です.実はアルゴリズムもたくさんあります.例えば、訪問した結点をマークするという考えも悪くないと思います.また、木がいっぱいある場合にもよく使います.しかし、マーキングが許されない場合は使えません.いろいろな制限の条件の下で、上のこのような計算方法があって、実は思想はとても簡単です.二人が運動場で走っているように、一人の速度があれば、他の人の速度より少し速いです.彼らはきっと出会いがあります.しかし、リングチェーンは運動場とは違って、リングチェーンの状態は離散的なので、歩くより速いのを選ぶことが大切です.たとえばここでは、一つの針が一回に三歩、一つの針が一回に一回ずつ歩くと、一つのリングの中にいますが、永遠に会えないかもしれません.これはリングの大きさと二つのポインタの初期位置の違いによって違います.へへ.二つの針の速度はどのような関係を満たすべきですか?リングがある場合に出会うことができますか?もし知っているなら、私と相談してもいいです.

左神アルゴリズム学習日記——単調スタック