《郝斌数据结构自学笔记知识点+程序源代码.pdf》由会员分享，可在线阅读，更多相关《郝斌数据结构自学笔记知识点+程序源代码.pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 郝斌数据结构自学笔记-知识点+程序源代码 By-HZM 1_什么叫做数据结构 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作 2_衡量算法的标准 算法 解题的方法和步骤 衡量算法的标准 1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性 3_数据结构的特点【数据结构的地位
2、 数据结构是软件中最核心的课程 程序=数据的存储+数据的操作+可以被计算机执行的语言 4_预备知识_指针_1 5_预备知识_指针_2*指针的重要性：指针是 C 语言的灵魂 定义：地址：地址是内存单元的编号,从 0 开始的非负整数，范围：0-FFFFFFFF【0-4G-1】CPU=地址线，控制线，数据线=内存 指针：指针就是地址，地址就是指针。指针变量是存放内存单元地址的变量。指针的本质是一个操作受限的非负整数。分类：1.基本类型的指针 2.指针和数组的关系?变量并不一定连续分配，随机分配内存。内存：内存是多字节组成的线性一维存储空间。内存的基本划分单位是字节。每个字节含有 8 位，每一位存放
3、1 个 0 或 1 个 1.内存和编号是一一对应的。（软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。2）局部变量只在本函数内部使用。如何通过被调函数修改主调函数中普通变量的值。1）实参为相关变量的地址；2）形参为以该变量的类型为类型的指针变量；3）在被调函数中通过 *形参变量名的形式 的形式就可以修改主函数。CASE 1#include int main(void)|int*p;id，而
4、(*pst).sid 等价于，所以 pst-sid 等价于 Return 0;注意事项：结构体变量不能加减乘除，但可以相互赋值 普通结构体变量和结构体指针变量作为函数传参的问题 CASE 2,#include struct Student int sid；char name200;int age;void f(struct Student*pst);void g(struct Student st);void g2(struct Student*pst);int main(void)struct Student st;id=99;strcpy(pst-name,”zhagnsan”);-pst
5、-age=22;9_malloc()动态分配内存概述 动态内存的分配和释放 CASE 1#icclude，#include int main(void)int a5=1,2,3,4,5;.int fun(int*q)】int s;.int fun(int*q)*q=(int*)malloc(4);1=2+3+4+.100 的和 2.求阶乘 3.汉诺塔 4.走迷宫 模块二：非线性结构 树 图 连续存储数组.1.什么叫数组 元素类型相同，大小相同 2.数组的优缺点：CASE 1#include#include en=99;pArr-pBase=(int*)malloc(sizeof(int)*le
6、ngth);%if(NULL=pArr-pBase)printf(动态内存分配失败！n);exit(-1);值存入 r 所代表的位置 2.错误的写法：r=r+1;正确写法是：r=（r+1）%数组的长度 42 _ 队列 8 _ 循环队列出队伪算法讲解 f=（f+1）%数组的长度 43 _ 队列 9 _ 如何判断循环队列是否为空 如果 front 于 rear 的值相等，则该队列就一定为空。44 _ 队列 10 _ 如何判断循环队列是否已满 若 f、r 相等，不知道队列到底是空还是满。预备知识：front 的值可能比 rear 大，也可能比 rear 小，也可能两者相等。如何判断循环队列是否已满
7、两种方式：1.多增加一个标志参数 2.少用一个元素【通常使用第二种方式】如何判断队列已满：如果 f 和 r 的值紧挨着，则队列已满 用 C 语言伪算法表示就是：if（r+1）%数组长度=f）已满 else 不满 。45 _ 复习 _ 求链表的长度 46 _ 复习上节课队列知识 队列 定义：一种可以实现先进先出的存储结构 分类：静态队列 链式队列 47 _ 循环队列程序演示 队列算法：入队 出队#include#include typedef struct Queue int*pBase;int front;int rear;QUEUE;void init(QUEUE*);bool en_que
8、ue(QUEUE*,int);+100 的和 2,求阶乘 3,汉诺塔 4,走迷宫#include void f();void g();void k();int main(void)f();return 0;void f()printf(FFFFn);g();printf(1111n);void g()printf(GGGGn);k();printf(2222n);void k()printf(KKKKn);printf(3333n);!51 _ 递归 2 _ 一个函数自己调自己 程序举例#include void f(int n)if(n=1)printf(自己调自己n);else f(n-1
9、);int main(void)f(7);return 0;：52 _ 递归 3 _ 1+2+3+.+100 之和用递归来实现 CASE 1#include int main(void)int val;int i,mult=1,s;printf(请输入一个数字：);printf(val=);scanf(%d,&val);for(i=1;i=val;+i)mult=mult*i;printf(%d 的阶乘是：%dn,val,mult);return 0;!CASE 2#include.+100 的和是:n%dn,sum(100);return 0;,53 _ 递归 4 _ 布置作业_汉诺塔 54
10、 _ 递归 5 _ 一个函数为什么可以自己调用自己 CASE 1#include 归必须得有一个明确的终止条件 -2.该函数所处理的数据规模必须在递减 3.这个转化必须是可解的 CASE 1#include 历：先序遍历，中序遍历，后序遍历 2.已知两种遍历序列求原始二叉树 先序遍历：【先访问根节点】先访问根节点，再先序访问左子树，再先序访问右子树。:68_树 9_二叉树的中序遍历【中间访问根节点】中序遍历左子树，再访问根节点，再中序遍历右子树 69_树 10_二叉树的后序遍历【最后访问根节点】序遍历左子树，后序遍历右子树后序遍历根节点 )70_树 11_已知两种遍历序列求原始二叉树概述 通过
11、先序和中序 或者 中序和后序我们可以还原出原始的二叉树，但是通过先序和后序是无法还原出原始的二叉树的。换种说法，只有通过先序和中序，或通过中序和后序，我们才能唯一的确定一个二叉树。71_树 12_已知先序和中序求后序 -72_树 13_已知中序和后序求先序 73_树 14_树的应用简单介绍 树是数据库数据组织的一种重要形式。操作系统子父进程的关系本身就是一棵树。面向对象语言中类的继承关系本身就是一棵树。赫夫曼树【74_树 15_复习上节课知识 75_树 16_链式二叉树遍历具体程序演示 /程序执行有问题。#include#include struct BTNode int data;struc
12、t BTNode*pLchhid;/p 是指针，L 是左，child 是孩子 struct BTNode*pRchhid;void PreTraverseBTree(struct BTNode*pT);void InTraverseBTree(struct BTNode*pT);void PostTraverseBTree(struct BTNode*pT);struct BTNode*CreateBTree(void);int main(void)struct BTNode*pT=CreateBTree();printf(前序遍历：n);PreTraverseBTree(pT);printf
13、(中序遍历：n);InTraverseBTree(pT);printf(后序遍历：n);PostTraverseBTree(pT);return 0;struct BTNode*CreateBTree(void)struct BTNode*pA=(struct BTNode*)malloc(sizeof(struct BTNode);struct BTNode*pB=(struct BTNode*)malloc(sizeof(struct BTNode);struct BTNode*pC=(struct BTNode*)malloc(sizeof(struct BTNode);struct B
14、TNode*pD=(struct BTNode*)malloc(sizeof(struct BTNode);struct BTNode*pE=(struct BTNode*)malloc(sizeof(struct BTNode);pA-data=A;pB-data=B;pC-data=C;pD-data=D;pE-data=E;?pA-pLchhid=pB;pA-pRchhid=pC;pB-pLchhid=pB-pRchhid=NULL;pC-pLchhid=pD;pC-pRchhid=NULL;pD-pLchhid=NULL;&pD-pRchhid=pE;pE-pLchhid=pE-pRc
15、hhid=NULL;return pA;void PreTraverseBTree(struct BTNode*pT)；if(pT!=NULL)printf(%cn,pT-data);if(NULL!=pT-pLchhid)PreTraverseBTree(pT-pLchhid);&if(NULL!=pT-pLchhid)PreTraverseBTree(pT-pRchhid);/pT-pLchhid 可以代表整个左子树 void InTraverseBTree(struct BTNode*pT)if(pT!=NULL)if(NULL!=pT-pLchhid)InTraverseBTree(p
16、T-pLchhid);printf(%cn,pT-data);if(NULL!=pT-pLchhid)InTraverseBTree(pT-pRchhid);/pT-pLchhid 可以代表整个左子树 void PostTraverseBTree(struct BTNode*pT)if(pT!=NULL)if(NULL!=pT-pLchhid)PostTraverseBTree(pT-pLchhid);if(NULL!=pT-pLchhid)PostTraverseBTree(pT-pRchhid);printf(%cn,pT-data);/pT-pLchhid 可以代表整个左子树 76_树 17_5 种常用排序概述 和 快速排序详细讲解 排序：冒泡 插入 选择 快速排序 归并排序 排序和查找的关系：排序是查找的前提，排序是重点 77_树 18_再次讨论什么是数据结构 研究的是数据的存储和数据的操作的一门学问。数据的存储分为两类：分体的存储 个体关系的存储 从某个角度而言，数据的最核心的就是个体关系的存储，个体的存储可以忽略不计。78_树 19_再次讨论到底什么是泛型 同一种逻辑结构，无论该逻辑结构物理存储是什么样子的，我们可以对它执行相同的操作。