数据结构

数据结构走起！

基础+ 栈

<script>
      // 数据结构和算法
   // 数据结构：数据对象和相关实例元素的各种联系，可以通过相关的函数来给出
   // 在计算机中存储和组织数据的方式 
   // 常见的数据结构
   // 队列  树  堆  栈  数组  链表  图  散列表
   // 算法：排序算法 
   // 是一定的指令集 指令描述不依赖于语言 接收一些输入和输出 在一定步骤后结束
   // 解决问题的方法 数据结构离不开算法
   
   // 数组 简书笔记  自由的线性结构 任意位置插入和删除
   
   // 栈结构  受限的线性结构 限制数组修改的随意性 只能在栈底或者栈顶添加 进栈和出栈 后进先出
   // 只允许表的一端插入和删除  进栈，入栈和压栈 
   // 栈的应用 函数相互调用 a调用b b调用c a在栈底 b压上去 c在栈顶 执行完以后c b a顺序出栈
   // 递归会出现栈的溢出 无限调用自己
   // 栈的面试题
   // 栈结构的实现 基于数组实现 基于链表实现
	// 栈操作
	// push栈顶添加新元素
	// pop移除栈顶元素 返回被删除的元素
	// peek返回栈顶元素 不做任何操作
	// isEmpty如果栈里没有任何元素就返回true
	// size返回元素个数
	// toString将栈结构的内容以字符串形式返回
	// 栈实现的相关构造函数封装
	function Stack(){
		this.items = []
		// push
		Stack.prototype.push = function(elment){
			this.items.push(elment)
		}
		// pop
		Stack.prototype.pop = function(){
			return this.items.pop()
		}
		// peek
		Stack.prototype.peek =function(){
			return this.items[this.items.length - 1]
		}
		// isEmpty
		Stack.prototype.isEmpty = function(){
			return this.items.length === 0
		}
		// size
		Stack.prototype.size = function(){
			return this.items.length
		}
		// toString
		Stack.prototype.toString = function(){
			var result = ''
			for(var i = 0; i < this.items.length; i++){
				result +=this.items[i] + ''
			}
			return result
		}
	}
	let stack = new Stack()
	stack.push('123')
	stack.push('12')
	stack.push('30')
	stack.pop()
	stack.pop()
	console.log(stack)
	// 栈的应用 十进制转二进制 计算机识别语言是二进制
	function getTwo(number){
		var stack = new Stack()
		while(number > 0){
			stack.push(number % 2)
			number = Math.floor(number / 2)
		}
		var bind = ''
		while(!stack.isEmpty()){
			bind += stack.pop()
		}
		return bind
	}
	console.log(getTwo(100))
	console.log(getTwo(200))
	console.log(getTwo(1000))
   </script>

队列

<script type="text/javascript">
			// 队列结构 受限的线性结构 先进先出 只允许在表的前端进行删除操作 在表的后端进行插入操作
			// 类似排队上wc 上完之后走，下一个进来 打印机先打印先出来
			// 鲜橙队列 在开发中 为了让任务可以并行处理 通常会开启多个线程 但是会占用过多资源
			
		// 队列的实现 基于数组实现 基于链表实现 链表性能更好
		// 队列常见操作
		// enqueue(element)向队列尾部添加一个或者多个新的项
		// dequeue()移除队列的第一:即排在队列最前面的项 并返回被移除的元素
		// front()返回队列第一个元素 队列不作任何变动
		// isEmpty()队列为空返回true 反之返回false
		// size()返回队列包含元素个数 与length相似
		// toString()将队列内容转换为字符串形式
		function Duilie(){
			this.items = []
			// 插入
			this.enqueue = function(element){
				this.items.push(element)
			}
			// 移除第一个
			this.dequeue = function (){
				return this.items.shift()
			}
			// 返回队列第一个元素
			this.front = function(){
				return this.items[0]
			}
			// 判断数组是否为空
			this.isEmpty = function(){
				return this.items.length == 0
			}
			// 返回数组长度
			this.size = function(){
				return this.items.length
			}
			// 将队列数据转化为字符串
			this.toString = function (){
				var newarr = []
				for(var i = 0; i < this.items.length; i++){
					newarr.push(this.items[i] + '')
				}
				return newarr
			}
		}
		let duilie = new Duilie()
		duilie.enqueue(10)
		duilie.enqueue(21)
		duilie.enqueue(31)
		console.log(duilie.dequeue())
		console.log(duilie.front())
		console.log(duilie.isEmpty())
		console.log(duilie.size())
		console.log(duilie.toString())
		console.log(duilie.items)
		console.log('--------')
		// 击鼓传花 一群人玩游戏 某个人数到某个数字就淘汰，接着循环数 最后留下的那个人的索引值
		function winner(list,num){
			var que = new Duilie()
			for(var i = 0; i <list.length; i++){
				que.enqueue(list[i])
			}
			while(que.size() > 1){
				for(var i = 0; i < num - 1; i++){
					que.enqueue(que.dequeue())
				}
				que.dequeue()
			}
			console.log(que.size())
			var endname = que.front()
			return list.indexOf(endname)
		}
		winner(['1','2','3'],3)
		
		console.log('----------')
		</script>

优先级队列

<script type="text/javascript">
			function Youxian(){
				function Neibu(element,youxianji){
					this.element = element
					this.youxianji = youxianji
				}
				this.items = []
				this.enqueqe = function(element,youxianji){
					var neibu = new Neibu(element,youxianji)
					// 判断队列是否为空
					if(this.items.length == 0){
						 this.items.push(neibu)
					} else {
						// 判断有没有插入
						var added  = false
						for(var i = 0; i < this.items.length; i++){
							if(neibu.youxianji < this.items[i].youxianji){
								this.items.splice(i,0,neibu)
								added = true
								break
							}
						}
						if(!added){
							this.items.push(neibu)
						}
					}
				}
			}
			let youxian = new Youxian()
			youxian.enqueqe('a',10)
			youxian.enqueqe('b',200)
			youxian.enqueqe('c',66)
			youxian.enqueqe('d',100)
			for(var i = 0; i < youxian.items.length; i++){
				console.log(youxian.items[i])
			}
		</script>

