《郝斌老师数据结构大纲word版》由会员分享，可在线阅读，更多相关《郝斌老师数据结构大纲word版（21页珍藏版）》请在金锄头文库上搜索。
1、数据结构资料教材：数据结构严蔚敏 吴伟民 清华大学出版社数据结构算法实现及解析高一凡 西安电子科技大学出版社第一部分数据结构概述一、定义（研究是数据结构的存储和数据的操作的）如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主 存储器（內存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某 个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。数据结构=个体的存储（从某个角度而言，可忽略）+个体与个体之间关 系的存储（核心）算法=对存储数据的操作二、算法解题的方法和步骤衡量算法的标准1. 时间复杂度大概程序要执行的次数，而非执行的时间2. 空间复杂度
2、算法执行过程中大概所占用的最大内存3. 难易程度（即可读性）4. 健壮性三、数据结构的地位数据结构是软件中最核心的內容程序=数据的存储+数据的操作+可以被计算机执行的语言第二部分预备知识一、指针# -数据结构资料指针的重要性：指针是C语言的灵魂定义地址：内存单元的编号从零开始的非负整数范围：O-FFFFFFFF （即 0-4G-1）指针：指针就是地址，地址就是指针指针变量是存放內存单元地址的变量指针的本质是一个操作受限的非负整数（只能进行减运算）分类：1. 基本类型的指针2. 指针和一维数组的关系二、结构体为什么会出现结构体为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体结
3、构体是用户根据实际需要自己定义的数据类型如何使用结构体两种方式：stmct Student st = 1000, zhangsan1*, 20stmct Student * pst = &st;1. st.sid2. pst-sidpst所指向的结构体变量中的sid这个成员-#-数据结构资料注意事项结构体变量不能加减乘除，但可以相互赋值普通结构体变量和结构体指针变量作为函数传参问题三、动态内存的分配和释放假设动态构造一个int型的一位数组int len;int * pArr = (int *)malloc (sizeof(int) * len); 本语句分配了两块內存，一块内存是动态分配的，总
4、共len个字节；另一块是 静态分配的，是pAn变量本身所占的内存，总共4个字节。 malloc只有一个int型的形参，表示要求系统分配的字节数 malloc函数的功能是请求系统分配len个字节的内存空间，如果分配成功，则 返回第一个字节的地址，如果分配不成功，则返回NULLmaI Ioc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实 际意义的第一个字节的地址(俗称干地址)转化为一个有实际意义的地址，因此, mal loc函数前面必须加強制类型转换(数据类型*),表示把这个无实际意义的 第一个字节的地址转化为相应类型的地址。 free (* pArr)表示把pArr所指向的內存给释
5、放掉pArr本身的内存是静态的，不能有程序员手动释放，只能在pArr变量所在的函 数运行终止时有系统自动释放 跨函数使用内存静态内存不可以跨函数使用：静态内存在函数执行期间可以被其它函数使用静态内存在函数执行完毕之后就不能在被其它函数使用动态内存可以跨函数使用动态内存在函数执行完毕之后仍然可以被其它函数使用第三部分 模块一：线性结构把所有的结点用一条直线穿起来一、连续存储数组1. 什么叫做数组元素类型相同，大小相等2. 数组的优缺点（相对于链表）优点：存取速度快缺点：实现必须知道数组的长度需要大块连续的內存块插入和删除元素很慢空间通常是有限制的二、离散存储链表1. 定义N个结点离散分配彼此通过
6、指针相连每个结点只有一个前驱结点，每个结点只有一个后续结点首结点没有前驱结点，尾结点没有后续结点专业术语：首结点：第一个存放有效数据的结点尾结点：最有一个存放有效数据的结点头结点：头结点的数据类型和首结点的类型是一样的首结点之前的结点头结点并不存放有效数据加头结点的目的是为了方便对链表的操作头指针：指向头结点的指针变量尾指针：指向尾结点的指针变量确定一个链表需要几个参数：（如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的那些参 数）一个参数，即头指针，因为我们通过头指针可以推算出链表的其它所有的信息2. 分类单链表双链表：每一个结点有两个指针域循环链表：能通过任何一个结点找到其它所
7、有的结点非循环链表3. 算法遍历/查找/清空/销毁/求长度/排序/删除结点/插入结点插入结点：（伪算法） r 二 p-pNext; p-pNext 二 q; q-pNext 二 r; q-pNext二p-pNext; p-pNext二q;（这两彳亍代码不能倒过来）删除结点：（伪算法）r = p-pNext; p-pNext 二 p-pNext-pNext; free（r）;狭义的算法是与数据的存储方式密切相关广艾的算法是与数据的存储方式无关泛型：利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的-# -数据结构资料同一种逻辑结构（包括线性结构和非线性结构，其中非线性结构包括树和 图
8、），无论该逻辑结构物理存储（包括数组和链表）是什么样子的，我们都可以 对它执行相同的操作4. 链表的优缺点（相对于数组）优点：空间没有限制插入和删除元素很快缺点：存取的速度很慢三、线性结构的两种常见应用之一 栈1. 定义：一种可以实现“先进后出”的存储结构栈类似于箱子2. 分类静态栈：以数组为内核动态栈：以链表为内核3. 算法出栈/入栈4. 应用函数调用/中断/表达式求值/内存分配/缓冲处理/迷宫四、线性结构的两种常见应用之一 队列1. 定义：一种可以实现“先进先出”的存储结构队列类似于排队买票2. 分类链式队列一用链表实现静态队列用数组实现静态队列通常都必须是循环队列#-数据结构资料循环队列
9、的讲解： 静态队列为什么必须是循环队列普通队列的参数front和rear只增不减，导致內存浪费 循环队列需要几个参数来确定需要两个参数：front / rear 循环队列各个参数的含义两个参数在不同的场合有不同的含义 队列初始化front和rear的值都为零 队列非空front代表的是队列的第一个元素W3T代表的是队列的最后一个有效元素的下一个元素 队列空front和Tear的值相等，但不一定是零 循环队列入队伪算法讲解(在尾部入队)第一步：将值存入WdT所指向的位置第二步：rear = (rear + 1)%数组的长度 循环队列出队伪算法讲解(在头部出队)front = (front +1)
10、%数组的长度 如何判断循环队列为空如果ftont与rear的值相等，则该队列一定为空 如何判断循环队列为满第一种方法：多增加一个标识参数，即数组的长度(常用)第二种方法：少用一个元素，如果front = (rear + 1)%数组的长度，则循环队列已满3. 算法出队/入队4. 应用所有和时间有关的操作都有队列的影子五、专题：递归（使用栈实现的）1、定义:一个函数自己直接或间接调用自己2、函数的调用当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：a、将所有的实际参数、返回地址等信息传递给被调函数保存b、为被调函数的局部变量（包括形参）分配存储空间c、将控制转移到被
11、调函数的入口从被调函数返回主调函数之前，系统也要完成三件事：a保存被调函数返回结果b、释放被调函数所占的存储空间c、依照被调函数保存的返回地址将控制转移到调用函数当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间的信息 传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间 安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作; 每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远都 在栈顶位置。A函数调用A函数与A函数调用B函数在计算机看来是没有任何区别的，只不 过用我们日常的思维方式理解比较怪异而已。3、递归必须满足的三
12、个条件：a递归必须得有一个明确的终止条件b、该函数处理的数据规模必须在递减c、这个转化必须是可解的4、循环和递归之间的关系理论上循环能解决的问题，肯定可以转化为递归解决，但是这个过程是复杂 的数学转化过程，递归能解决的问题不一定能转化为循环解决递归的优缺点：易于理解速度慢存储空间大循环的优缺点：不易理解速度快存储空间小5、举例：1.1+2+3+4+.+100 的和2. 求阶乘使用for循环实现：求和求阶乘# include # include int main(void)int main(void)long sum = 0;long mult = 1;-# -数据结构资料for (int i
13、= l;i v= 100;i+)sum = sum + i;prmtf(nl 到 100 的和是：%ld, sum);return 0;使用递归实现：#include long sum (int val)if(l =val)return 1;elsereturn val+sum(val - 1);int man(void)int val;prmtfC请输出整数：”)scanf (%d,&val);for (int i = 1; i = val; i +) mult = mult * i;printf(%d 的阶乘是%ld”, val, mult); return 0;#include long
14、 mult (int val)if( 1 = val)return 1;elsereturn val*mult(val-l);int main(void)printf(nl 到 100 的和是：%ldn,sum(100); printf(n请输出整数：”)return 0;scanf (n%d,&val);printf(n%d 的阶乘是%ld, val, mult(val)return 0;3. 汉诺塔伪算法:if （1 = n）直接将盘子从A移动到Celse（三步）第一步：将A上的前n1个盘子借助E移动到C第二步：将A上的第n个盘子直接移动到C第三步：将B上的个盘子借助A移动到C4. 走迷宫6、递归的应用树和森林就是以递归的方式定义的树和图的很多算法都是以递归来实现的很多数学公式就是以递归的方式定义的（例如：斐波拉契序列）第四部分 模块二：非线性结构一、树1、定义（专业定义）有且只有一个称为根的结点；有若干
