数据结构笔记介绍.docx

数据结构笔记参考书目：严蔚敏、吴伟民【伪算法】了解：高一凡【真正的程序】黄国瑜【数据结构】数据结构概述定义：我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，【存储数据主要解决两个问题个体如何进行保存；个体与个体之间的关系如何保存】；在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有的元素进行排序）而执行的相应操作，这个相应的操作也叫算法。数据结构=个体+个体的关系算法=对存储数据的操作算法 解题的方法和步骤数据结构狭义的讲是专门研究数据存储的问题，数据的存储包含两个方面个体存储+个体关系存储广义的讲数据结构既包括数据的存储也包含数据的操作，对存储数据的操作就是算法算法狭义地讲算法和数据的存储方式密切相关广义的讲算法和数据的存储方式无关这就是泛型的思想衡量算法的标准 1、时间复杂度 大概程序要执行的次数【运行次数最多的步骤】，而非执行的时间 2、空间复杂度 算法执行过程中大概所占用的最大内存 3、难易程度 4、健壮性数据结构的地位数据结构是软件中最核心的课程程序=数据存储+数据操作+可以被计算机执行的语言预备知识指针（C语言里的指针复习）所有的指针变量只占4个子节 用第一个字节的地址表示整个变量的地址指针定义： 地址：内存单元的编号 从0开始的非负整数 范围：0——FFFFFFFF【0——4G-1】 指针：指针就是地址，地址就是指针； 指针变量是存放内存单元地址的变量； 指针的本质就是一个操作受限的非负整数 分类：基本类型例子：#include stdio.h Int main(void) { int *p; //p是个变量名字，int*表示该p只能存储int类型变量的地址 Int i =10; Int j; P = i; J=*p //等价于j=i；Printf(“i=%d,j=%d,*p=%d”,i,j,*p) Return 0; } 该程序输出10，10，10总结 1、如何一个指针变量（假定为p）存放了某个普通变量（假定为i）的地址，那么我们可以说“p指向了i但是p与i是两个不同的变量”，修改p的值不影响i的值；修改i的值不影响p的值； 2、*p等价于i 或者说*p可以与i在任何地方互换 3、如果一个指针变量指向了某个普通变量则 *指针变量就完全等于该普通变量注意 指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址 普通变量前不能加* 常量和表达式前不能加如何通过被调函数修改主调函数中普通变量 1、实参为相关变量的地址 2、形参为以该变量的类型为类型的指针变3、在被调函数中通过*形参变量名的方式就可以修改主调函数中普通变量指针和数组 指针和一维数组 数组名一维数组名是个指针常量，它存放的是一维数组第一个元素的地址，它的值不能被改变，一维数组名指向的是鼠族的第一个元素。 下标和指针的关系 a[i]==*(a+i) 假设指针变量的名字为p，则p+i的值是p+i*（p所指向的变量所占的字节数） 指针变量的运算 指针变量不能相加，不能相乘，不能相除 如果指针变量同属于一个数组，则可以相减 指针变量可以加减一整数，前提是最终结果不能超过指针P-i的值是p-i*（p所指向的变量所占的字节数）P+i的值是p+i*（p所指向的变量所占的字节数）P++ == p+1P -- == p-1例子：如何通过一维数组修改主调函数中一维数组的内容存放数组首元素的指针变量存放数组元素的整型变量结构体 为什么会出现结构体？要表示一些复杂的数据；而普通的基本类型变量无法表示；需要通过结构体来表示或Java里的类表示 什么叫结构体？例子：struct Student { int sid; String name; Int sage; }结构体是用户根据实际需要自己定义的复合数据类型 如何使用结构