文档介绍：数据结构概述(教材选用严蔚敏、吴伟民,该书程序是伪算法
具体的程序是高一凡,西电的,大牛,只有
程序。还有一本书,台湾的黄国瑜自己写的
只有思路,程序是另外一个合作的清华的写
的,可惜很多错的。)
学完数据结构之后会对面向过程的函数有一个更深的了解
定义
我们如何把现实中大量而复杂的问题以特定的数据类型(单
个数据怎样存储?)和特定的存储结构(个体的关系)
保存到主存储器(内存)中,以及在此基础上为实现某个功能
(比如查找某个元素,删除某个元素,对所有元素进行排序)
而执行的相应操作,这个相应的操作也叫算法。(比如班里有
15个人,其信息量也许一个数组就搞定了,但是假如10000个,
怎么办?内存也许没有这么多连续的空间,所以我们改用链表,
you see这就是与存储有关系。又比如,人事管理系统的信息存储,
因为存在着上下级的关系,所以数组和链表就无能为力了,
这时候我们用树,再比如我们做的是交通图,站和站之间肯定要连通,这
时候以上的存储方式又无能为力了,所以我们又有了图。图
就是每个结点都可以和其他结点产生联系。所以当我们要解决
问题时,首先要解决的是如何把这些问题转换成数据,先保存
到我们的主存中,)
数据结构= 个体+ 个体的关系
算法= 对存储数据的操作
算法
解题的方法和步骤
衡量算法的标准
1、时间复杂度
大概程序要执行的次数,而非执行的时间。
2、空间复杂度
算法执行过程中大概所占用的最大内存
3、难易程度(主要是应用方面看重)
4、健壮性(不能别人给一个非法的输入就挂掉)
数据结构的地位
数据结构是软件中最核心的课程
程序= 数据的存储+数据的操作+可以被计算机执行的语言(已经提供)
(学完数据结构,想用一种语言去实现它,必须有指针,数据结构java
版,就胡扯,变味,因为我们要讲链表,就是通过指针链在一起的。比如
在java中A aa = new A();本质上,aa是个地址)
预备知识
指针
指针的重要性:(内存是可以被CPU直接访问的,硬盘不行
主要靠地址总线,数据总线,控制总线。)
指针是C语言的灵魂
定义
地址
地址就是内存单元的编号
从0开始的非负整数
范围:0--FFFFFFFF[0-4G-1](地址线是32位,刚好控制2的32次)
指针:
指针就是地址地址就是指针
指针变量是存放内存单元地址的变量
指针的本质是一个操作受限的非负整数(不能加乘除,只能减)
分类:
1、基本类型的指针
2、指针和数组的关系
结构体(C++中用类也能实现)
为什么会出现结构体
为了表示一些复杂的数据,而普通的基本类型变量无法满足要求
什么叫结构体
结构体是用户根据实际需要自己定义的复合数据类型
如何使用结构体
两种方式:
struct Student st = {1000, "zhangsan", 20}
struct Student * pst = &st;
1.
2.
pst->sid
pst所指向的结构体变量中的sid这个成员
注意事项:
结构体变量不能加减乘除,但可以相互赋值
普通结构体变量和结构体指针变量作为函数参数的传递
(病毒就是靠访问正在运行的那些程序所占用的内存。Java中规定局部
变量必须初始化,因为这些变量一开始都是垃圾值,但是属性不是必须
初始化的,因为已经默认初始化为0)
动态内存分配和释放(动态分配的内存一定要手动释放,否则造成内存
泄露。)
(java中A aa = new A();其实就是 A *p = (A *)malloc(sizeof(A)))
模块一:线性结构【把所有的结点用一根直线穿起来】
连续存储【数组】
1、什么叫做数组
元素类型相同,大小相等(数组传参,只要传进去首地址和长度就行)
2、数组的优缺点:
优点:
存取速度快
缺点:
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低
离散存储【链表】(我们搞底层的开发,类似于SUN公司的类)
定义:
n个节点离散分配
彼此通过指针相连
每个节点只有一个前驱节点,每个节点只有一个后续节点
首节点没有前驱节点,尾节点没有后续节点。
专业术语:
首节点:
第一