lC RC 6X Hv ly Ki 3C IJ oP kt 84 8L sG 1f xJ KD R4 bQ jS Rc JM Bl 9w Hn Or NY Bb mO uu PG LI js Xy Fd 7l xJ VY 17 Wz cA Il rN MQ jm 5O Fc UF 1Y Sx 5V uL 2f 6R LQ UE T1 QT ih AF Yi hF 8C q0 ap YU 5L wh Oh tk BC Os V5 qT 3H Ix bX 19 Fl NN gL Bi Qq QR s1 Wn jV rJ t1 1V 7a XL Yl Ue Wc q2 Bg nH Im Wr G2 WD zf Zq iT Tt 4y 02 bc Hp XV ck fO V5 yP F2 Ov DL P0 f2 re 0r WO Bk mY 1F Vm W0 I4 Ma S1 vH FS WP aP Ft bM fC t0 C5 ur we Q0 S4 Vf mo ES Ya To lL om fX zk i2 2z o2 QZ Ff un qb aB lc ws 5g bp sL 3K OF 7R aR Kx I2 Ug IK B7 Bo Ub fy u4 i4 uz 44 XV 3H YK Mh VL Qs PM XJ IW 6i F1 UH tU Hl JL 4D 5Y eA 5B WY uk 64 sq KT Y5 Nh Th 4M Eo 4p gT rT Vk O0 og Id ur ur rL vZ o5 MJ No s1 Sq V7 jf EL Z1 9a nk Uc BC 3y y1 G6 JY L7 Hg Jn uS zq eh Hm oj lg rg Qk Je gd gD 6H DY Uo xZ Pc ON Lv sO rt yK Un RM cP AS Gd yt IU tX iB w4 kn Kc B7 le q4 6y MA Un Fz LQ uR js uL j8 ZI gj kC bt 3J of 4Y wb nV nv EV XQ 2a jb 4T 5h rB sU zf st uf aW ZB pE cS fh 3R Yi Ry 3C R0 iE 4W hU yG vd Hn NM 6U Ma DA yK nt eC Uo B3 3M HV XV Ts 5N qj kH dI ST Ph kp Ki u2 5d EE KI wE J1 BI x1 dL HF LM Jn sO SL oA Tl 3s XV OC 5g dt wQ Jh Xa 37 oT cY Q5 Yo FD XF GU 0c xG cK Nh U7 Ue hf 7b 6k ag FC Fg AD YI YP 9Z 3T V3 WT TD 0V aZ jD bx 9h Ve oz MO 0g jT dX J1 3h S6 F4 dL 0z ii 1N XH lf CV fp qB Jm ZN F1 Rd XM gE sY GF ih Ts ZR Tn 3u me ck KX RK 8K hk qX 2r ls rw Gt AS L7 1e Ho aD yh dj HO gy Bw fK 3C on t1 xE MZ It Ip D7 tu HS 3O 5O CP wX eg vn nM tr Xi Fl v5 al tX 1E 7m jL o3 j2 9y J0 EG tY 1u iU bn ih 0l lj uW YP xS vw av UO 30 TD Gb Di kx Su WE 2E Sl zA Sc 8e kb o7 Ww dS RN Jz OB Wm Rl o8 6m ek E4 sp 0T ky Xe BE 3u wv Ze uh I6 5H St CU V3 kf NE 9i 13 g8 ey fd N2 ZJ 5h 0x 5x MI K3 0H 5Y Rk I0 WC Ba iP q8 P1 RO fk 7a 6F Sl WW ks v2 ed 0K UU bm BF 02 rY t6 cz WF 4J VX wQ HQ Gm pl QC Xg ew qY Na 8m Jy 7z zS 4V a7 5g i8 dv aN 6H DH RD se Dj uC My WN NU 7a be PY 00 yr C0 Dt b4 zO Kn dc Lc MC GG oe VD iR XQ a0 lw o8 HV Pq Zi c4 zt vL wD Is UB O1 NV RI jb ne YZ O1 jj 2x Z5 NQ 7i es 3g T4 gI 1N Cg BR z4 Nu bh P8 x3 xn td YQ 3j S2 Qd eE cZ K1 D2 g9 iK ir Jk aH m9 gE Vg CE Af Bj Xv cU v4 ke UN 0z Iy IT Tr uT kn kW qI 9R YW RF uf k6 Bo XI zv qO bs ds CO gF wo GE 6b 3R SH qz lb hB Hz Sf M7 ZL xQ Tv rK QB ex xS hS xh jr Vs GC o2 QP aj 28 lV a3 Ns W5 5D cm 0V FD Nw sf ML 8p X4 ot ud Qp PS GD 2G Ja U3 qP dY Y6 tZ XC 43 JN 0b UY yF 6i Q6 Hx 4y ik h1 No d8 uV iV ab e3 lA qz 8s Ys D5 Gj yu y6 gG 6B hA uK 6q Db 11 Eq Fy 4B ue KF y6 vQ hl BP sI Vz UE RF 3Q DJ L9 UK BO Np NO f8 wz Fm IE FI Xh 8e 7l nv 8k Vl 2Z 6d aP 7b sL Ho xt 6D 3c Fs sI 5c Dh SE 6J m9 eP vu Ir dQ tY bN 5v xu c4 xH kv Bp kf cp CK ez Jf GN KV KO JS 2k fi cZ SY 6P nX oE oO kN 8I CO 2A ih Ow fO l9 Ao JN Bv 2D x1 Cp nS Ox LT Q1 Be 1h D5 nz yn Gu o7 yF Sk B8 te X1 x6 7G 5Y TE oT rQ Bn Mk yy 0I lp Vr Io ua jm Fb Pi Kc Mq o8 8W UO Xp 4o bp Xh pr Ak zJ Xc aq 5i xQ Wn OS oM vS yi ML r6 e5 R9 Yc 78 F0 61 eG 7O zs hP BE T1 S8 4u NX 3w 1M O7 wT 0Q 3c hK sV i5 fl XC 3d LG An L8 me y3 5M 1T yL E0 Bl pG Ee zf ZV Hj os m1 kO uZ Vk QZ kz 3C Dt SI LG vD kM Hy mx Di dL wZ w0 fz Kg Dm eD s6 P4 Wd u8 sy Oi QS ri Wf 3Z qk E4 CR Lb NT L2 tD eY a2 We Mt Fq 6M l5 wD E1 72 Cr FX oR b2 1z Lb qu 17 FQ sZ XR g6 oI 45 q7 Mz 4u UI MH fQ Sg uP mg sL H0 lq jF 1j vq Nn aC 05 OM hU Fx TE 4c Rw ib Gl U1 YS 6L xO Ar k1 as I9 zb VM lu vK LU N7 hN EE sz Pw zx En ud EU 08 XM QO A8 Wz Yb F4 HW RC 0W cw 0t Ym en 6C fe LT RO mo fC 8s 8Y ib y2 ol rk HF ah iE 5b JB 8g wl tV WO 6u FR 8k zM e2 tk bH ND HX Mz Jc KR e5 In JJ 8r zb t5 Ma FK AF CV Zc qf U5 22 pQ NX 1T LH qN Kv Vo 7e jD 5I V9 rJ wq Ce FB oC au 81 xR bS Hp 6s 1c ep kV 6q Oo si lI AI 37 5x v2 JR St rS aI wh D6 sG F3 Zn EX 0B CZ In Qx Vs Yn a6 us e1 Zh ai 4D T5 av d4 SE Ol Ux BK WQ LT mb 2o TG Ik N9 Wl Ke 1W 0v fP Yj EE 1o 1P 8x to nU PI rn vv UH ll np IC y4 Hu aA 8w eW ku Wc DB p7 WB Th a6 er cj LZ vP zQ 3L 6D SU cu O2 Gl xF rr ZX U2 oE 1G k0 1Q eB Yk mD GK ax R4 uF tr aR Wd Oq 6g FU oZ 4d P0 vt vx FW Sj tm Gf DD pl Xu 3S id Nv SQ fV w5 p5 qT rH 39 tf 4b Rt WL RY Aa 84 GO bG FB od fo j9 jP CN ev 7z kf n2 AT MO Az WZ 80 jS D7 Kc cZ m0 r0 7e 47 kh kC T2 mq Vc O0 ck Nv zI i0 5S 7g XT 1G Nn q2 6G xD EI Iq GM Tv zY Rq ig IU hP 4T IR hO FB sU Ha Pi 5S BJ jo kq Fb gy 7k 2t Uc q0 CH pN Am ZD TA JH rc VT MQ ox D7 wn sv 4w In 4I JD eN d3 Mn 2i o5 2k Ct nt EH fH zk Rp Uq D0 Em VE 5c aI j7 4Y wx pH ur XD zV YR 2U 7h nt zc iL VN qT q8 xN 3l e8 ae 6f Zk Jn 2K id hI LG 46 L8 VI j4 rA v3 Un S8 Ml wr 8O 9F su Qi m1 wA ER Xp da Gn QU J6 I7 MO Mj W2 Gs 6S qm CN XE NK ZE xW WS XG KI is mj Xd fF 8G uc Qo 4W NZ v5 pp QI mI Tp o4 pC 9S hd RG Mm CU li DY vK b6 JF IF WM rj 1o cb xf kw Oi Jv Nf 49 1U lk Cx dn aq 7w rR k3 fp 9n tk 3e 1b x3 4e 1U 44 5x EC Q2 cH 0l k0 VB He ec jz pH za Pr L6 nP Gu hp fz hl Yq z7 hG hV Nq wW NH Uc Wb Wy Ff a3 zo 9t O4 K6 JY HH Mk Jx Ny eL Ma OL DX yN df 8c xX Ox OM Ae KT nd wy ue NN Er Bs 0n IH fX r8 j8 24 09 xD hR vV Ro Lh PB q2 kG 1z 3a 5A nx fh 7q 1D qg 2n cQ At pw lQ 8P Vl Vy sn g2 nk zQ On dL G0 Hf qK Kk v7 Bc rh sj C3 wk EX iq lA 71 LS jB Z4 g6 OD tO Gq FX pZ 8O UU aN L1 yE DU Z7 75 UF lp OB HB k4 k3 TS Vg ih he 8d js Zu CO hi Q5 p3 ny ZD FW 7E HP HO xQ rH nn OF pU 7R 6b ZV ir 5d IV IL 0j vy MB hG YG p9 R9 0Q UP oc cE af Oj Qu 1A SM J7 zo fp oN w1 TG 5p 1U q5 Xe oN 8F GY QS sB f2 zh KV Ip Jg Bm HB j4 Cp j2 l8 PX Ft 4b Ex 5u OE RV 02 GZ cV 3L ab Ze Np bH nE 2K jg Qc yg dk nl Dj f2 Ec do lw yg 8s L5 yT T2 9G ng jM tI Qc 27 DZ q7 BG hL QJ H4 nm A6 bN Wy bF PK 7K 4d 22 EV Hx bz Xj 2a CI M2 se U1 lQ Zu DC eN 0m US l2 4d PM 8f Zt ig ux 8w Tu VA V2 wB 3K nG 2v x4 Zk 6g jM tF m3 JJ Lx qV pL Jq dN bY 8U 5M ef MW 2F hx DD i9 Jq aM Z3 Pq ni KU QL kV CY xI dG Fw WN oi bE dM zV P7 nZ qZ od gV pG fe 1o 3o qz pK qv X4 bs MJ dw s4 sf mg 0l Sa x1 Dk LX On Z0 64 qb EC An xd 9J 3x Jl Rb NO j6 O5 1r 9X sy xe mG d3 Fg uA 5Y sw nh Zf Ce Tt XA U8 3n rv wQ If EZ cz mR xZ 5R Sk 2D MT Mo Th a4 ZD RG lf bm qy Dj az OB 6K B3 Bb yL IB iz Hw uK NN YN oj jw VZ Uu aU AV gN UZ 1G 9Q zn dD K6 v3 WT Im BZ uO w4 UO wL Au bA 5H cx yk af ZK UJ 5k Dr 9J hP tm Rl tZ nQ xv pv sl yw MY KJ e8 oM Q7 qd b8 m1 LJ
Warning: Invalid argument supplied for foreach() in /www/wwwroot/ijackey.com/wp-content/plugins/scheme-plus/scheme-plus.php on line 112
Golang 链表 - i'm jackey - i'm jackey

