今天正式开工！开始总结数据结构这部分知识.
在正式总结前，我们梳理下数据结构的内容，算是绪论内容吧。
00
知识框架
在数据结构三要素中，我们主要梳理下数据的逻辑结构和物理结构。逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。常见的数据逻辑结构分类如上图1.1。集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性结构结构中的数据元素之间只存在一对一的关系。树形结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。存储结构是指数据结构在计算机中的表示(又称映像)，也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。关于这些存储结构的定义请大家自行搜索理解。
抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作，通常用(数据对象、数据关系、基本操作集)这样的三元组来表示抽象数据类型。因此可以用ADT定义一个完整的数据结构。
线性表01
理论知识
线性表的主要操作有：
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第一个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1元素，称i为元素在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
注意：线性表中元素的位序是从1开始的，而数组中元素的下表是从0开始
假定线性表的元素类型为ElemType,则线性表的顺序存储类型使用C语言描述为
#defineMaxSize50//定义线性表的最大长度typedefstruct{ElemTypedata[MaxSize];//顺序表的元素intlength;//顺序表的当前长度}SqList;//顺序表的类型定义
一维位数组可以是静态分配的，也可以是动态分配的，在静态分配中由于数组大小和空间已定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。
而在动态分配中，存储数组的空间是在程序执行过程中通过动态分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性的划分所有空间。
#defineInitSize//表长度的初始定义typedefstruct{ElemType*data;//指示动态分配数组的指针intMaxSize,length;//数组的最大容量和当前个数}SeqList;//动态分配数组顺序表的类型定义
C的初始动态分配语句为
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
C++的初始动态分配语句为
L.data=newElemType[InitSize];
顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。顺序表的存储密度高，每个结点只存储数据元素。顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
02
编程实现
考虑到自己日后以Go语言为主要工作语言，因此我会将所有的数据结构以Go语言改写，当然C/C++如何实现也是需要掌握的，理论知识暂且以C/C++进行总结。
packagemainimport"fmt"//SqListisasqlistfile//定义顺序表typeSqListstruct{//定义顺序表的最大长度maxSizeint//定义当前顺序表的长度lengthint//顺序表的元素data[]int}//InitSqLististoinitmylist//初始化顺序表funcInitSqList(InitSizeint)*SqList{returnSqList{maxSize:InitSize,data:make([]int,InitSize)}}//IsEmptyisornotempty//检查顺表是否为空//方法是查看当前顺序表的长度是否为0func(mySqList*SqList)IsEmpty()bool{returnmySqList.length==0}//IsFullisornotfull//判断当前顺序表长度是否已达到最大值func(mySqList*SqList)IsFull()bool{returnmySqList.length==mySqList.maxSize}//ListInsertfunctionistoinsertanelement//在i位置插入元素efunc(mySqList*SqList)ListInsert(i,eint)bool{ifi1
imySqList.length+1{fmt.Println("不合法,请检查i")returnfalse}ifimySqList.maxSize{fmt.Println("不合法,请检查i")returnfalse}forj:=mySqList.length;j=i;j--{//将第i个元素及之后的元素后移mySqList.data[j]=mySqList.data[j-1]}mySqList.data[i-1]=e//在位置i处放入emySqList.length++//线性表长度加1returntrue}//ListAppendfunctionistoappendanelement//在尾部追加一个元素,需要和最大长度比较func(mySqList*SqList)ListAppend(eint)bool{ifmySqList.IsFull(){fmt.Println("sorrylistismaxsize")returnfalse}mySqList.data[mySqList.length]=emySqList.length++returntrue}//ListDeletefunctionistoremoveenelement//此方法是用来删除指定位置元素//method1func(mySqList*SqList)ListDelete(iint)bool{ifi1
imySqList.length+1{fmt.Println("i不合法,请检查i")returnfalse}ifimySqList.maxSize{fmt.Println("i不合法,请检查i")}forj:=i-1;jmySqList.length-1;j++{//将第i个位置之后的元素前移mySqList.data[j]=mySqList.data[j+1]}mySqList.data[mySqList.length-1]=0mySqList.length--returntrue}//ListDeletefunctionistoremoveelement//method2//func(mySqList*SqList)ListDelete(iint)bool{//ifi1
imySqList.length+1{//fmt.Println("i不合法,请检查i")//returnfalse//}//ifimySqList.maxSize{//fmt.Println("i不合法,请检查i")//}//区别主要在这里，有两种思路//for(j:=i;jmySqList.length;j++){//mySqList.data[j-1]=mySqList.data[j]//}//mySqList.length--//returntrue//}//ListFindfunctionistofindanelement//此方法用来查找指定位置的元素func(mySqList*SqList)ListFind(iint)bool{ifi1
imySqList.length+1{fmt.Println("i不合法,请检查i")returnfalse}ifimySqList.maxSize{fmt.Println("i不合法,请检查i")returnfalse}fmt.Println(mySqList.data[i-1])returntrue}funcmain(){list:=InitSqList(20)//设置最大长度为20list.ListInsert(1,22)list.ListAppend(12)list.ListAppend()list.ListAppend()list.ListAppend()list.ListAppend()list.ListAppend()list.ListAppend()list.ListAppend()list.ListAppend()fmt.Println(list)fmt.Println(*list)fmt.Println(*list.length)list.ListDelete(5)//fmt.Println(*list.data[2])fmt.Println(*list)list.ListFind(3)}
程序执行结果是
注意：区别顺序表的位序和数组下标。理解为什么判断插入位置是否合法时if语句中用length+1，而移动元素的for语句中只用length？03
算法复杂度分析
最好情况：在表尾插入（即i=n+1）元素后移语句将不执行，时间复杂度为O(1).
最坏情况：在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O(n).
平均情况：假设是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为
因此，线性表插入算法的平均时间复杂度为O(n).
最好情况：删除表尾元素（即i=n）无需移动元素，时间复杂度为O(1).
最坏情况：删除表头元素（即i=1）需要移动除第一个元素外的所有元素，时间复杂度为O(n).
平均情况：假设是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为
因此，线性表删除算法的平均时间复杂度为O(n).
顺序查找
最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1).
最坏情况：查找的元素在表尾（或不存在）时候，需要比较n次，时间复杂度为O(n).
平均情况：假设是查找的元素在第i（1=i=L.length）个位置上的概率，则在长度为n的线性表中查找值为e的元素所需比较的平均次数为
因此，线性表按值查找算法的平均时间复杂度为O(n).
end说明：考虑到时间成本，有些理论知识截图借鉴了部分计算机专业教材。还有考虑到一些数学符号问题，会逐渐使用LaTex命令进行排版。另外，由于每个部分知识点较多，故可能不会日更
预览时标签不可点收录于话题#个上一篇下一篇