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

郝斌数据结构自学笔记--知识点+程序源代码2015.12By-HZM1_什么叫做数据结构数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。数据结构=个体的存储+个体的关系存储算法=对存储数据的操作2_衡量算法的标准算法解题的方法和步骤衡量算法的标准1）时间复杂度：大概程序执行的次数，而非执行的时间2）空间复杂度：算法执行过程中大概所占用的最大内存3）难易程度4）健壮性3_数据结构的特点数据结构的地位数据结构是软件中最核心的课程程序=数据的存储+数据的操作+可以被计算机执行的语言4_预备知识_指针_15_预备知识_指针_2指针的重要性：指针是C语言的灵魂定义：地址：地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】CPU=====地址线，控制线，数据线=====内存指针：指针就是地址，地址就是指针。指针变量是存放内存单元地址的变量。指针的本质是一个操作受限的非负整数。分类：1.基本类型的指针2.指针和数组的关系变量并不一定连续分配，随机分配内存。内存：内存是多字节组成的线性一维存储空间。内存的基本划分单位是字节。每个字节含有8位，每一位存放1个0或1个1.内存和编号是一一对应的。软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。2）局部变量只在本函数内部使用。如何通过被调函数修改主调函数中普通变量的值。1）实参为相关变量的地址；2）形参为以该变量的类型为类型的指针变量；3）在被调函数中通过*形参变量名的形式的形式就可以修改主函数。CASE1#includestdio.hintmain(void){int*p;//p是个变量名字，int*表示该p变量只能存储int类型变量的地址inti=10;intj;//j=*p;//printf(%d\n,j);//error,p未指定//charch='A';//p=&ch;//error，类型不一致p=&i;//p保存i的地址，p指向i；修改p的值不影响i的值，修改i的值不影响p的值；任何场合下，*p和i可以互换。*p等价于i。//p=10;//errorj=*p;//等价于j=i;printf(i=%d,j=%d,*p=%d\n,i,j,*p);return0;}CASE2#includestdio.hvoidf(int*i)//不是定义了一个名字叫做*i的形参，而是定义了一个形参，该形参名字叫做i，它的类型是int*{*i=100;}intmain(void){inti=9;f(&i);//局部变量只在本函数内部使用。printf(i=%d\n,i);}指针和数字数组名：一维数组名是个指针变量，它存放的是一维数组第一个元素的地址，它的值不能被改变，一维数组名指向的是数组的第一个元素。CASE1a[3]==*(3+a);3[a]==*(a+3)==*(3+a);inta[5]={1,2,3,4,5};Show_Aarry(a,5);//a等价于&a[0],&a[0]本身就是int*类型voidShow_Array(int*p,intlen){IntI;//P[2]=-1;//p[0]=*p;p[2]==*(p+2)==*(a+2)==a[2];p[i]就是主函数的a[i]for(i=0;ilem;i++)printf(“%d\n”,p[i]);}指针变量的运算指针变量不能相加，不能相乘，不能相除。如果两指针变量属于同一数组，则可以相减。指针变量可以加减一整数，前提是最终结果不能超过指针变量p+i的值是p+i*(p所指向的变量所占的字节数)p-i的值是p-i*(p所指向的变量所占的字节数)p++==p+1p--==P-16_所有的指针变量只占4个子节用第一个字节的地址表示整个变量的地址CASE1double*p;doublex=66.6;//一个double占8个字节p=&x;//x占8个字节，1个字节是8位，1个字节一个地址，p内只存放了一个地址，通常是字节的首地址doublearr[3]={1.1,2.2,3.3};double*q;q=&arr[0];printf(“%p\n”,q);//%p实际就是以十六进制输出q=&arr[1];q=printf(“%p\n”,q);//p,q相差8无论指针指向的变量占多少个字节，指针变量统一都只占4个字节7_如何通过函数修改实参的值发送地址CASE1修改指针变量的值，只能修改地址voidf(int**);intmain(void){inti=9;int*p=&i;//*p;p=&i;printf(“%p\n”,p);f(&p);printf(“%p\n”,p);return0;}//voidf(int*q)//{//q=(int*)0xffffffff;//错误，不会改变p的值//}voidf(int**q){*q=(int*)0xffffffff;}8_结构体的使用概述结构体为什么会出现结构体：为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫做结构体：结构体是用户根据实际需要自己定义的复合数据类型如何使用结构体：两种方式——structStudentst={1000,”zhagnsan”,20};structStudent*pst=&st;1)通过结构体变量名来实现st.sid2)通过指向结构体变量的指针来实现【重点】pst-sidpst所指向的结构体变量中的sid这个成员CASE1#includestdio.h#includestring.hstructStudent{intsid；charname[200];intage;};//分号不能省Intmain(void){structStudentst={1000,”zhagnsan”,20};printf(“%d,%s%d\n,”,st.sid,st.name,st.age);printf(“%d,%s%d\n,”,st);//errorst.sid=99;//第一种//st.name=”lisi”;//errorstrcpy(st.name,”lisi”);st.age=22;structStudent*pst;pst=&st;//第二种pst-sid=99;//pst-等价于(*pst).sid，而(*pst).sid等价于st.sid，所以pst-sid等价于st.sidReturn0;}注意事项：结构体变量不能加减乘除，但可以相互赋值普通结构体变量和结构体指针变量作为函数传参的问题CASE2#includestdio.hstructStudent{intsid；charname[200];intage;};voidf(structStudent*pst);voidg(structStudentst);voidg2(structStudent*pst);intmain(void){structStudentst;//已经为st分配好了内存f(&st);//g(st);g2(&st);//printf(“%d%s%d\n”,st.sid,st.name,st.age);//输出方法一return0;}voidg(structStudentst)//整体变量赋值//输出方法二，速度慢，耗空间，耗内存，不推荐{printf(“%d%s%d\n”,st.sid,st.name,st.age);}voidg2(structStudent*pst){printf(“%d%s%d\n”,pst-sid,pst-name,pst-age);}voidf(structStudent*pst){(*pst).sid=99;strcpy(pst-name,”zhagnsan”);pst-age=22;}9_malloc()动态分配内存概述动态内存的分配和释放CASE1#iccludestdio.h#includemalloc.hintmain(void){inta[5]={1,2,3,4,5};//静态数组intlen;printf(“请输入你需要分配的数组长度：len=”);scanf(“%d”,&len);int*pArr=(int*)malloc(sizeof(int)*len);//(int*)为强制转换，强制使pArr指向前四个字节。可以将pArr当做数组名来操作//*pArr=4;//类似于a[0]=4;//pArr[1]=10;//类似于a[1]=10;//printf(“%d%d\n”,*pArr,pArr[1]);//我们可以把pArr当做一个普通数组来使用for(inti=0;ilen;++i)scanf(“%d”,&pArr);for(i=0;ilen;++i)printf(“%d\n”,*(pArr+i));free(pArr);//把pArr所代表的的动态分配的20个字节的内存释放return0;}10_跨函数使用内存讲解及其示例CASE1#includestdio.hintf();intmain(void){inti=10;i=f();printf(“i=%d\n”,i);for(i=0;i2000;++i)f();return0;}intf(){intj=20;returnj;}CASE2main(){int*p;fun(&p);...}intfun(int**q){ints;//s为局部变量。调用完毕后s就没有了，最终p没有指向一个合法的整型单元*q=&s;}CASE3main(){int*p;fun(&p);...}intfun(int**q){*q=(int*)malloc(4);//返回4个字节，只取第1个字节地址赋给*q，*q==p。执行完后，因为没有free()，内存没有释放。如果没有free()，整个程序彻底终止时才能释放}程序内部类定义方法Aaa=newA();A*pa=(A*)malloc(sizeof(A));CASE4#includestdio.h#includemalloc.hstructStudent{intsid;intage;}structStudent*CreatStudent(void);voidShowStudent(structStudent*);intmain(void){structStudent*ps;ps=CreatStudent();ShowStudent(ps);return0;}structStudent*CreatStudent(void){structStudent*P=(structStudent*)malloc(sizeof(structStudent));p-sid=99;p-age=88;returnp;}voidShowStudent(structStudent*pst){printf(“%d%d\n”,pst-sid,pst-age);}11_复习12_连续存储数组的算法演示_113_连续存储数组的算法演示_2模块一：线性结构【把所有的结点用一根直线穿起来】1）连续存储[数组]2）离散存储[链表]线性结构的两种常见应用之一栈线性结构的两种常见应用之二队列专题：递归1.1=2+3+4+...100的和2.求阶乘3.汉诺塔4.走迷宫模块二：非线性结构树图连续存储[数组]1.什么叫数组元素类型相同，大小相同2.数组的优缺点：CASE1#includestdio.h#includemalloc.h//包含了malloc函数#includestdlib.h//包含了exit函数//定义