链表

<script type="text/javascript">
		// 链表和数组一样 具有存储数据的功能 但是实现的机制不一样
		// 数组的创建需要申请一段连续的内存空间 当数组不能满足容量需求时 需要扩容 申请更大空间复制内容
		// 在数组开头和中间插入数据的成本很高 需要进行大量元素的位移
		// 链表的元素在内存中不必是连续的存储
		// 链表的每个元素由一个存储元素的本身的节点和一个指向下一个元素的引用(有些语言称为指针或者连接)组成
		
		// 与数组对比 优点
		// 内存空间不必是连续的 可以充分利用计算机内存 实现灵活的内存动态管理
		// 链表不必再创建时就确定大小 大小可以无限延伸
		// 链表再插入和删除时 时间复杂度可以达到O(1)。相对数组效率高很多
		
		// 聊链表缺点
		// 链表访问任何一个元素时 需要从头开始访问 无法跳过访问 数组可以通过下标索引的方式访问
		// 一个一个访问直到找到相应的元素
		
		// 封装单向链表结构 
		function Lianbiao(){
			function Node(data){
				this.data = data
				this.next = null
			}
			// 链表头部是空
			this.head = null
			// 记录链表长度
			this.length = 0
			// 链表的常见操作
			// append(element)向列表尾部添加一个新的项
			this.append = function (element){
				var newnode = new Node(element)
				if(this.length == 0){
					// 判断第一个节点
					this.head = newnode
				}else{
					// 判断最后一个节点
					var current = this.head
					while(current.next){
						current = current.next
					}
					current.next = newnode
				}
				this.length += 1
			}
			// insert(position,element)向链表的特定位置插入项
			this.insert = function (position,element){
				// 负数和边界判断
				if(position < 0 || position > this.length) return false
				var newnode = new Node(element)
				// 判断插入位置是否是第一个
				if(position == 0){
					newnode.next = this.head
					this.head = newnode
				}else{
					// position大于0
					var index = 0 
					var current = this.head
					var previous = null
					while(index++ < position){
						previous = current 
						current = current.next
					}
					newnode.next = current
					previous.next = newnode
				}
				this.length += 1
				return true
			}
			// get(position)获取对应位置元素
			this.get = function (position){
				if(position < 0 || position >= this.length) return null
				// 获取对应data数据
				var current = this.head
				var index = 0
				while(index++ < position){
					current = current.next
				}
				return current.data
			}
			// indexOf(element)返回元素在列表中的索引 如果列表中没有该元素则返回-1
			this.indexOf = function(element){
				var current = this.head
				var index = 0
				while(current){
					if(current.data == element){
						return index
					}
					current = current.next
					index +=1
				}
				return -1
			}
			// update(position,newdata)修改某个位置的元素
			this.update = function(position,newdata){
				if(position < 0 || position >= this.length) return false
				// 查找正确节点
				var current = this.head
				var index = 0
				while(index++ < position){
					current = current.next
				}
				current.data = newdata
				return true
			}
			// removeAt(position)从列表的特定位置移除一项
			this.removeAt = function(position){
				// 越界判断
				if(position < 0 || position >= this.length) return null
				var current = this.head
				if(position == 0){
					this.head = this.head.next
				}else{
					var index = 0
					var previous = null
					while(index++ < position){
						previous = current
						current = current.next
					}
					previous.next = current.next
				}
				this.length -= 1
				return current.data
			}
			// remove(element)从列表中移除一项
			this.remove = function(element){
				var position = this.indexOf(element)
				return this.removeAt(position)
			}
			// isEmpty()如果链表中不包含任何元素返回true 链表长度>0返回false
			this.isEmpty = function(){
				return this.length == 0
			}
			// size()返回链表包含的元素个数
			this.size = function(){
				return this.length
			}
			// toString()
			this.toString = function(){
				var current = this.head
				var liststring = ''
				while(current){
					liststring += current.data + ' '
					// 防止死循环
					current = current.next
				}
				return liststring
			}
		}
		let lianbiao = new Lianbiao()
		lianbiao.append(1)
		lianbiao.append(2)
		lianbiao.append(3)
		lianbiao.insert(1,'111')
		lianbiao.insert(2,'222')
		console.log(lianbiao.get(1))
		console.log(lianbiao.get(2))
		console.log(lianbiao.indexOf('111'))
		console.log(lianbiao.indexOf('222'))
		console.log(lianbiao.update(1,'333'))
		console.log(lianbiao.removeAt(1))
		console.log(lianbiao.remove('222'))
		console.log(lianbiao.isEmpty())
		console.log(lianbiao.size())
		console.log(lianbiao)
		</script>

双向链表

