当前位置:文档之家› 数据结构复习笔记

数据结构复习笔记

第一章概论1.数据:信息的载体,能被计算机识别、存储和加工处理。

2.数据元素:数据的基本单位,可由若干个数据项组成,数据项是具有独立含义的最小标识单位。

3.数据结构:数据之间的相互关系,即数据的组织形式。

它包括:1)数据的逻辑结构,从逻辑关系上描述数据,与数据存储无关,独立于计算机;2)数据的存储结构,是逻辑结构用计算机语言的实现,依赖于计算机语言。

3)数据的运算,定义在逻辑结构上,每种逻辑结构都有一个运算集合。

常用的运算:检索/插入/删除/更新/排序。

4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的存储结构是逻辑结构用计算机语言的实现。

5.数据类型:一个值的集合及在值上定义的一组操作的总称。

分为:原子类型和结构类型。

6.抽象数据类型:抽象数据的组织和与之相关的操作。

优点:将数据和操作封装在一起实现了信息隐藏。

7. 抽象数据类型ADT:是在概念层上描述问题;类:是在实现层上描述问题;在应用层上操作对象(类的实例)解决问题。

8.数据的逻辑结构,简称为数据结构,有:(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。

(2)非线性结构,一个结点可能有多个直接前趋和后继。

9.数据的存储结构有:1)顺序存储,把逻辑相邻的结点存储在物理上相邻的存储单元内。

2)链接存储,结点间的逻辑关系由附加指针字段表示。

3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。

4)散列存储,按结点的关键字直接计算出存储地址。

10.评价算法的好坏是:算法是正确的;执行算法所耗的时间;执行算法的存储空间(辅助存储空间);易于理解、编码、调试。

11.算法的时间复杂度T(n):是该算法的时间耗费,是求解问题规模n的函数。

记为O(n)。

时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

13.算法的空间复杂度S(n):是该算法的空间耗费,是求解问题规模n的函数。

12.算法衡量:是用时间复杂度和空间复杂度来衡量的,它们合称算法的复杂度。

13. 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。

第二章线性表1.线性表:是由n(n≥0)个数据元素组成的有限序列。

3.顺序表:把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。

4.顺序表结点的存储地址计算公式:Loc(ai)=Loc(a1)+(i-1)*C;1≤i≤n5.顺序表上的基本运算public interface List {//返回线性表的大小,即数据元素的个数。

public int getSize();//如果线性表为空返回 true,否则返回 false。

public boolean isEmpty();//判断线性表是否包含数据元素 epublic boolean contains(Object e);//将数据元素 e 插入到线性表中 i 号位置public void insert(int i, Object e) throws OutOfBoundaryException;//删除线性表中序号为 i 的元素,并返回之public Object remove(int i) throws OutOfBoundaryException;//删除线性表中第一个与 e 相同的元素public boolean remove(Object e);//返回线性表中序号为 i 的数据元素public Object get(int i) throws OutOfBoundaryException;}在顺序表上插入要移动表的n/2结点,算法的平均时间复杂度为O(n)。

在顺序表上删除要移动表的(n+1)/2结点,算法的平均时间复杂度为O(n)。

public class ListArray implements List {private final int LEN = 8; //数组的默认大小private Strategy strategy; //数据元素比较策略private int size; //线性表中数据元素的个数private Object[] elements; //数据元素数组//构造方法public ListArray (Strategy strategy){size = 0;elements = new Object[LEN];}//返回线性表的大小,即数据元素的个数。

public int getSize() {return size;}//如果线性表为空返回 true,否则返回 false。

public boolean isEmpty() {return size==0;}//判断线性表是否包含数据元素 epublic boolean contains(Object e) {for (int i=0; i<size; i++)if ( e = = elements[i]) return true;return false;}//将数据元素 e 插入到线性表中 i 号位置public void insert(int i, Object e) throws OutOfBoundaryException {if (i<0||i>size)throw new OutOfBoundaryException("错误,指定的插入序号越界。

");if (size >= elements.length)expandSpace();for (int j=size; j>i; j--)elements[j] = elements[j-1];elements[i] = e;size++;return;}private void expandSpace(){Object[] a = new Object[elements.length*2];for (int i=0; i<elements.length; i++)a[i] = elements[i];elements = a;}//删除线性表中序号为 i 的元素,并返回之public Object remove(int i) throws OutOfBoundaryException {if (i<0||i>=size)throw new OutOfBoundaryException("错误,指定的删除序号越界。

");Object obj = elements[i];for (int j=i; j<size-1; j++)elements[j] = elements[j+1];elements[--size] = null;return obj;}//替换线性表中序号为 i 的数据元素为 e,返回原数据元素public Object replace(int i, Object e) throws OutOfBoundaryException {if (i<0||i>=size)throw new OutOfBoundaryException("错误,指定的序号越界。

");Object obj = elements[i];elements[i] = e;return obj;}//返回线性表中序号为 i 的数据元素public Object get(int i) throws OutOfBoundaryException {if (i<0||i>=size)throw new OutOfBoundaryException("错误,指定的序号越界。

");return elements[i];}//删除线性表中第一个与 e 相同的元素public boolean remove(Object e) {int i = indexOf(e);if (i<0) return false;remove(i);return true;}}6.单链表:只有一个链域的链表称单链表。

在结点中存储结点值和结点的后继结点的地址,data next data是数据域,next是指针域。

(1)建立单链表。

时间复杂度为O(n)。

加头结点的优点:1)链表第一个位置的操作无需特殊处理;2)将空表和非空表的处理统一。

(2)查找运算。

时间复杂度为O(n)。

public class SLNode implements Node {private Object element;private SLNode next;public SLNode(Object ele, SLNode next){this.element = ele;this.next = next;}public SLNode getNext(){return next;}public void setNext(SLNode next){this.next = next;}public Object getData() {return element;}public void setData(Object obj) {element = obj;}}public class ListSLinked implements List { private SLNode head; //单链表首结点引用private int size; //线性表中数据元素的个数public ListSLinked () {head = new SLNode();size = 0;}//辅助方法:获取数据元素 e 所在结点的前驱结点private SLNode getPreNode(Object e){SLNode p = head;while (p.getNext()!=null)if (p.getNext().getData()==e)return p;else p = p.getNext();return null;}//辅助方法:获取序号为 0<=i<size 的元素所在结点的前驱结点private SLNode getPreNode(int i){SLNode p = head;for (; i>0; i--)p = p.getNext();return p;}//获取序号为 0<=i<size 的元素所在结点private SLNode getNode(int i){SLNode p = head.getNext();for (; i>0; i--)p = p.getNext();return p;}//返回线性表的大小,即数据元素的个数。

相关主题