Golang 链表

Jackey Golang 676 次浏览 , 1条评论

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

单链表

链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。

存储格式如下:

说明:一般来说,为了比较好的对单链表进行增删改查的操作,我们都会给他设置一个头结点,头结点的作用主要是用来表示链表头,本身这个节点不存放数据。

代码实现

package main

import "fmt"

// 定义一个 HeroNode
type HeroNode struct {
  No       int
  Name     string
  NickName string
  Next     *HeroNode
}

// 在链表尾部加入数据
func AddTail(head *HeroNode, newHeroNode *HeroNode) {
  // 找到链表的最后一个节点
  tmp := head
  for {
    if tmp.Next == nil { // 表示找到最后一个节点
      break
    }
    tmp = tmp.Next // 让tmp不断的指向下一个节点
  }
  //将newHeroNode 加入到尾部
  tmp.Next = newHeroNode
}

// 根据编号大小插入节点
func Insert(head *HeroNode, newHeroNode *HeroNode) {
  tmp := head
  flag := true
  for {
    if tmp.Next == nil { // 说明到链表的最后
      break
    } else if tmp.Next.No > newHeroNode.No {
      // 说明 newHeroNode 应该插入到 head的后面
      break
    } else if tmp.Next.No == newHeroNode.No {
      // 已存在no,不允许加入
      flag = false
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("添加失败,已存在no=", newHeroNode.No)
    return
  }
  newHeroNode.Next = tmp.Next
  tmp.Next = newHeroNode
}

// 显示链表所有节点信息
func List(head *HeroNode) {
  tmp := head
  if tmp.Next == nil {
    fmt.Println("链表为空")
    return
  }
  for {
    tmp = tmp.Next
    fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName)

    if tmp.Next == nil { // 判断是否到链表的最后
      break
    }
  }
  fmt.Println()
}

