郝斌老师数据结构笔记

《郝斌老师数据结构笔记》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构概述（1）定义：我们如何把现实中大量而复杂的问题已特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此基础上位实现某个功能二执行的相应操作，这个相应的操作也叫算法。解释：数据结构要解决的问题就是把现实中大量复杂的问题存储到内存中，把单个数据的类型确定，再把数据之间关系确定，这样就可以存储到内存中去了，算法就是对数据结构的操作。比如数组是一个数据结构，单个数据类型就确定，数据之间关系就是连续存储，操作数组就是一个算法。侠义的算法是依附于某个数据结构上，也就是说同样对数组遍历和对链表遍历，算法肯定不一样。数据结构

2、解决存储问题，算法解决数据间的关系。数据结构=个体+个体的关系算法=对存储数据的操作。狭义的算法算法：解题的方法和步骤（2）衡量算法的标准：1时间复杂度大概程序要执行的次数，而非执行的时间：运行步骤最多的最关最核心的要运行的次数可以大概代表2空间复杂度：算法执行过程中大概所占有的最大内存。3难易程度4健壮性前两个最重要（一般算法有循环）（3）第三个内容：数据结构的地位（数据结构是软件中最核心的课程）数据库和数据结构的区别：数据库是数据结构的简化版程序：数据的存储+数据段操作+可以被计算机之行的语言（4）预备知识：伪算法不是真正的

3、算法通过语言来实现伪算法，希望编程语言实现要通过指针。链表的知识很重要，以后都会用到。C++的指针不够，学C语言的用途是为了以后能看懂更高级的语言*p就代表一个变量，例如i。int*p表示定义一个存放整形变量的地址的指针变量。程序运行完，内存就终止了。复习：1:指针：int*p//p是个变量名字，用来存放地址，只能存储int型变量的地址指针的重要性：是C语言的灵魂，定义地址线cpu内存0控制线1。。。。数据线地址内存单元的编号（cpu只能访问内存，不能访问硬盘）从0开始的非负整数，范围为0——4g-1指针就是地址，地址就是指针指

4、针变量是存放内存单元地址的变量指针和指针变量不一样指正的本质是一个操作受限的非负整数分类：Int*p;Int*j;Inti=10;P=&I;//(1).把i的地址赋给i，*p就指向了I(2).p和i没有任何的关系(3)*p就是iP=10//errorI=*j//error1基本类型的指针（p=&i表示指针变量存储i的地址，但是p为p，i为i两者无任何关系，但是*p和i却是等效的两者可以互换）变量不进行初始化，会是一个随机数的原因。2:指针结构体3:动态内存的分配和释放。4：内存的基本单位是字节5：&为取地址符号6:#includ

5、evoidf(int*p){*p=100}intmain(){inti=9；f(&i)printf("i=%d",i);return0}@@如何实现被掉函数修改主调函数中普通变量的值1：实参为相关变量的地址（&i）2：形参为以该变量的类型（int型）为类型的指针变量（指针变量p）3：在被调函数中通过*形参变量名的方式就可以修改主函数中普通变量的值（*p和i可以等效替换两者无任何区别）指针和数组（Array）数组名一位数组名a是个指针常量//inta[]={1,2,3,4,5};//在内存中开辟了一个连续的5

6、个整形变量的内存空间。它们是共生共亡。它存放的是一维数组第一个元素的地址，、】它的值不能被改变//&a[1]=….是错误的！一维数组名指向的是数组的第一个元素。下表和指针的关系a[i]<<==>>*（a+i）下标和指针的关系假设指针变量的名字为p则p+i的值是p+i*（p所指向的变量所占的字节数）指针变量的运算指针变量不能相加，乘除。如果两指针变量属于同一数组，则可以相减指针变量可以相减一整数，前提是最终结果不能草果指针的范围p+i的值是p+i*(p所指向的变量所占的字节数)p-i的值是p-i*(p所指向的变量所占的字节数）p+

7、+《==》p+1如何通过被调函数修改主函数中一位数组的内容两个参数存放数组首元素的指针变量存放数组元素长度的整形变量#include《stdio.h》voidshow-array（int*p，intlen）{p[2]=-1;//p[0]==*pp[2]==*(p+2)==*(a+2)==a[2]//p【i】此时就是主函数的a【i】}intmain(void){inta[5]={11,2,3,4,5};show_arraya(a,5)//a等价于&a[0],&a[0]本身就是int*类型return0}一个double占八个字节，

8、一个字节是8位，美一个字节都占一个地址。指针变量都只占四个字节（无论指针变量指向的对象占多少字节，它只占4个字节。）指针变量只占4个字节原因：在32位的操作系统中，一共有32根地址总线，可以有2的32次方大小的地址编码，所以需要4个字节的大小来表示，所以32位的