<script type="text/javascript">
			// 单向链表
			// 只能从头遍历到尾或者丛尾遍历到头 过程是单向的 实现原理是上一个链表中有一个指向下一个的引用
			// 缺点 轻松到达下一个节点 但是无法快速返回上一个节点
			// 双向链表
			// 即可从头遍历到尾 也可从尾遍历到头， 一个节点既有向前连接的引用，也有向后链接的引用
			// 缺点：插入删除某个节点时 需要处理四个引用 实现麻烦 占用内存空间更大些 但是使用起来方便
			function Shuangxiang(){
				// 头和尾都是null
				this.head = null
				this.tail = null
				this.length = 0
				function Node(data){
					this.prev = null
					this.data = data
					this.next = null
				}
				// append(element)列表尾部追加
				this.append = function(data){
					var node = new Node(data)
					if(this.length == 0){
						this.head = node
						this.tail = node
					}else{
						// 尾部追加
						// 倒数第二项
						node.prev = this.tail
						this.tail.next = node
						this.tail = node
					}
					this.length += 1
				}
				// insert(position,element)特定位置插入
				this.insert = function(position,data){
					if(position < 0 || position > this.length) return false
					var node = new Node(data)
					if(this.length == 0){
						this.head = node
						this.tail = node
					}else{
						// 判断position是否为0 插入开头
						if(position == 0){
							this.head.prev = node
							node.next = this.head
							this.head = node
							// 插入结尾
						} else if (position == this.length){
							node.prev = this.tail
							this.tail.next = node
							this.tail = node
						} else {
							// 插入中间
							var current = this.head
							var index = 0
							while(index++ < position){
								current = current.next
							}
							// 修改指针
							node.next = current
							node.prev = current.prev
							current.prev.next = node 
							current.prev = node
						}
						this.length += 1
						return true
					}
				}
				// get(position)获取对应位置元素
				this.get = function(position){
					if(position < 0 || position > this.length)return null
					// this.length / 2 > position 从头遍历
					// this.length / 2 < position 从后向前遍历
					var current = this.head
					var index = 0
					while(index++ < position){
						current = current.next
					}
					return current.data
				}
				// indexOf(element)返回对应元素索引
				this.indexOf = function(element){
					var current  = this.head
					var index = 0
					while(current){
						if(current.data == element){
							return index
						}
						current = current.next
						index += 1
					}
					return -1
				}
				// update(position,element)修改某个位置的元素
				this.update = function(position,element){
					if(position < 0 || position > this.length) return false
					// this.length / 2 > position 从头遍历
					// this.length / 2 < position 从后向前遍历
					var current = this.head
					var index = 0
					while(index++ < position){
						current = current.next
					}
					// 修改信息
					current.data = element
					return true
				}
				// remove(element)移除某个元素
				this.remove = function(element){
					var index = this.indexOf(element)
					return this.removeAt(index)
				}
				// removeAt(position)移除某个位置元素
				this.removeAt = function(position){
					if(position < 0 || position >= this.length) return null
					var current = this.head
					if(this.length == 0){
						this.head = null
						this.tail = null
					}else{
						// 判断是否删除的是第一个
						if(position == 0){
							this.head.next.prev = null
							this.head = this.head.next
						}else if(position == this.length - 1){
							current = this.tail
							this.tail.prev.next = null
							this.tail = this.tail.prev
						}else{
							var index = 0
							while(index++ < position){
								current = current.next
							}
							current.prev.next = current.next
							current.next.prev = current.prev
						}
					}
					this.length -= 1
					return current.data
				}
				// isEmpty()是否为空
				this.isEmpty = function(){
					return this.length == 0
				}
				// size()返回链表元素个数
				this.size = function (){
					return this.length
				}
				// toString()
				this.toString = function(){
					return this.forwardString()
				}
				// forwardString()正向遍历的节点字符串形式
				this.forwardString = function(){
					var current = this.head
					var resultString = ''
					while(current){
						resultString += current.data + ' '
						current = current.next
					}
					return resultString
				}
				// backwordString()反向遍历的节点字符串形式
				this.backwordString = function(){
					var current = this.tail
					var resultString = ''
					while(current){
						resultString += current.data + ' '
						current = current.prev
					}
					return resultString
				}
				// 获取链表第一个head
				this.gethead = function (){
					return this.head
				}
				// 获取链表最后一个tail
				this.gettail = function (){
					return this.tail
				}
			}
			let shuangxiang = new Shuangxiang()
			shuangxiang.append('1')
			shuangxiang.append('2')
			shuangxiang.append('3')
			shuangxiang.insert(3,'111')
			shuangxiang.insert(4,'221')
			console.log(shuangxiang.forwardString())
			console.log(shuangxiang.backwordString())
			console.log(shuangxiang.toString())
			console.log(shuangxiang.get(2))
			console.log(shuangxiang.get(3))
			console.log(shuangxiang.indexOf('101'))
			console.log(shuangxiang.indexOf('1'))
			console.log(shuangxiang.indexOf('3'))
			console.log('------')
			console.log(shuangxiang.update(1,'1010'))
			// alert(shuangxiang)
			console.log(shuangxiang.removeAt(1))
			console.log(shuangxiang.removeAt(0))
			console.log(shuangxiang.remove('221'))
			console.log(shuangxiang.toString())
			console.log(shuangxiang)
		</script>

集合

