郝斌老师数据结构笔记

数据结构概述定义：我们如何把现实中大量而复杂的问题已特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此基础上位实现某个功能二执行的相应操作，这个相应的操作也叫算法。数据结构解决存储问题，算法解决数据间的关系。数据结构=个体+个体的关系算法=对存储数据的操作。狭义的算法算法：解题的方法和步骤衡量算法的标准：1时间复杂度大概程序要执行的次数，而非执行的时间：运行步骤最多的最关最核心的要运行的次数可以大概代表2空间复杂度：算法执行过程中大概所占有的最大内存。3难易程度4健壮性前两个最重要（一般算法有循环）第三个内容：数据结构的地位（数据结构是软件中最核心的课程）数据库和数据结构的区别：数据库是数据结构的简化版程序：数据的存储+数据段操作+可以被计算机之行的语言预备知识：伪算法不是真正的算法通过语言来实现伪算法，希望编程语言实现要通过指针。链表的知识很重要，以后都会用到。C++的指针不够，学C语言的用途是为了以后能看懂更高级的语言*p就代表一个变量，例如i。int*p表示定义一个存放整形变量的地址的指针变量。程序运行完，内存就终止了。复习：1:指针：int*p//p是个变量名字，用来存放地址，只能存储int型变量的地址指针的重要性：是C语言的灵魂，定义地址内存单元的编号（cpu只能访问内存，不能访问硬盘）从0开始的非负整数，范围为0——4g-1指针就是地址，地址就是指针指针变量是存放内存单元地址的变量指针和指针变量不一样指正的本质是一个操作受限的非负整数分类：1基本类型的指针（p=&i表示指针变量存储i的地址，但是p为p，i为i两者无任何关系，但是*p和i却是等效的两者可以互换）22:指针结构体3:动态内存的分配和释放。4：内存的基本单位是字节5：&为取地址符号6:#includestdio.hvoidf(int*p){*p=100}intmain(){inti=9；f(&i)printf(i=%d\n,i);return0}@@如何实现被掉函数修改主调函数中普通变量的值1：实参为相关变量的地址（&i）2：形参为以该变量的类型（int型）为类型的指针变量（指针变量p）3：在被调函数中通过*形参变量名的方式就可以修改主函数中普通变量的值（*p和i可以等效替换两者无任何区别）指针和数组（Array）数组名一位数组名a是个指针常量它存放的是一维数组第一个元素的地址，它的值不能被改变一维数组名指向的是数组的第一个元素。下表和指针的关系a[i]==*（a+i）下标和指针的关系假设指针变量的名字为p则p+i的值是p+i*（p所指向的变量所占的字节数）指针变量的运算指针变量不能相加，乘除。如果两指针变量属于同一数组，则可以相减指针变量可以相减一整数，前提是最终结果不能草果指针的范围p+i的值是p+i*(p所指向的变量所占的字节数)p-i的值是p-i*（p所指向的变量所占的字节数）p++《==》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位，美一个字节都占一个地址。指针变量都只占四个字节p=&x表示p只代表x的第一个字节的地址如何通过函数修改时惨的值#includestdio.hvoidf（int*q）//函数声明intmain(void){inti=9;int*p=&i；//等效为int*p;p=&i;printf(%p\n,p)；//%P表示输出指针变量所指向的元素的地址例如此例中就输出的事i的地址。return0;}voidf(int**q){*q=(int*)0xFFFFFFFF；//（int*）表示强制转换0xFFFFFFFF为地址，如果不强制转换0xFFFFFFFF只表示一个十六进制的数}如果想改写一个变量的值，只需要发送它的地址给被掉函数，否则无法实现对主函数中变量的值的改变。结构体：为什么会出现结构体：为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体：（是c++中类的过度）是用户根据实际需要自己定义的复合数据类型如何使用结构体：structStudent={1000,”zhangshan”,20};结构体Structsudent*pst=&st;1;st.sid2.pst-sidPst所指向的结构体中的sid这个成员注意事项；结构体变量不能加减乘除，但是可以相互赋值普通结构体变量和结构体指针变量作为函数传参的问题#includestdio.h#includestring.h//一串，一行struct结构体Student{intsid;charname[200];intage;};//分号不能省intmain(void){structStudentst={1000,zhangshan,20};printf(%d%s%d\n,st.sid,st.name,st.age);st.sid=99;strcpy(st.name,lisi);//st.name=lisi;errorst.age=22;printf(%d%s%d\n,st.sid,st.name,st.age);//printf(%d%s%d\n,st);return0;}结构体2#includestdio.h#includestring.h//一串，一行struct结构体Student{intsid;charname[200];intage;};//分号不能省intmain(void){结构体StructStudentst={1000，“张三”，20}；//st.sid=99;第一种方式StructStudent*pst；//定义一个指针变量，此指针变量只能存放我们自己定义的StructStudent类型的变量的地址Pst=&st;Pst-sid=99;//pst-sid等价于（*pst）.sid而（*pst）.sid等价于st.sid,所以pst-sid=st.sidreturn0；}第八次课:结构体：1：为什么会出现结构体为了表示一些复杂的数据，而普通的基本类型变量无法满足要求2：什么叫做结构体用户根据实际需要自己定义的复合数据类型3：如何使用结构体算法1：#includestdio.hstructStudent{intsid;charname[100];intage;};intmain(){structStudentst={2013213990,wangchuankun,20};printf(%d%s%d\n,st.sid,st.name,st.age);return0;}输出结果：————————————--2013213990wangchuankun2请按任意键继续...有两种方式：1：4：注意事项结构提变量不能加减乘除，但是可以相互赋值。结构提变量和结构体指针变量作为函数传参算法2：算法目的：通过结构体调用指针给主函数中结构体变量赋值#includestdio.h#includestring.hstructStudent{intsid;charname[200];intage;};voidf(structStudent*pst){(*pst).sid=2013213990;strcpy(pst-name,wangchuankun);pst-age=22;}intmain(){structStudentst;f(&st);printf(%d%s%d\n,st.sid,st.name,st.age);return0;}运行结果：——————————————————2013213990wangchuankun22请按任意键继续...——————————————————算法3：算法目的：通过结构体调用指针给主函数中结构体变量赋值并且通过函数调用将主函数中的结构体变量依次输出。#includestdio.h#includestring.hstructStudent{intsid;charname[100];intage;};voidf(structStudent*pst){(*pst).sid=2013213990;strcpy(pst-name,汪传坤);pst-age=20;}voidg(structStudent*pst){printf(学号：%d\n姓名：%s\n年龄：%d\n\n,pst-sid,pst-name,pst-age);}intmain(){structStudentst;f(&st);g(&st);return0;}运行结果：学号：2013213990姓名：汪传坤年龄：20请按任意键继续...跨函数使用内存必须要通过动态分配来完成！算法4：跨函数使用内存必须通过动态分配内存来实现#includestdio.h#includemalloc.hintf(int**q){inti;*q=(int*)malloc(16);/*for(i=0;i4;i++){printf(%d\n,q[i]);}*/return0;}intmain(){inti;int*p;f(&p);for(i=0;i4;i++){scanf(%d,&p[i]);}for(i=0;i4;i++){printf(%d\n,p[i]);}return0;}运行结果：7845891278458912请按任意键继续...算法总结：通过把指针变量的地址发给形参变量q（int**q表示q是存放int*类型变量的地址q本身是一个变量，）算法5：#includestdio.h#includemalloc.hstructStudent{intsid;intage;};structStudent*CreateStudent(void);voidShowStudent(structStudent*);intmain(){structStudent*ps;ps=CreateStudent();ShowStudent(ps);return0;}voidShowStudent(structStudent*pst){printf(%d%d\n,pst-sid,pst-age);}structStudent*CreateStudent(void){structStudent*p=(structStudent*)malloc(sizeof(structStudent));p-sid=99;p-age=88;returnp;}运算结果：9988请按任意键继续...注：只能通过动态分配内存通过调用函数分配内存才有效。数据结构正式课程模块一：算法1；静态调用函数：#includestdio.hintf(){intj=20;returnj;}intmain(){inti;i=f();printf(%d\n,i);return0;}#includestdio.h#includemalloc.h#includestdlib.hstructArr//定义数据类型,数据类型名为structArr，该数据类型含有三个成员。没有定义变量{int*pBase;//存储第一个元素的地址intlen;intcnt;//当前有效元素的个数//intincrement;//自动增长因子};voidinit_arr(structArr*pArr,intlen);boolappend_arr(structArr*pArr,intval);//追加boolinsert_arr(structArr*pArr,int