数据结构-用C语言描述耿国华版总结笔记（上篇）

数据结构-----用C语言描述
两年前的考研笔记了，再回首，不忍唏嘘，时间过得真快。

下篇：https://blog.csdn.net/weixin_38244174/article/details/90707831

第一章绪论
（1）数据结构：相互之间存在一种或多种特定关系的数据元素集合。
（2）数据元素之间的相互关系：数据逻辑结构（集合结构：同属一集合、无关、线性结构：一对一、树状结构：一对多、网状结构：多对多）、存储结构（顺序映像、非顺序映像）、运算结构（增删改等）。
（3）抽象数据类型：定义一个数据对象、各元素之间的结构关系以及处理数据的操作。其重要特点是数据抽象（抽象反映问题的本质点）和信息隐藏（对用户隐藏数据存储和操作的实现细节）。
（4）结构化程序设计：
程序=算法+数据结构
4.1.目的:以程序的良好静态结构保证程序动态执行的正确性。
4.2构成单元：顺序结构、选择结构、重复结构。
4.3设计方法：1.自顶向下、逐步求精；2.独立功能，一个入口，一个出口的模块化结构；3.仅用三个基本控制结构的设计原则。
（5）面向对象程序设计：
面向对象=对象+类+继承+通信；其特点是：封装继承多态。与前者面向过程的开发方法相比，面向对象着眼于问题涉及对象，包括对象、对象属性以及操作，具有更高可靠性、可修改性、可复用性、可理解性等等。
（6）算法：
6.1算法的特性：1.有限性（无无穷循环）；2.确定性（无二义性）；3.可行性（可精确运行）；4.输入（0个或者多个）；5.1个或者多个输出。
6.2算法设计的要求：1.算法正确性；2.算法可读性；3.算法健壮性；4.高效率与低存储。
6.3时间复杂度：随着问题规模的扩大，算法执行时间的增长率与f(n)的增长率相同。

第二章线性表
1.顺序存储与链式存储的优缺点：
（1）基于空间上：顺序存储静态分配空间，链式存储动态分配空间；存储密度上：顺序存储等于1，链式存储小于1.
（2）基于时间上：顺序表可随机存取，也可顺序，而线性表只能顺序存取；插入时，顺序表平均需要移动近一半元素，而链表不需要移动元素，只需要修改相关指针域即可。
2.线性表顺序存储结构的基本操作：查找、删除、插入等。线性表链式存储结构的基本操作：头插法、尾插法、插入、查找、删除等。此外还有循环链表和双向链表。
可参考我之前的帖子看具体实现：
https://blog.csdn.net/weixin_38244174/article/details/88552709
3.链表List：（选读）
（1）在 List 中，用户可以精确控制列表中每个元素的插入位置，另外用户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。
（2）List的常见实现类：
ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。（ArrayList 实现了RandomAccess 接口，支持快速随机访问。实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。和 Vector 不同，ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList。
参考：https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/ArrayList.md）
查看源码：学习如何使用System.arraycopy进行数组赋值；学习使用移位运算符实现扩容机制；length属性是针对数组；length()方法是针对字符串String说的size()方法是针对泛型集合说的;

