go-データ構造
41814 ワード
データ構造
データ構造(アルゴリズム)の紹介
データ構造の紹介
1)データ構造はアルゴリズムを研究する学科で、プログラミング言語があるだけでデータ構造ができます.データ構造をよく勉強すれば、より綺麗で効率的なコードが作成できます.2)データ構造を勉強するには、どのように生活の中で発生した問題をプログラムで解決しますか?3)プログラム＝データ構造＋アルゴリズム20.2データ構造とアルゴリズムの関係を考慮しなければなりません.
アルゴリズムはプログラムの魂です.
なぜ一部のウェブサイトは高合併で、海の量とスループットの状況下では依然として磐石のように堅く、皆さんは言うかもしれません.ウェブサイトはサーバの群集技術、データベースの読み書き分離とキャッシュ技術(例えばRedisなど)を使っています.皆さんは一つの問題を考えてください.何が違う人に書かれたコードですか?機能から見ても同じですが、効率的には雲泥の差があります.
ある人から聞いたことがあります.「私はサーバーをしています.環境はUNIXです.機能は1000万人以上の人を同時にオンラインでサポートし、データ転送の安定を保証しています.サーバーをオンラインにする前に、内部テストをして、すべてOKです.オンラインに行ったら、サーバーがサポートできなくなります.会社のCTOは私のコードを最適化し、再度オンラインにして、磐石のようにします.その瞬間、私はプログラムに魂があると認識しました.アルゴリズムです.会社で働く実際の経験から言えば、いつまでもコード労働者でありたくないなら、時間をかけてアルゴリズムを研究してみましょう.「
まばらなsparsearray配列
まず実際の需要を見てください.によって作成された五目並べのプログラムには、ディスクを残して終了する機能があります. は、元の方式による二次元配列の問題を解析する.この二次元配列の多くの値はデフォルト値0であるため、多くの無意味なデータ が記録されている.
基本的な紹介
1つの配列のほとんどの要素が0であるか、または同じ値の配列である場合には、その配列はまばらな配列を使用して保存されます.まばらな配列の処理方法は、1)記録配列は全部で何列あり、いくつかの異なる値がありますか?
アプリケーションのインスタンス
1)まばらな配列を使用して、前の二次元配列(碁盤、地図など)のような2)を保持し、まばらな配列を保存し、元の二次元配列数を新たに復元することができる.
キューの紹介列は、整列リストであり、配列またはチェーンテーブルで実現することができます. は先入先出の原則に従います.つまり、先に列のデータを保存して、先に取り出します.後で預け入れたものは後で を取り出します.
行列シミュレーション
チェーンの紹介
チェーンは順序正しいリストです.
シングルリストの紹介
一般的には、より良いのために、単一のチェーンテーブルを削除し、操作を修正するために、私たちは彼の頭の結点を設定します.頭の結点の役割は主にチェーンのヘッダを識別するために使用されます.自分のこの結点はデータを保存しません.
シングルチェーン表の応用例例の説明:
headヘッド付きの一方向チェーンを使って実現します.水滸英雄ランキングの管理が完了しました.
第一の方法はヒーローを追加する時、直接チェーンの最後に追加します.
ジョセフ問題
Josephuの問題は、番号を1、2、・・nとするn個人が一回り囲んで、約束番号をk(1)(=k(=n)とする人が1から数え、mまで数える人が出てきます.その次は1から数えて、mまで数える人がまた出て、順番に類推して、全員が列に出るまで、チーム番号を出す順番ができます.
ヒント
まずn個の結点がある単循環チェーンを構成し、その後k結点から1から数え始め、mまで計算すると、対応する結点はチェーンから削除され、その後、削除された結点の次の結点から1から数え始め、最後の結点がチェーンから削除されるまで計算方法は終了します.問題
並べ替えの紹介
並べ替えは、指定された順序で並べ替えられたデータのセットです.一般的な並べ替え:1)泡立ち順2)並べ替え3を選択します.並べ替え4を挿入します.
並べ替えの基本的な紹介を選択します.
選択式の並べ替えも内部の並べ替え法に属して、並べ替えたいデータの中から指定の規則によってある元素を選んで、他の元素と改質して、更に原則によって位置を交換した後に並べ替えの目的を達成します.
並べ替えの思想を選択:
並べ替え(select sorting)を選択するのも簡単な並べ替え方法です.基本的な考え方は、R[0]~R[n-1]の中から最小値を選択し、R[0]と交換し、2回目はR[1]~R[n-1]の中から最小値を選択し、R[1]と交換し、3回目はR[2]~R[n-1]の中から最小値を選択し、R[1]と交換します.交換、…、第n-1回はR[n-2]~R[n-1]の中から最小値を選び、R[n-2]と交換し、全部でn-1回を通して、小さい順に並べられた順序付けのシーケンスを得る.
挿入順序は内部並べ替え法で、並べ替えを求める要素に対して挿入する方法で要素の適切な位置を探して、並べ替えの目的を達成します.
並べ替えの思想を挿入:
並べ替えの挿入(Insertion Sorting)の基本的な考え方は、n個の順序付けされている要素を秩序表と無秩序表として見て、最初の順序表には一つの要素しか含まれていません.無秩序表にはn-1個の要素が含まれています.順序付け中には毎回無秩序表から最初の要素を取り出して、順序表要素の順序付けコードと比較して、秩序表の中の適切な位置に挿入します.新しい秩序表にします.
クイックソート(Quicksort)バブル順序の改善の一つです.基本的な考え方は、順序付けされるデータを1つの順序で独立した2つの部分に分割します.その中の一部のすべてのデータは他の部分のすべてのデータよりも小さいです.そして、この方法によって、この2つの部分のデータをそれぞれ迅速に並べ替えて、順序付けプロセス全体を再帰的に行うことができます.これによってデータ全体が秩序化されます.シーケンス
スタック
一部のプログラマはまたスタックをスタックと呼んでいます.つまり、スタックとスタックは同じ概念です.
1)スタックの英語は(stack)2)スタックで、先に入れてから出す(FILO-First In Last Out)のシーケンステーブルです.3)スタック(stack)は、線形表の要素の挿入と削除を制限する特殊な線形表です.挿入と削除を許可する端は、変化の一端として、スタックトップ(Top)といいます.他端はボトムと呼ばれます.4)スタックの定義により、最初にスタックの中の要素をスタックの底に入れ、最後に入れた要素がスタックの上にあることが分かります.削除要素はちょうど反対です.最後に入れた要素は最初に削除し、最初に入れた要素は最後に削除されます.
スタックの応用シーン
1)サブルーチンの呼び出し:サブルーチンにジャンプする前に、次の命令のアドレスをスタックに保存し、サブルーチンが実行された後にアドレスを取り出して元のプログラムに戻す.変換とシークレット.4)二叉樹のエルゴード.5)図形の深さ優先検索法
再帰的な応用シーン「迷宮問題」
再帰的概念
簡単に言いますと、第帰は関数/方法自分で自分を呼び出して、毎回呼び出した時に異なる変数が入ってきます.第帰はプログラミング者に複雑な問題を解決するのに役立ちます.同時にコードを簡潔にすることができます.
どのような問題を解決するために再帰的に使用されますか?
1)各種数学問題:8皇后問題、ハノータ、階乗問題、迷宮問題、ボールとバスケットの問題(googleプログラミングコンテスト)2)はスタックで解決する問題です.第帰コードは比較的簡潔です.
再帰的に守るべき重要な原則
1)関数を実行すると、新しい保護された独立空間(新しい関数スタック)2を作成します.関数の局所変数は独立しています.相互に影響はありません.各関数スタックが同じデータを使用したいなら、参照転送3を使用して再帰的条件に迫る必要があります.さもなくば無限再帰で、死んだカメ:)4)一つの関数が実行し終わったら、あるいはreturnに会ったら、戻ってきます.誰の呼出に従い、結果を誰に返しますか?
実際の需要
google社の一つの問題:
ある会社では、新入社员が报道されると、その社员の情报を(id,性别,年齢,住所.)に入れるように要求しています.この社员のIDを入力すると、その社员の情报をすべて调べることが要求されます.
ハッシュ表の基本的な紹介
ハッシュテーブルとは、キーコード値に従って直接アクセスするデータ構造であり、つまり、キーパーコード値を表の位置にマッピングすることによって、検索の速度を速くすることができる.このマッピング関数はハッシュ関数と呼ばれ、記録を保存する配列をハッシュリストと呼ぶ.
hashtableを使って従業員の管理システムを実現します.
応用例google社の一つの問題:
ある会社では、新入社员が报道されると、その社员の情报を(id,性别,年齢,住所.)に入れるように求められています.
要求:
1)データベースを使用しないで、メモリをできるだけ節約して、スピードが速いほどいいです.
1)チェーンを使用してハッシュ・テーブルを実現し、このチェーン・テーブルはヘッダを持たない.
データ構造(アルゴリズム)の紹介
データ構造の紹介
1)データ構造はアルゴリズムを研究する学科で、プログラミング言語があるだけでデータ構造ができます.データ構造をよく勉強すれば、より綺麗で効率的なコードが作成できます.2)データ構造を勉強するには、どのように生活の中で発生した問題をプログラムで解決しますか?3)プログラム＝データ構造＋アルゴリズム20.2データ構造とアルゴリズムの関係を考慮しなければなりません.
アルゴリズムはプログラムの魂です.
なぜ一部のウェブサイトは高合併で、海の量とスループットの状況下では依然として磐石のように堅く、皆さんは言うかもしれません.ウェブサイトはサーバの群集技術、データベースの読み書き分離とキャッシュ技術(例えばRedisなど)を使っています.皆さんは一つの問題を考えてください.何が違う人に書かれたコードですか?機能から見ても同じですが、効率的には雲泥の差があります.
ある人から聞いたことがあります.「私はサーバーをしています.環境はUNIXです.機能は1000万人以上の人を同時にオンラインでサポートし、データ転送の安定を保証しています.サーバーをオンラインにする前に、内部テストをして、すべてOKです.オンラインに行ったら、サーバーがサポートできなくなります.会社のCTOは私のコードを最適化し、再度オンラインにして、磐石のようにします.その瞬間、私はプログラムに魂があると認識しました.アルゴリズムです.会社で働く実際の経験から言えば、いつまでもコード労働者でありたくないなら、時間をかけてアルゴリズムを研究してみましょう.「
まばらなsparsearray配列
まず実際の需要を見てください.
基本的な紹介
1つの配列のほとんどの要素が0であるか、または同じ値の配列である場合には、その配列はまばらな配列を使用して保存されます.まばらな配列の処理方法は、1)記録配列は全部で何列あり、いくつかの異なる値がありますか?
アプリケーションのインスタンス
1)まばらな配列を使用して、前の二次元配列(碁盤、地図など)のような2)を保持し、まばらな配列を保存し、元の二次元配列数を新たに復元することができる.
package main
import (
"fmt"
)
type ValNode struct {
row int
col int
val int
}
func main() {
//1.
var chessMap [11][11]int
chessMap[1][2] = 1 //
chessMap[2][3] = 2 //
//2.
for _, v := range chessMap {
for _, v2 := range v {
fmt.Printf("%d\t", v2)
}
fmt.Println()
}
//3. 。 ->
//
//(1). chessMap, 0， node
//(2).
var sparseArr []ValNode
// ( ， )
// ValNode
valNode := ValNode{
row : 11,
col : 11,
val : 0,
}
sparseArr = append(sparseArr, valNode)
for i, v := range chessMap {
for j, v2 := range v {
if v2 != 0 {
// ValNode
valNode := ValNode{
row : i,
col : j,
val : v2,
}
sparseArr = append(sparseArr, valNode)
}
}
}
//
fmt.Println(" :::::")
for i, valNode := range sparseArr {
fmt.Printf("%d: %d %d %d
", i, valNode.row, valNode.col, valNode.val)
}
// ， d:/chessmap.data
//
//1. d:/chessmap.data => .
//2.
//
var chessMap2 [11][11]int
// sparseArr [ ]
for i, valNode := range sparseArr {
if i != 0 { //
chessMap2[valNode.row][valNode.col] = valNode.val
}
}
// chessMap2 .
fmt.Println(" ......")
for _, v := range chessMap2 {
for _, v2 := range v {
fmt.Printf("%d\t", v2)
}
fmt.Println()
}
}キューの紹介
行列シミュレーション
package main
import (
"fmt"
"os"
"errors"
)
//
type Queue struct {
maxSize int
array [5]int // =>
front int //
rear int //
}
//
func (this *Queue) AddQueue(val int) (err error) {
//
if this.rear == this.maxSize - 1 { // ; rear ( )
return errors.New("queue full")
}
this.rear++ //rear
this.array[this.rear] = val
return
}
//
func (this *Queue) GetQueue() (val int, err error) {
//
if this.rear == this.front { //
return -1, errors.New("queue empty")
}
this.front++
val = this.array[this.front]
return val ,err
}
// , ，
//
func (this *Queue) ShowQueue() {
fmt.Println(" :")
//this.front
for i := this.front + 1; i <= this.rear; i++ {
fmt.Printf("array[%d]=%d\t", i, this.array[i])
}
fmt.Println()
}
// ，
func main() {
//
queue := &Queue{
maxSize : 5,
front : -1,
rear : -1,
}
var key string
var val int
for {
fmt.Println("1. add ")
fmt.Println("2. get ")
fmt.Println("3. show ")
fmt.Println("4. exit ")
fmt.Scanln(&key)
switch key {
case "add":
fmt.Println(" ")
fmt.Scanln(&val)
err := queue.AddQueue(val)
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println(" ok")
}
case "get":
val, err := queue.GetQueue()
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println(" =", val)
}
case "show":
queue.ShowQueue()
case "exit":
os.Exit(0)
}
}
}
package main
import (
"fmt"
"errors"
"os"
)
//
type CircleQueue struct {
maxSize int // 4
array [5]int //
head int // 0
tail int // 0
}
// AddQueue(push) GetQueue(pop)
//
func (this *CircleQueue) Push(val int) (err error) {
if this.IsFull() {
return errors.New("queue full")
}
// this.tail ，
this.array[this.tail] = val //
this.tail = (this.tail + 1) % this.maxSize
return
}
//
func (this *CircleQueue) Pop() (val int, err error) {
if this.IsEmpty() {
return 0, errors.New("queue empty")
}
// ,head ，
val = this.array[this.head]
this.head = (this.head + 1) % this.maxSize
return
}
//
func (this *CircleQueue) ListQueue() {
fmt.Println(" ：")
//
size := this.Size()
if size == 0 {
fmt.Println(" ")
}
// ， head
tempHead := this.head
for i := 0; i < size; i++ {
fmt.Printf("arr[%d]=%d\t", tempHead, this.array[tempHead])
tempHead = (tempHead + 1) % this.maxSize
}
fmt.Println()
}
//
func (this *CircleQueue) IsFull() bool {
return (this.tail + 1) % this.maxSize == this.head
}
//
func (this *CircleQueue) IsEmpty() bool {
return this.tail == this.head
}
//
func (this *CircleQueue) Size() int {
// .
return (this.tail + this.maxSize - this.head ) % this.maxSize
}
func main() {
//
queue := &CircleQueue{
maxSize : 5,
head : 0,
tail : 0,
}
var key string
var val int
for {
fmt.Println("1. add ")
fmt.Println("2. get ")
fmt.Println("3. show ")
fmt.Println("4. exit ")
fmt.Scanln(&key)
switch key {
case "add":
fmt.Println(" ")
fmt.Scanln(&val)
err := queue.Push(val)
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println(" ok")
}
case "get":
val, err := queue.Pop()
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println(" =", val)
}
case "show":
queue.ListQueue()
case "exit":
os.Exit(0)
}
}
}チェーンの紹介
チェーンは順序正しいリストです.
シングルリストの紹介
一般的には、より良いのために、単一のチェーンテーブルを削除し、操作を修正するために、私たちは彼の頭の結点を設定します.頭の結点の役割は主にチェーンのヘッダを識別するために使用されます.自分のこの結点はデータを保存しません.
シングルチェーン表の応用例例の説明:
headヘッド付きの一方向チェーンを使って実現します.水滸英雄ランキングの管理が完了しました.
第一の方法はヒーローを追加する時、直接チェーンの最後に追加します.
package main
import (
"fmt"
)
// HeroNode
type HeroNode struct {
no int
name string
nickname string
next *HeroNode //
}
//
// ， .[ ]
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
//
//1.
//2. [ , ]
temp := head
for {
if temp.next == nil { //
break
}
temp = temp.next // temp
}
//3. newHeroNode
temp.next = newHeroNode
}
//
// 2 ， no ..【 】
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
//
//1.
//2. [ , ]
temp := head
flag := true
// no， temp no
for {
if temp.next == nil {//
break
} else if temp.next.no >= newHeroNode.no {
// newHeroNode temp
break
} else if temp.next.no == newHeroNode.no {
// no, .
flag = false
break
}
temp = temp.next
}
if !flag {
fmt.Println(" ， no=", newHeroNode.no)
return
} else {
newHeroNode.next = temp.next
temp.next = newHeroNode
}
}
//
func DelHerNode(head *HeroNode, id int) {
temp := head
flag := false
// no， temp no
for {
if temp.next == nil {//
break
} else if temp.next.no == id {
// .
flag = true
break
}
temp = temp.next
}
if flag {// ,
temp.next = temp.next.next
} else {
fmt.Println("sorry, id ")
}
}
//
func ListHeroNode(head *HeroNode) {
//1. [ , ]
temp := head
//
if temp.next == nil {
fmt.Println(" 。。。。")
return
}
//2.
for {
fmt.Printf("[%d , %s , %s]==>", temp.next.no,
temp.next.name, temp.next.nickname)
//
temp = temp.next
if temp.next == nil {
break
}
}
}
func main() {
//1. ,
head := &HeroNode{}
//2. HeroNode
hero1 := &HeroNode{
no : 1,
name : " ",
nickname : " ",
}
hero2 := &HeroNode{
no : 2,
name : " ",
nickname : " ",
}
hero3 := &HeroNode{
no : 3,
name : " ",
nickname : " ",
}
// hero4 := &HeroNode{
// no : 3,
// name : " ",
// nickname : " ",
// }
//3.
InsertHeroNode2(head, hero3)
InsertHeroNode2(head, hero1)
InsertHeroNode2(head, hero2)
// 4.
ListHeroNode(head)
// 5
fmt.Println()
DelHerNode(head, 1)
DelHerNode(head, 3)
ListHeroNode(head)
}
package main
import (
"fmt"
)
// HeroNode
type HeroNode struct {
no int
name string
nickname string
pre *HeroNode //
next *HeroNode //
}
//
// ， .[ ]
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
//
//1.
//2. [ , ]
temp := head
for {
if temp.next == nil { //
break
}
temp = temp.next // temp
}
//3. newHeroNode
temp.next = newHeroNode
newHeroNode.pre = temp
}
//
// 2 ， no ..【 】
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
//
//1.
//2. [ , ]
temp := head
flag := true
// no， temp no
for {
if temp.next == nil {//
break
} else if temp.next.no >= newHeroNode.no {
// newHeroNode temp
break
} else if temp.next.no == newHeroNode.no {
// no, .
flag = false
break
}
temp = temp.next
}
if !flag {
fmt.Println(" ， no=", newHeroNode.no)
return
} else {
newHeroNode.next = temp.next //ok
newHeroNode.pre = temp//ok
if temp.next != nil {
temp.next.pre = newHeroNode //ok
}
temp.next = newHeroNode //ok
}
}
// [ ]
func DelHerNode(head *HeroNode, id int) {
temp := head
flag := false
// no， temp no
for {
if temp.next == nil {//
break
} else if temp.next.no == id {
// .
flag = true
break
}
temp = temp.next
}
if flag {// ,
temp.next = temp.next.next //ok
if temp.next != nil {
temp.next.pre = temp
}
} else {
fmt.Println("sorry, id ")
}
}
//
//
func ListHeroNode(head *HeroNode) {
//1. [ , ]
temp := head
//
if temp.next == nil {
fmt.Println(" 。。。。")
return
}
//2.
for {
fmt.Printf("[%d , %s , %s]==>", temp.next.no,
temp.next.name, temp.next.nickname)
//
temp = temp.next
if temp.next == nil {
break
}
}
}
func ListHeroNode2(head *HeroNode) {
//1. [ , ]
temp := head
//
if temp.next == nil {
fmt.Println(" 。。。。")
return
}
//2. temp
for {
if temp.next == nil {
break
}
temp = temp.next
}
//2.
for {
fmt.Printf("[%d , %s , %s]==>", temp.no,
temp.name, temp.nickname)
//
temp = temp.pre
if temp.pre == nil {
break
}
}
}
func main() {
//1. ,
head := &HeroNode{}
//2. HeroNode
hero1 := &HeroNode{
no : 1,
name : " ",
nickname : " ",
}
hero2 := &HeroNode{
no : 2,
name : " ",
nickname : " ",
}
hero3 := &HeroNode{
no : 3,
name : " ",
nickname : " ",
}
InsertHeroNode(head, hero1)
InsertHeroNode(head, hero2)
InsertHeroNode(head, hero3)
ListHeroNode(head)
fmt.Println(" ")
ListHeroNode2(head)
}
package main
import (
"fmt"
)
//
type CatNode struct {
no int //
name string
next *CatNode
}
func InsertCatNode(head *CatNode, newCatNode *CatNode) {
//
if head.next == nil {
head.no = newCatNode.no
head.name = newCatNode.name
head.next = head //
fmt.Println(newCatNode, " ")
return
}
// ， ,
temp := head
for {
if temp.next == head {
break
}
temp = temp.next
}
//
temp.next = newCatNode
newCatNode.next = head
}
//
func ListCircleLink(head *CatNode) {
fmt.Println(" ：")
temp := head
if temp.next == nil {
fmt.Println(" ...")
return
}
for {
fmt.Printf(" =[id=%d name=%s] ->
", temp.no, temp.name)
if temp.next == head {
break
}
temp = temp.next
}
}
//
func DelCatNode(head *CatNode, id int) *CatNode {
temp := head
helper := head
//
if temp.next == nil {
fmt.Println(" ， ")
return head
}
//
if temp.next == head { //
if temp.no == id {
temp.next = nil
}
return head
}
// helper
for {
if helper.next == head {
break
}
helper = helper.next
}
//
flag := true
for {
if temp.next == head { // ， 【 】
break
}
if temp.no ==id {
if temp == head { //
head = head.next
}
// .,
helper.next = temp.next
fmt.Printf(" =%d
", id)
flag = false
break
}
temp = temp.next // 【 】
helper = helper.next // 【 helper】
}
//
if flag { // flag ，
if temp.no == id {
helper.next = temp.next
fmt.Printf(" =%d
", id)
}else {
fmt.Printf(" ， no=%d
", id)
}
}
return head
}
func main() {
//
head := &CatNode{}
//
cat1 := &CatNode{
no : 1,
name : "tom",
}
cat2 := &CatNode{
no : 2,
name : "tom2",
}
cat3 := &CatNode{
no : 3,
name : "tom3",
}
InsertCatNode(head, cat1)
InsertCatNode(head, cat2)
InsertCatNode(head, cat3)
ListCircleLink(head)
head = DelCatNode(head, 30)
fmt.Println()
fmt.Println()
fmt.Println()
ListCircleLink(head)
}ジョセフ問題
Josephuの問題は、番号を1、2、・・nとするn個人が一回り囲んで、約束番号をk(1)(=k(=n)とする人が1から数え、mまで数える人が出てきます.その次は1から数えて、mまで数える人がまた出て、順番に類推して、全員が列に出るまで、チーム番号を出す順番ができます.
ヒント
まずn個の結点がある単循環チェーンを構成し、その後k結点から1から数え始め、mまで計算すると、対応する結点はチェーンから削除され、その後、削除された結点の次の結点から1から数え始め、最後の結点がチェーンから削除されるまで計算方法は終了します.問題
package main
import (
"fmt"
)
//
type Boy struct {
No int //
Next *Boy // [ nil]
}
// ，
// num ：
// *Boy :
func AddBoy(num int) *Boy {
first := &Boy{} //
curBoy := &Boy{} //
//
if num < 1 {
fmt.Println("num ")
return first
}
//
for i := 1; i <= num; i++ {
boy := &Boy{
No : i,
}
// ， [ ]
//1.
if i == 1 { //
first = boy //
curBoy = boy
curBoy.Next = first //
} else {
curBoy.Next = boy
curBoy = boy
curBoy.Next = first //
}
}
return first
}
// [ ]
func ShowBoy(first *Boy) {
//
if first.Next == nil {
fmt.Println(" ， ...")
return
}
// ， .[ ]
curBoy := first
for {
fmt.Printf(" =%d ->", curBoy.No)
// ?curBoy.Next == first
if curBoy.Next == first {
break
}
//curBoy
curBoy = curBoy.Next
}
}
/*
1，2，… n n ， k（1<=k<=n）
1 ， m ， 1 ，
m ， ， ，
*/
//
//1. ，PlayGame(first *Boy, startNo int, countNum int)
//2. ， ，
func PlayGame(first *Boy, startNo int, countNum int) {
//1.
if first.Next == nil {
fmt.Println(" ， ")
return
}
// ， startNO <=
//2. ，
tail := first
//3. tail ,
// tail .
for {
if tail.Next == first { // tail
break
}
tail = tail.Next
}
//4. first startNo [ ， first ]
for i := 1; i <= startNo - 1; i++ {
first = first.Next
tail = tail.Next
}
fmt.Println()
//5. countNum, first
for {
// countNum-1
for i := 1; i <= countNum -1; i++ {
first = first.Next
tail = tail.Next
}
fmt.Printf(" %d
", first.No)
// first
first = first.Next
tail.Next = first
// tail == first, .
if tail == first {
break
}
}
fmt.Printf(" %d
", first.No)
}
func main() {
first := AddBoy(500)
//
ShowBoy(first)
PlayGame(first, 20, 31)
}並べ替えの紹介
並べ替えは、指定された順序で並べ替えられたデータのセットです.一般的な並べ替え:1)泡立ち順2)並べ替え3を選択します.並べ替え4を挿入します.
並べ替えの基本的な紹介を選択します.
選択式の並べ替えも内部の並べ替え法に属して、並べ替えたいデータの中から指定の規則によってある元素を選んで、他の元素と改質して、更に原則によって位置を交換した後に並べ替えの目的を達成します.
並べ替えの思想を選択:
並べ替え(select sorting)を選択するのも簡単な並べ替え方法です.基本的な考え方は、R[0]~R[n-1]の中から最小値を選択し、R[0]と交換し、2回目はR[1]~R[n-1]の中から最小値を選択し、R[1]と交換し、3回目はR[2]~R[n-1]の中から最小値を選択し、R[1]と交換します.交換、…、第n-1回はR[n-2]~R[n-1]の中から最小値を選び、R[n-2]と交換し、全部でn-1回を通して、小さい順に並べられた順序付けのシーケンスを得る.
package main
import (
"fmt"
"math/rand"
"time"
)
// selectSort
func SelectSort(arr *[80000]int) {
//
//(*arr)[1] = 600 arr[1] = 900
//arr[1] = 900
//1. arr[0] =>
//1 arr[0]
for j := 0; j < len(arr) - 1; j++ {
max := arr[j]
maxIndex := j
//2. 1---[len(arr) -1]
for i := j + 1; i < len(arr); i++ {
if max < arr[i] { //
max = arr[i]
maxIndex = i
}
}
//
if maxIndex != j {
arr[j], arr[maxIndex] = arr[maxIndex], arr[j]
}
//fmt.Printf(" %d %v
", j+1 ,*arr)
}
/*
max = arr[1]
maxIndex = 1
//2. 2---[len(arr) -1]
for i := 1 + 1; i < len(arr); i++ {
if max < arr[i] { //
max = arr[i]
maxIndex = i
}
}
//
if maxIndex != 1 {
arr[1], arr[maxIndex] = arr[maxIndex], arr[1]
}
fmt.Println(" 2 ", *arr)
max = arr[2]
maxIndex = 2
//2. 3---[len(arr) -1]
for i := 2 + 1; i < len(arr); i++ {
if max < arr[i] { //
max = arr[i]
maxIndex = i
}
}
//
if maxIndex != 2 {
arr[2], arr[maxIndex] = arr[maxIndex], arr[2]
}
fmt.Println(" 3 ", *arr)
max = arr[3]
maxIndex = 3
//2. 4---[len(arr) -1]
for i := 3 + 1; i < len(arr); i++ {
if max < arr[i] { //
max = arr[i]
maxIndex = i
}
}
//
if maxIndex != 3 {
arr[3], arr[maxIndex] = arr[maxIndex], arr[3]
}
fmt.Println(" 4 ", *arr)*/
}
func main() {
// ,
//arr := [6]int{10, 34, 19, 100, 80, 789}
var arr [80000]int
for i := 0; i < 80000; i++ {
arr[i] = rand.Intn(900000)
}
//fmt.Println(arr)
start := time.Now().Unix()
SelectSort(&arr)
end := time.Now().Unix()
fmt.Printf(" =%d ", end - start)
fmt.Println("main ")
//fmt.Println(arr)
}挿入順序は内部並べ替え法で、並べ替えを求める要素に対して挿入する方法で要素の適切な位置を探して、並べ替えの目的を達成します.
並べ替えの思想を挿入:
並べ替えの挿入(Insertion Sorting)の基本的な考え方は、n個の順序付けされている要素を秩序表と無秩序表として見て、最初の順序表には一つの要素しか含まれていません.無秩序表にはn-1個の要素が含まれています.順序付け中には毎回無秩序表から最初の要素を取り出して、順序表要素の順序付けコードと比較して、秩序表の中の適切な位置に挿入します.新しい秩序表にします.
package main
import (
"fmt"
"math/rand"
"time"
)
func InsertSort(arr *[80000]int) {
// ，
for i := 1; i < len(arr); i++ {
insertVal := arr[i]
insertIndex := i - 1 //
//
for insertIndex >= 0 && arr[insertIndex] < insertVal {
arr[insertIndex + 1] = arr[insertIndex] //
insertIndex--
}
//
if insertIndex + 1 != i {
arr[insertIndex + 1] = insertVal
}
//fmt.Printf(" %d %v
",i, *arr)
}
/*
// 2 ， 3
insertVal = arr[2]
insertIndex = 2 - 1 //
//
for insertIndex >= 0 && arr[insertIndex] < insertVal {
arr[insertIndex + 1] = arr[insertIndex] //
insertIndex--
}
//
if insertIndex + 1 != 2 {
arr[insertIndex + 1] = insertVal
}
fmt.Println(" 2 ", *arr)
// 3 ， 4
insertVal = arr[3]
insertIndex = 3 - 1 //
//
for insertIndex >= 0 && arr[insertIndex] < insertVal {
arr[insertIndex + 1] = arr[insertIndex] //
insertIndex--
}
//
if insertIndex + 1 != 3 {
arr[insertIndex + 1] = insertVal
}
fmt.Println(" 3 ", *arr)
// 4 ， 5
insertVal = arr[4]
insertIndex = 4 - 1 //
//
for insertIndex >= 0 && arr[insertIndex] < insertVal {
arr[insertIndex + 1] = arr[insertIndex] //
insertIndex--
}
//
if insertIndex + 1 != 4 {
arr[insertIndex + 1] = insertVal
}
fmt.Println(" 4 ", *arr)*/
}
func main() {
//arr := [7]int{23, 0, 12, 56, 34, -1, 55}
var arr [80000]int
for i := 0; i < 80000; i++ {
arr[i] = rand.Intn(900000)
}
//fmt.Println(arr)
start := time.Now().Unix()
//fmt.Println(" =", arr)
InsertSort(&arr)
end := time.Now().Unix()
fmt.Println("main ")
fmt.Printf(" %d ", end-start)
//fmt.Println(arr)
}クイックソート(Quicksort)バブル順序の改善の一つです.基本的な考え方は、順序付けされるデータを1つの順序で独立した2つの部分に分割します.その中の一部のすべてのデータは他の部分のすべてのデータよりも小さいです.そして、この方法によって、この2つの部分のデータをそれぞれ迅速に並べ替えて、順序付けプロセス全体を再帰的に行うことができます.これによってデータ全体が秩序化されます.シーケンス
package main
import (
"fmt"
"math/rand"
"time"
)
//
//
//1. left
//2. right
//3 array
func QuickSort(left int, right int, array *[8000000]int) {
l := left
r := right
// pivot ，
pivot := array[(left + right) / 2]
temp := 0
//for pivot
// pivot
for ; l < r; {
// pivot pivot
for ; array[l] < pivot; {
l++
}
// pivot pivot
for ; array[r] > pivot; {
r--
}
// 1 >= r , break
if l >= r {
break
}
//
temp = array[l]
array[l] = array[r]
array[r] = temp
//
if array[l]== pivot {
r--
}
if array[r]== pivot {
l++
}
}
// 1== r,
if l == r {
l++
r--
}
//
if left < r {
QuickSort(left, r, array)
}
//
if right > l {
QuickSort(l, right, array)
}
}
func main() {
// arr := [9]int {-9,78,0,23,-567,70, 123, 90, -23}
// fmt.Println(" ", arr)
var arr [8000000]int
for i := 0; i < 8000000; i++ {
arr[i] = rand.Intn(900000)
}
//fmt.Println(arr)
start := time.Now().Unix()
//
QuickSort(0, len(arr) - 1, &arr)
end := time.Now().Unix()
fmt.Println("main..")
fmt.Printf(" %d ", end - start)
//fmt.Println(arr)
}スタック
package main
import (
"fmt"
)
func test(n int) {
if n > 2 {
n-- // æ»é¾Ÿ
test(n)
} else {
fmt.Println("n=", n)
}
}
func main() {
n := 4
test(n)
}一部のプログラマはまたスタックをスタックと呼んでいます.つまり、スタックとスタックは同じ概念です.
1)スタックの英語は(stack)2)スタックで、先に入れてから出す(FILO-First In Last Out)のシーケンステーブルです.3)スタック(stack)は、線形表の要素の挿入と削除を制限する特殊な線形表です.挿入と削除を許可する端は、変化の一端として、スタックトップ(Top)といいます.他端はボトムと呼ばれます.4)スタックの定義により、最初にスタックの中の要素をスタックの底に入れ、最後に入れた要素がスタックの上にあることが分かります.削除要素はちょうど反対です.最後に入れた要素は最初に削除し、最初に入れた要素は最後に削除されます.
スタックの応用シーン
1)サブルーチンの呼び出し:サブルーチンにジャンプする前に、次の命令のアドレスをスタックに保存し、サブルーチンが実行された後にアドレスを取り出して元のプログラムに戻す.変換とシークレット.4)二叉樹のエルゴード.5)図形の深さ優先検索法
package main
import (
"fmt"
"errors"
)
//
type Stack struct {
MaxTop int //
Top int // , ， Top
arr [5]int //
}
//
func (this *Stack) Push(val int) (err error) {
//
if this.Top == this.MaxTop - 1 {
fmt.Println("stack full")
return errors.New("stack full")
}
this.Top++
//
this.arr[this.Top] = val
return
}
//
func (this *Stack) Pop() (val int, err error) {
//
if this.Top == -1 {
fmt.Println("stack empty!")
return 0, errors.New("stack empty")
}
// ， this.Top--
val = this.arr[this.Top]
this.Top--
return val, nil
}
// ，
func (this *Stack) List() {
//
if this.Top == -1 {
fmt.Println("stack empty")
return
}
fmt.Println(" ：")
for i := this.Top; i >= 0; i-- {
fmt.Printf("arr[%d]=%d
", i, this.arr[i])
}
}
func main() {
stack := &Stack{
MaxTop : 5, // 5
Top : -1, // -1，
}
//
stack.Push(1)
stack.Push(2)
stack.Push(3)
stack.Push(4)
stack.Push(5)
//
stack.List()
val, _ := stack.Pop()
fmt.Println(" val=", val) // 5
//
stack.List() //
fmt.Println()
val, _ = stack.Pop()
val, _ = stack.Pop()
val, _ = stack.Pop()
val, _ = stack.Pop()
val, _ = stack.Pop()//
fmt.Println(" val=", val) // 5
//
stack.List() //
}package main
import (
"fmt"
"errors"
"strconv"
)
//
type Stack struct {
MaxTop int //
Top int // , ， Top
arr [20]int //
}
//
func (this *Stack) Push(val int) (err error) {
//
if this.Top == this.MaxTop - 1 {
fmt.Println("stack full")
return errors.New("stack full")
}
this.Top++
//
this.arr[this.Top] = val
return
}
//
func (this *Stack) Pop() (val int, err error) {
//
if this.Top == -1 {
fmt.Println("stack empty!")
return 0, errors.New("stack empty")
}
// ， this.Top--
val = this.arr[this.Top]
this.Top--
return val, nil
}
// ，
func (this *Stack) List() {
//
if this.Top == -1 {
fmt.Println("stack empty")
return
}
fmt.Println(" ：")
for i := this.Top; i >= 0; i-- {
fmt.Printf("arr[%d]=%d
", i, this.arr[i])
}
}
// [+, - , * , /]
func (this *Stack) IsOper(val int) bool {
if val == 42 || val == 43 || val == 45 || val == 47 {
return true
} else {
return false
}
}
//
func (this *Stack) Cal(num1 int, num2 int, oper int) int{
res := 0
switch oper {
case 42 :
res = num2 * num1
case 43 :
res = num2 + num1
case 45 :
res = num2 - num1
case 47 :
res = num2 / num1
default :
fmt.Println(" .")
}
return res
}
// ， [ ]
//[* / => 1 + - => 0]
func (this *Stack) Priority(oper int) int {
res := 0
if oper == 42 || oper == 47 {
res = 1
} else if oper == 43 || oper == 45 {
res = 0
}
return res
}
func main() {
//
numStack := &Stack{
MaxTop : 20,
Top : -1,
}
//
operStack := &Stack{
MaxTop : 20,
Top : -1,
}
exp := "30+30*6-4-6"
// index ， exp
index := 0
// ，
num1 := 0
num2 := 0
oper := 0
result := 0
keepNum := ""
for {
// ，
//
ch := exp[index:index+1] // .
//ch ==>"+" ===> 43
temp := int([]byte(ch)[0]) // ASCiI
if operStack.IsOper(temp) { //
// operStack ，
if operStack.Top == -1 { //
operStack.Push(temp)
}else {
// opertStack
//， pop ， pop ， ，
// ，
if operStack.Priority(operStack.arr[operStack.Top]) >=
operStack.Priority(temp) {
num1, _ = numStack.Pop()
num2, _ = numStack.Pop()
oper, _ = operStack.Pop()
result = operStack.Cal(num1,num2, oper)
//
numStack.Push(result)
//
operStack.Push(temp)
}else {
operStack.Push(temp)
}
}
} else { //
//
//1. keepNum string,
keepNum += ch
//2. index ， ，
// ， keepNum
if index == len(exp) - 1 {
val, _ := strconv.ParseInt(keepNum, 10, 64)
numStack.Push(int(val))
} else {
// index [index]
if operStack.IsOper(int([]byte(exp[index+1:index+2])[0])) {
val, _ := strconv.ParseInt(keepNum, 10, 64)
numStack.Push(int(val))
keepNum = ""
}
}
}
//
// index
if index + 1 == len(exp) {
break
}
index++
}
// ， ， ，
// ， ，
for {
if operStack.Top == -1 {
break //
}
num1, _ = numStack.Pop()
num2, _ = numStack.Pop()
oper, _ = operStack.Pop()
result = operStack.Cal(num1,num2, oper)
//
numStack.Push(result)
}
// ， ， numStack
res, _ := numStack.Pop()
fmt.Printf(" %s = %v", exp, res)
}再帰的な応用シーン「迷宮問題」
再帰的概念
簡単に言いますと、第帰は関数/方法自分で自分を呼び出して、毎回呼び出した時に異なる変数が入ってきます.第帰はプログラミング者に複雑な問題を解決するのに役立ちます.同時にコードを簡潔にすることができます.
どのような問題を解決するために再帰的に使用されますか?
1)各種数学問題:8皇后問題、ハノータ、階乗問題、迷宮問題、ボールとバスケットの問題(googleプログラミングコンテスト)2)はスタックで解決する問題です.第帰コードは比較的簡潔です.
再帰的に守るべき重要な原則
1)関数を実行すると、新しい保護された独立空間(新しい関数スタック)2を作成します.関数の局所変数は独立しています.相互に影響はありません.各関数スタックが同じデータを使用したいなら、参照転送3を使用して再帰的条件に迫る必要があります.さもなくば無限再帰で、死んだカメ:)4)一つの関数が実行し終わったら、あるいはreturnに会ったら、戻ってきます.誰の呼出に従い、結果を誰に返しますか?
package main
import (
"fmt"
)
// ，
//myMap *[8][7]int: ， ，
//i,j
func SetWay(myMap *[8][7]int, i int, j int) bool {
// ，
//myMap[6][5] == 2
if myMap[6][5] == 2 {
return true
} else {
//
if myMap[i][j] == 0 { //
// ,
//
myMap[i][j] = 2
if SetWay(myMap, i + 1, j) { //
return true
} else if SetWay(myMap, i , j + 1) { //
return true
} else if SetWay(myMap, i - 1, j) { //
return true
} else if SetWay(myMap, i , j - 1) { //
return true
} else { //
myMap[i][j] = 3
return false
}
} else { // ， 1，
return false
}
}
}
func main() {
// ，
//
//1. 1 ，
//2. 0,
//3. 2,
//4. 3， ，
var myMap [8][7]int
// 1
for i := 0 ; i < 7 ; i++ {
myMap[0][i] = 1
myMap[7][i] = 1
}
// 1
for i := 0 ; i < 8 ; i++ {
myMap[i][0] = 1
myMap[i][6] = 1
}
myMap[3][1] = 1
myMap[3][2] = 1
// ?myMap[1][2] = 1
// ?myMap[2][2] = 1
//
for i := 0; i < 8; i++ {
for j := 0; j < 7; j++ {
fmt.Print(myMap[i][j], " ")
}
fmt.Println()
}
//
SetWay(&myMap, 1, 1)
fmt.Println(" ....")
//
for i := 0; i < 8; i++ {
for j := 0; j < 7; j++ {
fmt.Print(myMap[i][j], " ")
}
fmt.Println()
}
}実際の需要
google社の一つの問題:
ある会社では、新入社员が报道されると、その社员の情报を(id,性别,年齢,住所.)に入れるように要求しています.この社员のIDを入力すると、その社员の情报をすべて调べることが要求されます.
ハッシュ表の基本的な紹介
ハッシュテーブルとは、キーコード値に従って直接アクセスするデータ構造であり、つまり、キーパーコード値を表の位置にマッピングすることによって、検索の速度を速くすることができる.このマッピング関数はハッシュ関数と呼ばれ、記録を保存する配列をハッシュリストと呼ぶ.
hashtableを使って従業員の管理システムを実現します.
応用例google社の一つの問題:
ある会社では、新入社员が报道されると、その社员の情报を(id,性别,年齢,住所.)に入れるように求められています.
要求:
1)データベースを使用しないで、メモリをできるだけ節約して、スピードが速いほどいいです.
1)チェーンを使用してハッシュ・テーブルを実現し、このチェーン・テーブルはヘッダを持たない.
package main
import (
"fmt"
"os"
)
// emp
type Emp struct {
Id int
Name string
Next *Emp
}
// ..
func (this *Emp) ShowMe() {
fmt.Printf(" %d %d
", this.Id % 7, this.Id)
}
// EmpLink
// EmpLink ,
type EmpLink struct {
Head *Emp
}
// ..
//1. , ，
func (this *EmpLink) Insert(emp *Emp) {
cur := this.Head //
var pre *Emp = nil // pre cur
// EmpLink
if cur == nil {
this.Head = emp //
return
}
// , emp
// cur emp ， pre cur
for {
if cur != nil {
//
if cur.Id > emp.Id {
//
break
}
pre = cur //
cur = cur.Next
}else {
break
}
}
// ， emp
pre.Next = emp
emp.Next = cur
}
//
func (this *EmpLink) ShowLink(no int) {
if this.Head == nil {
fmt.Printf(" %d
", no)
return
}
// ，
cur := this.Head //
for {
if cur != nil {
fmt.Printf(" %d id=%d =%s ->", no, cur.Id, cur.Name)
cur = cur.Next
} else {
break
}
}
fmt.Println() //
}
// id ， nil
func (this *EmpLink) FindById(id int) *Emp {
cur := this.Head
for {
if cur != nil && cur.Id == id {
return cur
} else if cur == nil {
break
}
cur = cur.Next
}
return nil
}
// hashtable ,
type HashTable struct {
LinkArr [7]EmpLink
}
// HashTable Insert .
func (this *HashTable) Insert(emp *Emp) {
// ，
linkNo := this.HashFun(emp.Id)
//
this.LinkArr[linkNo].Insert(emp) //
}
// ， hashtable
func (this *HashTable) ShowAll() {
for i := 0; i < len(this.LinkArr); i++ {
this.LinkArr[i].ShowLink(i)
}
}
//
func (this *HashTable) HashFun(id int) int {
return id % 7 // ，
}
// ，
func (this *HashTable) FindById(id int) *Emp {
// ，
linkNo := this.HashFun(id)
return this.LinkArr[linkNo].FindById(id)
}
func main() {
key := ""
id := 0
name := ""
var hashtable HashTable
for {
fmt.Println("=============== ============")
fmt.Println("input ")
fmt.Println("show ")
fmt.Println("find ")
fmt.Println("exit ")
fmt.Println(" ")
fmt.Scanln(&key)
switch key {
case "input":
fmt.Println(" id")
fmt.Scanln(&id)
fmt.Println(" name")
fmt.Scanln(&name)
emp := &Emp{
Id : id,
Name : name,
}
hashtable.Insert(emp)
case "show":
hashtable.ShowAll()
case "find":
fmt.Println(" id :")
fmt.Scanln(&id)
emp := hashtable.FindById(id)
if emp == nil {
fmt.Printf("id=%d
", id)
} else {
// ，
emp.ShowMe()
}
case "exit":
os.Exit(0)
default :
fmt.Println(" ")
}
}
}