<script type="text/javascript">
			// 集合 集合最常见的方式是哈希表 由无序的不能重复的元素构成
			// 一种特殊的数组 里面的元素没有顺序 不能重复 不能通过下标值访问 相同的对象只会存在一份
			// ea6的set已实现 此处自己封装
			function Set(){
				// 属性
				this.items = {}
				// 操作
				// add(value)添加新的项
				this.add = function(value){
					if(this.has(value)) return false
					this.items[value] = value
					return true
				}
				// remove(value)移除一个项
				this.remove = function(value){
					if(!this.has(value))return false
					delete this.items[value]
					return true
				}
				// has(value)包含值返回tru 反之返回false
				this.has = function(value){
					return this.items.hasOwnProperty(value)
				}
				// clear()清空
				this.clear = function(){
					this.items = {}
				}
				// size()类似数组length
				this.size = function(){
					return Object.keys(this.items).length
				}
				// values()返回包含所有值的数组
				this.values = function(){
					return Object.keys(this.items)
				}
				// 集合间操作
				// 并集 返回包含两个集合中所有元素的新集合
				this.union = function(otherset){
					// this.items已经是一个集合了 联合otherset集合
					var unionset = new Set()
					var values = this.values()
					for(var i = 0; i < values.length; i++){
						unionset.add(values[i])
					}
					values = otherset.values()
					for(var i = 0; i < values.length; i++){
						unionset.add(values[i])
					}
					return unionset
				}
				// 交集 返回包含两个集合中所有共有元素的集合
				this.intersection = function(otherset){
					var intersection = new Set()
					var values = this.values()
					for(var i = 0; i < values.length; i++){
						var item = values[i]
						if(otherset.has(item)){
							intersection.add(item)
						}
					}
					return intersection
				}
				// 差集 返回一个包含所有存在于第一个集合且不存在于第二个集合的新元素
				this.difference = function(otherset){
					var difference = new Set()
					var values = this.values()
					for(var i = 0; i < values.length; i++){
						var item = values[i]
						if(!otherset.has(item)){
							difference.add(item)
						}
					}
					return difference
				}
				// 子集 验证一个给定集合是否是另一个集合的子集
				this.subset = function(otherset){
					var subset = new Set()
					var values = this.values()
					for(var i = 0; i < values.length; i++){
						var item = values[i]
						if(!otherset.has(item)){
							return false
						}
					}
					return true
				}
			}
			let set = new Set()
			set.add('1')
			set.add('2')
			console.log(set.has('1'))
			// set.clear()
			set.remove('1')
			console.log(set.remove('3'))
			console.log(set.values())
			console.log(set.size())
			console.log('--------')
			set.add('hao')
			set.add('ge')
			console.log(set.values())
			// 并集
			var set2 = new Set()
			set2.add('111')
			set2.add('222')
			console.log(set2.items)
			var uniset = set.union(set2)
			console.log(uniset.values())
			// 交集
			var inter = new Set()
			inter.add('1')
			inter.add('2')
			inter.add('3')
			var inter2 = new Set()
			inter2.add('1')
			inter2.add('2')
			console.log(inter.values())
			console.log(inter.intersection(inter2).values())
			// 差集
			var differ = new Set()
			differ.add('9')
			differ.add('10')
			console.log(inter2.values())
			console.log(inter2.difference(differ).values())
			// 子集
			console.log(set.subset(differ))
			console.log(set.subset(set))
		</script>

字典

<script type="text/javascript">
		// 字典 : js默认有数组 es6添加的集合和字典
		// 键值对的对应关系 通过key取出value key不可以重复 value可以重复
		
</script>

哈希表

// 哈希表 js中并没有哈希表 但是更够实现 理论知识多 代码少
// 基于数组实现 快速插入删除查找 哈希表的速度比树更快 基本可以瞬间查找到元素
// 相对于树来说编码容易些
// 数组进行插入操作时  效率比较低
// 查找时：如果基于下标查找效率高  如果基于内容查找效率很低
// 数组进行删除操作 效率低 各种位移操作
// 数组进行修改和查找差不多

// 哈希表相对于数组的不足
// 数据没有顺序 不能以一种固定的从小到大或者从大到小的顺序遍历元素
// key值不允许重复 不能使用相同的key保存不同的值

// 哈希表结构是数组 特别的地方是对下标值的变换 称为哈希函数
// 通过哈希函数可以获取到HashCode

// 公司员工存储
// 数组结构存储一个个员工信息 下标效率较高 定义员工编号查找
// 链表结构 插入和删除效率比较高 从头到尾查找效率低

// 联系人和电话存储
// 存储单词

// 将字符串转换为下标值方案 字母文字转数字
// 字符编码 ASCII编码 a是97 b是98，，，122是z   GBXXXX GBK GB18030十万中文文字
// 单独设置本地区域独特文字的编码一旦上了国际就不行 因此Unicode万国码出来了utf-8 utf-32
			
// 设计自己的编码 方便理解
			
// 方案1:吧单词每个字符的编码求和 cats是3+1+20+19=43 那么43就作为cats单词的下标存在于数组中
// 名称key不会重复 但是编码值相加下标值可能会重复 后来的数据必然会覆盖 下标值存储很多值不合理
			
// 方案2:幂的连乘 7654 = 7*10的3次方 + 6*10的2次方 + 5*10的1次方 + 4
// 基本可以保持数据的唯一性 不会和别的单词重复 
// cats = 3 * 26(自己编码的26个字符)的3次幂 + 1 * 26的2次幂 + 20 * 27 + 17 = 60337
// 但是如果是zzzzzzzz的话那么下标值就是70000000000.。 创建大的下标值的数组没有意义
// 会存在很多下标值是空的位置 虽然保证了数字的唯一性 但是对空间造成了很大的浪费性
			
// 改进方案2 hash化 哈希化 把幂的连乘方案中得到的巨大的整数范围压缩到可接受的范围内
// 0-70000000000压缩到0-100000   使用取余操作符 也会存在一定的重复性 后续解决
// 哈希化  将大数字压缩成规定范围下标值
// 哈希函数 将字母文字单词转换为大数字的函数
// 哈希表 将最终得到的数字插入数组 整体结构的封装称之为哈希表
			
// 什么事冲突 下标值相同 已存在 即使概率小 也要考虑解决方案 
// 常见两种解决方式
// 1：链地址法 / 拉链法
// 2：开放地址法
// 1链地址法
// 将相同下标值的元素存放在链表（或者数组）中，每个数组单元存储的不再是单个数据 而是一个链表
// 如果插入前端 使用链表    插入后端使用数组
			
// 2:开放地址法 寻找空白的单元格添加重复的数据
// 探索空白位置有三种方法 查找空位厕所 找坑填坑
// 线性检测法  如果单元格存在数据 index + 1依次向后查找  删除元素后 不能将下表设置为null
 // 会影响之后查询的其他操作 所以通常删除一个数据后 会进行特殊处理（将下标值设置为-1）
// 线性检测有问题 
// 聚集 一连串的相同下标值向后查找填充后续多个单元单元就是聚集 影响hash表的性能 查询/删除/插入
			
// 二次检测法 优化的是探测的步长 x + 1  x + 3相隔多个步数探测 一次性探测较远距离 避免聚集影响
 // 问题：也会存在累加步数到达相同位置的元素 还是会影响效率 因此要设置每个人的步长都不一样

// 再哈希法  
// 为了消除线性检测和二次检测中步长的问题
// 需要一种方法产生一种依赖关键字的探测序列 而不是每个关键字都一样 不同的关键字即使映射到
// 相同的数组下标 也可以使用不同的探测序列 
// 把关键字用另外一个函数再做一个哈希化 用这次哈希化的结果作为步长 对于指定的关键字
// 步长在整个探测中是不变的 不过不同的关键字使用不同的时长

