1.線性表
線性表：有0個或多個數(shù)據(jù)元素組成的有序序列麸折。
性質(zhì)：除了第一個和最后一個都是有且只有一個前驅(qū)和一個后繼
有直接一個前驅(qū)和一個直接后繼
數(shù)據(jù)類型：指的是一組性質(zhì)相同的集合及定義集合上一些操作的總稱-
數(shù)據(jù)類型的分類：
1.原子類型 不可分解2.結(jié)構(gòu)類型 是可以在分解的
抽象數(shù)據(jù)類型：
Data:除了第一個和最后一個都是有且只有一個前驅(qū)和一個后繼,一對一的關(guān)系
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存放的數(shù)據(jù)
locateElem(l,e);
listInsert(l,i,e)線性表的存儲結(jié)構(gòu)：
順序存儲結(jié)構(gòu)：依次按照順序存儲的數(shù)形式
一個元素存儲占有n個字節(jié)
位置關(guān)系：loc(ai)=loc(a1)+(i-1)*c
鏈?zhǔn)酱鎯Y(jié)構(gòu)：
-
2 js數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組
1.concat:連接兩個或多個數(shù)組矮湘，并返回結(jié)果
2.foreach：對數(shù)組中的每一項運行給定函數(shù)褐着，這個方法沒有返回值<script> var arr=[1,2,3] arr.forEach(function (x) { console.log(x % 2 == 0,'---'); }) </script>3.join：將數(shù)組中的元素鏈接成一個字符串
4.indexOf:返回數(shù)組中每一個元素的索引逃顶，沒有返回值-1脾歧；
5.lastIndexOf:返回在數(shù)組中搜索到的與給定參數(shù)相等的元素的索引的最大值
6.map:對數(shù)組中的每一項應(yīng)用給定函數(shù)甲捏，返回每次函數(shù)調(diào)用的結(jié)果并返回數(shù)組<script> var isEven=function (x) { console.log(x); return (x%2==0); } var arr=[2,5,8,9]; console.log(arr.map(isEven));//map；返回的結(jié)果組成數(shù)組 console.log(arr.filter(isEven));//filter鞭执；返回的結(jié)果組成新數(shù)組 </script>7.reverse:翻轉(zhuǎn)數(shù)組的順序
8.slice:傳入索引值司顿，將數(shù)組里對應(yīng)的索引范圍內(nèi)的元素作為新數(shù)組
9.some:對數(shù)組中的每一項運行給定函數(shù)，如果任一項返回true兄纺，則返回true;
10.every:對數(shù)組中的每一項運行給定函數(shù)大溜，如果該函數(shù)對每一項都返回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:對數(shù)組中的每一項運行給定函數(shù),則返回函數(shù)為true項組成的數(shù)組
12.sort:按照字母順序?qū)?shù)組排序估脆，支持傳入指定排序方法的函數(shù)作為參數(shù)(當(dāng)做字符串比較)
13.toString:將數(shù)組當(dāng)做字符串返回
14.valueOf:將數(shù)組當(dāng)做字符串返回
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() 返回索引-
輸出數(shù)組返回字符串的方法：
toString
join
棧和隊列
棧：先進(jìn)后出的有序集合(新元素在棧頂钦奋，舊元素在棧底)
棧的方法：
1.push(element)：添加一個或者多個元素到棧頂
2.pop():移除棧頂?shù)脑兀⒎祷匦碌脑?br> 3.peek()；返回棧頂?shù)脑兀ú蛔鋈魏蔚男薷模?br> 4.isEmpty():判斷棧是否為空付材，沒有為true,否則false
5.clear():移除棧里的所有元素
6.size()朦拖；返回棧的元素個數(shù)隊列：先進(jìn)先出的序列集合
1.enqueue(element)：向隊列尾部添加一個或多個新的項
2.dequeue():移除隊列的第一個元素，并返回該元素
3.front():返回隊列中的第一個元素（不對隊列做修改）
4.isEmpty():判斷隊列是否包含元素
5.size（）：返回隊列的元素的個數(shù)厌衔、
隊列;
1.優(yōu)先隊列
2.循環(huán)隊列<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> // 隊列的創(chuàng)建 function Queue() { var items=[]; } </script>
5.鏈表
數(shù)組是鏈表的一種璧帝，但是數(shù)組的缺點是大小固定，從數(shù)組中插入或刪除一個元素代價較高
鏈表的元素在內(nèi)存中并不是連續(xù)的富寿，每一個鏈表元素都有節(jié)點本身和指針組成（鏈表查找元素要從頭開始）
<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;//列表最后一個節(jié)點的下一個元素為null
}else{
current=head;
// 循環(huán)列表知道找到最后一項
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類
散列算法的作用就是盡可能快的在數(shù)據(jù)結(jié)構(gòu)中找到一個值
散列函數(shù)的作用是給定一個值，然后返回在表中的地址
<script> function HashTable() { var table=[]; this.put=function (key,value) {//添加新的項 }; this.remove=function (key) {//從鍵值中移除值 }; this.get=function (key) {//返回鍵值檢索到的特定值 } } </script>
-
- 樹（非順序結(jié)構(gòu)）
位于樹頂部的節(jié)點叫做根節(jié)點
節(jié)點分為內(nèi)部節(jié)點和外部節(jié)點
節(jié)點有深度页徐，節(jié)點的深度取決于祖先節(jié)點的數(shù)量
樹的高度取決于所有節(jié)點深度的最大值
二叉樹和二叉搜索樹
二叉樹的節(jié)點最多只有兩個子節(jié)點理疙，一個是左側(cè)子節(jié)點，另一有右側(cè)子節(jié)點
二叉搜索樹：
左側(cè)存儲的節(jié)點比父節(jié)點小的值
右側(cè)存儲比父節(jié)點大或者相等的值
邊：表示的是節(jié)點之間的關(guān)系
在雙向鏈表中泞坦，每個節(jié)點有兩個指針窖贤，一個指向下一個節(jié)點，一個指向上一個節(jié)點
同樣在樹中贰锁，每個節(jié)點也有兩個指針赃梧，一個指向左側(cè)子節(jié)點，一個指向右側(cè)子節(jié)點
樹中的方法：
insert(key):向樹中插入新的鍵
search(key):在樹中查找一個鍵豌熄，如果存在則返回true,否則返回false
inOrderTraverse():通過中序遍歷的方式遍歷所有的節(jié)點
PreOrderTraverse():通過先序遍歷的方式遍歷所有的節(jié)點
postOrderTraverse():通過后序的方式遍歷所有的節(jié)點授嘀。
min():返回樹中最小的鍵
max()；返回樹中最大的鍵
remove(key):從樹中刪除某個鍵
<script>
function BinarySearchTree() {
var Node=function (key) {//表示樹的每一個節(jié)點
this.key=key;
this.left=null;
this.right=null;
};
// var root=null;
var insertNode=function (node,newNode) {//實現(xiàn)插入節(jié)點的位置
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);//優(yōu)先于后代排列的方式
}
};
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);//創(chuàng)建節(jié)點
if(root==null){//判斷是否特殊情況的第一個節(jié)點
root=newNode;
}else{
insertNode(root,newNode);//把節(jié)點加入非根節(jié)點的位置
}
}
this.inOrderTraverse=function (callback) {
inOrderTraverseNode(root,callback);
};
this.preOrderTraverse=function (callback) {
preOrderTraverseNode(root,callback);
}
this.postOrderTraverse=function (callback) {
postOrderTraverseNode(root,callback);
}
}
</script>
- 樹的遍歷：指的是樹中的每一個節(jié)點都進(jìn)行某種操作
訪問樹的節(jié)點的三種方法：中序锣险，先序和后續(xù)
中序遍歷是上行的遍歷方式：也就是從小到大的遍歷所有節(jié)點
先序遍歷是父節(jié)點優(yōu)先于后代節(jié)點的方式蹄皱，也就是從根節(jié)點開始
后序遍歷是后代節(jié)點優(yōu)先于父節(jié)點的方式，從子節(jié)點開始訪問的
在樹中：有三種經(jīng)常執(zhí)行的搜索類型
最大值
最小值
搜索特定值
- 圖
非線性數(shù)據(jù)結(jié)構(gòu)--圖芯肤。
圖是網(wǎng)絡(luò)結(jié)構(gòu)的抽象模型巷折。圖是有邊鏈接的節(jié)點（主要表示的是二元關(guān)系的）
有一條邊鏈接的頂點叫做相鄰頂點
一個頂點的度是相鄰頂點的數(shù)量
如果圖中不存在環(huán)，怎稱該圖是無環(huán)的崖咨，如果圖中每兩個頂點之間存在路徑锻拘，則該圖是連通的
有向圖和無向圖
強連通：如果圖中的每個頂點都是雙向連通的
1用鄰接矩陣表示常見的圖（arr[i][j]==1相鄰 arr[i][j]==0不相鄰）
2.使用鄰接表表示圖
3.使用關(guān)聯(lián)矩陣表示圖（邊數(shù)比頂點多的情況）
圖的遍歷:可以尋找特定頂點或者尋找兩個頂點之間的路徑（思想：必須每個第一次訪問的頂點）
1.廣度優(yōu)先（BFS） （隊列）（先寬后深訪問形式）
2.深度優(yōu)先 (DFS) （棧） （先深度后廣度的形式）
兩種方法的不同點在于帶訪問頂點的數(shù)據(jù)結(jié)構(gòu)不同
-
排序和搜索算法
排序算法：
<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); // 選擇排序（思想：是找到最小的元素放在第一位置，接著找第二小的數(shù)击蹲，以此類推） 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)); // 插入排序：是每次排一個數(shù)組項 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>-
歸并排序：思想：將原始數(shù)組切分成較小的數(shù)組署拟，知道每一小數(shù)組只有一個位置，接著將小數(shù)組
歸并為一個大數(shù)組歌豺，知道最后只有一個排序完畢的大數(shù)組<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>
-
