My Little World

发表于

结构

1
2
3
4
5
typedef struct DualNode{
	ElemType data;
	struct DualNode *prior;//前驱结点
	struct DualNode *next;//后继结点
}DualNode,*DuLinkList;

doublylinklist1
doublylinklist2
双向链表插入
doublylinklist3
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
双向链表删除
doublylinklist4
p->prior->next = p->next;
p->next ->prior = p->prior;
free(p)
小结
双向链表相对于单链表来说复杂一点，每个结点对了一个prior指针，在进行插入和删除时需要注意;
双向链表可以有效提高算法的时间性能，用空间换取时间

My Little World

发表于

lating1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function Latinsquare(num){
	var list=[];
	for(var i = 0;i<num;i++){
	  var pre = 0;
	  if(i==0){
	    pre=num;
	  }else{
	    pre = i;
	  }
	  var nextt = 0;
	  if(i ==num-1){
	    nextt = 1;
	  }else{
	    nextt = i+2;
	  }
	  list.push({
	    prior:pre,
	    data:i+1,
	    next:nextt
	  })
	}
	for(var i = 0;i<num;i++){
	  var string=[];
	  var p = 1;
	  for(var j = 0;j<i;j++){
	    p = list[p-1].next;
	  }
	  for(var k = 0;k<num;k++){
	    string.push(list[p-1].data);
	    p = list[p-1].next;
	  }
	  console.log(string);
	}
}
Latinsquare(5);

My Little World

发表于

有环定义:链表的尾节点指向了链表中的某个结点
ishascircle
方法一：p、q指针同时向前走，但q每次都从头开始走，对于每个结点，若p、q走的步数不等则说明有环
方法二：快慢指针:使用p,q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p==q,则存在环
代码

My Little World

发表于

头插法建立单链表

chaintable17
chaintable18
代码链接

尾插法建立单链表

头插法建立的链表输入顺序与结点次序相反，尾插法可以使二者顺序相同
chaintable20
R做索引，S做中介节点
代码链接
重点r=p;将尾节点更新为r

整表删除

chaintable21
参照删除单链表制定位置结点代码代码链接

快慢指针—>标尺思想

staticlinklist3
快速找到未知长度单链表的中间结点 代码链接

单链表与顺序存储结构优缺点

1.存储分配方式：
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;
单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
2.时间性能：
—查找
顺序存储结构O(1);
单链表O(n)
—插入和删除
顺序存储结构需要平均移动表长一半的元素，时间为O(n);
单链表在计算出某位置的指针后，插入和删除时间仅为O(1)
3.空间性能
顺序存储结构需要预分配存储空间，分大了容易造成空间浪费，分小了容易发生溢出
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

小结

1.频繁查找，较少插入删除操作，宜用顺序存储结构，如，游戏开发时用户注册的个人信息的存储
2.频繁插入删除操作，较少查找，宜用单链表结构，如游戏中的玩家的装备列表
3.当线性表大致长度已知，宜用顺序存储结构，反之，长度变化大或未知，则用单链表

My Little World

发表于

用数组描述的链表叫做静态链表
这种描述方法叫做游标实现法
staticlinklist1
Staticlinklist是一个容量为maxsize大的数组，数组每一项是一个结构struct，
这个结构包含两项，数据data和游标cur
整个数组的第一项(下标为0)和最后一项（下标为maxsize-1）的数据部分不存放数据
把未使用的数组元素（数据部分为空称为备用链表
约定：
——第一项的游标指向数组中除收尾两项外的项中，第一个数据部分为空的项，即首项游标为该项的下标/备用链表第一个结点的下标;
——尾项游标指向第一个有数据的元素 相当于头结点作用
——其他元素游标等于其指向的元素位于数组中的下标
——数据元素的最后一项的游标等于首项下标0,即指向备用链表开始结点

初始化静态链表相当于初始化数组

1
2
3
4
5
6
7
8
Status InitList(StatixLinkList space)
{
	int i;
	for(i =0;i<MAXSIZE-1;i++){
		space[MAXSIZE-1].cur = 0;
		return OK;
	}
}

链表插入，删除，求长度 代码链接

My Little World