// 特点
// 和第一个哈希函数不相同  不能输出为0 否则将没有步长 每次探测都是原地踏步 算法就进入死循环 
// 计算机专家已经设计出了工作很好的哈希函数
// stepSize = constant - （key % constant）
// 其中constant是质数 且小于数组的容量
// 例如stepSize = 5 - （key % 5）满足需求 那么结果不可能为0

// 哈希化的效率
// 哈希化执行插入和搜索效率是非常高的 如果没有冲突效率更高 如果存在冲突 那么查询事件就依赖后来的探测长度
// 平均探测长度以及平均存取时间 取决于装填因子 随着装填因子变大 探测长度也越长
// 随着装填因子变大 效率下降 在不同开发地址法方案中比链地址法更严重

// 装填因子 表示当前哈希表中已经包含的数据项和整个哈希表长度的比值
// 装填因子 = 总数据项 / 哈希表长度
// 开放地址法的最大装填因子是1 必须找到空白单元格才能放入 后续效率也会变低
// 链地址法的装填因子可以大于1 因为拉链法可以无线延伸下去 但是后续效率会变低


// 优秀的哈希函数
// 哈希表的优点在于速度 提高速度的一个方法就是让哈希函数中尽量少有乘法和除法因为他们性能低
// 快速获取hashCode值 无论是链地址法还是开放地址法 当多个元素映射到同一个位置都会影响效率 
// 所以 优秀的哈希函数尽量会把元素映射到不同的位置 让元素在哈希表中均匀的分布

// 3*2的10次方 + 3*2的9次方 + 3*2的8次方 + 3*2的7次方 。。。 效率低下
// 优化：霍纳法则（秦九韶算法）
// 大O表示法从O(N的2次方)变成了O(N)
// 大O表示法：（N的2次方 + n） / 2   随着数据增加查找数据的时间的变化趋势
// 在需要使用常量的地方尽量使用质数 
// 质数使用的位置
// 哈希表的长度 N次幂的底数

// 设计哈希函数
// 1：将字符转换为比较大的数字hashCode
// 2：将大的数字压缩到数组范围内
function hashFunc(str,size){
    // 1:定义hashCode变量
    var hashCode = 0
    // 2:霍纳算法计算hashCode值
    for(var i = 0;i < str.length;i++){
    // 获取该字符unicode
    // str.charCodeAt(i)
    hashCode = 37 * hashCode + str.charCodeAt(i)
}
// 取余操作
var index = hashCode % size
console.log('index',index)
}
hashFunc('cats',7)
hashFunc('catss',7)
hashFunc('catsss612',7)


// 采用链地址法实现hash表格
function hashTable(){
// 属性
this.storage = [] //存放相关元素
this.count = 0 //表示已经存在多长的数据
this.limit = 7 //标记数组中一共可以存多少数据
// 装填因子loadFactor 如果超过0.75就需要对数组进行扩容 小于0.25还需要变小压缩
// 方法
// 哈希函数
hashTable.prototype.hashFunc =  function (str,size){
// 1:定义hashCode变量
var hashCode = 0
// 2:霍纳算法计算hashCode值
for(var i = 0;i < str.length;i++){
// 获取该字符unicode
// str.charCodeAt(i)
hashCode = 37 * hashCode + str.charCodeAt(i)
}
// 取余操作
var index = hashCode % size
return index
}
// 插入修改
hashTable.prototype.put = function(key,value){
// 1：根据key获取索引值 将数据插入对应位置
var index = this.hashFunc(key,this.limit)
// 2：根据索引值取出桶 判断桶是否存在 不存在就创造桶，放在该位置
var bucket = this.storage[index]
if(bucket == null){
bucket = []
this.storage[index] = bucket
}
// 3：一定有桶以后判断是修改还是添加操作 如果有值了那么就修改值 如果没有执行添加操作
// 修改操作
for(var i = 0; i < bucket.length; i++){
// 从数组中线性查找
var tuple = bucket[i]//tuple是桶中的每一个数组
if(tuple[0] == key){
tuple[1] = value
return
}
}
// 新增操作
bucket.push([key,value])
this.count += 1
// 判断是否需要扩容操作
if(this.count > this.limit * 0.75){
// 判断扩容完成是否是质数
var newSize = this.limit * 2
var newZhishu = this.getZhishu(newSize)
this.resize(newSize)
}

}
// 查找获取
hashTable.prototype.get = function(key){
// 1：根据key获取索引值
var index = this.hashFunc(key,this.limit)
// 2：根据index获取对应桶bucket 判断bucket是否为空
var bucket = this.storage[index]
if(bucket == null){
return null
}
// 循环遍历桶中每一个数值的key是否和传入的key相同
for(var i = 0; i < bucket.length; i++){
var tuple = bucket[i]
if(tuple[0] == key){
// 找到对应key返回value
return tuple[1]
}
}
// 还没找到
return null
}
// 删除操作
hashTable.prototype.remove = function(key){
// 1：根据key获取索引值
var index = this.hashFunc(key,this.limit)
// 2：根据index获取对应桶bucket 判断bucket是否为空
var bucket = this.storage[index]
// 不存在直接返回null
if(bucket == null){
return null
}
// 3：循环遍历桶中每一个数值的key是否和传入的key相同
for(var i = 0; i < bucket.length; i++){
var tuple = bucket[i]
if(tuple[0] == key){
// 找到对应key删除
tuple.splice(i,1)
this.count--
return tuple[1]
// 如果storage过长 内部数据太少 那么就需要缩小容量 此处应该不会执行 放置位置有错误
if(this.limt > 7 && this.count < this.limit * 0.25){
// 缩小为质数
var newSize = Math.floor(this.limit / 2)
var newZhishu = this.getZhishu(newSize)
this.resize(newSize)
}
}
}
// 依然没有找到
return null
}
// 其他操作
// 是否为空
hashTable.prototype.isEmpty = function(){
return this.count == 0
}
// 获取hash表中元素的个数
hashTable.prototype.size = function(){
return this.count
}
// 哈希表扩容思想
// 因为使用的是链地址法 填充因子可以大于1 所以这个hash表可以无线填充新数据
// 但是随着数据量的增多 每一个index对应的bucket就会越来越长 也就会造成效率的降低 
// 所以要在适当的时候对数组进行扩容 比如扩容两倍
// 但是这种情况下 所有的数据项一定要同时进行修改 重新调用hash函数获取不同位置 虽然耗时 但是如果扩容这是必须的
// 填充因子>0.75时扩充
// 实现扩容 取出所有桶和元素 插入新的storage中通过put插入
// 容量质数 容量最好是质数 虽然链地址法中没有开放地址法长度是质数重要 但是还是有好处的
// 如何判断一个数是质数？（面试题）质数特点：也称为素数 质数表示大于1的自然数中 只能被1和自己整除
// function isZhishu(num){
// 这样的写法效率低
// for(var i = 2; i < num; i++){
// if(num % i == 0){
// 	return false 不是质数
// }
// }
// return true 是质数
// 更高效的方式 不需要从2判断到num-1 判断开平方根 面试选这个
// var temp = parseInt(Math.sqrt(num))//求平方根
// for(var i = 2; i <= temp; i++){
// 	if(num % i == 0){
// 		return false
// 	}
// }
// return true
// }
// 扩容操作 还需实现扩容大小limit恒为质数
hashTable.prototype.resize = function(newlimit){
// 1:保存旧storage
let oldstorage = this.storage
// 2:重置所有属性
this.count = 0
this.limit = newlimit
// 3:遍历oldStorage中所有的bucket
for(var i = 0; i < oldstorage.length; i++){
// 3.1:取出所有桶
var bucket = oldstorage[i]
if(bucket == null){
continue
}
// 3.2buckey有数据重新插入
for(var j = 0; j < bucket.length; j++){
var tuple = bucket[j]
// 4:插入新的storage
this.put(tuple[0],tuple[1])
}
}
}
// 判断是否是质数
hashTable.prototype.isZhishu = function(){
var temp = parseInt(Math.sqrt(num))//求平方根
for(var i = 2; i <= temp; i++){
if(num % i == 0){
return false
}
}
return true
}
// 获取质数方法
hashTable.prototype.getZhishu = function(num){
// 判断num是否是质数 如果不是向后查找
while(!this.isZhishu(num)){
num++
}
return num
}
}
let table = new hashTable()
// 最后的形式 [[[key,value],[key,value],[key,value]],[[key,value],[key,value]],[]]
// 测试hash表
table.put('abc','321')
table.put('nba','521')
table.put('mba','1')
table.put('aaa','13')
table.put('bba','12')
console.log('获取',table.get('abc'))
console.log('删除',table.remove('bba'))
console.log('为空',table.isEmpty())
console.log('size长度',table.size())
console.log(table)

