数据结构总结复习笔记.doc

欢迎阅读
第一章 概 论
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≤n
5.顺序表上的基本运算
public interface List {
//返回线性表的大小，即数据元素的个数。
public int getSize();
//如果线性表为空返回 true，否则返回 false。
public boolean isEmpty();
//判断线性表是否包含数据元素 e
public 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;
}
//判断线性表是否包含数据元素 e
public 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;
}
//返回线性表的大小，即数据元素的个数。
public int getSize() {
return size;
}
//如果线性表为空返回 true，否则返回 false。
public boolean isEmpty() {
return size==0;
}
//判断线性表是否包含数据元素 e
public boolean contains(Object e) {
SLNode p = head.getNext();
while (p!=null){
if (p.getData()==e)) return true;
else p = p.getNext();
} return false;
}
//将数据元素 e 插入到线性表中 i 号位置
public void insert(int i, Object e) throws OutOfBoundaryException {
if (i<0||i>size)
throw new OutOfBoundaryException("错误，指定的插入序号越界。");
SLNode p = getPreNode(i);
SLNode q = new SLNode(e,p.getNext());
p.setNext(q);
size++;
return;
}
//删除线性表中序号为 i 的元素,并返回之
public Object remove(int i) throws OutOfBoundaryException {
if (i<0||i>=size)
throw new OutOfBoundaryException("错误，指定的删除序号越界。");
SLNode p = getPreNode(i);
Object obj = p.getNext().getData();
p.setNext(p.getNext().getNext());
size--;
return obj;
}
//删除线性表中第一个与 e 相同的元素
public boolean remove(Object e) {
SLNode p = getPreNode(e);
if (p!=null){
p.setNext(p.getNext().getNext());
size--;
return true;
}
return false;
}
//替换线性表中序号为 i 的数据元素为 e，返回原数据元素
public Object replace(int i, Object e) throws OutOfBoundaryException {
if (i<0||i>=size)
throw new OutOfBoundaryException("错误，指定的序号越界。");
SLNode p = getNode(i);
Object obj = p.getData();
p.setData(e);
return obj;
}
//返回线性表中序号为 i 的数据元素
public Object get(int i) throws OutOfBoundaryException {
if (i<0||i>=size)
throw new OutOfBoundaryException("错误，指定的序号越界。");
SLNode p = getNode(i);
return p.getData();
}
}
7.循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。
8.空循环链表仅由一个自成循环的头结点表示。
9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。
10.在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。
public class DLNode implements Node {
private Object element;
private DLNode pre;
private DLNode next;
public DLNode(Object ele, DLNode pre, DLNode next){
this.element = ele;
this.pre = pre;
this.next = next;
}
public DLNode getNext(){
return next;
}
public void setNext(DLNode next){
this.next = next;
}
public DLNode getPre(){
return pre;
}
public void setPre(DLNode pre){
this.pre = pre;
}
public Object getData() {
return element;
}
public void setData(Object obj) {
element = obj;
}
}
public class LinkedListDLNode implements LinkedList {
private int size; //规模
private DLNode head;//头结点,哑元结点
private DLNode tail;//尾结点,哑元结点
public LinkedListDLNode() {
size = 0;
head = new DLNode();//构建只有头尾结点的链表
tail = new DLNode();
head.setNext(tail);
tail.setPre(head);
}
//辅助方法，判断结点 p 是否合法，如合法转换为 DLNode
protected DLNode checkPosition(Node p) throws InvalidNodeException {
if (p==null)
throw new InvalidNodeException("错误：p 为空。");
if (p==head)
throw new InvalidNodeException("错误：p 指向头节点，非法。");
if (p==tail)
throw new InvalidNodeException("错误：p 指向尾结点，非法。");
DLNode node = (DLNode)p;
return node;
}
//查询链接表当前的规模
public int getSize() {
return size;
}
//判断链接表是否为空
public boolean isEmpty() {
return size==0;
}
//返回第一个结点
public Node first() throws OutOfBoundaryException{
if (isEmpty())
throw new OutOfBoundaryException("错误：链接表为空。");
return head.getNext();
}
//返回最后一结点
public Node last() throws OutOfBoundaryException{
if (isEmpty())
throw new OutOfBoundaryException("错误：链接表为空。");
return tail.getPre();
}
//返回 p 之后的结点
public Node getNext(Node p)throws InvalidNodeException,OutOfBoundaryException {
DLNode node = checkPosition(p);
node = node.getNext();
if (node==tail)
throw new OutOfBoundaryException("错误：已经是链接表尾端。");
return node;
}
//返回 p 之前的结点
public Node getPre(Node p) throws InvalidNodeException, OutOfBoundaryException {
DLNode node = checkPosition(p);
node = node.getPre();
if (node==head)
throw new OutOfBoundaryException("错误：已经是链接表前端。");
return node;
}
//将 e 作为第一个元素插入链接表
public Node insertFirst(Object e) {
DLNode node = new DLNode(e,head,head.getNext());
head.getNext().setPre(node);
head.setNext(node);
size++;
return node;
}
//将 e 作为最后一个元素插入列表,并返回 e 所在结点
public Node insertLast(Object e) {
DLNode node = new DLNode(e,tail.getPre(),tail);
tail.getPre().setNext(node);
tail.setPre(node);
size++;
return node;
}
//删除给定位置处的元素，并返回之
public Object remove(Node p) throws InvalidNodeException {
DLNode node = checkPosition(p);
Object obj = node.getData();
node.getPre().setNext(node.getNext());
node.getNext().setPre(node.getPre());
size--;
return obj;
}
//删除首元素，并返回之
public Object removeFirst() throws OutOfBoundaryException{
return remove(head.getNext());
}
//删除末元素，并返回之
public Object removeLast() throws OutOfBoundaryException{
return remove(tail.getPre());
}
//将处于给定位置的元素替换为新元素，并返回被替换的元素
public Object replace(Node p, Object e) throws InvalidNodeException {
DLNode node = checkPosition(p);
Object obj = node.getData();
node.setData(e);
return obj;
}
}
11.顺序表和链表的比较
1）?基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。
2）?基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。
12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）
存储密度：顺序表=1，链表<1。

