2023年郝斌数据结构自学笔记知识点程序源代码.docx
《2023年郝斌数据结构自学笔记知识点程序源代码.docx》由会员分享,可在线阅读,更多相关《2023年郝斌数据结构自学笔记知识点程序源代码.docx(93页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、郝斌数据结构自学笔记-知识点+程序源代码2023.12 By-HZM1_什么叫做数据结构数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作,这个相应的操作也叫算法。数据结构=个体的存储+个体的关系存储算法=对存储数据的操作2_衡量算法的标准算法解题的方法和环节衡量算法的标准1)时间复杂度:大约程序执行的次数,而非执行的时间2)空间复杂度:算法执行过程中大约所占用的最大内存3)难易限度4)健壮性3_数据结构的特点数据结构的地位数据结构是软件中最
2、核心的课程程序=数据的存储+数据的操作+可以被计算机执行的语言4_预备知识_指针_15_预备知识_指针_2指针的重要性:指针是C语言的灵魂定义:地址:地址是内存单元的编号,从0开始的非负整数,范围:0-FFFFFFFF【0-4G-1】CPU=地址线,控制线,数据线=内存指针:指针就是地址,地址就是指针。指针变量是存放内存单元地址的变量。指针的本质是一个操作受限的非负整数。分类:1.基本类型的指针2.指针和数组的关系变量并不一定连续分派,随机分派内存。内存:内存是多字节组成的线性一维存储空间。内存的基本划分单位是字节。每个字节具有8位,每一位存放1个0或1个1.内存和编号是一一相应的。软件在运营
3、前需要向操作系统申请存储空间。在软件运营期间,该软件所占空间不再分派给其他软件。当软件运营完毕后,操作系统将回收该内存空间(操作系统并不清空该内存空间中遗留下来的数据)。NOTE:1)指针变量也是变量,普通变量前不能加*,常亮和表达式前不能加&。2)局部变量只在本函数内部使用。如何通过被调函数修改主调函数中普通变量的值。1)实参为相关变量的地址;2)形参为以该变量的类型为类型的指针变量;3)在被调函数中通过 *形参变量名的形式 的形式就可以修改主函数。CASE 1#includeint main(void)int *p;/p是个变量名字,int*表达该p变量只能存储int类型变量的地址int
4、i=10;int j;/j=*p;/printf(%dn,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;/errorj=*p;/等价于j=i;printf(i=%d,j=%d,*p=%dn,i,j,*p); return 0;CASE 2#includevoid f(int * i)/不是定义了一个名字叫做*i的形参,而是定义了一个形参,该形参名字叫做i,它的类型是int*i=100;int main(void
5、)int i=9;f(&i);/局部变量只在本函数内部使用。printf(i=%dn,i);指针和数字数组名:一维数组名是个指针变量,它存放的是一维数组第一个元素的地址,它的值不能被改变,一维数组名指向的是数组的第一个元素。CASE 1a3=*(3+a); 3a =*(a+3)=*(3+a);int a5=1,2,3,4,5;Show_Aarry(a,5);/a等价于&a0,&a0自身就是int*类型void Show_Array(int * p,int len)Int I;/P2=-1;/ p0=*p ; p2=*(p+2)=*(a+2)=a2 ; pi就是主函数的aifor (i=0;il
6、em;i+)printf(“%dn”,pi);指针变量的运算指针变量不能相加,不能相乘,不能相除。假如两指针变量属于同一数组,则可以相减。指针变量可以加减一整数,前提是最终结果不能超过指针变量p+i的值是p+i*(p所指向的变量所占的字节数)p-i的值是p-i*(p所指向的变量所占的字节数)p+p+1 p-P-16_所有的指针变量只占4个子节 用第一个字节的地址表达整个变量的地址CASE 1double *p;double x=66.6;/一个double占8个字节p=&x;/x占8个字节,1个字节是8位,1个字节一个地址,p内只存放了一个地址,通常是字节的首地址double arr3=1.1
7、,2.2,3.3;double *q;q=&arr0;printf(“%pn”,q); /%p实际就是以十六进制输出q=&arr1;q=printf(“%pn”,q);/p,q相差8无论指针指向的变量占多少个字节,指针变量统一都只占4个字节7_如何通过函数修改实参的值发送地址CASE 1 修改指针变量的值,只能修改地址void f(int *);int main(void)int i=9;int *p=&i;/*p;p=&i;printf(“%pn”,p);f(&p); printf(“%pn”,p);return 0;/void f(int *q)/q=(int *)0xffffffff;
8、/错误,不会改变p的值/void f(int * q)*q=(int *)0xffffffff; 8_结构体的使用概述结构体为什么会出现结构体:为了表达一些复杂的数据,而普通的基本类型变量无法满足规定什么叫做结构体:结构体是用户根据实际需要自己定义的复合数据类型如何使用结构体:两种方式struct Student st=1000,”zhagnsan”,20;struct Student*pst=&st;1)通过结构体变量名来实现st.sid2)通过指向结构体变量的指针来实现【重点】pst-sidpst所指向的结构体变量中的sid这个成员CASE 1#include#include struct
9、 Studentint sid;char name200;int age;/分号不能省Int main(void)struct Student st=1000,”zhagnsan”,20;printf(“%d,%s%dn,”,st.sid,st.name,st.age);printf(“%d,%s%dn,”,st);/errorst.sid=99;/第一种/st.name=”lisi”;/error strcpy(st.name,”lisi”);st.age=22;struct Student*pst;pst=&st;/第二种pst-sid=99;/pst-等价于(*pst).sid,而(*p
10、st).sid等价于st.sid,所以pst-sid等价于st.sidReturn 0;注意事项:结构体变量不能加减乘除,但可以互相赋值普通结构体变量和结构体指针变量作为函数传参的问题CASE 2#includestruct Studentint sid;char name200;int age;void f(struct Student *pst);void g(struct Student st);void g2(struct Student *pst);int main (void)struct Student st;/已经为st分派好了内存f(&st);/g(st);g2(&st);/
11、 printf(“%d %s %dn”,st.sid,st.name,st.age);/输出方法一return 0;void g(struct Student st)/整体变量赋值/输出方法二,速度慢,耗空间,耗内存,不推荐printf(“%d %s %dn”,st.sid,st.name,st.age);void g2(struct Student *pst)printf(“%d %s %dn”,pst-sid,pst-name,pst-age);void f(struct Student *pst)(*pst).sid=99;strcpy(pst-name,”zhagnsan”);pst-
12、age=22;9_malloc()动态分派内存概述动态内存的分派和释放CASE 1#icclude#includeint main(void)int a5=1,2,3,4,5;/静态数组int len;printf(“请输入你需要分派的数组长度:len=”);scanf(“%d”,&len);int *pArr=(int *)malloc(sizeof(int)*len);/(int *)为强制转换,强制使pArr指向前四个字节。可以将pArr当做数组名来操作/*pArr=4;/类似于a0=4;/pArr1=10;/类似于a1=10;/printf(“%d %dn”,*pArr,pArr1);
13、/我们可以把pArr当做一个普通数组来使用for (int i=0;ilen;+i)scanf(“%d”,&pArr);for (i=0;ilen;+i)printf(“%dn”,*(pArr+i);free(pArr);/把pArr所代表的的动态分派的20个字节的内存释放return 0;10_跨函数使用内存讲解及其示例CASE 1#includeint f();int main(void)int i=10;i=f();printf(“i=%dn”,i);for(i=0;i2023;+i)f();return 0;int f()int j=20;return j;CASE 2main ()i
14、nt *p;fun(&p);.int fun (int *q)int s; /s为局部变量。调用完毕后s就没有了,最终p没有指向一个合法的整型单元*q=&s;CASE 3main()int *p;fun(&p);.int fun(int *q)*q=(int *)malloc(4);/返回4个字节,只取第1个字节地址赋给*q,*q=p。执行完后,由于没有free(),内存没有释放。假如没有free(),整个程序彻底终止时才干释放程序内部类定义方法A aa=new A();A *pa=(A*)malloc(sizeof(A);CASE 4#include#includestruct Studen
15、tint sid;int age;struct Student * CreatStudent(void);void ShowStudent(struct Student *);int main(void)struct Student *ps;ps=CreatStudent();ShowStudent(ps);return 0;struct Student * CreatStudent(void)struct Student *P=(struct Student *)malloc(sizeof(struct Student);p-sid=99;p-age=88;return p;void Sho
16、wStudent(struct Student *pst)printf(“%d %dn”,pst-sid,pst-age);11_复习12_连续存储数组的算法演示_113_连续存储数组的算法演示_2模块一:线性结构【把所有的结点用一根直线穿起来】1)连续存储数组2)离散存储链表线性结构的两种常见应用之一 栈线性结构的两种常见应用之二 队列专题:递归1. 1=2+3+4+.100的和2. 求阶乘3. 汉诺塔4. 走迷宫模块二:非线性结构树图连续存储数组1. 什么叫数组元素类型相同,大小相同2. 数组的优缺陷:CASE 1#include#include/包含了malloc函数#include/包
17、含了exit函数/定义了一个数据类型,该数据类型的名字叫做struct Arr,该数据类型具有3个成员,分别为pBase,len,cntstruct Arrint *pBase;/存储的是数组第一个元素的地址int len;/数组所能容纳的最大元素的个数int cnt;/当前数组有效元素的个数/int increment;/自动增长因子;void init_arr(struct Arr *pArr,int length);/初始化,使pBase指向一个有效的数组,而不再是垃圾数字bool append_arr(struct Arr *pArr,int val);/追加,也许成功,也许失败boo
18、l insert_arr(struct Arr *pArr,int pos,int val);/pos的值从1开始bool delete_arr(struct Arr *pArr,int pos,int *pVal);int get();bool is_empty(struct Arr *pArr);/是否已满bool is_full(struct Arr *pAr);/是否为空void sort_arr(struct Arr *pArr);/排序void show_arr(struct Arr *pArr);/显示,分号不能省void innversion_arr(struct Arr *p
19、Arr);/倒置int main (void)struct Arr arr; /只定义没初始化时,内部三个变量里都是垃圾数字int val;int posi=2;int len=6;/init_arr(arr);/会输出垃圾数字,并不能改变arr的值/printf(%dn,arr.len);init_arr(&arr,len);/会输出垃圾数字,并不能改变arr的值show_arr(&arr);append_arr(&arr,1);append_arr(&arr,-3);append_arr(&arr,6);append_arr(&arr,45);append_arr(&arr,13);if(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2023 年郝斌 数据结构 自学 笔记 知识点 程序 源代码
限制150内