数据结构笔记.doc

//2018/5/23
数据结构概述：
预备知识
模块一：线性结构
连续存储[数组]
离散结构[链表]
线性结构的两种常见应用之一 栈〔堆栈〕
线性结构的两种常见应用之二 队列
专题：递归
+2......+100的和



模块二：非线性结构
树
图
模块三：查找和排序
折半查找
排序：冒泡 插入 选择 快速排序 归并排序
补录：Java中容器和数据结构相关知识
Iterator接口
Map 哈希表
严蔚敏---高一凡---黄国瑜
//2018/5/24
数据结构概述
定义
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器〔内存〕中，以与在此根底上为实现某个功能〔比如查找或删除某个元素，对所有元素进展排序〕而执行的相应操作，这个相应操作叫做算法。
特定的数据类型:个体如何保存
特定的存储结构:个体与个体的关系如何保存
数据结构 = 个体的存储 + 个体关系的存储
算法〔狭义〕 = 对存储数据的操作
算法：即解题的方法和步骤
衡量算法的标准
时间复杂度[重要]
大概程序要执行的次数，而非执行的时间
空间复杂度[重要]
算法执行过程中大概所占用的最大内存
难易程度
健壮性
数据结构的地位
数据结构是软件中最核心的课程。
程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言
预备知识：
指针
结构体
动态内存的分配和释放
指针：
指针的重要性:
表示一些复杂的数据结构
快速的传送数据
使函数返回一个以上的值
能否直接访问硬件
能够方便的使用数组和字符串
是理解面向对象语言中引用的根底
指针是C语言的灵魂
定义
地址
内存单元的编号
从0开始的非负整数
X围0-FFFFFFFF 【0 到 4G-1】
注：无论一个变量有多大，其地址只用第一个字节的地址表示，均只占四个字节。
指针
指针就是地址 地址就是指针
指针变量就是存放内存单元地址的变量
指针本质上就是一个操作受限的非负整数
分类
1、根本类型指针【略】
根本概念
int i=10;
int *p = &i; //等价于 int *p;p = &i;
详解这两部操作：
1〕p存放了i的地址，所以我们说p指向了i
2〕p和i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值
3〕p指向i，*p就是i变量本身。更形象的说所有出现 *p的地方都可以换成i，所有出现i的地方都可以换成*p
4〕int * p，不是定义了*p的参数，而是定义了一个变量p，为int *类型。
总结：
1、如何一个指针变量(假定为p)存放了某个普通变量(假定为i)的地址，那我们就可以说：“p指向了i〞， 但p与i是两个不同的变量，修改p的值不影响i的值，修改i的值不影响p的值.
2、*p等价于i 或者说*p可以与i在任何地方互换
3、如果一个指针变量指向了某个普通变量，如此*指针变量 就完全等价于该普通变量
注意：
指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址
普通变量前不能加*
常量和表达式前不能加&
如何通过被调函数修改主调函数中普通变量的值
Ⅰ 实参为相关变量的地址
Ⅱ 形参为以该变量的类型为类型的指针变量
Ⅲ 在被调函数中通过 *形参变量名 的方式就可以修改主函数相关变量的值
Eg:void f(int * p) //II
{
*p = 100; //III
}
int main(void)
{
int i = 9;
f(&i); //I
printf(“i = %d\n〞, i);
}
指针和数组的关系
指针 和 一维数组
数组名
一维数组名是个指针常量，
它存放的是一维数组第一个元素的地址，
它的值不能被改变
一维数组名指向的是数组的第一个元素
下标和指针的关系
a[i] <<==>> *(a+i)
*a+3 = a[0]+3
假设指针变量的名字为p
如此p+i的值是p+i*(p所指向的变量所占的