資料結構_02.線性表及go中切片的實作

2. 線性表

基本特點:節點之間滿足線性關系

動态數組,連結清單,棧,隊列都屬于線性結構(共同點:都隻有一個開始節點和終端節點,主要差別是操作不同)

線性表是零個或有限個相同類型的資料元素的有序清單.

分析go中切片是如何實作的

unsafe包-unsafe包提供了一些跳過go語言類型安全限制的操作。

type uintptr

type uintptr uintptr
           

可以儲存任意指針的位模式的整數類型。

unsafe.Sizeof()-檢視資料所占空間大小

func Sizeof(v ArbitraryType) uintptr
           

Sizeof傳回類型v本身資料所占用的位元組數。傳回值是“頂層”的資料占有的位元組數。例如，若v是一個切片，它會傳回該切片描述符的大小，而非該切片底層引用的記憶體的大小。

一個位元組占用8個bit

func main() {
	var arr []int
	fmt.Println("sizeof =",unsafe.Sizeof(arr))
}
           

Output:

若代碼行2中var arr []int 改為 var arr [2]int，會發現Output：

這裡可以看下slice的結構

type Slice struct {
    * p
    len int
    cap int
}
           

slice的底層有3個元素,若聲明的數組沒有長度,就會顯示3個元素的長度

unsafe.Pointer-萬能指針

type Pointer *ArbitraryType
           

Pointer類型用于表示任意類型的指針。有4個特殊的隻能用于Pointer類型的操作：

1) 任意類型的指針可以轉換為一個Pointer類型值
2) 一個Pointer類型值可以轉換為任意類型的指針
3) 一個uintptr類型值可以轉換為一個Pointer類型值
4) 一個Pointer類型值可以轉換為一個uintptr類型值
           

是以，Pointer類型允許程式繞過類型系統讀寫任意記憶體。使用它時必須謹慎。

建立一個slice檔案夾，在其中建立slice.go的函數

package slice

/*
#include<stdlib.h>
*/
import "C"
//引用了c的子產品，可以使用c的代碼

import (
	"fmt"
	"unsafe"
)

type Myslice struct {
	Data unsafe.Pointer //資料，萬能指針
	len int
	cap int
}

const TAG = 8

//建立切片
func (this *Myslice) Create(c int ,Data ...int) {
	//初始化資料為空
	if len(Data) == 0 {
		return
	}

	//在堆上申請空間
	this.Data = C.malloc(C.ulonglong(c)*8) //ulonglong代表unsigned長整型
	this.len = len(Data)
	this.cap = c

	//在堆上空間填資料
	p := uintptr(this.Data)  // 給定一個指針，傳回整型值
	for i := 0; i < len(Data); i++ {
		//資料指派
		*(*int)(unsafe.Pointer(p)) = Data[i] //強轉成int類型的指針，再取它的值。相當于将Data[i]賦給p所指向的空間
		//指針偏移
		p += TAG  //data往後偏移8位
	}

}

//列印切片
func (this *Myslice) Print() {
	if this == 0 {
		return
	}

	//輔助指針
	p := uintptr(this.Data)
	for i := 0; i < this.len; i++ {
		fmt.Println("值:",*(*int)(unsafe.Pointer(p)))
		p += TAG
	}
}
           

在前面引用了C語言的子產品，進行堆上空間的申請

/*
#include<stdlib.h>
*/
import "C"
//引用了c的子產品，可以使用c的代碼
           

建立在slice檔案夾同級建立main.go檔案，進行調用slice包

package main

import (
	"./slice"
)

func main() {
	var s slice.Myslice
	//建立切片
	s.Create(10,1,2,3,4,5)
	//列印切片
	s.Print()
}