数据结构总结复习笔记

1、欢迎阅读第一章概论1 .数据：信息J勺载体，能被计算机识别、存储和加工处理。2 .数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3 .数据结构：数据之间的相互关系，即数据的组织形式。它包括：1)数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2)数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3)数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。4 .数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实 现。5 .数据类型：一个

2、值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6 .抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。7 .抽象数据类型 ADT :是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象(类的实例) 解决问题。8 .数据的逻辑结构，简称为数据结构，有：(1)线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。(2)非线性结构，一个结点可能有多个直接前趋和后继。i 产 J F 1 I, I /之7 I .9 .数据的存储结构有： '.I 一二一一I1)顺序存储，把逻辑相邻的结点存储

3、在物理上相邻的存储单元内。2)链接存储，结点间的逻辑关系由附加指针字段表示。3)索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4)散列存储，按结点的关键字直接计算出存储地址。10 .评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间(辅助存储空间)；易于理 解、编码、调试。11 .算法的时间复杂度 T(n):是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶0人2)、立方阶0人3)、k次方阶0(n")、指数阶0

4、(2、)。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 /返回线性表的大小，即数据元素的

5、个数。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相同的

6、元素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 s

7、ize; /线性表中数据元素的个数数据元素数组欢迎阅读private Object口 elements;/构造方法public ListArray (Strategy strategy)size = 0;elements = new ObjectLEN;/返回线性表的大小，即数据元素的个数 public int getSize() return size;/如果线性表为空返回true ,否则返回false 。public boolean isEmpty() return size=0;/判断线性表是否包含数据元素epublic boolean contains(Object e) for (i

8、nt i=0; i<size; i+)if (e = = elements。) 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>

9、i; j-)elementsj = elements1;elementsi = e;size+;欢迎阅读return;private void expandSpace()Object口 a = new Objectelements.length*2;for (int i=0; i<elements.length; i+)ai = elements。;elements = a;删除线性表中序号为i的元素，并返回之public Object remove(int i) throws OutOfBoundaryException if (i<0|i>=size)throw new

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

11、Exception("错误，指定的序号越界。");Object obj = elements。;elements。 = e;return obj;/返回线性表中序号为i的数据元素public Object get(int i) throws OutOfBoundaryException if (i<0|i>=size)throw new OutOfBoundaryException("错误，指定的序号越界。");欢迎阅读return elements。;/删除线性表中第一个与e相同的元素public boolean remove(Object

12、 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

13、;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 SL

14、Node 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的元素所在

15、结点的前驱结点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 ,否则返

16、回false 。public boolean isEmpty() return size=0;/判断线性表是否包含数据元素epublic 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&

17、gt;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("错误，

18、指定的删除序号越界。");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 ,返回原数

19、据元素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

20、 (i<0|i>=size)throw new OutOfBoundaryException("错误，指定的序号越界。")；SLNode p = getNode(i);return p.getData(); 7 .循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理 灵活方便。8 .空循环链表仅由一个自成循环的头结点表示。9 .很多时候表的操作是在表的首尾位置上进行， 此时头指针表示的单循环链表就显的不够方便， 改 用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；

21、用尾指针表示的单循环链表查找开始结点和尾结点的时间都是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

22、 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

23、 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是否合法，如合法转换为 DLNodeprotected DLNode checkPosition(Node p) throws InvalidNodeException if (p=nu

24、ll)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 boo

25、lean isEmpty() return size=0;/返回第一个结点public Node first() throws OutOfBoundaryExceptionif (isEmpty()throw new OutOfBoundaryException(" 错误：链接表为空。");return head.getNext();/返回最后一结点public Node last() throws OutOfBoundaryExceptionif (isEmpty()throw new OutOfBoundaryException(" 错误：链接表为空。&quo

26、t;);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 Invali

27、dNodeException, 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

28、);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 = checkP

29、osition(p);欢迎阅读Object obj = node.getData();node.getPre().setNext(node.getNext();node.getNext().setPre(node.getPre();size-;return obj;/删除首元素，并返回之public Object removeFirst() throws OutOfBoundaryExceptionreturn remove(head.getNext();/删除末元素，并返回之public Object removeLast() throws OutOfBoundaryException re

30、turn 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) ?基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺

31、序表作为存储结构 2) ?基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操 作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的 首尾时采用尾指针表示的单循环链表。12.存储密度=(结点数据本身所占的存储量)/ (整个结点结构所占的存储总量)存储密度：顺序表=1,链表1。欢迎阅读第？三州？维？和？队？歹4?1 .栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表( LIFO表)。插入、删除端称为栈顶， 另一端称栈底。表中无元素称空栈。2 .栈的基本运算有：1) ？initstack(s),构造一个空栈； I / _

32、.2) ？stackempty(s),判栈空；3) ？stackfull(s),判栈满；4) ？push(s,x),进栈;5) ？pop？(s),退栈;6) ？stacktop(s),取栈顶元素。3 .顺序栈：栈的顺序存储结构称顺序栈。4 .当栈满时，做进栈运算必定产生空间溢出，称土溢”。？当栈空时，做退栈运算必定产生空间溢出，称 下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。5 .在顺序栈上的基本运算：i 产 J F 1 I, I /之7 I .public interface Stack 返回堆栈的大小W jpublic int getSize();判断堆栈是否为空pub

