郝斌数据结构笔记.docx

《郝斌数据结构笔记.docx》由会员分享，可在线阅读，更多相关《郝斌数据结构笔记.docx（56页珍藏版）》请在三一文库上搜索。

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

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

3、是为了以后能看懂更高级的语言*p就代表一个变量，例如i。ini*p表示定义一个存放整形变量的地址的指针变量。程序运行完，内存就终止了。复习：I：指针：im*pp是个变量名字，用来存放地址，只能存储int型变量的地址指针的重要性：是C语言的灵魂，定义地址线cpuiA内存O控制线1OOOO数据线地址内存单元的编号(CPU只能访问内存，不能访问硬盘)从。开始的非负整数，范围为04g-1指针就是地址，地址就是指针指针变量是存放内存单元地址的变量指针和指针变量不一样指正的本质是一个操作受限的非负整数分类：Int*p;Int*j;Inti=10;P=&1;(1).把i的地址赋给i,*p就指向了I(2).P

4、和i没有任何的关系(3)*p就是iP=IOZZerrorI=*jerror1根木类型的指针(P=&i表示指针变量存储i的地址，但是P为p,i为i两者无任何关系，但是*p和i却是等效的两者可以互换)变量不进行初始化，会是一个随机数的原因。2:指针结构体3:动态内存的分配和释放。4：内存的根本单位是字节5：&为取地址符号6:# includevoidf(int*p)(*p=100)intmain()(inti=9；f(&i)printf(i=%dn,i);return0I如何实现被掉函数修改主调函数中普通变量的值1：实参为相关变量的地址1&i)2：形参为以该变量的类型Iinl型)为类型的指针变量(

5、指针变量P)3：在被调函数中通过*形参变量名的方式就可以修改主函数中普通变量的值(*p和i可以等效替换两者无任何区别)指针和数组(Array)数组名一位数组名a是个指针常量inta=1,2,345;在内存中开辟了一个连续的5个整形变量的内存空间。它们是共生共亡。它存放的是一维数组第一个元素的地址，、它的值不能被改变是错误的！一维数组名指向的是数组的第一个元素。下表和指针的关系ai*(a+i)下标和指针的关系假设指针变量的名字为P则p+i的值是p+i*(P所指向的变量所占的字节数)指针变量的运算指针变量不能相加，乘除。如果两指针变量属于同一数组，则可以相减指针变量可以相减一整数，前提是最终结果不

6、能草果指针的范围Pi的值是p+i*(P所指向的变量所占的字节数)p-i的值是p-i*(P所指向的变量所占的字节数)p+=p+1如何通过被调函数修改主函数中一位数组的内容两个参数存放数组首元素的指针变量存放数组元素长度的整形变量# includestdio.hvoidshow-array(int*p,intIen)(p2=-l;/p0=*pp21=*(p2)=*(a+2)=af21pi此时就是主函数的ai)intmain(void)(inta5=11,2,3,4,5;show_arraya(a,5)/a等价于&a0,&a0本身就是int*类型return0一个double占八个字节，一个字节是8

7、位，美一个字节都占一个地址。指针变量都只占四个字节(无论指针变量指向的对象占多少字节，它只占4个字节J指针变量只占4个字节原因：在32位的操作系统中，一共有32根地址总线，可以有2的32次方大小的地址编码，所以需要4个字节的大小来表示，所以32位的操作系统中，指针的大小是4个字节。P=&x表示p只代表X的第一个字节的地址如何通过函数修改实参的值#includevoidf(int*q)函数声明intmain(void)(inti=9;inl*p=&i；/等效为ini*p;p=&i;Primf(pn”,p)；/%P表示输出指针变量所指向的元素的地址例如此例中就输出的事i的地址.return0;)v

8、oidf(int*q)(*q=(inl*)0xFFFFFFFF;/(int*)表示强制转换OXFFFFFFFF为地址，如果不强制转换OXFFFFFFFF只表示一个十六进制的数)如果想改写一个变量的值，只需要发送它的地址给被掉函数，否则无法实现对主函数中变量的值的改变。结构体：为什么会出现结构体：为了表示一些复杂的数据，而普通的根本类型变量无法满足要求什么叫结构体：(是c+中类的过度)是用户根据实际需要自己定义的复合数据类型如何使用结构体:structStudent=1000,vZhangshanw,20);结构体Structsudent*pst=&st;1;st.sid2.pst-sidPst