package list;
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListDemo {public static void main(String[] srgs){ArrayList<Integer> arrayList = new ArrayList<Integer>();System.out.printf("Before add:arrayList.size() = %d\n",arrayList.size());arrayList.add(1);arrayList.add(3);arrayList.add(5);arrayList.add(7);arrayList.add(9);System.out.printf("After add:arrayList.size() = %d\n",arrayList.size());System.out.println("Printing elements of arrayList");// 三种遍历方式打印元素// 第一种：通过迭代器遍历System.out.print("通过迭代器遍历:");Iterator<Integer> it = arrayList.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();// 第二种：通过索引值遍历System.out.print("通过索引值遍历:");for(int i = 0; i < arrayList.size(); i++){System.out.print(arrayList.get(i) + " ");}System.out.println();// 第三种：for循环遍历System.out.print("for循环遍历:");for(Integer number : arrayList){System.out.print(number + " ");}// toArray用法// 第一种方式(最常用)Integer[] integer = arrayList.toArray(new Integer[0]);// 第二种方式(容易理解)Integer[] integer1 = new Integer[arrayList.size()];arrayList.toArray(integer1);// 抛出异常，java不支持向下转型//Integer[] integer2 = new Integer[arrayList.size()];//integer2 = arrayList.toArray();System.out.println();// 在指定位置添加元素arrayList.add(2,2);// 删除指定位置上的元素arrayList.remove(2);    // 删除指定元素arrayList.remove((Object)3);// 判断arrayList是否包含5System.out.println("ArrayList contains 5 is: " + arrayList.contains(5));// 清空ArrayListarrayList.clear();// 判断ArrayList是否为空System.out.println("ArrayList is empty: " + arrayList.isEmpty());}
}

LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。LinkedList不是线程安全的。

参考帖子：https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/LinkedList.md

package list;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListDemo {public static void main(String[] srgs) {//创建存放int类型的linkedListLinkedList<Integer> linkedList = new LinkedList<>();/************************** linkedList的基本操作 ************************/linkedList.addFirst(0); // 添加元素到列表开头linkedList.add(1); // 在列表结尾添加元素linkedList.add(2, 2); // 在指定位置添加元素linkedList.addLast(3); // 添加元素到列表结尾   System.out.println("LinkedList（直接输出的）: " + linkedList);System.out.println("getFirst()获得第一个元素: " + linkedList.getFirst()); // 返回此列表的第一个元素System.out.println("getLast()获得第最后一个元素: " + linkedList.getLast()); // 返回此列表的最后一个元素System.out.println("removeFirst()删除第一个元素并返回: " + linkedList.removeFirst()); // 移除并返回此列表的第一个元素System.out.println("removeLast()删除最后一个元素并返回: " + linkedList.removeLast()); // 移除并返回此列表的最后一个元素System.out.println("After remove:" + linkedList);System.out.println("contains()方法判断列表是否包含1这个元素:" + linkedList.contains(1)); // 判断此列表包含指定元素，如果是，则返回trueSystem.out.println("该linkedList的大小 : " + linkedList.size()); // 返回此列表的元素个数/************************** 位置访问操作 ************************/System.out.println("-----------------------------------------");linkedList.set(1, 3); // 将此列表中指定位置的元素替换为指定的元素System.out.println("After set(1, 3):" + linkedList);System.out.println("get(1)获得指定位置（这里为1）的元素: " + linkedList.get(1)); // 返回此列表中指定位置处的元素/************************** Search操作 ************************/System.out.println("-----------------------------------------");linkedList.add(3);System.out.println("indexOf(3): " + linkedList.indexOf(3)); // 返回此列表中首次出现的指定元素的索引System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));// 返回此列表中最后出现的指定元素的索引/************************** Queue操作 ************************/System.out.println("-----------------------------------------");System.out.println("peek(): " + linkedList.peek()); // 获取但不移除此列表的头System.out.println("element(): " + linkedList.element()); // 获取但不移除此列表的头linkedList.poll(); // 获取并移除此列表的头System.out.println("After poll():" + linkedList);linkedList.remove();System.out.println("After remove():" + linkedList); // 获取并移除此列表的头linkedList.offer(4);System.out.println("After offer(4):" + linkedList); // 将指定元素添加到此列表的末尾/************************** Deque操作 ************************/System.out.println("-----------------------------------------");linkedList.offerFirst(2); // 在此列表的开头插入指定的元素System.out.println("After offerFirst(2):" + linkedList);linkedList.offerLast(5); // 在此列表末尾插入指定的元素System.out.println("After offerLast(5):" + linkedList);System.out.println("peekFirst(): " + linkedList.peekFirst()); // 获取但不移除此列表的第一个元素System.out.println("peekLast(): " + linkedList.peekLast()); // 获取但不移除此列表的第一个元素linkedList.pollFirst(); // 获取并移除此列表的第一个元素System.out.println("After pollFirst():" + linkedList);linkedList.pollLast(); // 获取并移除此列表的最后一个元素System.out.println("After pollLast():" + linkedList);linkedList.push(2); // 将元素推入此列表所表示的堆栈（插入到列表的头）System.out.println("After push(2):" + linkedList);linkedList.pop(); // 从此列表所表示的堆栈处弹出一个元素（获取并移除列表第一个元素）System.out.println("After pop():" + linkedList);linkedList.add(3);linkedList.removeFirstOccurrence(3); // 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表）System.out.println("After removeFirstOccurrence(3):" + linkedList);linkedList.removeLastOccurrence(3); // 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表）System.out.println("After removeFirstOccurrence(3):" + linkedList);/************************** 遍历操作 ************************/System.out.println("-----------------------------------------");linkedList.clear();for (int i = 0; i < 100000; i++) {linkedList.add(i);}// 迭代器遍历long start = System.currentTimeMillis();Iterator<Integer> iterator = linkedList.iterator();while (iterator.hasNext()) {iterator.next();}long end = System.currentTimeMillis();System.out.println("Iterator：" + (end - start) + " ms");// 顺序遍历(随机遍历)start = System.currentTimeMillis();for (int i = 0; i < linkedList.size(); i++) {linkedList.get(i);}end = System.currentTimeMillis();System.out.println("for：" + (end - start) + " ms");// 另一种for循环遍历start = System.currentTimeMillis();for (Integer i : linkedList) ;end = System.currentTimeMillis();System.out.println("for2：" + (end - start) + " ms");// 通过pollFirst()或pollLast()来遍历LinkedListLinkedList<Integer> temp1 = new LinkedList<>();temp1.addAll(linkedList);start = System.currentTimeMillis();while (temp1.size() != 0) {temp1.pollFirst();}end = System.currentTimeMillis();System.out.println("pollFirst()或pollLast()：" + (end - start) + " ms");// 通过removeFirst()或removeLast()来遍历LinkedListLinkedList<Integer> temp2 = new LinkedList<>();temp2.addAll(linkedList);start = System.currentTimeMillis();while (temp2.size() != 0) {temp2.removeFirst();}end = System.currentTimeMillis();System.out.println("removeFirst()或removeLast()：" + (end - start) + " ms");}
}

Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。
4.集合Set：（选读）
（1）Set 继承于 Collection 接口，是一个不允许出现重复元素，并且无序的集合，主要 HashSet 和 TreeSet 两大实现类。在判断重复元素的时候，Set 集合会调用 hashCode()和 equal()方法来实现。
（2）无序/有序集合：
有序集合：集合里的元素可以根据 key 或 index 访问 (List、Map)
无序集合：集合里的元素只能遍历。（Set）
（3）HashSet 和 TreeSet 底层数据结构
HashSet 是哈希表结构，主要利用 HashMap 的 key 来存储元素，当有元素插入的时候，会计算元素的hashCode值，将元素插入到哈希表对应的位置中来；TreeSet 是红黑树（特殊的二叉查找树）结构，每一个元素都是树中的一个结点，插入的元素都会进行排序；
（4）HashTable、HashSet、HashMap的区别。
参考链接：剑指Offer（上篇）帖子

第三章栈与队列
1.栈的定义：
只允许在栈顶进行插入、删除的限定线性表。具有后进先出的特点。
2.栈与递归：
（1）递归：定义自身同时又对自身进行调用；
（2）优点：结构清晰，将复杂问题分而治之、简单求解；缺点：时空效率低，无法得到中间过程。
（3）适用问题：
原问题可层层分解为类似子问题，子问题的规模更小；最小问题有解。
（4）递归过程的实现：
递归进层（i->i+1）三件事：
1.保留本层参数与返回地址；2.为被调用函数的局部变量分配存储区，给下层参数赋值；3.将程序转移到被调函数的入口。
递归退层三件事：
1.保存被调函数的计算结果；2.释放被调函数的数据区，恢复上层函数；3.依照被调函数保存的返回地址，将控制转移回调用函数。
（5）举例：n的阶乘的递归写法。

每调用一个函数时，就会为栈顶分配一个存储区；而每当从一个函数退出时，就会释放存储区。为保证递归函数正确进行，系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区；每层递归所需信息构成一个工作记录，其中包括所有的实参、局部变量以及上一层的返回地址。每进一层，产生新的工作记录进入栈顶；每退层一次，弹出一个工作记录，递归工作栈是由JVM管理的。
3.队列
尾部添加，头部删除的限定性的线性表。满足先进先出的特性。
（1）队列的种类：
单队列：初始化队列；rear=front = 0;入队时，直接将新元素送到尾指针rear所指的单元，尾指针+1；出队时，取出头指针front所指的元素，然后头指针+1，真正的队满条件时：rear-front == MAXSIZE；可能存在假溢出问题：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。将存储队列的数组头尾相接，形成循环队列。参考链接：https://blog.csdn.net/will130/article/details/49306523

循环队列：规定最后一个单元的后继是第一个单元，非空循环队列中，队头指针始终指向对头元素，而队尾指针始终指向真正元素后面的单元。凭借front==rear无法判断队列是空是满，损失一个元素空间的方法，当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远也追不上队头指针，所以队满条件为(rear+1)%size==front,队空仍然为front==rear。
（2）Java 集合框架中的队列 Queue
Java 集合中的 Queue 继承自 Collection 接口，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。Queue 还添加了额外的添加、删除、查询操作。1.add(E), offer(E) 在尾部添加；2.remove(), poll() 删除并返回头部；3.element(), peek() 获取但不删除。链接：https://blog.csdn.net/u011240877/article/details/52860924

第四章串
1.串基础概念：
串是特殊的线性表，其特殊性是组成串的元素是字符。理解子串、子串在主串中的位置；以及串相等的概念。
2.串的简单模式匹配（布鲁特-福斯）算法：
算法思想：从主串的第一个位置和模式串的第一个字符开始比较，如果相等，则继续逐一比较后续字符；否则从主串的第二个字符开始，再重新用上一步的方法与模式串中的字符作比较，以此类推，直到比较完模式串中的所有字符。若匹配成功则返回模式串在主串中的位置，若匹配不成功，则返回一个可区别于主串所有位置的标记，如”0”。设立三个指示器即可。O(m*n)算法复杂度。
3.KMP模式匹配算法
链接：https://blog.csdn.net/v_july_v/article/details/7041827
4.String、StingBuilder、StringBuffer。
链接：https://blog.csdn.net/weixin_41101173/article/details/79677982
（1）不同之处
String：不可变字符串；
StringBuffer：可变字符串、效率低、线程安全；
StringBuilder：可变字符序列、效率高、线程不安全；
小结：
如果要操作少量的数据用 String；多线程操作字符串缓冲区下操作大量数据 StringBuffer；单线程操作字符串缓冲区下操作大量数据 StringBuilder（推荐使用）。
（2）为什么不能用字符串拼接

String s = "hello" 会在常量池开辟一个内存空间来存储”hello"。
s += "world"会先在常量池开辟一个内存空间来存储“world"。然后再开辟一个内存空间来存储”helloworld“。
这么一来，001与002就成为了垃圾内存空间了。这么简单的一个操作就产生了两个垃圾内存空间，如果有大量的字符串拼接，将会造成极大的浪费。
（3）三者的转换。
String转StringBuilder或Stringbuffer：
StringBuilder sb = new StringBuilder(s);
StringBuffer sb = new StringBuilder(s);
StringBuilder或Stringbuffer转String：
String s1 = sb.toString();

第五章数组和广义表
1.数组的定义（一般线性表的补充，一维、二维数组）、基本运算（获取特定位置、修改特定位置）、以及存储方式（按行或按列存储）；
2.多维数组中某元素地址的计算公式：包括一维数组、二维数组、三维数组、三角矩阵、带状矩阵等。参考：https://wenku.baidu.com/view/c980954de45c3b3567ec8bf3.html
3.特殊矩阵：定义：元素分布有个特殊规律的矩阵，譬如三角矩阵、带状矩阵等（非零元素按行存储）；非零元素很少的矩阵。譬如稀疏矩阵（三元组表表示法：非零元素所在行、非零元素所在列以及非零元素的值）
4.广义表：
4.1特点：1.广义表的元素可以是子表，可能有着多重结构；2.广义表可能为其他广义表所共享，通过子表名称即可引用该表；3.广义表具有递归性。
4.2概念：表头：广义表的第一个元素（head操作为取表头）；表尾：除了第一个元素外，其他元素所构成的广义表。（tail操作为去表头）存储方式为：头尾链表存储结构和同层结点链存储结构。