树

// 树的优点
			// 数组的优点缺点
			// 优点：下标值访问效率高 缺点：需要先对数组进行排序生成有序数组 才能提高查找效率 在插入和删除时会有大量位移操作效率低
			// 链表的优点和缺点
			// 优点：链表的插入和删除效率都很高 
			// 缺点：查找效率很低 需要从头开始依次访问链表中的每个数据项 直到找到 即使插入删除效率高 删除和插入还是要从头遍历
			// 哈希表优点和缺点
			// 优点：插入删除查询效率高 缺点：空间利用率不高 底层使用数组 并且某些单元没有被利用 元素时无序的不能按照固定顺序遍历访问
			// 不能快速找到hash表中最大值或者是最小值
			// 树结构
			// 效率一般没有哈希表高 弥补了一些结构的缺点 模拟某些场景树结构会更加方便 因为树结构非线性 一对多比如文件的目录结构
			// 每个结构都有各自适合的应用场景
			
			// 树结构相关概念 术语
			// 树：由n(n>=0)个节点构成的有限集合
			// 当n=0时称为空树 n>0的非空树具有一下性质
		    // 树中有一个称为根(Root)的特殊节点 用r表示
		    // 其余节点可分为m(m>0)个互不相交的有限集合T1，T2，T3，，，，，TM  其中每个集合本身又是一棵树 称为原来树的子数 子树SubTree
			// 术语
			// 1：节点的度（Degree）：节点的子树个数
			// 2：树的度：树的所有节点中最大的度数
			// 3：叶节点（Leaf）度为0的节点（也成为了子节点）没有子节点的节点
			// 4：父节点（Parent）有子树的节点是其子树的根节点的父节点
			// 5：子节点（Child）若A节点是B节点的父节点 则称B节点是A节点的子节点 子节点也称为孩子节点
			// 6：兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点
			// 7：路径和路径长度：从节点n1到nk的路径为一个节点序列n1，n2，，，，nk，ni是ni+1的父节点，路径所包含边的个数为路径的长度
			// 8：节点的层次（Level）：规定根节点在1层，其他任一节点的层数是其父节点的层数+1
			// 9：树的深度（Depth）：树中所有节点中的最大层次是这棵树的深度
			
			// 树的表示方式
			// 儿子兄弟表示法
			
			// 二叉树：如果每个节点最多只有两个节点 这样的树就称为二叉树 所有的树都可以表示成二叉树的形式 二叉树可以为空 可以没有节点
            // 若不为空 则它是由根节点和左子树TL和右子树TR的两个不想交的二叉树组成
            //   Element
            // left | right

二叉树

