1.线性表
线性表：有0个或多个数据元素组成的有序序列。
性质：除了第一个和最后一个都是有且只有一个前驱和一个后继
有直接一个前驱和一个直接后继
数据类型：指的是一组性质相同的集合及定义集合上一些操作的总称-
数据类型的分类：
1.原子类型 不可分解2.结构类型 是可以在分解的
抽象数据类型：
Data:除了第一个和最后一个都是有且只有一个前驱和一个后继,一对一的关系
opration:
InitList(l):建立空的线性表
ListEmpty(l)
ListInsert(l,i,e):在线性L的第i个位置插入元素e
ListtDelete(*l,i,e):在线性L的第i个位置删除元素e并集:A+B
listLength(l);
GetElement(l,i,e);//l是操作的线性表，i,索引的位置，e存放的数据
locateElem(l,e);
listInsert(l,i,e)线性表的存储结构：
顺序存储结构：依次按照顺序存储的数形式
一个元素存储占有n个字节
位置关系：loc(ai)=loc(a1)+(i-1)*c
链式存储结构：
-
2 js数据结构之数组
1.concat:连接两个或多个数组，并返回结果
2.foreach：对数组中的每一项运行给定函数，这个方法没有返回值<script> var arr=[1,2,3] arr.forEach(function (x) { console.log(x % 2 == 0,'---'); }) </script>3.join：将数组中的元素链接成一个字符串
4.indexOf:返回数组中每一个元素的索引，没有返回值-1；
5.lastIndexOf:返回在数组中搜索到的与给定参数相等的元素的索引的最大值
6.map:对数组中的每一项应用给定函数，返回每次函数调用的结果并返回数组<script> var isEven=function (x) { console.log(x); return (x%2==0); } var arr=[2,5,8,9]; console.log(arr.map(isEven));//map；返回的结果组成数组 console.log(arr.filter(isEven));//filter；返回的结果组成新数组 </script>7.reverse:翻转数组的顺序
8.slice:传入索引值，将数组里对应的索引范围内的元素作为新数组
9.some:对数组中的每一项运行给定函数，如果任一项返回true，则返回true;
10.every:对数组中的每一项运行给定函数，如果该函数对每一项都返回true，则返回true;
<script>
var isEven=function (x) {
console.log(x);
return (x%2==0)?true:false;
}
var arr=[2,5,8,9];
console.log(arr.every(isEven));//每一项都是为true
console.log(arr.some(isEven));//找到返回true的那一项为止</script>
11.filter:对数组中的每一项运行给定函数,则返回函数为true项组成的数组
12.sort:按照字母顺序对数组排序，支持传入指定排序方法的函数作为参数(当做字符串比较)
13.toString:将数组当做字符串返回
14.valueOf:将数组当做字符串返回
15.reduce:迭代累加
<script>
var arr=[3,6,9,10];
var res=arr.reduce(function (pre,curr,index) {
return pre+curr;
})
console.log(res);
</script>
搜索和排序
排序的方法：
1.reverse
2.sort(function(a,b){return a-b})搜索的方法：
indexof()
lastindexxof() 返回索引-
输出数组返回字符串的方法：
toString
join
栈和队列
栈：先进后出的有序集合(新元素在栈顶，旧元素在栈底)
栈的方法：
1.push(element)：添加一个或者多个元素到栈顶
2.pop():移除栈顶的元素，并返回新的元素
3.peek()；返回栈顶的元素（不做任何的修改）
4.isEmpty():判断栈是否为空，没有为true,否则false
5.clear():移除栈里的所有元素
6.size()；返回栈的元素个数队列：先进先出的序列集合
1.enqueue(element)：向队列尾部添加一个或多个新的项
2.dequeue():移除队列的第一个元素，并返回该元素
3.front():返回队列中的第一个元素（不对队列做修改）
4.isEmpty():判断队列是否包含元素
5.size（）：返回队列的元素的个数、
队列;
1.优先队列
2.循环队列<script> // 栈的方法 function Stack() { var items=[]; this.push=function (element) { items.push(element); }; this.pop=function () { items.pop() }; this.peek=function () { return items[items.length-1]; }; this.isEmpty=function () { return items.length==0; } this.size=function () { return items.length; } this.clear=function () { items=[]; }; this.print=function () { console.log(items.toString()); } } </script> <script> // 队列的创建 function Queue() { var items=[]; } </script>
5.链表
数组是链表的一种，但是数组的缺点是大小固定，从数组中插入或删除一个元素代价较高
链表的元素在内存中并不是连续的，每一个链表元素都有节点本身和指针组成（链表查找元素要从头开始）
<script>
function Linkedlist() {
var Node=function (element) {//要添加的项
this.element=element;
this.next=null;
}
var length=0;
var head=null;
this.append=function (element) {
// 向列表中添加元素
var node=new Node(element),
current;
if(head==null){
head=node;//列表最后一个节点的下一个元素为null
}else{
current=head;
// 循环列表知道找到最后一项
while(current.next){
current=current.next;
}
// 找到最后一项，将其next赋值为node,建立连接
current.next=node;
}
length++;
};
this.insert=function (position,element) {};
this.removeAt=function (position) {
// 检查是否越界
if()
};
this.move=function (element) {};
this.indexOf=function (element) {};
this.isEmpty=function (element) {
this.size=function () {};
this.toString=function () {};
this.print=function () {}
}
}
</script>
- 散列表：
-
hashTable类
散列算法的作用就是尽可能快的在数据结构中找到一个值
散列函数的作用是给定一个值，然后返回在表中的地址
<script> function HashTable() { var table=[]; this.put=function (key,value) {//添加新的项 }; this.remove=function (key) {//从键值中移除值 }; this.get=function (key) {//返回键值检索到的特定值 } } </script>
-
- 树（非顺序结构）
位于树顶部的节点叫做根节点
节点分为内部节点和外部节点
节点有深度，节点的深度取决于祖先节点的数量
树的高度取决于所有节点深度的最大值
二叉树和二叉搜索树
二叉树的节点最多只有两个子节点，一个是左侧子节点，另一有右侧子节点
二叉搜索树：
左侧存储的节点比父节点小的值
右侧存储比父节点大或者相等的值
边：表示的是节点之间的关系
在双向链表中，每个节点有两个指针，一个指向下一个节点，一个指向上一个节点
同样在树中，每个节点也有两个指针，一个指向左侧子节点，一个指向右侧子节点
树中的方法：
insert(key):向树中插入新的键
search(key):在树中查找一个键，如果存在则返回true,否则返回false
inOrderTraverse():通过中序遍历的方式遍历所有的节点
PreOrderTraverse():通过先序遍历的方式遍历所有的节点
postOrderTraverse():通过后序的方式遍历所有的节点。
min():返回树中最小的键
max()；返回树中最大的键
remove(key):从树中删除某个键
<script>
function BinarySearchTree() {
var Node=function (key) {//表示树的每一个节点
this.key=key;
this.left=null;
this.right=null;
};
// var root=null;
var insertNode=function (node,newNode) {//实现插入节点的位置
if(newNode.key<node.key){
if(node.left==null){
node.left=newNode;
}else{
insertNode(node.left,newNode);
}
}else{
if(node.right==null){
node.right=newNode;
}else{
insertNode(node.right,newNode);
}
}
};
var inOrderTraverseNode=function (node,callback) {
if(node!==null){
inOrderTraverseNode(node.left,callback);
callback(node.key);
inOrderTraverseNode(node.right,callback);//中序遍历从大到小的顺序排列的
}
};
var preOrderTraverseNode=function (node,callback) {
if(node!==null){
callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);//优先于后代排列的方式
}
};
var postOrderTraverseNode=function (node,callback) {
if(node!==null){
callback(node.key);
postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.key);
}
};
this.insert=function (key) {
var newNode=new Node(key);//创建节点
if(root==null){//判断是否特殊情况的第一个节点
root=newNode;
}else{
insertNode(root,newNode);//把节点加入非根节点的位置
}
}
this.inOrderTraverse=function (callback) {
inOrderTraverseNode(root,callback);
};
this.preOrderTraverse=function (callback) {
preOrderTraverseNode(root,callback);
}
this.postOrderTraverse=function (callback) {
postOrderTraverseNode(root,callback);
}
}
</script>
- 树的遍历：指的是树中的每一个节点都进行某种操作
访问树的节点的三种方法：中序，先序和后续
中序遍历是上行的遍历方式：也就是从小到大的遍历所有节点
先序遍历是父节点优先于后代节点的方式，也就是从根节点开始
后序遍历是后代节点优先于父节点的方式，从子节点开始访问的
在树中：有三种经常执行的搜索类型
最大值
最小值
搜索特定值
- 图
非线性数据结构--图。
图是网络结构的抽象模型。图是有边链接的节点（主要表示的是二元关系的）
有一条边链接的顶点叫做相邻顶点
一个顶点的度是相邻顶点的数量
如果图中不存在环，怎称该图是无环的，如果图中每两个顶点之间存在路径，则该图是连通的
有向图和无向图
强连通：如果图中的每个顶点都是双向连通的
1用邻接矩阵表示常见的图（arr[i][j]==1相邻 arr[i][j]==0不相邻）
2.使用邻接表表示图
3.使用关联矩阵表示图（边数比顶点多的情况）
图的遍历:可以寻找特定顶点或者寻找两个顶点之间的路径（思想：必须每个第一次访问的顶点）
1.广度优先（BFS） （队列）（先宽后深访问形式）
2.深度优先 (DFS) （栈） （先深度后广度的形式）
两种方法的不同点在于带访问顶点的数据结构不同
-
排序和搜索算法
排序算法：
<script> function ArrayList() { var array=[]; this.insert=function (item) { array.push(item); }; this.toString=function () { return array.join(); } } </script> <script> // 1.冒泡排序 function bubbleSort(array) { for(var i=0;i<array.length;i++){ for(var j=0;j<array.length-i-1;j++){ if(array[j]>array[j+1]){ var temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } return array; } var array=[1,4,9,6,3], res=bubbleSort(array); console.log(res); // 选择排序（思想：是找到最小的元素放在第一位置，接着找第二小的数，以此类推） function selectionSort(array) { var indexMin; for(var i=0;i<array.length;i++){ indexMin=i; for(var j=i;j<array.length;j++){ if(array[indexMin]>array[j]){ indexMin=j; } } if(i!==indexMin){ var temp=array[i]; array[i]=array[indexMin]; array[indexMin]=temp; } } return array; } console.log(selectionSort(array)); // 插入排序：是每次排一个数组项 function insertSort(array) { var j,temp; for(var i=0;i<array.length;i++){ j=i; temp=array[i]; while(j>0&&array[j-1]>temp){ array[j]=array[j-1]; j--; } array[j]=temp; } return array; } console.log(insertSort(array)); </script>-
归并排序：思想：将原始数组切分成较小的数组，知道每一小数组只有一个位置，接着将小数组
归并为一个大数组，知道最后只有一个排序完毕的大数组<script> var mergeSortRec=function (array) { if(array.length==1){ return array; } var mid=Math.floor(array.length/2), left=array.slice(0,mid), right=array.slice(mid,array.length); return (mergeSortRec(left),mergeSortRec(right)) }; var merge=function (left,right) { var res=[],i_1=0; var i_r=0; while (i_1<left.length&&i_r<right.length){ } } function mergeSort(array) { mergeSortRec(array); } var array=[1,5,0,4,9,3]; var res=mergeSort(array); console.log(res); </script>顺序搜索
<script> function sequentSearch(item,array) { for(var i=0;i<array.length;i++){ if(item==array[i]){ return i; } } return -1; } </script> </body> </html>
-