9、所指向的结构体中的sid这个成员考前须知；结构体变量不能加减乘除，但是可以相互赋值普通结构体变量和结构体指针变量作为函数传参的问题#include#includes【ring.h一串，一行struct结构体Student(intsid;charname200;intage;)；分号不能省intmain(void)(structStudentst=1000.,zhangshan,20);printf(%d%s%dn,st.sid,st.name,stage);st.sid=99;strcpy(st.name,lisi);/st.name=lisi,r;errorst.age=22;printf(

10、d%s%dn,st.sid,st.name,stage);/printf(,%d%s%dn,st);returnO;)结构体2#include#include/串，一行struct结构体Student(intsid;charname200;intage;);分号不能省intmain(void)结构体StructStudentst=1000,“张三”，20；/sl.sid=99;第一种方式StructStudent*pst；定义一个指针变量，此指针变量只能存放我们自己定义的StructStudent类型的变量的地址Pst=sid=99Jpsl-sid等价于*pst).sid而(*psl).si

11、d等价于sl.sid,所以pst-sid=st.sidreturn0；I第八次课：结构体：1：为什么会出现结构体为了表示一些复杂的数据，而普通的根本类型变量无法满足要求2：什么叫做结构体用户根据实际需要自己定义的复合数据类型3：如何使用结构体算法1：#includestructStudentintsid;charname100;intage;1；intmain()(structStudentst=2013213990,wangchuankun,20prinlf(,%d%s%dnst.sid,st.name,st.age);returnO;输出结果:2013213990Wangchuankun2

12、请按任意键继续.有两种方式：1：4：考前须知结构提变量不能加减乘除，但是可以相互赋值。结构提变量和结构体指针变量作为函数传参算法2：算法目的：通过结构体调用指针给主函数中结构体变量赋值#include#includestructStudent(intsid;charname200;intage;)；voidf(structStudent*pst)(*pst).sid=2013213990;strcpy(pst-name,wangchuankun);psl-age=22;)intmain()(structStudentst;f(&st);printf(,%d%s%dn,st.sid,st.nam

13、e,st.age);returnO;运行结果:2013213990Wangchuankun22请按任意键继续.算法3：算法目的：通过结构体调用指针给主函数中结构体变量赋值并且通过函数调用将主函数中的结构体变量依次输出。#include#includestructStudentintsid;charname100;intage;)；voidf(structStudent*pst)(*pst).sid=2013213990;strcpy(pst-name,汪传坤)；pst-age=20;)voidg(structStudent*pst)(printf(,学号：%dn姓名：%sn年龄：%dnn,ps

14、l-sid,pst-name,pst-age);)intmain()structStudentst;g(&st);g(si)速度慢，并且耗内存return0;)运行结果：学号：2013213990姓名：汪传坤年龄：20请按任意键继续.*p=(int*)malioc(4);Inlmain()Int*p;Foo(&p);)DVoidf(int*p)(*p=(int*)malloc(4);IIntmain()Int*p;F(p);Free(p);)练习程序：#include#includevoidf(int*p)*p=(int*)malloc(sizeof(int);*p=1000;)intmain

15、)int*p;foo(&p);printf(,%dn,*p);free(p);return0;I看懂以下程序：#include#includestructStudent)intage;ininum;1;Student*get(S(udent*ps)*ps=(Student*)malloc(sizeof(Student);(*ps)-age=12;(*ps)-num=44;return*ps;)voidshow(Student*ps)prin(f(,%d%dn,ps-age,ps-num);free(ps);intmain()Student*sl;sl=get(&sl);show(s1);re