发表于

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表
singlelooplinklist1
循环链表并不一定要有头结点
与单链表的主要差异为判断链表是否为空
单链表为空条件为head->next = null
循环链表为空条件为head->next = head
终端节点用尾指针rear指示，查找终端结点是O(1);开始结点是rear->next->next,也是O(1);
[插入、删除、返回位置 代码思路参考单链表]
Rear == rear->next 空循环链表
singlelooplinklist2
小结
循环链表的特点是无须增加存储量，仅对链接方式稍作改变，即可使得表处理更加方便灵活

My Little World

发表于

线性表

由0个或多个数据元素组成的有限序列

1.序列，有顺序
2.若元素存在多个，则第一个无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继
3.有限的，无论计算机发展到多强大，线性表处理的元素都是有限的

(ai-1,ai,ai+1) ai-1是ai 的直接前驱元素;ai+1是ai的直接后继元素
线性表长度即线性表元素个数,个数为0，即为空表

数据类型

一组性质相同的值的集合及定义在此集合上的一些操作的总称（编程语言中的各种类型）

抽象数据类型 把数据类型和操作结合捆绑在一起

标准格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ADT（抽象数据名）list
Data（数据元素之间逻辑关系的定义）
	  数据间关系一对一
Operation（操作）
	Initlist()初始化操作 新建一个空表
	ListEmpty(list) 判断线性表list是否为空，空返回true
	Clearlist(list) 清空线性表
	Getitem(list,i,e) 获取线性表第i个位置元素并返回给e
	Search(item,list) 在list里面查找item是否在里面，存在返回序号；否则返回0
	  				 线性表从1 开始
	Listinsert(item,i,list) 在list的第i个位置插入item
	Listdelete(item,i,list) 删除list中第i个位置元素，并返回该元素给item
	Listlength(list) 返回线性表list元素个数
endADT

My Little World

发表于

链式存储结构

用一组任意的存储单元存储线性表数据元素，这组存储单元可以存在内存中未被占用的任意位置；每个元素需要两个位置，一个存储元素本身，一个存储它后继元素的存储地址（指针）
数据域：存储数据元素信息的域；
指针域：存储直接后继位置的域；
指针/链：指针域中存储的信息
存储映像/结点（node）：数据域和指针域这两部分信息组成的数据元素
链式存储结构：n个结点连接成一个链表
单链表：链表中每个结点中只包含一个指针域
chaintable1
头指针：链表中第一个结点的存储位置
最后一个结点指针为空
chaintable2
头结点的数据域一般不存储任何信息
头指针
—— 指 指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针
在头结点之前
—— 头指针具有标志作用，所以常用头指针冠以链表的名字（指针变量的名字）
—— 无论链表是否为空，头指针均不为空
—— 头指针是链表的必要元素
头结点
—— 为了操作统一和方便而设立，放在第一个元素的结点之前，其数据域一般无
意义（但也可以用来存放链表的长度）
—— 有了头结点，对第一个元素节点前插入结点和删除第一个结点操作与其他结
点的操作就统一了
——头结点不一定是链表的必须要素
chaintable3
用结构指针来描述单链表

1
2
3
4
5
6
typedef struct Node
{
	ElemType data;//数据域
	struct Node* Next;//指针域
}Node;
Typedef struct Node* LinkList

Typedef struct Node LinkList 将Node取别名为LinkList
结点由存放数据元素的数据域和存放后继结点的地址指针组成

假设P是指向线性表第i个元素的指针，则该结点ai的数据域为p->data
指针域为p->next,因为p->next是一个指针，它指向第i+1个元素ai+1
因此，如果p->data=ai,那么p->next->data=ai+1

单链表元素读取

链表元素不像顺序存储线性表通过位置计算可以得到，需要一个一个找
chaintable6

时间复杂度为O（n）;核心思想：“工作指针后移”

单链表元素插入O(n)

chaintable8
chaintable9

单链表元素删除O(n)

chaintable11
chaintable12
chaintable13

以上操作代码链接

小结

如果我们想从第i个位置开始，插入连续10个元素，
对顺序存储结构意味着，每次插入都需要移动n-i个位置,所以每次都是O(n);
而单链表，只需要在第一次找到第i个位置的指针，此时时间复杂度为O(n),
接下来只是简单的赋值移动指针而已，时间复杂度都是O(1)
因此对于频繁插入或删除数据来说，单链表效率更高。

My Little World

发表于

顺序存储结构

