0

n 個のノードのリストがあります。

3 つのポインターを使用して、リストの 2/3 のノードを出力する擬似コードを作成する必要があります。複雑さは何ですか?

カウンターで使えれば楽だったけど禁止。

最初の 3 つのノードの 3 つのポインターを置き、次に 3 つ目のポインターに移動することを考えます。それが終了ノードでない場合は、2 番目のノードの隣に移動します..しかし、私の擬似コードは長すぎて複雑です。

別の質問: 2 つのポインターを使用してそれを行うにはどうすればよいですか?

例: リスト: 1->2->3->4->5->6->7->8->9 は、要素を出力します: 4,5,6。

どんな助けでも大歓迎です!

4

4 に答える 4

1

最後に、カウンターなし、二重リンクリストなしの2ポインターソリューション

set the pointer1 in the 1st position
set the pointer2 in the 3rd position

while pointer2/=null{
pointer1.next
pointer2.next 3 times if pointer2=/null
}

//at this point we have the pointer1 in the first middle third element
//we only have to do the process again, but printing the elements
//we have to set the pointer2 to the third element, to start again

set the pointer2 in the 3rd position

while pointer2/=null{
pointer1.print
pointer1.next
pointer2.next 3 times if pointer2/=null
}

最初の反復では、pointer1 を中間 3 分の 1 の最初の要素に配置し、2 回目の反復では、必要なすべての要素を出力します。トリックは、pointer2 が最初に最後に到達したときにリセットすることです。

于 2013-04-13T15:37:17.227 に答える
1

2 つのポインターを使用すると簡単です。ポインター 1 を 1 番目の位置に置き、ポインター 2 を 3 番目の位置に置きます。

そして、やります:

while pointer2 not null{
print pointer1
pointer1.next
print pointer1
pointer1.next
pointer2.next 3 times if pointer2 is not null
}

たとえば、リストは 1、2、3、4、5、6 です。

pointer1=1
pointer2=3

pointer2/=null then
print pointer1 (1)
pointer1.next
print pointer1 (2)
pointer1.next
pointer2=pointer2.next 3 times then pointer2=6

また

pointer2/null then
print pointer1 (3)
pointer1.next
print pointer1 (4)
pointer1.next
pointer2.next is null, then the program will terminate here

取得したリストは 1,2,3,4 で、6 つの要素リストの 2/3 です

ここで疑問に答えます:)

于 2013-04-13T14:02:45.960 に答える
1
  • すべてのポインターをリストの先頭に設定します。
  • pointer3 が null ではなく、その next が null でない間、pointer1 を 1 ノード、pointer2 を 2 ノード、pointer3 を 3 ノード進めます (コースの終わりに達すると停止します)。
  • pointer3 がリストの最後に達すると、各ポインターはリストの 1/3 になり、それらの間のすべてのノードを出力できます。

2つのポインターはそのバリエーションにすぎませんが、質問の書き方が少し曖昧です

リストの 2/3 のノード (2/3)

私にとって、「2 番目の 3 分の 1」はリストの真ん中の 3 分の 1 を意味しますが、あなたは 2/3 と書きました。

于 2013-04-13T13:52:25.710 に答える
0

2 つのポインターを使用する他の解決策を見つけましたが、リンクされたリストは二重にリンクされたリストでなければなりません (次と前を使用)

set pointer 1 to the first element
set pointer 2 to the third element
while pointer 2/=null {
pointer1.next
pointer2.next 3 times if pointer2.next/=null
}
//in this part we have pointer1 in the first middle third element
while pointer1/=pointer2{
pointer1.next
pointer1.print
pointer2.prev
}

1,2,3,4,5,6 の例

pointer1=1
pointer2=3

pointer2.next/=null then
pointer1.next (pointer1=2)
pointer2.next 3 times, (pointer2=6)

pointer2.next=null then we enter in the second loop
pointer1.next  (pointer1=3)
pointer1.print (3)
pointer2.prev (pointer2=5)

pointer1/=pointer2 then
pointer1.next (pointer1=4)
pointer1.print(4)
pointer2.prev (pointer2=4)

pointer1==pointer2, end of program

コンソール出力に 3,4 があります

于 2013-04-13T14:31:55.090 に答える