数据结构的几个小问题（数据结构是解决什么问题）

数据结构的几个小问题（数据结构是解决什么问题）

准备好开始了吗，我觉得你没有准备好，准备好的意思是，你得做十个标准俯卧撑，然后心平气和，喝口水，我喝的是咖啡，这有助于提高注意力。要知道这部分内容有些许无聊，这样的准备是很有必要的。

数据结构与算法

概念全背

数据是信息的载体，是所有能够被计算机识别，存储和加工处理的符号的总称。 数据项是具有独立含义的标识单位，是数据不可分割的最小单位。 数据元素是数据的基本单位。 数据对象是具有相同性质的数据元素的集合。 数据结构是指互相之间存在着一种或多种关系的数据元素的集合。 逻辑结构：数据元素之间的关系称为逻辑结构 存储结构：最常用的是顺序存储和链式存储 数据的运算：运算是对数据的处理

空间复杂度是指算法运行从开始到结束所需的存储量

空间复杂度是指算法的时间耗费。

数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的计算方法和运算的学科。

算法必须具备可行性，有穷性，确定性。

非常痛苦对不对，不过别担心，第一章已经过去了，如果说会考到其他没有入选的题目，那就看运气了。

递归

见微知著，识人心智。

说句真话，递归大家可以不用看的。

概念全背，不要有侥幸心理

递归是一个过程或函数直接或间接调用自身的一种方法。

递归的方法只需少量的代码就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

当递归算法所涉及的数据定义形式是递归的情况下，通常可以将递归算法转化为递推算法，用递归的边界条件作为递推的边界条件。

汉诺塔

public class HanoiY { void Move(char chSour, char chDest) { System.out.println("Move the top plate of" + chSour + " to " + chDest); } void Hanoi(int n, char a, char b, char c) { if (n == 1) { Move(a, c); } else { Hanoi(n - 1, a, c, b); this.Move(a, c); Hanoi(n - 1, b, a, c); } } public static void main(String[] args) { int n = Integer.parseInt(args[0]); HanoiY hanoi = new HanoiY(); hanoi.Hanoi(n, 'a', 'b', 'c'); } }

递归的优点：结构清晰，可读性强，而且容易用数学归纳法证明算法的正确性。

递归的缺点：递归算法的运行效率低，耗费时间长，占用存储空间大。

递归算法是一种直接或者间接地调用自身算法的过程。

算法设计题

import java.util.Scanner; public class FinalSalary{ public static void main(String[] args){ Scanner input = new Scanner(System.in); System.out.print("请输入要求的哪一年工资："); int n = input.nextInt(); //方法一：递推（迭代） int salary = 1500; for(int i = 1 ; i < n ; i++){ salary *= 1.1; } System.out.println("第"+n+"年的工资为：" + salary); System.out.println("第"+n+"年的工资为："+ Salary(n)); } //方法二：递归 public static int Salary(int n){ if(n == 1){ return 1500; }else{ return (int)(Salary(n - 1) * 1.1); } } }

线性结构

算法设计题 将单循环列表转换为双向循环列表no

public static DLinkList(LinkList L) { DLinkList H; DLinkNode rear, s; LinkNode p; H = new DLinkList(); rear = H.Head; p = L.Head.next; while (p) { s = new LinkList(Null); s.data = p.data; s.next = rear.next; s.prior = rear; rear.next = s; H.Head.prior = s; rear = s; p = p.next; } return H; }

天命靡常，唯德是辅。

概念背诵

顺序存储优点：方法简单，各种高级语言中都有数组类型，容易实现，不用为表示节点间的逻辑关系而增加存储开销，逻辑相邻与物理相邻一直。顺序表具有按元素序号随机访问的特点。

链式存储的优点：在顺序表中做插入删除操作时，不需要多次移动元素，效率高。不需要预先分配足够大的存储空间，不会出现存储大量闲置或溢出。

非空的循环单链表head的尾节点满足 p.next==head

循环队列的优点：克服了假上溢现象，充分利用了向量空间(删除元素后的空间仍然可以利用，最大限度的利用空间)有效的利用了资源。

如何判断循环队列的空和满

方法之一是附设一个存储队中元素个数的变量，如num。num=0，对空，num=MAXSIZE，队满。

另一种方法是少用一个元素空间，(rear+1)%MAXSIZE==front。队满

树结构

丧家之犬，主公实不足虑也。

快把朕扶起来。 概念全部要背

二叉树的主要性质

一颗非空二叉树的第i层上最多有 2^i-1^ 个节点 一颗深度为k的二叉树中，最多具有2^k^-1个节点 对于一颗非空的二叉树，若叶子节点数为n~0~,度数为2的节点数为n~2~,则有n~0~=n~2~+1。

只有增添一些并不存在的空节点，使之成为一颗完全二叉树的形式，然后再顺序存储。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。