33、lic 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; 栈顶指针pub

34、lic StackArray() top = -1;elements = new ObjectLEN;返回堆栈的大小public int getSize() return top+1;i . J F 1 I- I判断堆栈是否为空.I小二二一二public boolean isEmpty() i" .111return top<0;/数据元素e入栈public void push(Object e) if (getSize()>=elements.length)expandSpace();elements+top = e;欢迎阅读private void expandSpa

35、ce()Object a = new Objectelements.length*2;for (int i=0; i<elements.length; i+)ai = elementsi;elements = a;栈顶元素出栈public Object pop() throws StackEmptyException if (getSize()<1)throw new StackEmptyException("错误，堆栈为空。"工Object obj = elementstop;elementstop- = null;return obj;i产 J F 1 I,

36、 I J/, I .取栈顶元素 . I N 二二一 public Object peek() throws StackEmptyException if (getSize()<1)throw new StackEmptyException("错误，堆栈为空。 ");return elementstop;6 .链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。7 .链栈上的基本运算:欢迎阅读public class StackSLinked implements Stack private SLNode top;链表首结点引用private int size; 栈的

37、大小public StackSLinked() top = null;size = 0;返回堆栈的大小public int getSize() return size;判断堆栈是否为空public boolean isEmpty() return size=0;/数据元素e入栈 public void push(Object e) T i2 3；SLNode q = new SLNode(e,top);top = q;size+;栈顶元素出栈public Object pop() throws StackEmptyException if (size<1)欢迎阅读Object obj =

38、 top.getData();top = top.getNext();size-;return obj;取栈顶元素public Object peek() throws StackEmptyException I / _if (size<1)throw new StackEmptyException("错误，堆栈为空。"力.return top.getData();?8 .队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表,FIFO 表。9 .队列的基本运算：1) ?initqueue(q),置空队；.1* I I- I2

39、) ?queueempty(q),判队空；3) ?queuefull(q),判队酒； 、 C，、一4) ?enqueue(q,x),入队；I I5) ?dequeue(q),出队;6) ?queuefront(q),返回队头元素。10 .顺序队列：队列的顺序存储结构称顺序队列。设置 front和rear指针表示队头和队尾元素在向量空间的位置。11 .顺序队列中存在 假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队 尾指针超过向量空间的上界而不能入队。12 .为克服 假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。 i=(i+1)%q

40、ueuesize欢迎阅读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 dequ

41、eue() throws QueueEmptyException;i 产 J F 1 I, II .取队首元素 . 二二一public Object peek() throws QueueEmptyException;public class QueueArray implements Queue private static final int CAP = 7; 队列默认大小private Object口 elements;/ 数据元素数组private int capacity; 数组的大小 elements.lengthprivate int front;队首指针，指向队首private

42、 int rear;队尾指针，指向队尾后一个位置欢迎阅读public QueueArray() this(CAP);public QueueArray(int cap)capacity = cap + 1;elements = new Objectcapacity;front = rear = 0;返回队列的大小public int getSize() return (rear -front+ capacity)%capacity;判断队列是否为空public boolean isEmpty() return front=rear;X' 1) I"- "i产 J F

43、 1 I, I /u I数据元素e入队JIpublic void enqueue(Object e) if (getSize()=capacity-1) expandSpace();elementsrear = e;rear = (rear+1)%capacity;private void expandSpace()Object口 a = new Objectelements.length*2;欢迎阅读int i = front;int j = 0;while (i!=rear)将从front开始到rear前一个存储单元的元素复制到新数组aj+ = elements1;i = (i+1)%ca

44、pacity;elements = a;capacity = elements.length;front = 0;rear = j;设置新的队首、队尾指针队首元素出队public Object dequeue。throws QueueEmptyException if (isEmpty()/1) I- -i产 J F1 I,II .throw new QueueEmptyException(" 错误：队列为空 ");Object obj = elementsfront; . I二二一二elementsfront = null;y. /front = (front+1)%ca

