数据结构

Ywnline

2019-08-09

概念

数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。
数据元素：数据（集合）中的一个“个体”，数据及结构中讨论的基本单位
数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、字符型等等
逻辑结构：数据之间的相互关系。
- 集合结构中的数据元素除了同属于一种类型外，别无其它关系。
- 线性结构数据元素之间一对一的关系
- 树形结构数据元素之间一对多的关系
- 图状结构或网状结构结构中的数据元素之间存在多对多的关系
物理结构/存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等
在数据结构中,从逻辑上可以将其分为线性结构和非线性结构
数据结构的基本操作的设置的最重要的准则
- 实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”
- 存储的是“物理结构”。逻辑结构主要是对该结构操作的设定物理结构是描述数据具体在内存中的
- 顺序结构、链式结构、索引结构、希哈结构
顺序存储结构中，线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序一般是不同的。
算法五个特性：有穷性、确定性、可行性、输入、输出
算法设计要求：正确性、可读性、健壮性、高效率与低存储量需求。
算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型，不是程序的描述方式。
设计算法在执行时间时需要考虑：算法选用的规模、问题的规模
时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)
空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

线性表

对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型
线性表是一种典型的线性结构。头结点无前驱有一个后继，尾节点无后继有一个前驱。链表只能顺序查找，定位一个元素的时间为O(N)，删除一个元素的时间为O(1)

线性表的顺序存储结构

把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。是一种随机存取的存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。如果是存储，则是指按顺序的，如果是存取，则是可以随机的，可以利用元素下标进行。数组比线性表速度更快的是：原地逆序、返回中间节点、选择随机节点。

便于线性表的构造和任意元素的访问
插入：插入新结点，之后结点后移。平均时间复杂度:O(n)
删除：删除节点，之后结点前移。平均时间复杂度:O(n)

线性链表

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于最后一个结点无后继，故结点的指针域为空，即NULL。头插法建表(逆序)、尾插法建表(顺序)。增加头结点的目的是算法实现上的方便，但增大了内存开销。
- 查找：只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
- 插入：先找到表的第i-1的存储位置，然后插入。新结点先连后继，再连前驱。
- 删除：首先找到ai-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间.r=p->next;p->next=r->next;delete r。
  判断一个单向链表中是否存在环的最佳方法是快慢指针。
静态链表：用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）；链表：插入与删除同前面所述的动态链表方法相同。静态链表中指针表示的是下一元素在数组中的位置。
静态链表是用数组实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配大小。动态链表是用申请内存函数（C是malloc,C++是new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。静态链表在插入、删除时也是通过修改指针域来实现的，与动态链表没有什么分别
循环链表：是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。
双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链。双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表，比从一个方向搜索双链表的方差要小。
- 插入：先搞定插入节点的前驱和后继，再搞定后结点的前驱，最后搞定前结点的后继。
- 在有序双向链表中定位删除一个元素的平均时间复杂度为O(n)
- 可以直接删除当前指针所指向的节点。而不需要像单向链表中，删除一个元素必须找到其前驱。因此在插入数据时，单向链表和双向链表操作复杂度相同，而删除数据时，双向链表的性能优于单向链表

线性表的抽象数据类型描述

线性表的置空操作clear()：将一个已经存在的线性表置为空表。
线性表判空操作isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false。
求线性表的长度操作length()：求线性表中的数据元素的个数并返回其值。
取元素操作get(i)：读取并返回线性表中的第i个数据元素的值。其中i的取值范围为0≤i≤length()-1。
插入操作insert(i,x)：在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i的取值范围为0≤i≤length()。当i=0时，在表头插入x；当i=length()时，在表尾插入x。
删除操作remove(i)：删除并返回线性表中第i个数据元素。其中i的取值范围为0≤i≤length()-1。
查找操作indexOf(x)：返回线性表中首次出现的指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1。

线性表的抽线数据类型用Golang接口描述如下：

