数据结构的总结

数据与结构知识点总结数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型（比如：结构体等）和特定的存储结构（比如：数组，链表等）保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如：查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。数据结构=个体+个体的关系算法=对存储数据的操作理解：如果数据都无法保存的话，如何对数据进行操作呢？这时候数据的存储是一个很关键的问题，那么我们就要通过特定的数据类型和特定的存储结构保存到内存中。那么问题来了：问题1：保存一个省的人事之间的关系就不能用链表或数组来实现，因为那样不能得知哪个是老大老二，谁是领导和属下，所以它无法体现，那么怎么办呢？——利用用树来实现，做一个人事管理系统问题2：如果是个交通图，开辟很多站点，那么我要在各站点间修路每个站点相同，或者说给出两个站点，系统能给出两站点间最短路径，那又该怎么办呢？——利用图来实现，使各个点之间相关联发现：把一个实际的问题如何保存在计算机里面，这是第一步要解决的问题。如果数据都不能保存，那还怎么对它操作呢？那么该如何保存呢？保存个体（特定的数据类型）；保存个体和个体之间的关系（特定的存储结构）。算法：解题的方法和步骤衡量算法的标准（前2条最关键）1、时间复杂度：大概程序要执行的次数，而非执行的时间2、空间复杂度：算法执行过程中大概所占用的最大内存3、难易程度4、健壮性：不能出现当给一个非法的数整个程序就挂了数据结构的地位：数据结构是软件中最核心的课程，几乎所有的编程语言都能找到数据结构的影子程序=数据的存储+数据的操作+可被计算机执行的语言预备知识指针指针的重要性：C语言的灵魂定义地址：内存单元的编号从0开始的非负整数范围：0—0FFFFFFFF【0-4G-1】指针：指针就是地址，地址就是指针指针变量是专门存放内存单元地址的变量指针本质是一个操作受限的非负数分类：1、基本类型的指针eg：#includestdio.hintmain(void){int*p;//p是个变量名字，int*表示p只能存放整形变量的地址inti=10;intj;p=&i;//p指向ij=*p;//等价于j=iprintf(i=%d,j=%d,*p=%d\n,i,j,*p);//10return0;}eg：#includestdio.hvoidf(int*p)//int*是变量p的数据类型,形参的名字是p，而不是*p{*p=100;}intmain(void){inti=9;f(&i);//实参必须为相关变量的地址printf(i=%d\n,i);//100return0;}2、指针和数组的关系eg：#includestdio.hintmain(void){inta[5]={1,2,3,4,5};//a==&a[0],它是常量值不能变a[3]=*(a+3);//a[i]==*(a+i)printf(%p\n,a+1);//%p是输出地址printf(%p\n,a+2);printf(%p\n,a+3);printf(%d\n,*a+3);//等价于a[0]+3return0;}eg：#includestdio.hvoidShow_Array(int*p,intlen){inti=0;p[0]=-1;//p[0]==*p;p[2]==*(p+2)==*(a+2)==a[2]//p[i]就是主函数的a[i]for(i=0;ilen;i++){printf(%d\n,p[i]);}}intmain(void){inta[5]={1,2,3,4,5};Show_Array(a,5);//a等价于&a[0]printf(%d\n,a[0]);//-1return0;}/*-12345-1*/eg：#includestdio.hintmain(void){double*p,*q,x=66.6;doublearr[3]={1.1,2.2,3.3};p=&x;//x占8个字节(8位)，一个字节一个地址q=&arr[0];printf(%p\n,q);//%p实际就是一16进制输出q=&arr[1];printf(%p\n,q);return0;}//相差8个字节无论指针变量指向谁，它本身只占4个字节。结构体为什么会出现结构体？为了表示一些复杂的数据，而普通的基本类型无法满足要求。什么叫结构体？是用户根据实际需要自己定义的复合数据类型。如何使用结构体？eg：#includestdio.h#includestring.hstructStudent{intsid;charname[10];intage;};//分号不能省intmain(void){structStudentst={1000,luxiong,20};printf(%d%s%d\n,st.sid,st.name,st.age);st.sid=99;//第一种方式structStudent*pst;pst=&st;pst-sid=99;//第二种方式pst-sid等价于(*pst).sid又等价于st.sid//st.name=lisi;//errorstrcpy(st.name,lisi);st.age=22;printf(%d%s%d\n,st.sid,st.name,st.age);//printf(%d%s%d\n,st);//errorreturn0;}注意事项：结构体变量不能相加减，但可以相互赋值；普通结构体变量和结构体指针变量作为函数传参的问题。eg：#includestdio.h#includestring.hvoidf(structStudent*pst);voidg(structStudent*pst);structStudent{intsid;charname[10];intage;};//分号不能省intmain(void){structStudentst;f(&st);g(&st);//printf(%d%s%d\n,st.sid,st.name,st.age);//第一种方式return0;}voidf(structStudent*pst){(*pst).sid=99;strcpy(pst-name,luxiong);//字符赋值用这个函数pst-age=22;}voidg(structStudent*pst)//第二种方式{printf(%d%s%d\n,pst-sid,pst-name,pst-age);}动态内存的分配和释放eg：#includestdio.h#includemalloc.hintmain(void){inta[5]={4,10,2,8,6};intlen;printf(请输入需要分配的数组的长度：len=);scanf(%d,&len);int*pArr=(int*)malloc(sizeof(int)*len);//pArr等价于a*pArr=4;//类似于a[0]=4;pArr[1]=10;//类似于a[1]=10;printf(%d%d\n,*pArr,pArr[1]);free(pArr);//把pArr所代表的如20个字节释放return0;}假设动态构造一个int型一维数组eg：#includestdio.h#includemalloc.hintmain(void){inta[5];//如果int占4个字节的话，则本数组总共包含有20个字节每4个字节被当做一个int变量来使用intlen;int*pArr;inti;/*动态的构造一位数组*/printf(请输入你要存放的元素的个数:);scanf(%d,&len);//假如是5,则下面pArr指向是前4个字节,不能理解为指向第一个字节pArr=(int*)malloc(4*len);//12行/*12．．行动态的构造一个动态数组．．．．．．．．．．．．类似．．intpArr[len]．．．．．．．．．．．．，每个．．．元．素是．．int．．．类型．．pArr．．．．是数组名．．．．,．和静态数组用法一样。而静态．．．．．．．．．．．．．的数组不能这样弄．．．．．．．．,．需先给定长度．．．．．．*//*对一位数组进行操作如：对动态一位数组进行赋值*/for(i=0;ilen;i++)scanf(%d,&pArr[i]);/*对一位数组进行输出*/printf(一位数组的内容是：\n);for(i=0;ilen;i++)printf(%d\n,pArr[i]);free(pArr);}//释放掉动态分配的数组，动态的随时都可以释放，而不需要程序终止再释放跨函数使用内存问题：#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);}模块一：线性结构【把所有的结点用一根直线穿起来】连续存储[数组]1、什么叫数组：元素数据类型相同，大小相等2、数组的优缺点：优点：存取速度很快缺点：插入删除元素很慢，空间通常是有限制的离散储存[链表]定义：n个结点离散分配；彼此通过指针相连；每个结点只有一个前驱结点，每个结点只有一个后续结点；首结点没有前驱结点，尾结点没有后续结点。专业术语：头结点：头结点的数据类型和首结点类型一样；第一个有效结点之前的那个结点；头结点并不存放有效数据；加头结点的目的主要是为了方便对链表的操作。首结点：第一个存放有效数据的结点。尾结点：最后一个存放有效数据结点。头指针：指向头结点的指针变量。尾指针：指向尾结点的指针变量。确定一个链表需要几个参数？只需要一个参数：头指针。因为我们通过头指针可以推算出链表的其他所有信息。分类：单链表：双链表：每一个结点有两个指针域循环链表：能通过任何一个结点能找到其他所有结点非循环链表算法：遍历查找清空销毁求长度排序狭义的算法是与数据的存储方式密切相关广义的算法是与数据的存储方式无关泛型：利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的。插入结点（伪算法）：q-next=p-next;千万不能互换顺序p-next=q;删除结点（伪算法）：p-next=p-next-next;错误写法改写了p-next的值free(p-next);r=p-next;正确写法p-next=p-next-next;free(r);链表的创建和链表的遍历、插入、删除、排序、计算长度等算法演示：#includestdio.h#includemalloc.h#includestdlib.htypedefstructNode{intdata;//数据域structNode*next;//指针域}NODE,*PNODE;//NODE等价于structNode，PNODE等价于structNode*PNODEcreate_list(void);voidtraverse_list(PNODEpHead);boolis_empty(PNODEpHead);intlength_list(PNODE);boolinsert_list(PNODE,int,int);booldelete_list(PNODE,i