郝斌数据结构自学笔记--知识点+程序源代码..docx

郝斌数据结构自学笔记-- 知识点+ 程序源代码 1_ 什么叫做数据结构数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作,这个相应的操作也叫算法。数据结构= 个体的存储+ 个体的关系存储算法= 对存储数据的操作 2_ 衡量算法的标准算法解题的方法和步骤衡量算法的标准 1 )时间复杂度:大概程序执行的次数,而非执行的时间 2 )空间复杂度:算法执行过程中大概所占用的最大内存 3 )难易程度 4 )健壮性 3_ 数据结构的特点数据结构的地位数据结构是软件中最核心的课程程序= 数据的存储+ 数据的操作+ 可以被计算机执行的语言 4_ 预备知识_ 指针_1 5_ 预备知识_ 指针_2 指针的重要性: 指针是 C 语言的灵魂定义: 地址: 地址是内存单元的编号,从0 开始的非负整数,范围: 0-FFFFFFFF 【 0-4G-1 】 CPU===== 地址线,控制线,数据线===== 内存指针: 指针就是地址,地址就是指针。指针变量是存放内存单元地址的变量。指针的本质是一个操作受限的非负整数。分类: 1. 基本类型的指针 2. 指针和数组的关系变量并不一定连续分配,随机分配内存。内存: 内存是多字节组成的线性一维存储空间。内存的基本划分单位是字节。每个字节含有 8 位,每一位存放 1个0或1个 1. 内存和编号是一一对应的。软件在运行前需要向操作系统申请存储空间。在软件运行期间, 该软件所占空间不再分配给其他软件。当软件运行完毕后, 操作系统将回收该内存空间( 操作系统并不清空该内存空间中遗留下来的数据)。 NOTE :1 )指针变量也是变量,普通变量前不能加* ,常亮和表达式前不能加&。 2 )局部变量只在本函数内部使用。如何通过被调函数修改主调函数中普通变量的值。 1 )实参为相关变量的地址; 2 )形参为以该变量的类型为类型的指针变量; 3 )在被调函数中通过* 形参变量名的形式的形式就可以修改主函数。 CASE 1 #include<> int main(void) { int *p; //p 是个变量名字, int* 表示该 p 变量只能存储 int 类型变量的地址 int i=10; int j; // j=*p; // printf("%d\n",j); //error,p 未指定// char ch='A'; // p=&ch; //error ,类型不一致 p=&i; //p 保存 i 的地址,p 指向 i; 修改 p 的值不影响 i 的值, 修改 i 的值不影响 p的值;任何场合下, *p和i 可以互换。*p 等价于 i。//p=10; //error j=*p;// 等价于 j=i; printf("i=%d,j=%d,*p=%d\n",i,j,*p); return 0; } CASE 2 #include<> void f(int * i)// 不是定义了一个名字叫做*i 的形参, 而是定义了一个形参, 该形参名字叫做 i, 它的类型是 int* { *i=100; } int main(void) { int i=9; f(&i); // 局部变量只在本函数内部使用。 printf("i=%d\n",i); } 指针和数字数组名: 一维数组名是个指针变量, 它存放的是一维数组第一个元素的地址, 它的值不能被改变,一维数组名指向的是数组的第一个元素。 CASE 1 a[3]==*(3+a); 3[a] ==*(a+3)==*(3+a); int a[5]={1,2,3,4,5}; Show_Aarry(a,5);//a 等价于&a[0],&a[0] 本身就是 int* 类型 void Show_Array(int * p,int len) { Int I; //P[2]=-1;// p[0]=*p ; p[2]==*(p+2)==*(a+2)==a[2] ; p[i] 就是主函数的 a[i] for (i=0;i<lem;i++) printf( “%d\n ”,p[i]); } 指针变量的运算指针变量不能相加,不能相乘,不能相除。如果两指针变量属于同一数组,则可以相减。指针变量可以加减一整数,前提是最终结果不能超过指针变量 p+i 的值是 p+i*(p 所指向的变量所占的字节数) p-i 的值是 p-i*(p 所指向的变量所占的字节数) p++<==>p+1 p--<==>P-1 6_ 所有的指针变量只占 4 个子节用第一个字节的地址表示整个变量的地址 CASE 1 double *p; double x=; // 一个