作者简介:

       姜海强:闷骚码农,互联网行业摸爬滚打数余载,先后担任中国体育直播TV主程、网信集团先锋支付架构师、奇虎360服务器端资深开发。热爱技术,喜欢分享,热衷领域:PHP/Golang语言、面向对象设计模式、Redis、Yaf、Yii2、微服务等。

视频课程

yaf+yar微服务-腾讯课堂
yaf+yar微服务-51CTO学院
CSDN学院

Github

个人主页
swoole-boot
roach
roach-orm

QQ群:

姜海强的QQ群

公众号:

360tryst公众号

顺序存储线性表

零个或者多个数据元素组成的有序集合,也就是我们常用的数组。

2.1 顺序存储线性表

顺序存储线性表

代码实现

  1. package line
  2. type LineTable struct {
  3. size int
  4. items []interface{}
  5. length int
  6. }
  7. func NewLineTable(size int) *LineTable {
  8. return &LineTable{
  9. size : size,
  10. items: make([]interface{}, size),
  11. }
  12. }
  13. func (this *LineTable) Length() int {
  14. return this.length
  15. }
  16. func (this *LineTable) Get(index int) interface{} {
  17. if this.length == 0 || index < 0 || this.length - 1 < index {
  18. return nil
  19. }
  20. return this.items[ index ]
  21. }
  22. func (this *LineTable) Set(index int, item interface{}) bool {
  23. if index < 0 || this.length < index || index >= this.size {
  24. return false
  25. }
  26. this.items[ index ] = item
  27. if index == this.length {
  28. this.length++
  29. }
  30. return true
  31. }
  32. func (this *LineTable) Insert(index int, item interface{}) bool {
  33. //索引不能小于0
  34. if index < 0 {
  35. return false
  36. }
  37. //索引超过了容量
  38. if index > (this.size - 1) {
  39. return false
  40. }
  41. //超出范围
  42. if index > this.length {
  43. return false
  44. }
  45. //满了
  46. if this.size == this.length {
  47. return false
  48. }
  49. defer func() {
  50. this.length++
  51. }()
  52. if index <= this.length - 1 {
  53. //从最后一个元素开始移位,直到index位
  54. for i := this.length - 1 ; i >= index; i-- {
  55. this.items[ i + 1 ] = this.items[ i ]
  56. }
  57. }
  58. this.items[ index ] = item
  59. return true
  60. }
  61. func (this *LineTable) Append(item interface{}) bool {
  62. return this.Insert(this.length, item)
  63. }
  64. func (this *LineTable) Prepend(item interface{}) bool {
  65. return this.Insert(0, item)
  66. }
  67. func (this *LineTable) Remove(index int) bool {
  68. if this.length == 0 || index > (this.length - 1) || index < 0 {
  69. return false
  70. }
  71. defer func() {
  72. this.length--
  73. }()
  74. for i := index ; i< this.length - 1; i++ {
  75. this.items[i] = this.items[ i + 1 ]
  76. }
  77. this.items[ this.length - 1 ] = nil
  78. return true
  79. }
  80. func (this *LineTable) Range(f func(index int, item interface{})) {
  81. for i :=0; i < this.length; i++ {
  82. f(i, this.items[i])
  83. }
  84. }

使用

  1. //初始化,长度为10
  2. lt := line.NewLineTable(10)
  3. //向索引位置1插入数据10,由于索引位置0还没有数据,此处插入失败
  4. result := lt.Insert(1, 10)
  5. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  6. //向索引位置0插入数据0,索引位置0为头结点,故插入成功,此时数据为:0
  7. result = lt.Insert(0, 0)
  8. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  9. //向索引位置8插入数据80,由于索引位置7还没有数据,故插入失败,此时数据为:0
  10. result = lt.Insert(8, 80)
  11. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  12. //向索引位置0插入数据10,由于索引位置0存储了数据0,所以在插入过程数据0需要向后移位放到索引位置1,然后将数据10插入到索引位置0
  13. //此时数据为:10 0
  14. result = lt.Insert(0, 10)
  15. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  16. lt.Range(func(index int, item interface{}) {
  17. fmt.Printf("index:%d; item:%v\n", index, item)
  18. })
  19. //向索引位置1插入数据20,索引位置1的数据0继续向后移位到索引位置2,数据20插入到索引位置1
  20. ////此时数据为:10 20 0
  21. result = lt.Insert(1, 20)
  22. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  23. //在尾结点追加数据30,此处即将数据30插入到索引位置3
  24. //此时数据为:10 20 0 30
  25. result = lt.Append(30)
  26. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  27. //在头结点追加数据50,此处即所有索引节点向后移1位,然后将数据50插入到索引位置0
  28. //此时数据为:50 10 20 0 30
  29. result = lt.Prepend(50)
  30. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  31. lt.Range(func(index int, item interface{}) {
  32. fmt.Printf("index:%d; item:%v\n", index, item)
  33. })
  34. lt.Append(60)
  35. lt.Append(70)
  36. lt.Append(80)
  37. lt.Append(90)
  38. lt.Append(100)
  39. //元素数量为10,已经达到最大长度,尾结点追加数据失败
  40. result = lt.Append(110)
  41. fmt.Printf("Insert: %t, lt.Length:%d\n", result, lt.Length())
  42. for i :=0; i < 10; i++ {
  43. fmt.Printf("i:%d; item: %v\n", i, lt.Get(i))
  44. }
  45. //删除
  46. lt.Remove(0)
  47. fmt.Printf("i:%d; item: %v\n", 0, lt.Get(0))
  48. lt.Set(9, 999)
  49. fmt.Printf("i:%d; item: %v\n", 9, lt.Get(9))

以上例程运行结果

  1. Insert: false, lt.Length:0
  2. Insert: true, lt.Length:1
  3. Insert: false, lt.Length:1
  4. Insert: true, lt.Length:2
  5. index:0; item:10
  6. index:1; item:0
  7. Insert: true, lt.Length:3
  8. Insert: true, lt.Length:4
  9. Insert: true, lt.Length:5
  10. index:0; item:50
  11. index:1; item:10
  12. index:2; item:20
  13. index:3; item:0
  14. index:4; item:30
  15. Insert: false, lt.Length:10
  16. i:0; item: 50
  17. i:1; item: 10
  18. i:2; item: 20
  19. i:3; item: 0
  20. i:4; item: 30
  21. i:5; item: 60
  22. i:6; item: 70
  23. i:7; item: 80
  24. i:8; item: 90
  25. i:9; item: 100
  26. i:0; item: 10
  27. i:9; item: 999

时间复杂度

操作 最好时间复杂度 最差时间复杂度
查询 O(1) O(1)
删除 O(1) O(n)
插入 O(1) O(n)
修改 O(1) O(1)

QQ群:

姜海强的QQ群

公众号:

360tryst公众号