package main
import (
    "errors"
    "fmt"
)
const MAX_LENGTH = 20 // 常量定义线性表最大长度
//　定义一个线性表顺序存储结构体
type LineList struct {
    MaxLength  int
    Length int
    LineListContent []interface{}
}
//　初始化一个线性表
func InitLineList () *LineList{
    return &LineList{MaxLength:MAX_LENGTH, LineListContent:make([]interface{},0,MAX_LENGTH)}
}
//　判断当前线性表是否为空
func (l LineList) IsEmpty() bool {
    if l.Length == 0{
        return true
    }
    return false
}
// 判断当前线性表是否满了
func (l LineList) IsFull() bool{
    if l.Length == l.MaxLength{
        return true
    }
    return false
}
// 判断索引是否越界，越界返回ｔｒｕｅ
func (l LineList) indexOver(i int) bool{
    if i < 1 || i >l.Length{
        return true
    }
    return false
}
// 获取一个ｎｏｄｅ数据
func (l LineList) getData(i int )(interface{},error){
    if ok:= l.indexOver(i); ok{
        return "",errors.New("查找的索引不在线性表范围内")
    }
    return l.LineListContent[i+1],nil
}
// 任意位置删除一个ｎｏｄｅ数据
func (l *LineList) Delete(i int)(interface{},error){
    if ok:= l.indexOver(i); ok{
        return "",errors.New("删除的索引不在线性表范围内")
    }
    if ok:=l.IsEmpty();ok{
        return  "",errors.New("空表没有可删除的数据")
    }
    deleteData := l.LineListContent[i-1]
    for j:=i-1; j<l.Length-1;j++{
        l.LineListContent[j] = l.LineListContent[j+1]
        fmt.Println(j,"个",l.LineListContent[j])
    }
    l.LineListContent = l.LineListContent[:l.Length-1] // 留了最后一个在，需要切除
    l.Length --
    return deleteData,nil
}
//末尾　ｐｏｐ　一个数据
func (l *LineList) Pop()(interface{},error){
    if ok:= l.IsEmpty();ok{
        return "",errors.New("空表，无法删除任何数据")
    }
    temp := l.LineListContent[l.Length-1]
    l.LineListContent = l.LineListContent[:l.Length-1]
    l.Length --
    return temp,nil
}
// 末尾　Append 一个数据
func (l *LineList) Append(data interface{})(bool,error){
    if ok:= l.IsFull(); ok{
        return false,errors.New("线性表已满，无法添加数据")
    }
    l.LineListContent = append(l.LineListContent, data)
    l.Length ++
    return true,nil
}
// 任意位置　ｉｎｓｅｒｔ　一个数据
func (l *LineList) Insert(i int,data interface{})(bool,error){
    if ok:= l.IsFull(); ok{
        return false,errors.New("线性表已满，无法添加数据")
    }
    if ok:= l.indexOver(i);ok{
        return false,errors.New("插入点越界")
    }
    l.Append("") // 增加一个空数据，防止下面访问越界
    for j:=l.Length-1;j>i-1;j--{
        //从后往前赋值，新增一个空ｎｏｄｅ，然后把数据一个个后移，直到插入的位置
        //知道线性表从１开始，而切片是从０开始的
        l.LineListContent[j] = l.LineListContent[j-1]
    }
    l.LineListContent[i-1] = data
    return true,nil
}
func main(){
    ls := InitLineList()
    ls.Append(11)
    fmt.Println(ls.LineListContent) //[11]
    fmt.Println(ls.Length) // 1
    ls.Insert(3,"gac")
    ls.Insert(1,"gac")
    fmt.Println(ls.LineListContent) //[gac 11]
    fmt.Println(ls.Length)  //2
    ls.Delete(2)
    fmt.Println(ls.LineListContent) //[gac]
    fmt.Println(ls.Length)     // 1
    cd,err0 := ls.Pop()
    if err0==nil{
        fmt.Println(cd)      // gac
    }
    fmt.Println(ls.LineListContent) //[]
    fmt.Println(ls.Length)    // 0
}

数据结构

概念

线性表

线性表的顺序存储结构

线性链表

线性表的抽象数据类型描述

Previous

GOLANG测试

Next

Redis学习

数据库