// 二叉树
			// 二叉树形态
			// 一个二叉树第i层的最大节点数为2的(i-1)次方 i>=1
			// 深度为k的二叉树有最大节点总数为 2的(K-1)次方 k>=1
			// 对任何非空二叉树T，若n0表示叶节点的个数 n2是度为2的非叶节点个数 那么两者满足关系n0 = n2 + 1
			// 完美二叉树 也称为满二叉树 除了最下层的叶节点外 每层节点都有2个子节点 就构成了满二叉树
			
			// 完全二叉树 除了最后一层外 其他各层的节点数都达到最大个数
			// 且最后一层从左向右的叶节点持续存在 只缺右侧若干节点
			// 完美二叉树是特殊的完全二叉树
			
			// 二叉树的存储 常见方式是数组和链表
			// 使用数组 完全二叉树 从上到下 从左到右顺序存储
			// 非完全二叉树需要转换成完全二叉树才能按照上面方式存储 但是会造成很大的空间浪费
			
			// 二叉树常见方式是链表
			// 每个节点封装成一个Node，Node中包存储的数据，左节点的引用，右节点的引用
			// left | data | right
			
			// 二叉搜索树(BST，Binary Search Tree) | 二叉排序树 | 二叉查找树
			// 在二叉树基础上加了一些限制
			// 二叉搜索树是一颗二叉树 可以为空
			// 如果不为空需要满足以下性质
			// 1：非空左子树的所有键值小于其根节点的键值
			// 2：非空右子树的所有键值大于其根节点的键值
			// 3：左右子树本身也都是二叉搜索树
			// 特点：较小值保存在左节点 较大值保存在右节点 查找效率非常高

二叉搜索树

<script type="text/javascript">
			// 二叉搜索树实现
			// 封装保存每一个节点的类Node 该类包含三个属性 节点对应的key 指向的左子树 右子树
			// 该函数只需要保存根节点即可 其他节点都可通过根节点找到
			function BinarySearchTree(){
				// 根节点
				this.root = null
				// 内部节点类
				function Node(key){
					this.key = key
					this.left = null
					this.right = null
				}
				// 插入新的键
				BinarySearchTree.prototype.insert = function (key){
					// 1根据key创建节点
					var newNode = new Node(key)
					// 2判断根节点是否有值 如果没有值就将该node作为根节点 如果有值就个根节点对比大小
					if(this.root == null){
						// 如果没有值就将该node作为根节点
						this.root = newNode
					}else{
						// 比较大小
						// 取出根节点的右节点和该newNode比较
						this.insertNode(this.root,newNode)
					}
				}
				// 内部方法，自己调用 node是比较的对象 newnode是插入的对象
				BinarySearchTree.prototype.insertNode = function(node,newNode){
					if(newNode.key < node.key){
						// 向左查找 
						if(node.left == null){
							// 左节点为空
							node.left = newNode
						}else{
							// 左节点不为空 继续比较
							this.insertNode(node.left,newNode)
						}
					}else{
						// 向右查找
						if(node.right == null){
							// 左节点为空
							node.right = newNode
						}else{
							// 左节点不为空 继续比较
							this.insertNode(node.right,newNode)
						}
					}
				}
				// 查找一个键 搜索特定key 如果存在返回true 不存在返回false
				BinarySearchTree.prototype.search = function (key){
					// 获取根节点
					var node = this.root
					while(node != null){
						if(key < node.key){
							node = node.left
						}else if(key > node.key){
							node = node.right
						}else{
							return true
						}
					}
					return false
				}
				// 遍历方式 针对所有树(每个树都能转换成二叉树) 不止二叉搜索树
				//  访问每一个节点做出操作 先/中/后还有层序遍历但是很少
				// 先序遍历是先遍历根节点 再遍历左子树 右子树
				// 后序遍历是先遍历右子树 再遍历左子树 根节点
				// 中序遍历是先遍历左子树 再遍历根节点 再遍历右子树
				// 通过中序遍历方式遍历所有节点
				BinarySearchTree.prototype.inOrderTraverse = function (handler){
					this.inOrderTraverseNode(this.root,handler)
				}
				// 封装的内部中序遍历递归方法
				BinarySearchTree.prototype.inOrderTraverseNode = function (node,handler){
					if(node != null){
						 // 处理经过节点的左子节点
						 this.inOrderTraverseNode(node.left,handler)
						 // 处理经过的节点
						  handler(node.key)
						 // 处理经过节点的右子节点
						 this.inOrderTraverseNode(node.right,handler)
					}
				}
				// 通过先序遍历方式遍历所有节点 先访问根节点 再遍历左子树 再遍历右子树
				BinarySearchTree.prototype.preTraverse = function (handler){
					this.preTraverseNode(this.root,handler)
				}
				// 封装的内部先序遍历递归方法
				BinarySearchTree.prototype.preTraverseNode = function (node,handler){
					if(node != null){
						// 处理经过的节点
						 handler(node.key)
						 // 处理经过节点的左子节点
						 this.preTraverseNode(node.left,handler)
						 // 处理经过节点的右子节点
						 this.preTraverseNode(node.right,handler)
					}
				}
				// 通过后序遍历方式遍历所有节点 先访问根节点 再遍历右子树 再遍历左子树
				BinarySearchTree.prototype.postTraverse = function (handler){
					this.postTraverseNode(this.root,handler)
				}
				// 封装的内部后序遍历递归方法
				BinarySearchTree.prototype.postTraverseNode = function (node,handler){
					if(node != null){
						 // 处理经过节点的左子节点
						 this.preTraverseNode(node.left,handler)
						 // 处理经过节点的右子节点
						 this.preTraverseNode(node.right,handler)
						 // 处理经过的节点
						 handler(node.key)
					}
				}
				// 返回树中最小的值/键
				BinarySearchTree.prototype.min = function (){
					var node = this.root
					while(node != null && node.left != null){
						node = node.left
					}
					return node.key
				}
				// 返回树中最大的值/键
				BinarySearchTree.prototype.max = function (){
					var node = this.root
					while(node != null && node.right != null){
						node = node.right
					}
					return node.key
				}
				// 从树中移除某个键
				// 需要考虑仨种情况
				// 该节点是叶节点 没有子节点 比较简单 节点left和right都为空 设置父元素的left或者right为null
				// 还要考虑该节点是否是根节点 如果只有单独的根 直接删除即可
				// 该节点有一个子节点
				 // 直接让父级跨级指向下一个
				// 给节点有两个子节点
				BinarySearchTree.prototype.remove = function (key){
					// 先查找到节点 如果没找到不需要删除 找到要删除的节点 粉三种情况
					// 寻找节点
					// 1:定义变量保存信息
					var current = this.root
					var parent = null
					// 是否是current的左子节点
					var isleft = true
					// 开始寻找节点
					while(current.key != key){
						parent = current
						// 叶节点
						if(key < current.key){
							isleft = true
							current = current.left
						}else{
							isleft = false
							current = current.right
						}
						// 还有一种情况 已经找到了最后一层但是依旧没找到==key
						if(current == null) return false
					}
					// 2:根据对应情况删除节点 根据几种情况删除 
					// 找到了current.key = key 还有种可能没有找到
					// 2.1删除的节点是叶子节点 考虑根节点
					if(current.left == null && current.right == null){
						// 删除的节点是根节点
						if(current == this.root){
							this.root = null
							// 根据isleft值判断删除节点位于父节点左侧还是右侧
						}else if(isleft){
							parent.left = null
						}else{
							parent.right = null
						}	
					}
					// 2.2删除的节点有一个子节点
					// 右节点为空
					else if(current.right == null){
						// 考虑根节点有一个子节点 删除根节点 用下一个节点元素覆盖称为根节点
						if(current == this.root){
							this.root = current.left
						}else if(isleft){
							parent.left = current.left
						}else{
							parent.right = current.left
						}
					// 左节点为空
					}else if(current.left = null){
						if(current == this.root){
							this.root = current.right
						}else if(isleft){
							parent.left = current.right
						}else{
							parent.right = current.right
						}
					}
					// 2.3删除的节点有两个子节点
					else{
						// 1、找到后续节点
						    let successor = this.getSuccessor(current);
						    // 2、判断是否为根节点
						    if (current === this.root) {
						      this.root = successor;
						    } else if (isLeftChild) {
						      parent.left = successor;
						    } else {
						      parent.right = successor;
						    }
						
						    // 3、将后续的左节点改为被删除的左节点
						    successor.left = current.left;
					}
				}
				// 删除带有两个节点的节点内部方法
				BinarySearchTree.prototype.getSuccessor = function(delNode){
					// 定义变量，保存要找到的后续
					  let successor = delNode;
					  let current = delNode.right;
					  let successorParent = delNode;
					
					  // 循环查找 current 的右子树节点
					  while (current !== null) {
					    successorParent = successor;
					    successor = current;
					    current = current.left;
					  }
					  // 判断寻找到的后续节点是否直接就是要删除节点的 right
					  if (successor !== delNode.right) {
					    successorParent.left = successor.right;
					    successor.right = delNode.right;
					  }
					  return successor;
				}
			}
			let binary = new BinarySearchTree()
			// 插入测试
			binary.insert(2)
			binary.insert(3)
			binary.insert(1)
			binary.insert(6)
			binary.insert(10)
			binary.insert(9)
			binary.insert(11)
			binary.insert(20)
			// 先序遍历测试
			var result = ''
			binary.preTraverse(function(key){
				result += key + ' '
			})
			console.log('先序遍历',result)
			// 先序遍历结束
			// 中序遍历测试
			var result2 = ''
			binary.inOrderTraverse(function(key){
				result2 += key + ' '
			})
			console.log('中序遍历',result2)
			// 中序遍历结束
			// 后序遍历测试
			var result3 = ''
			binary.postTraverse(function(key){
				result3 += key + ' '
			})
			console.log('后序遍历',result3)
			// 后序遍历结束
			console.log(binary)
			// 最小值最大值测试
			console.log('min:',binary.min(),'max:', binary.max())
			// 删除测试
			binary.remove(2)
			// 删除不存在的元素返回false
			console.log(binary.remove(100))
			// 测试搜索
			console.log(binary.search(20))
			console.log(binary.search(100))
			binary.postTraverse(function(key){
				result3 += key + ' '
			})
			// 删除后打印
			console.log('后序遍历',result3)
		</script>