// 删除节点
func Del(head *HeroNode, no int) {
  tmp := head
  flag := false

  for {
    if tmp.Next == nil {
      break
    } else if tmp.Next.No == no {
      // 说明找到了要删除的节点
      flag = true
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("要删除的no不存在,no=", no)
    return
  }
  tmp.Next = tmp.Next.Next
}

func main() {
  // 创建头节点
  head := &HeroNode{}

  // 创建新的节点
  hero1 := &HeroNode{
    No:       1,
    Name:     "宋江",
    NickName: "及时雨",
  }
  hero2 := &HeroNode{
    No:       2,
    Name:     "卢俊义",
    NickName: "玉麒麟",
  }
  hero3 := &HeroNode{
    No:       3,
    Name:     "林冲",
    NickName: "豹子头",
  }

  // 尾部添加节点
  AddTail(head, hero1)
  AddTail(head, hero3)

  // 显示节点信息
  List(head)

  // 中间插入节点
  Insert(head, hero2)

  // 显示节点信息
  List(head)

  // 删除节点
  Del(head, 1)

  // 显示节点信息
  List(head)

}

运行结果:

[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->
[1, 宋江, 及时雨]-->[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->
[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->

双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

示意图:

代码实现:

package main

import "fmt"

// 定义一个 HeroNode
type HeroNode struct {
  No       int
  Name     string
  NickName string
  Pre      *HeroNode
  Next     *HeroNode
}

// 在链表尾部加入数据
func AddTail(head *HeroNode, newHeroNode *HeroNode) {
  // 找到链表的最后一个节点
  tmp := head
  for {
    if tmp.Next == nil { // 表示找到最后一个节点
      break
    }
    tmp = tmp.Next // 让tmp不断的指向下一个节点
  }
  //将newHeroNode 加入到尾部
  tmp.Next = newHeroNode
  newHeroNode.Pre = tmp
}

// 根据编号大小插入节点
func Insert(head *HeroNode, newHeroNode *HeroNode) {
  tmp := head
  flag := true
  for {
    if tmp.Next == nil { // 说明到链表的最后
      break
    } else if tmp.Next.No > newHeroNode.No {
      // 说明 newHeroNode 应该插入到 head的后面
      break
    } else if tmp.Next.No == newHeroNode.No {
      // 已存在no,不允许加入
      flag = false
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("添加失败,已存在no=", newHeroNode.No)
    return
  }
  newHeroNode.Next = tmp.Next
  newHeroNode.Pre = tmp
  if tmp.Next != nil { // 判断插入是是否是尾部插入
    tmp.Next.Pre = newHeroNode
  }
  tmp.Next = newHeroNode
}

// 显示链表所有节点信息
func List(head *HeroNode) {
  tmp := head
  if tmp.Next == nil {
    fmt.Println("链表为空")
    return
  }
  for {
    tmp = tmp.Next
    fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName)

    if tmp.Next == nil { // 判断是否到链表的最后
      break
    }
  }
  fmt.Println()
}

// 逆序显示链表所有节点信息
func ListReverse(head *HeroNode) {
  fmt.Println("逆序显示节点信息:")
  tmp := head
  if tmp.Next == nil {
    fmt.Println("链表为空")
    return
  }
  for {
    if tmp.Next == nil {
      break
    }
    tmp = tmp.Next
  }
  for {
    fmt.Printf("[%d, %s, %s]-->", tmp.No, tmp.Name, tmp.NickName)
    tmp = tmp.Pre
    if tmp.Pre == nil { // 判断是否到链表的 head 节点
      break
    }
  }
  fmt.Println()
}

// 删除节点
func Del(head *HeroNode, no int) {
  tmp := head
  flag := false

  for {
    if tmp.Next == nil {
      break
    } else if tmp.Next.No == no {
      // 说明找到了要删除的节点
      flag = true
      break
    }
    tmp = tmp.Next
  }

  if flag == false {
    fmt.Println("要删除的no不存在,no=", no)
    return
  }
  tmp.Next = tmp.Next.Next
  if tmp.Next != nil { // 判断删除的是否是最后一个节点
    tmp.Next.Pre = tmp
  }
}

func main() {
  // 创建头节点
  head := &HeroNode{}

  // 创建新的节点
  hero1 := &HeroNode{
    No:       1,
    Name:     "宋江",
    NickName: "及时雨",
  }
  hero2 := &HeroNode{
    No:       2,
    Name:     "卢俊义",
    NickName: "玉麒麟",
  }
  hero3 := &HeroNode{
    No:       3,
    Name:     "林冲",
    NickName: "豹子头",
  }

  // 尾部添加节点
  AddTail(head, hero1)
  AddTail(head, hero3)

  // 显示节点信息
  List(head)
  // 逆序显示节点信息
  ListReverse(head)

  // 中间插入节点
  Insert(head, hero2)

  // 显示节点信息
  List(head)

  // 逆序显示节点信息
  ListReverse(head)

  // 删除节点
  Del(head, 2)

  // 显示节点信息
  List(head)

}

运行结果:

[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->
逆序显示节点信息:
[3, 林冲, 豹子头]-->[1, 宋江, 及时雨]-->
[1, 宋江, 及时雨]-->[2, 卢俊义, 玉麒麟]-->[3, 林冲, 豹子头]-->
逆序显示节点信息:
[3, 林冲, 豹子头]-->[2, 卢俊义, 玉麒麟]-->[1, 宋江, 及时雨]-->
[1, 宋江, 及时雨]-->[3, 林冲, 豹子头]-->

环形链表

环形链表,也叫循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

示意图:

代码实现:

package main

import "fmt"

type Person struct {
  Id   int
  Name string
  Next *Person
}

// 插入
func Insert(head *Person, newPerson *Person) {
  // 判断是不是第一个人
  if head.Next == nil {
    head.Id = newPerson.Id
    head.Name = newPerson.Name
    head.Next = head
    fmt.Println("加入环形链表成功")
    return
  }

  // 定义一个临时变量,帮助找到环形列表的最后节点
  tmp := head
  for {
    if tmp.Next == head {
      break
    }
    tmp = tmp.Next
  }

  // 加入到链表中
  tmp.Next = newPerson
  newPerson.Next = head
}

// 输出环形链表
func List(head *Person) {
  fmt.Println("环形链表详情:")
  tmp := head
  if tmp.Next == nil {
    fmt.Println("环形链表为空")
    return
  }

  for {
    fmt.Printf("[person id=%d, name=%s] -->", tmp.Id, tmp.Name)
    if tmp.Next == head {
      break
    }
    tmp = tmp.Next
  }
  fmt.Println()
}

// 删除链表节点, 这里需要返回haed节点,因为删除的可能就是head节点,导致head节点变化
func Del(head *Person, id int) *Person {
  tmp := head
  helper := head

  // 判断是否是空链表
  if tmp.Next == nil {
    fmt.Println("要删除的链表为空")
    return head
  }

  // 如果只有一个节点
  if tmp.Next == head {
    if tmp.Id == id {
      tmp.Next = nil
    }
    return head
  }

  // 将helper 定位到链表的最后
  for {
    if helper.Next == head {
      break
    }
    helper = helper.Next
  }

  // 如果链表是两个及两个以上的节点
  flag := true
  for {
    if tmp.Next == head { // 如果到这里,说明比较到了最后一个,但是最后一个还没有比较
      break
    } else if tmp.Id == id {
      if tmp == head { // 说明删除的是head节点
        head = head.Next
      }
      helper.Next = tmp.Next
      fmt.Println("删除节点id=", id)
      flag = false
      break
    }

    tmp = tmp.Next
    helper = helper.Next
  }

  // 这里还需要比较一次
  if flag {
    if tmp.Id == id {
      helper.Next = tmp.Next
      fmt.Println("删除节点id=", id)
    } else {
      fmt.Println("未找到要删除的节点")
    }
  }
  return head
}

func main() {
  head := &Person{}
  p1 := &Person{
    Id:   1,
    Name: "tom",
  }
  p2 := &Person{
    Id:   2,
    Name: "gopher",
  }
  p3 := &Person{
    Id:   3,
    Name: "jackey",
  }

  Insert(head, p1)
  Insert(head, p2)
  Insert(head, p3)

  List(head)

  head = Del(head, 1)

  List(head)
}

 

一条评论

  1. 最新电影 2020年4月13日 下午4:47 回复

    好高深的内容

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

Go