《数据结构的总结》由会员分享，可在线阅读，更多相关《数据结构的总结（27页珍藏版）》请在金锄头文库上搜索。
1、数据与结构知识点总结数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型（比如：结构体等）和特定的存储结构（比如：数组，链表等）保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如：查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。 数据结构 = 个体 + 个体的关系算法 = 对存储数据的操作理解：如果数据都无法保存的话，如何对数据进行操作呢？这时候数据的存储是一个很关键的问题，那么我们就要通过特定的数据类型和特定的存储结构保存到内存中。那么问题来了：问题1：保存一个省的人事之间的关系就不能用链表或数组来实现，因为那样不能得知哪个是老
2、大老二，谁是领导和属下，所以它无法体现，那么怎么办呢？利用用树来实现，做一个人事管理系统 问题2：如果是个交通图，开辟很多站点，那么我要在各站点间修路 每个站点相同，或者说给出两个站点，系统能给出两站点间 最短路径，那又该怎么办呢？ 利用图来实现，使各个点之间相关联发现：把一个实际的问题如何保存在计算机里面，这是第一步要解决的问题。如 果数据都不能保存，那还怎么对它操作呢？那么该如何保存呢？保存个体（特定的数据类型）；保存个体和个体之间的关系（特定的存储结构）。算法：解题的方法和步骤 衡量算法的标准（前2条最关键） 1、时间复杂度：大概程序要执行的次数，而非执行的时间 2、空间复杂度：算法执行
3、过程中大概所占用的最大内存 3、难易程度 4、健壮性：不能出现当给一个非法的数整个程序就挂了数据结构的地位：数据结构是软件中最核心的课程，几乎所有的编程语言都能找到数据结构的影子 程序 = 数据的存储 + 数据的操作 + 可被计算机执行的语言预备知识指针指针的重要性：C语言的灵魂定义地址：内存单元的编号从0开始的非负整数范围：00FFFFFFFF【0-4G-1】 指针：指针就是地址，地址就是指针指针变量是专门存放内存单元地址的变量指针本质是一个操作受限的非负数 分类：1、基本类型的指针 eg：#includeint main(void)int *p;/p是个变量名字，int *表示p只能存放整
4、形变量的地址int i=10;int j;p=&i;/p指向ij=*p;/等价于j=iprintf(i=%d,j=%d,*p=%dn,i,j,*p);/10return 0;eg：#includevoid f(int *p)/int *是变量p的数据类型,形参的名字是p，而不是*p*p=100;int main(void)int i=9;f(&i);/实参必须为相关变量的地址printf(i=%dn,i);/100return 0; 2、指针和数组的关系eg：#includeint main(void) int a5=1,2,3,4,5;/a=&a0,它是常量值不能变 a3=*(a+3);/a
5、i=*(a+i) printf(%pn,a+1);/%p是输出地址 printf(%pn,a+2); printf(%pn,a+3); printf(%dn,*a+3);/等价于a0+3 return 0; eg：#includevoid Show_Array(int *p,int len)int i=0;p0=-1;/p0=*p;p2=*(p+2)=*(a+2)=a2/pi就是主函数的aifor(i=0;ilen;i+)printf(%dn,pi);int main(void)int a5=1,2,3,4,5;Show_Array(a,5);/a等价于&a0printf(%dn,a0);/-
6、1return 0;/*-1 2 3 4 5 -1*/eg：#includeint main(void) double *p,*q,x=66.6; double arr3=1.1,2.2,3.3; p=&x;/x占8个字节(8位)，一个字节一个地址 q=&arr0; printf(%pn,q);/%p实际就是一16进制输出 q=&arr1; printf(%pn,q); return 0;/相差8个字节 无论指针变量指向谁，它本身只占4个字节。结构体为什么会出现结构体？为了表示一些复杂的数据，而普通的基本类型无法满足要求。什么叫结构体？是用户根据实际需要自己定义的复合数据类型。如何使用结构体？
7、eg：#include#includestruct Studentint sid;char name10;int age;/分号不能省int main(void)struct Student st=1000,luxiong,20;printf(%d %s %dn,st.sid,st.name,st.age);st.sid=99;/第一种方式struct Student *pst;pst=&st;pst-sid=99;/第二种方式 pst-sid等价于(*pst).sid又等价于st.sid/st.name=lisi;/errorstrcpy(st.name,lisi);st.age=22;pr
8、intf(%d %s %dn,st.sid,st.name,st.age);/printf(%d %s %dn,st);/errorreturn 0;注意事项：结构体变量不能相加减，但可以相互赋值；普通结构体变量和结构体指针变量作为函数传参的问题。eg：#include#includevoid f(struct Student *pst);void g(struct Student *pst);struct Studentint sid;char name10;int age;/分号不能省int main(void)struct Student st;f(&st);g(&st);/printf
9、(%d %s %dn,st.sid,st.name,st.age);/第一种方式return 0;void f(struct Student *pst)(*pst).sid=99;strcpy(pst-name,luxiong);/字符赋值用这个函数pst-age=22;void g(struct Student *pst)/第二种方式printf(%d %s %dn,pst-sid,pst-name,pst-age);动态内存的分配和释放eg：#include#includeint main(void)int a5=4,10,2,8,6;int len;printf(请输入需要分配的数组的长
10、度：len=);scanf(%d,&len);int *pArr=(int *)malloc(sizeof(int)*len);/pArr等价于a*pArr=4; /类似于a0=4;pArr1=10;/类似于a1=10;printf(%d %dn,*pArr,pArr1);free(pArr);/把pArr所代表的如20个字节释放return 0;假设动态构造一个int型一维数组eg：#include#includeint main(void)int a5;/如果int占4个字节的话，则本数组总共包含有20个字节每4个字节被当做一个int变量来使用int len;int *pArr;int i
11、;/*动态的构造一位数组*/printf(请输入你要存放的元素的个数:);scanf(%d,&len);/假如是5,则下面pArr指向是前4个字节,不 能理解为指向第一个字节pArr=(int *)malloc(4*len);/12行 /* 12行动态的构造一个动态数组 类似int pArrlen，每个元素是int类型pArr是数组名,和静态数组用法一样。而静态的数组不能这样弄,需先给定长度 */ /*对一位数组进行操作 如：对动态一位数组进行赋值*/ for(i=0;ilen;i+) scanf(%d,&pArri); /*对一位数组进行输出*/ printf(一位数组的内容是：n); for(i=0;ilen;i+) printf(%dn,pArri); free(pArr); /释放掉动态分配的数组，动态的随时都可以释放，而 不需要程序终止再释放
