郝斌《数据结构》笔记

该笔记与视频课程相同

用者自取，自由分享

《数据结构》书目：严蔚敏 吴伟民（伪算法）高一凡（程序实现）***黄国瑜（程序是错的）数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能而执行的相应操作（比附查找，删除，排序元素），这个相应的操作也叫算法数据结构时专门研究数据存储的问题数据的存储包含两方面：个体的存储+个体关系的存储算法是对存储数据的操作数据结构：个体 + 个体的关系算法 = 对存储数据的操作算法解题的方法和步骤衡量算法的标准1.时间复杂度大概程序要执行的次数，而非执行的时间2.空间复杂度算法执行过程中大概所占用的最大内存3.难易程度4.健壮性数据结构的地位数据结构是软件中最核心的课程程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言预备知识 指针指针的重要性：指针式C语言的灵魂定义地址内存单元的编号结构体为什么会出现结构体为了表示复杂的数据，而普通的基本类型变量无法满足需求什么叫结构体结构体是根据用户的实际需要自己定义的复合数据类型如何使用结构体两种方式：struct Student st = {1000, "zhangshan", 20};struct Student * pst = &st;1.st.sid2.pst->sidpst所指向的结构体变量中的sid这个成员 注意事项：1.结构体变量不能加减乘除但可以相互赋值2.普通结构体变量和结构体指针变量作为函数传参的问题动态内存的分配和释放模块一：线性结构[把所有结点都用一条直线穿起来]连续存储[数组]1.什么叫数组元素类型相同，大小相等2.数组的优缺点：优点存取速度很快缺点插入删除元素很慢(需要移动其他元素)空间通常是有限制的事先必须知道数组的长度需要大块连续的内存块离散存储[链表]定义：n个节点离散分配彼此通过指针相连每个节点只有一个前驱节点，每个节点只有一个后续节点首节点没有前驱节点，尾节点没有后续节点专业术语：首节点：第一个有效节点尾节点：最后一个有效节点头节点：头节点的数据类型和首节点类型一样首节点前的那个节点头节点并不存放有效数据加头节点的目的主要是为了方便对链表的操作头指针：指向头节点的指针变量尾指针：指向尾节点的指针变量确定一个链表最少需要几个参数：只需要一个参数：头指针因为通过头指针可以推算出链表的其他所有信息分类:单链表双链表：每一个结点有两个指针域循环链表能通过任何一个节点找到其他所有的结点非循环链表算法：遍历查找清空销毁求长度排序删除结点把p所指向的结点的后一个结点删除伪算法：1.p->pNext = p->pNext->pNext; //会导致内存泄露，C/C++需要手动释放，该方式找不到被删除节点的地址，故不能手动释放2.r = p->pNext;p->pNext = P->pNext->pNext;free(r);插入结点在p所指向的结点后插入q所指向的结点伪算法：1.r = p->pNext; p->pNext = q; q->pNext = r;2.q->pNext = p->pNext; p->pNext = q;算法：狭义的算法时与数据的存储方式密切相关广义的算法与数据的存储方式无关泛型：利用某种技术达到的效果：不同的存储方式，执行的操作是一样的链表的优缺点：优点空间没有限制插入删除元素的速度很快缺点存取速度很慢线性结构的两种产检应用之一 栈定义一种可以实现"先进后出"的存储结构栈类似于箱子分类静态栈动态栈算法出栈压栈应用函数调用中断表达式求值内存分配缓冲处理迷宫线性结构的两种产检应用之二 队列定义：一种可以实现“先进先出”的存储结构分类：链式队列 ——用链表实现静态队列 ——用数组实现静态队列通常都必须是循环队列循环队列的讲解：1.静态队列为什么必须是循环队列2.循环队列需要几个参数来确定两个，front和rear3.循环队列各个参数的含义2个参数不同场合有不同含义建议初学者先记住，然后慢慢体会1).队列初始化front和rear的值都是零2).队列非空front代表的是队列的第一个元素rear代表的是队列的最后一个有效元素的下一个元素3).队列空front和rear的值相等，但不一定是零4.循环队列入队伪算法讲解1).将值存入r所代表的位置2).错误的写法：r = r + 1;正确的写法：r = (r+1)%(数组的长度);//例如：//r = 3，数组长度为6，则r = 4即实现了r"上移"//r = 5，数组长度为6，则r = 0即实现了r"上移"后的循环5.循环队列出队伪算法讲解1).将front代表的值保存（可不保存）2).front = (front + 1) % (数组长度)6.如何判断循环队列是否为空如果front和rear的值相等，则该数列就一定为空7.如何判断循环队列是否已满预备知识：front的值可能比rear大front的值也可能比rear小当然也可能两者相等两种方式：1.多增加一个标志参数2.少用一个元素[通常用第二种方式]用C语言伪算法表示就是：if((r+1) % (数组长度) == f)已满else不满队列算法：入队出队队列的具体应用：所有和时间有关的操作都有队列的影子专题：递归定义：一个函数自己直接或间接调用自己严书：(函数的调用)通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：1)将所有的实参、返回地址等信息传递给被调用函数保存2)为被调用函数的局部变量分配储存区3)将控制转移到被调函数的入口。而从被调用函数返回调用函数之前，系统也应完成3件工作：1)保存被调函数的计算结果2)释放被调函数的数据区3)依照被调函数保存的返回地址将控制转移到调用函数当有多个函数构成嵌套调用时，按照"后调用先返回"的原则，上述函数之间的信息传递和控制转移必须通过"栈"来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。A函数调用A函数和A哈桑农户调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已递归满足三个条件：1.递归必须得有一个明确的终止条件2.该函数所处理的数据规模必须在递减3.这个转化必须是可解的循环和递归(所有的循环都能用递归解决，所有的递归不一定能用循环解决)递归：易于理解速度慢存储空间大循环：不易理解速度快存储空间小举例：1.1+2+3+..+100的和2.求阶乘3.汉诺塔伪算法：if(n - 1){1.先把A柱子上的前n-1个盘子从A借助C移到B2.将A柱子上的第n个盘子直接移到C3.再将B柱子上的n-1个盘子借助A移到C}4.走迷宫递归的应用：树和森林就是以递归的方式定义的树和图的很多算法都是以递归来实现的很多数学公式就是以递归的方式定义的模块二：非线性结构树定义：专业定义：1.有且只有一个称为根的节点2.有若干个互不相交的子树，这些子树本身也是一颗树通俗定义：1.树是由节点和边组成2.每一个节点只有一个父节点但可以有多个子节点3.但有一个节点例外，该节点没有父节点，此节点称为根节点专业术语：节点 父节点 子节点子孙 堂兄弟 深度：树中结点的最大层次从根节点到最底层结点的层数被称之为深度，根节点是第一层叶子结点：没有子节点的结点非终端节点：非叶子结点度子节点的个数称为度树的分类：一般树任意一个节点的子节点的个数都不受限制二叉树任意一个节点的子节点的个数最多是两个，且子节点的位置不可更改二叉树的分类：一般二叉树满二叉树在不增加树的层数的前提下，无法再多添加一个结点的二叉树完全二叉树(很重要)如果只是删除了满二叉树最底层最右边的连续若干个结点，这样形成的二叉树就是完全二叉树满二叉树是完全二叉树的特例，一个不删森林n个互不相交的树的集合树的存储（我的理解：将树的逻辑结构保存在计算机内存的物理结构中）树的存储二叉树的存储连续存储[完全二叉树]优点：查找某个结点的父节点和子节点（也包括判断有没有子节点）速度快缺点：耗用内存空间过大链式存储一般树的存储双亲表示法求父节点方便孩子表示法求子节点方便双亲孩子表示法求父节点和子节点都比较方便二叉树表示法把一个普通书转化成二叉树来存储具体转换方法：设法保证任意一个结点的左指针域指向它的第一个孩子右指针域指向它的兄弟只要能满足此条件，就可以把一个普通树转化成二叉树一个普通树转化成的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再存储二叉树操作遍历先序遍历[先访问根节点]先访问根节点再先序访问左子树再先序访问右子树中序遍历[中间访问根节点]中序遍历左子树再访问根节点再中序遍历右子树后序遍历[最后访问根节点]后序遍历左子树后序遍历右子树再访问根节点已知两种遍历求原始二叉树已知一种序列不能够推出原始二叉树，已知先序和后序也不能推出原始二叉树通过先序和中序 或者 中序和后序我们可以还原出原始得到二叉树换种说法：只有通过先序和中序或通过中序和后序我们才可以唯一的确定一个二叉树应用树是数据库中数据组织一种重要形式操作系统子父进程的关系本身就是一棵树面向对象语言中类的继承关系赫夫曼树图模块三：查找和排序折半查找排序：冒泡冒泡升序: void sort(int * a, int n) {int i, j;int t;for(i = 0; i < n-1; i++){for(j = 0; n-i-1; j++){if( a[j] > a[j+1] ){t = a[j];a[j] = a[j+1];a[j+1] = t;}}} }快速排序插入选择直接选择排序 void sort(int *a, int len) {int i, j, min, t;for(i = 0; i < len-1; ++i){for(min = i, j = i+1; i < len; ++j){if(a[min] > a[j]){min = j;}}if(min != i){t = a[i];a[i] = a[min];a[min] = t;}} }归并排序排序和查找的关系排序是查找的前提排序是重点Java中容器和数据结构相关知识Iterator接口Map哈希表再次讨论什么是数据结构数据结构研究的是数据的存储和数据的操作的一门学问数据的存储分为两部分：个体的存储个体关系的存储从某个角度而言，数据最核心的就是个体关系的存储个体的存储可以忽略不计再次讨论什么是泛型同一种逻辑结构，无论该逻辑结构物理存储是什么样子的我们可以对它执行相同的操作

总结

以上是生活随笔为你收集整理的郝斌_数据结构入门笔记的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。