学习数据结构

数据结构学习

 

1、数据项：数据结构中最小单元

2、数据元素：由数据项构成

3、数据结构：带结构的数据元素的集合

4、算法的时间复杂度：由该算法中的核心计算所决定，其时间复杂度T(n) = N^m ，N为计算次数，m为核心计算循环（重复操作）次数。

一般而言算法的时间复杂度与问题规模与算法所采用策略有关，同一个问题，采用不同的算法策略其时间复杂度有可能不同，例如：排序（冒泡排序与插入排序）

算法的空间复杂度

 

线性表的特点：1、集合中必须存在唯一的一个“第一元素”

     2、集合中必须存在唯一的一个“最后元素”

     3、除第一元素之外其他每个元素有且只有唯一的一个前驱元素

     4、除最后元素之外其他每个元素有且只有唯一的一个后继元素

 

线性表的顺序表示：

特点：用一组地址连续的存储单元存储，相邻两元素之间其物理地址相邻，方便查询，插入与删除数据则比较麻烦，长度固定。

线性表的链式表示：

特点：地址任意，通过使用数据+地址的节点序列来表示线性表，不方便查询，插入与删除数据则比较方便，长度不固定。

 

单链表、双向链表、循环链表

 

 

求两个正整数的最大公约数：

 

	//求最大公约数，现设a>b
	public int big(int a,int b){
		int c = a % b;
		while(c!=0){
			a = b;
			b = c;
			c = a % b;
		}
		return b;
	}

 求两个正整数的最小公倍数：

 

	//求最小公倍数
	public int small(int a,int b){
		int c = a * b;
		while(a!=b){
			if(a>b){
				a = a - b;
			}else{
				b = b - a;
			}
		}
		c = c / a;
		return c;
	}

   //已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。

	public double lineSmall(double[] line){
		double m = 0;
		if(line.length>0){
			m = line[0];
			for(int i=0;i<line.length;i++){
				if(m>line[i]){
					m = line[i];
				}
			}
		}else{
			//抛出异常
		}
		return m;
	}

 

 

栈与队列：

栈：先进后出，只能从队尾进栈或出栈。

队列：先进先出，从队尾进栈，从队首出栈。

 

 

树：

只有一个根节点，树结构可以通过递归来表示（树是由子树所构成，子树是由更小的子树所构成。。。。。）。

一个节点子树的个数称为该节点的次数或该节点的度；树中各节点的次数最大值称为该树的次数。

假设树T为一棵m次数，该树中非叶子节点的次数都为m，那么称T为一棵m次完全树。

二叉树：节点（包括根节点）可以为空，一个节点最多只有两个分支节点（左子树、右子树）。

二叉树第k层，其节点个数n<=2^k-1

深度为h的二叉树，其节点个数n<=2^k-1

对于任意一棵二叉树，若它含有n1个叶子节点，n2个度为2的节点，则：n1 = n2 + 1（树的分支个数与节点度数以及节点个数的关系）

满二叉树：深度为k且有2^k-1个节点个数的二叉树。

完全二叉树：树中所含n各节点与满二叉树中编号为1至n的节点一一对应。（即完全二叉树包含满二叉树，若完全二叉树不为满二叉树时，其1至k-1层为满二叉树，第k层中由左至右依次填充）

 

二叉树的遍历：

前序遍历：先访问根节点

 

中序遍历：第二次路过时访问根节点

 

后序遍历：最后访问根节点

（二叉树的遍历过程中每个子节点都可视为根节点，在探测其是否有左右子树并返回的过程中共经过所探测节点3次）