第?三?章???栈?和?队?列
??
1.栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。
2.栈的基本运算有：
1）?initstack(s),构造一个空栈；
2）?stackempty(s),判栈空；
3）?stackfull(s),判栈满；
4）?push(s,x),进栈；
5）?pop?(s),退栈；
6）?stacktop(s)，取栈顶元素。
3.顺序栈：栈的顺序存储结构称顺序栈。
4.当栈满时，做进栈运算必定产生空间溢出，称“上溢”。?当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。
5.在顺序栈上的基本运算：
public interface Stack {
//返回堆栈的大小
public int getSize();
//判断堆栈是否为空
public boolean isEmpty();
//数据元素 e 入栈
public void push(Object e);
//栈顶元素出栈
public Object pop() throws StackEmptyException;
//取栈顶元素
public Object peek() throws StackEmptyException;
}
public class StackArray implements Stack {
private final int LEN = 8; //数组的默认大小
private Object[] elements; //数据元素数组
private int top; //栈顶指针
public StackArray() {
top = -1;
elements = new Object[LEN];
}
//返回堆栈的大小
public int getSize() {
return top+1;
}
//判断堆栈是否为空
public boolean isEmpty() {
return top<0;
}
//数据元素 e 入栈
public void push(Object e) {
if (getSize()>=elements.length)
expandSpace();
elements[++top] = e;
}
private void expandSpace(){
Object[] a = new Object[elements.length*2];
for (int i=0; i<elements.length; i++)
a[i] = elements[i];
elements = a;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (getSize()<1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = elements[top];
elements[top--] = null;
return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (getSize()<1)
throw new StackEmptyException("错误，堆栈为空。");
return elements[top];
}
}
6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。
7.链栈上的基本运算：
public class StackSLinked implements Stack {
private SLNode top; //链表首结点引用
private int size; //栈的大小
public StackSLinked() {
top = null;
size = 0;
}
//返回堆栈的大小
public int getSize() {
return size;
}
//判断堆栈是否为空
public boolean isEmpty() {
return size==0;
}
//数据元素 e 入栈
public void push(Object e) {
SLNode q = new SLNode(e,top);
top = q;
size++;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (size<1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = top.getData();
top = top.getNext();
size--;
return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (size<1)
throw new StackEmptyException("错误，堆栈为空。");
return top.getData();
}
}?
8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。
9.队列的基本运算：
1）?initqueue(q),置空队；
2）?queueempty(q),判队空；
3）?queuefull(q),判队满；
4）?enqueue(q,x),入队；
5）?dequeue(q),出队；
6）?queuefront(q),返回队头元素。
10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。
11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。
12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize
13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。
解决的方法有：
1）?另设一个布尔变量以区别队列的空和满；
2）?少用一个元素，在入队前测试rear在循环意义下加1是否等于front；
3）?使用一个记数器记录元素总数。
14.循环队列的基本运算：
public interface Queue {
//返回队列的大小
public int getSize();
//判断队列是否为空
public boolean isEmpty();
//数据元素 e 入队
public void enqueue(Object e);
//队首元素出队
public Object dequeue() throws QueueEmptyException;
//取队首元素
public Object peek() throws QueueEmptyException;
}
public class QueueArray implements Queue {
private static final int CAP = 7;//队列默认大小
private Object[] elements; //数据元素数组
private int capacity; //数组的大小 elements.length
private int front; //队首指针,指向队首
private int rear; //队尾指针,指向队尾后一个位置
public QueueArray() {
this(CAP);
}
public QueueArray(int cap){
capacity = cap + 1;
elements = new Object[capacity];
front = rear = 0;
}
//返回队列的大小
public int getSize() {
return (rear -front+ capacity)%capacity;
}
//判断队列是否为空
public boolean isEmpty() {
return front==rear;
}
//数据元素 e 入队
public void enqueue(Object e) {
if (getSize()==capacity-1) expandSpace();
elements[rear] = e;
rear = (rear+1)%capacity;
}
private void expandSpace(){
Object[] a = new Object[elements.length*2];
int i = front;
int j = 0;
while (i!=rear){
//将从 front 开始到 rear 前一个存储单元的元素复制到新数组
a[j++] = elements[i];
i = (i+1)%capacity;
}
elements = a;
capacity = elements.length;
front = 0;