结构struct{
数据类型 数组名data[数组最大长度MAXSIZE]；
Int length;(线性表当前长度/数组当前数据个数)
}

封装3个属性
1.存储空间起始位置，数组data,它的存储位置就是线性表存储空间的存储位置
2.线性表最大存储容量：maxsize ,初始化后一般不变
3.线性表当前长度：length，时刻改变

地址计算方法

假设每个元素占C个存储单元（字节），LOC表示获得存储位置的函数
LOC( )= loc( )+C
LOC( )= loc( )+(i-1)*C
假设,线性表最大长度设置为10；当前长度为4；如下
var maxsize = 10;
var list ={
data:[1,2,3,4],
length:4
}

获取线性表第i个位置的元素

1
2
3
4
5
6
7
8
9
10
11
function getitem(list,i){
  if(i<1 || i >list.length || list.length == 0){   //线性表位置从1 开始
    console.log("input is error")
    return
  }
  var item;
  item = list[i-1]; //数组下标从0 开始，与线性表差1
  return item;
}
var ff = getitem(list.data,0);
console.log(ff);

在线性表第i个位置插入元素item

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertitem(list,i,item){
  if(list.data.length == maxsize){
    console.log("the list is full");
    return
  }
  if(i<1 || i >list.data.length){
    console.log("the position is not in the range")
    return
  }
  if(i<list.data.length){
    for(var j = list.data.length -1;j>=i-1;j--){
      list.data[j+1] = list.data[j];
    }
  }
  list.data[i-1] = item; 
  list.length = list.length+1;
}
insertitem(list,2,5);
console.log(list);

删除线性表第i个位置的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function deleteitem(list,i){
  if(list.data.length == 0){
    console.log("the list is empty")
    return
  }
  if(i<1 || i >list.data.length){
    console.log("the position is not in the range")
    return
  }
  var temp = list.data[i-1];//被删除的元素
  if(i<list.data.length){
    for(var j = i ;j<list.data.length;j++){
      list.data[j-1] = list.data[j];
    }
    
  }
  list.data.splice(list.data.length-1,1);//删除最后一个
  list.length = list.length-1;
}
deleteitem(list,3);
console.log(list);

小结

在存、读数据时，不管是那个位置,时间复杂度都是O(1).
而在插入或删除时，时间复杂度都是O(n);
比较适合元素个数稳定，不经常插入和删除元素，而更多操作是存取数据的应用。
优点：
1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间
2.可以快速存取表中任意位置元素
缺点
1.插入和删除操作需要移动大量元素
2.当线性表长度变化较大时，难以确定存储空间的容量
3.容易造成存储空间的碎片

My Little World

发表于

数据结构

逻辑结构：数据元素之间的关系
物理结构：逻辑结构在计算机中的存储形式

四大逻辑结构：
1.集合结构：同属一个集合，相互之间无关系
2.线性:一对一
3.树形：一对多
4.图形：多对多

物理机构：
顺序存储：地址连续
链式存储：可连续可不连续

算法

1.特性
输入：0或多个
输出：至少1个或多个
有穷性：不会无限循环，有限时间内结束
确定性：无歧义，一条路径得到结果相同
可行性：有限次数完成

2.设计要求
正确性：
算法程序没有语法错误；
对于合法输入能够产生满足要求的输出；
对于非法输入能够产生满足规格的说明；
对于故意刁难得测试输入都有满足要求的输出结果；
可读性：
便于阅读和修改
健壮性：
当输入数据不合法时，算法也能做出相关处理，而不是产生异常、崩溃或明明奇妙结果
时间效率高和存储量低

函数渐进增长

函数F(n)在n>N时,始终大于函数G(n),就说G(n)渐进增长F(n)

X为输入规模，Y 为算法执行次数（复杂度） aX^b+cX+d 执行次数计算方法
Y= aX^b+cX+d a,c,d对Y值的影响均可忽略，此时只看b值，b越大Y 增长越快
Y= cX+d c,d忽略,Y随X增长
Y = d d无论为多大常熟，均视作1

时间复杂度

T(n)=O(f(n)); f(n)是n的某个函数
执行次数 = 时间
O() 大O记法
T(n)增长最慢的算法为最优算法

推导大O阶

用常熟1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项存在且不是1，则去除与这个项相乘的常数

时间复杂度耗时从小到大O(以下项)
timelength