45、pacity;return obj;取队首元素public Object peek() throws QueueEmptyException if (isEmpty()throw new QueueEmptyException("错误：队列为空");欢迎阅读return elementsfront;15 .链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。16 .链队列的基本运算：public class QueueSLinked implements Queue private SLNode front;private SLNode rear;p

46、rivate int size;public QueueSLinked() front = new SLNode();rear = front;size = 0;返回队列的大小/ 1) I -i产 J F 1 I, I I,public int getSize() return size;判断队列是否为空public boolean isEmpty() return size=0;/数据元素e入队 public void enqueue(Object e) 欢迎阅读SLNode p = new SLNode(e,null);rear.setNext(p);rear = p;size+;队首元素

47、出队public Object dequeue。throws QueueEmptyException if (size<1)throw new QueueEmptyException("错误：队列为空");SLNode p = front.getNext();front.setNext(p.getNext();size-;if (size<1) rear = front;如果队列为空,rear指向头结点return p.getData();i产 J F 1 I, I I.取队首元素 . I 、不，二二一1?public Object peek() throws

48、QueueEmptyException if (size<1)throw new QueueEmptyException("错误：队列为空");return front.getNext().getData();第？四州？?串欢迎阅读1 .串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；2 .空串：长度为零的串称空串；？?行白串：由一个或多个空格组成的串称空白串；子串：串中任意个连续字符组成的子序列称该串的子串；？?在串：包含子串的串称主串;子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；3 .空串是任意串的子串；？肛意串是自身的子串；串常量

49、在程序中只能引用但不能改变其值；？串变量取值可以改变；4 .串的基本运算1) ?int?strlen(char?*s);求串长。2) ?char?*strcpy(char?*?to,char?*?from);串复制。3) ?char?*strcat(char?*?to,char?*?from);串联接。4) ?int?strcmp(char?*s1,char?*s2);串比较。5) ?char?*strchr(char?*s,char?c);字符定位。5 .串的存储结构：(1)串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：i产 J F 1 I, I /之7 I .1) ?静态存储

50、分配的顺序串：直接用定长的字符数组定义，以“0”表示串值终结。#de巾ne?maxstrsize?256 typedef?char?seqstringmaxstrsize;seqstring?s;不设终结符，用串长表示。Typedef?struct?Char?chmaxstrsize;?Int?length;欢迎阅读seqstring;以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。2) ?动态存储分配的顺序串：简单定义：typedef?char?*?string;复杂定义：typedef?struct?char?*ch;?int?length;?hstring;(2)串的链

51、式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedef?struct?node?char?data;?struct?node?*next;linkstrnode;typedef?linkstrnode?*linkstring;linkstring?s;i. J j I, I将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义: . I一二一二 7#define?nodesize?80typedef?struct?node?char?datanodesize;?struct?node?*?next;linkstrnode;6 .串运算的实现(1)顺序串

52、上的子串定位运算。1)子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。欢迎阅读2)朴素的串匹配算法。时间复杂度为0人2)。比较的字符总次数为(n-m+1) m。Int?naivestrmatch(seqstring?t,seqstring?p)?int?i,j,k;?int?m=p.length;?int?n=t.length;?for(i=0;i<=n-m;i+)?j=0;k=i;?while(j<m&&t.chk=p.chj)?j+;k+;?if?(j=m)?return?i;?return? T;. 1* I I; I(2)链串上的子串定位运

53、算。时间复杂度为 O(nA2)。比较的字符总次数为(n-m+1) m。 . I二二Linkstrnode?*?lilnkstrmatch(linkstring?T,?linkstring?P)1" -.i '?linkstrnode?*shift,?*t,?*p;?shift=T;?t=shift;p=P;?while(t&&p)?if(t->data=p->data) t=t->next;欢迎阅读?p=p->next;?else?shift=shift->next;?t=shift;?p=P;?if(p=NULL)?return

54、?shi化?else?return?NULL;?第？五年？?修 W ?数？组讲口 ？广？义?表i 产 J F 1 I, II1 .多维数组：一般用顺序存储的方式表示数组。2 .常用方式有：1)行优先顺序，将数组元素按行向量排列；2)列优先顺序，将数组元素按列向量排列。3 .计算地址的函数：LOC(Aij尸LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d4 .矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。(1) ?对称矩阵：在一个 n阶的方阵A中，元素满足 Aij=Aji?0<=i,j<=n-1;称为对称矩阵。元素的总数为：n(n+1)/2;设：I=i或j中大的一个数；J=i或j中小的一个数； 则