数据结构_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()
}