哈希表是一个固定大小的数组，数组的每个元素是一个链表（单向或双向）的头指针。如果Key一样，则在一起，如果Key不一样，则不在一起。哈希表的查询是飞快的。因为它不需要从头搜索，它利用Key的“哈希算法”直接定位，查找非常快，各种数据库中的数据结构基本都是它。但带来的问题是，哈希表的尺寸、哈希算法。 哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数，最小的质数尺寸是17。 根据不同的数据量，会有不同的哈希表的大小。对于数据量很时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。下面的数库是哈希表变化尺寸时尺寸大小的一个列表。 “`CPP static int prime_array[] = {     17,             /* 0 */     37,             /* 1 */     79,             /* 2 */     163,            /* 3 */     331,            /* 4 */     … “数据结构之Hash Table”

线性表或者说线性结构的特点: 1. 存在唯一的一个首位元素. 2. 存在唯一的一个末位元素. 3. 除首位外,结构中的每个数据元素都有且只有一个前驱. 4. 除末位外,结构中的每个数据元素都有且只有一个后继. ## 顺序线性表 顺序线性表指的是使用一组地址连续的存储单元一次存储线性表的数据元素,也称作顺序存储结构或者顺序顺序映像. 其特点是: > 逻辑上相邻的数据元素,其物理次序也是相邻的,因此占用空间紧凑. ### 初始化 “`CPP int InitList(List &L){ L.elem =new ElemType[MaxSize]; if(!L.elem) return ERROR; L.length=0; return SUCCESS; } “` ### 查找 “`CPP … “数据结构之线性表”

时间复杂度 一个算法的执行时间大致等于其所有语句执行时间的总和,而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积. 一条语句的重复执行次数乘坐语句的频度(Frequency Count). 设每条语句执行一次所需的时间为单位时间,则一个算法的执行时间就是该算法中所有语句频度之和. for(int i=0;i<n;++i){ //频度n+1 for(int j=0;j<n;++j){ //频度n*(n+1) c[i][j]=0; //频度n*n for(int k=0;k<n;++k){ //频度n*n*(n+1) c[i][j]=c[i][j]+a[i][j]*b[k][j]; //频度n*n*n } } } 因此以上算法所有语句的频度之和,即为算法的执行时间,用T(n)表示: {{T(n) = 2n^3+3n^2+2n+1}} 求解的输入量称之为规模,一般用n表示.以上求解式,当n趋于无限大时,则有: {{\displaystyle\lim_{x \to \infty} \dfrac{T(n)}{n^3} = \displaystyle\lim_{x \to \infty} \dfrac{(2n^3 … “关于算法的时间复杂度与空间复杂度的认知”

算法的特性 算法是为了解决某类问题而规定的一个有限长的操作序列. 一个算法必须满足以下五个重要特性: 1. 有穷性.一个算法必须总是在执行有穷步后结束,且每步都必须在有穷时间内完成. 2. 确定性.对于每种情况所应执行的操作,在算法中有确定的规定,不会产生二义性,使算法的执行者与阅读者都能明确知道其中的含义. 3. 可行性.算法的所有操作都可以通过已经实现的基本操作运算执行有限次来完成. 4. 输入.一个算法有零个或多个输入.当用函数描述算法时,输入往往时通过形参表示. 5. 输出.一个算法有一个或多个输出,它们是经过算法加工后结果,无输出的算法没有意义. 算法的优劣评判 一个算法的优劣应该有以下方面来评判: 1. 正确性. 在合理的数据输入下,能够在有限时间内得到正确的结果. 2. 可读性.一个好的算法首先是能够直观的阅读,便于人类理解. 3. 健壮性.当输入的数据非法时,好的算法能够进行正确的反应,而不会崩溃或输出奇怪的结果. 4. 高效性.一个好的算法应该能够在消耗最少的资源(时间/内存使用率/CPU占有率)下而得出正确的结果.可以使用时间复杂度和空间复杂度来衡量.

数据结构是相互之间存在一种或多种特定关系的数据元素的集合. 数据结构包括逻辑结构和物理结构两个层面. 逻辑结构 逻辑结构存在两个要素: 1. 一是数据元素. 2. 二是关系. 数据元素就是存放的数据对象,有各式各样的类型,而关系是数据元素之间的逻辑关系.根据数据元素之间的不同特性,通长有四类基本结构:集合结构,线性结构,树结构,图结构/网状结构.除线性结构外,其它皆可称之为非线性结构. 集合结构: 数据元素除了同属同一集合外,无其他关系.如确定这两个学生是否属于同一个班级. 线性结构: 数据元素之间存在一对一关系.如学生按照入学时间排序. 树结构: 数据元素之间存在一对多关系.如班长管理多个组长,组长管理组员. 图结构: 数据元素直接存在多对多关系.如多位同学之间的朋友关系. 物理结构 物理结构也是数据对象在存储中的存储结构.数据元素在计算机内用一个节点来表示. 而在存储过程中,数据元素有两种基本的存储结构,分别是顺序存储结构和链式存储结构. 顺序存储结构: 顺序存储结构要求所有元素以此存放在一片连续的存储空间中. 链式存储结构: 链式存储结构则无需占用一整片的存储空间,它是随机存放.但为了表示节点的关系,需要给每个节点附加指针字段,用于存放后继元素的位置.