二叉搜索树总结和缺陷

// 删除操作很复杂 很多程序员是通过
// 在node类中添加一个boolean字段 比如名称为Deleted
// 要删除一个节点时 就将该属性设置为true
// 在查找时判断该属性是否是true 为true就是已删除
// 相对简单 且不会改变原有数据结构
// 看起来很聪明 但是被删除的元素依旧保留在二叉树的存储中 造成了巨大的空间浪费

        // 二叉搜索树缺陷
        // 优点：快速找到给定关键字的数据项 快速插入删除
        // 缺陷：二叉搜索树插入有序顺序 深度会非常大
        // 比较好的二叉树左右数据分布较平衡 分布的不均匀叫做非平衡树
        // 平衡二叉树查找效率是O(logN)
        // 非平衡二叉树相当于编写了一个链表 查找效率变成了O(N)
        
        // 为了能以较快的时间O(logN)来操作一棵树 我们需要保证树总是平衡的
        // 至少大部分是平衡的 那样时间复杂度也会无限趋近于O(logN)的
        // 每个节点左边的子孙点的个数应该尽可能的等于右边的子孙节点的个数
        
        // 常见平衡树
        // AVL树 早期的平衡树 他有些办法保持树的平衡（每个节点多存储了一个额外的数据）
        // 因为AVL树是平衡的 所以时间复杂度也是O(logN)
        // 但是每次插入删除效率不高，整体效率不如红黑树
        
        // 红黑树 红黑树也有一些特性来保持树的平衡
        // 因为是平衡树 所以时间复杂度也是O(logN)
        // 另外插入删除等操作 红黑树的性能要优于AVL树 所以平衡树的应用基本都是红黑树

loading……