16、turn0;I算法4：跨函数使用内存必须通过动态分配内存来实现# include# includeintf(int*q)(inti;*q=(int*)malloc(16);/malloc函数返EI的是第一个字节的地址，。!是这个地址没有类型，所以要强制转换一下。*for(i=0;i4;i+)printf(%dn,qi);returnO;)intmain()(inti;int*p;f(&p)；for(i=0;i4;i+)(scanf(,%dpi);)for(i=0;i4;i+)(printf(%dn,pi);)retum0;)运行结果：7845891278458912请按任意键继续.算法总结：通

17、过把指针变量的地址发给形参变量q(int*q表示q是存放int*类型变量的地址q本身是一个变量，)算法5：# include# includestructStudent(intsid;intage;)；structStudent*CreateStudent(void);voidShowStudent(structStudent*);intmain()(structStudent*ps;ps=CreateSiudentO;ShowStudent(ps);retum0;)voidShowStudent(structStudent*pst)(printf(,%d%dn,pst-sid,pst-age

18、);)structStudent*CreateStudenl(Void)(structStudent*p=(structStudent*)malloc(sizeof(structStudent);p-sid=99;p-age=88;returnp;)运算结果：9988请按任意键继续.注：只能通过动态分配内存通过调用函数分配内存才有效。数据结构正式课程模块一：线性结构(把所有的结点用一根直线穿起来J连续存储【数组】离散存储【链表】I.类型相同，元素大小相同。算法1；静态调用函数：#includeintf()(intj=20;returnj;Iintmain()(inti;i=f()；printf

19、dn,i);return0;)#include#include#includeSlrUClArr/定义数据类型，数据类型名为StnICtArr,该数据类型含有三个成员。没有定义变量(int*pBase;/存储第一个元素的地址intIen，数组所能容纳最大元素的个数intent;当前有效元素的个数/intincrement，自动增长因子voidinit-arr(structArr*pArr,intlen);blappend-arr(structArr*pArr,intval);追力IJboolinsert_arr(structArr*pArr,inlpos,intelem);booldel

20、ete_arr();iniget();boolis_empty(structArr*pArr);boolis_full(slructArr*pArr);voidsort-arr();voidshow_arr(structArr*pArr);voidinversion-arr();intmain()(SirUClAlTarr;已经分配好内存，数组没有形成init_arr(fcarr,10);/append_arr(&arr,1);if(append_arr(&arr,1)(Prinlf(追加成功n”)；)else(Prinlf(追加失败n”)；I/append_arr(&arr,2);if(ap

21、pend_arr(&arr,2)Primf(追加成功n”);elsePrinlf(追加失败n”);/append_arr(&arr,3);if(append_arr(&arr,3)(Primf(追加成功n”);)else(Prinlf(追加失败n”);)/append_arr(&arr,8);if(append_arr(&arr,78)(Prinlf(追加成功n”);Ielse(Prinlf(追加失败n”);)if(append_arr(&arr,1(X)O)(Prinlf(追加成功n”);Ielse(Prinlf(追加失败n”);)if(append_arr(&arr,188)PrinIf(

22、追加成功n);elsePrimf(追加失败n”)；Iif(append_arr(&arr,89)(Primf(追加成功n”)；)else(Prinlf(追加失败n”)；)if(append-a(pBase=(int*)malloc(sizeof(int)*length);(*pArr).len=99;if(NULL=pArr-pBase)(PrinIf(动态内存分配失败！n);exil(-l);/终止整个程序elsepArr-len=length;pArr-cnt=O;voidshow_arr(structArr*pArr)if(is-empty(pArr)Prinlf(数组为空！n);els

23、efor(inii=O;icnt;+i)(printf(%dn,pArr-pBaseil);printf(n);boolis_emply(structArr*pArr)if(0=pArr-cnt)returntrue;else(returnfalse;)Iboolis_full(slructArr*pArr)(if(pArr-cnl=pArr-len)(returntrue;)else(returnfalse;)Iblappend-arr(structArr*pArr,intval)(if(is-full(pArr)(returnfalse;Ielse(pArr-pBasepArr-cnll=

24、val;pArr-cnt+;returntrue;boolinsert_arr(structArr*pArr,intpos,inlelem)if(pos(pArr-cnt2)pArr-len=pArr-cnt)(printf(无法插入元素n);)else(for(inti=pArr-cnt-l;i=pos-1;i)pArr-pBasei+l=pArr-pBaseil;pArr-pBasepos-1=elem;printf(在第d个元素之前插入d成功n,pos,elem);)I#include#include#includeSIrUCtArr/定义数据类型，数据类型名为StrUCtArr,该数据

25、类型含有三个成员。没有定义变量(int*pBase;/存储第一个元素的地址intIen;intent，当前有效元素的个数inincrement;自动增长因子)；voidinit_arr(structArr*pArr,intlen);boolappend-arr(structArr*pArr,inlval);追加blinsert_arr(structArr*pArr,inlpos,inlelem);booldelete_arr();intget();boolis_empty(structArr*pArr);boolis_full(structArr*pArr);voidsort-arr();vo

26、idshow_arr(structArr*pArr);voidinversion-arr();intmain()(SirUClAlTarr;已经分配好内存，数组没有形成init_arr(fcarr,100);/append_arr(&arr,1);if(append_arr(&arrt1)(Prinlf(追加成功n”)；)else(PrinIf(追加失败n”)；I/append_arr(&arr,2);if(append_arr(&arr,2)(Prinlf(追加成功n”)；)else(PrinIf(追加失败n”)；)/append_arr(&arr,3);if(append_arr(&arr

27、3)Primf(追加成功n);Primf(追加失败n);/append_arr(&arr,8);if(append_arr(&arr.78)PrinIf(追加成功n);elsePrinIf(追加失败n“);if(append_arr(&arr,1(X)O)PrinIf(追加成功n);elsePrinIf(追加失败n“);if(append_arr(&arr,188)PrinIf(追加成功n);elsePrinIf(追加失败n“);if(append_arr(&arr.89)PrinIf(追加成功n);elsePrimf(追加失败n”);if(append_arr(&arr,8)(PrinIf

28、追加成功n”)；)else(Primf(追加失败n)show-arr(&arr);insert-arr(pBase=(int*)malloc(sizeof(int)*length);(*pArr).len=99;if(NULL=pArr-pBase)(Primf(动态内存分配失败！n)；exi(-l);/终止整个程序)elsepArr-len=length;voidshow_arr(structArr*pArr)(if(is-empty(pA)(Prinlf(数组为空！n);)else(for(inti=O;icnt;+i)(printfC,%dpAr-pBasei);printf(n);b

29、lis_emply(structArr*pArr)(if(0=pArr-cnt)(returntrue;Ielse(returnfalse;boolis_full(structArr*pArr)if(pArr-cnt=pArr-len)returntrue;)else(returnfalse;I)boolappend-arr(structArr*pArr,intval)(if(is-full(pArr)(returnfalse;)else(pArr-pBasepArr-cntl=val;pArr-cnt+;returntrue;)Iboolinsert_arr(structArr*pArr,i

30、ntpos,intelem)(/printf(”请输入要插入的位置和插入的数字：”)；/scanf(%d%dnn,&pos,&elem);if(pos(pArr-cnt+1)pArr-len=pArr-cntpospArr-len)Prinlf（无法插入元素n）;for(inti=pArr-cnl-1;i=pos-1i)pArr-pBasei+l=pArr-pBaseil;pArr-pBasepos-11-elem;Prinlf(在第d个位置插入d成功n,pos,elem);pArr-cnt+;show-arr(pArr);returntrue;#include#includeWinclude

31、structArr定义数据类型，数据类型名为StrUetArr,该数据类型含有三个成员。没有定义变量(int*PBaSe;存储第一个元素的地址intIen;intCnt;当前有效元素的个数/intincrement;自动增长因子)；voidinit_arr(structArr*pArr,intlen);boolappend_arr(structArr*pArr,intval);追力口boolinsert_arr(structArr*pArr,intpos,intelem);boolis_empty(structArr*pArr);boolis_full(structArr*pArr);void

32、show_arr(structArr*pArr);voidget(structArr*pArr,intpos);voidsort_arr(structArr*pArr);voidinversion_arr(structArr*pArr);booldelete_arr(structArr*pArr,intpos,inte);intmain()(structArrarr;已经分配好内存,数组没有形成init_arr(&arr,100);intposl;intpos;intelem;inte;/append_arr(&arr,1);if(append_arr(&arr,1)(printf(追加成功n

33、);else(printf(追加失败n);/append_arr(&arr,2);if(append_arr(&arr,2)(printf(追加成功n);else(printf(追加失败n);)/append_arr(&arr,3);if(append_arr(&arr,3)(printf(追加成功n);else(printf(追加失败n);)/append_arr(&arr,8);if(append_arr(&arr,78)(printf(追加成功n);)else(printf(追加失败n);)if(append_arr(&arr,1OOO)(printf(追加成功n);)elseprint

34、f(追加失败n);)if(append_arr(&arr,188)(printf(追加成功n);)else(printf(追加失败n);)if(append_arr(&arr,89)(printf(追加成功n);)else(printf(追加失败n);)if(append_arr(&arr,8)(printf(追加成功n);)else(printf(追加失败n);)show_arr(&arr);printf(请输入你要访问的元素位置：)；scanf(7z%d,z,&posl);get(&arr,posl);/printf(请输入要插入的位置和插入的数字：);/scanf(%d%dn”,&pos

35、elem);/insert_arr(&arr,pos,elem);/printf(请输入要插入的位置和插入的数字：);/scanf(%d%dn”,&pos,&elem);/insert_arr(&arr,pos,elem);/printf(请输入要插入的位置和插入的数字：);/scanf(%d%dn”,&pos,&elem);/insert_arr(&arr,pos,elem);/delete-arr(&arr,pos,e);/show_arr(&arr);/voidinversion_arr(&arr);voidsort_arr(&arr);show_arr(&arr);return0;

36、)voidinit_arr(structArr*pArr,intlength)pArr-pBase=(int*)malloc(sizeof(int)*length);(*pArr).Ien=99;if(NULL=pArr-pBase)(printf(动态内存分配失败!n)；exit(-D；终止整个程序)elsepArr-len=length;pArr-cnt-0;)voidshow_arr(structArr*pArr)(if(is_empty(pArr)(printf(数组为空!n);)else(for(inti=0;icnt;+i)(printf(zz%dzz,pArr-pBasei);p

37、rintf(n);)boolis_empty(structArr*pArr)(if(0=pArr-cnt)(returntrue;)else(returnfalse;)boolis_full(structArr*pArr)(if(pArr-cnt=pArr-1en)(returntrue;)else(returnfalse;)boolappend_arr(structArr*pArr,intval)(if(is_full(pArr)(returnfalse;)elsepArr-pBasepArr-cnt=val;pArr-cnt+;returntrue;)boolinsert_arr(stru

38、ctArr*pArr,intpos,intelem)(if(pos(pArr-cnt+l)pArr-len=pArr-cntpospArr-len)(printf(无法插入元素n)；)else(for(inti-pArr-cnt-l;i=pos-l;-i)pArr-pBasei+l=pArr-pBasei;pArr-pBasepos-l=elem;printf(在第%d个位置插入%d成功n”,pos,elem);pArr-cnt+;show_arr(pArr);returntrue;)voidget(structArr*pArr,intpos)inte;if(pospArr-cnt)(prin

39、tf(查无此数！n);)else(e=pArr-pBasepos-l;printf(第%d个元素为%dn”,pos,e);)booldelete_arr(structArr*pArr,intpos,inte)(printf(请输入你要删除元素的位置！)；scanf(%d,&pos);e=pArr-pBasepos-l;for(inti=pos-l;icnt-l;i+)pArr-pBasei=pArr-pBasei+l;)pArr-cnt一；printf(删除的第%d个元素为:%dn”,pos,c);)*voidinversion_arr(structArr*pArr)(inti,j;if(pArr-cnt%2=0)(j=pArr-cnt2;)else(j=(pArr-cnt-l)2;)for(i=l;ipBasei-l=pArr-pBasepArr-cnt-i;)*/voidsort_arr(structArr*pArr)(inti;intj;intt;for(i=pArr-cnt;i0;i-)(for(j=0;jpBasejpArr-pBasej+l)(t=pArr-pBasej+l;pArr-pBa