《郝斌自学数据结构大纲笔记高清免下载券》由会员分享，可在线阅读，更多相关《郝斌自学数据结构大纲笔记高清免下载券（54页珍藏版）》请在金锄头文库上搜索。
1、数据结构概述（教材选用严蔚敏、吴伟民，该书程序是伪算法 具体的程序是高一凡,西电的，大牛，只有 程序。还有一本书，台湾的黄国瑜自己写的 只有思路，程序是另外一个合作的清华的写 的，可惜很多错的。 ） 学完数据结构之后会对面向过程的函数有一个更深的了解 定义 我们如何把现实中大量而复杂的问题以特定的数据类型（单 个数据怎样存储？）和特定的存储结构（个体的关系） 保存到主存储器（内存）中，以及在此基础上为实现某个功能 （比如查找某个元素，删除某个元素，对所有元素进行排序） 而执行的相应操作，这个相应的操作也叫算法。 （比如班里有 15 个人，其信息量也许一个数组就搞定了，但是假如 10000 个，
2、 怎么办？内存也许没有这么多连续的空间，所以我们改用链表， you see 这就是与存储有关系。又比如，人事管理系统的信息存储， 因为存在着上下级的关系，所以数组和链表就无能为力了， 这时候我们用树，再比如我们做的是交通图，站和站之间肯定要连通，这 时候以上的存储方式又无能为力了，所以我们又有了图。图 就是每个结点都可以和其他结点产生联系。所以当我们要解决 问题时，首先要解决的是如何把这些问题转换成数据，先保存 到我们的主存中， ） 数据结构 = 个体 + 个体的关系 算法 = 对存储数据的操作 算法 解题的方法和步骤 衡量算法的标准 1、时间复杂度 大概程序要执行的次数，而非执行的时间。 2
3、、空间复杂度 算法执行过程中大概所占用的最大内存 3、难易程度（主要是应用方面看重） 4、健壮性（不能别人给一个非法的输入就挂掉） 数据结构的地位 数据结构是软件中最核心的课程 程序 = 数据的存储数据的操作可以被计算机执行的语言（已经提供） （学完数据结构，想用一种语言去实现它，必须有指针，数据结构 java 版，就胡扯，变味，因为我们要讲链表，就是通过指针链在一起的。比如 在 java 中 A aa = new A();本质上，aa 是个地址） 预备知识 指针 指针的重要性： （内存是可以被 CPU 直接访问的，硬盘不行 主要靠地址总线，数据总线，控制总线。 ） 指针是 C 语言的灵魂 定
4、义 地址 地址就是内存单元的编号 从 0 开始的非负整数 范围：0-FFFFFFFF0-4G-1（地址线是 32 位，刚好控制 2 的 32 次） 指针： 指针就是地址 地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数（不能加乘除，只能减） 分类： 1、基本类型的指针 2、指针和数组的关系 结构体（C+中用类也能实现） 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求 什么叫结构体 结构体是用户根据实际需要自己定义的复合数据类型 # include #include # include struct Student int sid;
5、 char name200; int age; ; int main(void) struct Student st = 1000,“zhangsan“,20; printf(“%d,%s,%dn“,st.sid,st.name,st.age); st.age=25; st.sid=100000; strcpy(st.name,“list“); printf(“%d,%s,%dn“,st.sid,st.name,st.age); return 0; 如何使用结构体 两种方式： struct Student st = 1000, “zhangsan“, 20 struct Student * p
6、st = / struct Student * pst; pst = printf(“请输入您需要分配数组的个数!“); scanf(“%d“, int *pArr = (int*)malloc(sizeof(int)*len); *pArr = 4; pArr1= 5; printf(“%d,%dn“,*pArr,pArr1); free(pArr); return 0; （java 中 A aa = new A();其实就是 A *p = (A *)malloc(sizeof(A)） 模块一：线性结构【把所有的结点用一根直线穿起来】 连续存储【数组】 1、什么叫做数组 元素类型相同，大小相
7、等（数组传参，只要传进去首地址和长度就行） 2、数组的优缺点： 优点： 存取速度快 缺点： 事先必须知道数组的长度 插入删除元素很慢 空间通常是有限制的 需要大块连续的内存块 插入删除元素的效率很低 /数组的举例 #include #include /包含了 malloc 函数 #include /包含了 exit 函数 #include /scanf 函数 struct Arr/定义了一个数据类型，不是变量，该数据类型是 struct Arr，该数据类型含有三个 成员 pBase，len，cnt int *pBase;/存储的是数组的第一个元素的地址 int len;/数组所能容纳的最大的元
8、素的个数 int cnt;/当前数组的有效元素的个数 ; void init_arr(struct Arr *pArr,int length);/初始化 bool append_arr(struct Arr *pArr,int val);/追加 bool insert_arr(struct Arr *pArr,int pos,int val); bool delect_arr(struct Arr *pArr,int pos,int * pval); int get(struct Arr *pArr, int pos, int *pval); bool is_empty(struct Arr
9、*pArr); bool is_full(struct Arr *pArr); void sort_arr(struct Arr *pArr); void show_arr(struct Arr *pArr); void inversion_arr(struct Arr *pArr); int main(void) int val; int pos;/在第 pos 个元素后插入 struct Arr arr; init_arr( append_arr( append_arr( append_arr( append_arr( append_arr( show_arr( printf(“删除后:n
10、“); if(delect_arr( printf(“您删除的元素是:%dn“,val); else printf(“删除不成功！n“); show_arr( printf(“输入插入元素的位置n“); scanf(“%d“, insert_arr( printf(“在第%d 个元素后插入后的数组：n“,pos); show_arr( printf(“倒置后:n“); inversion_arr( show_arr( printf(“排序后升序:n“); sort_arr( show_arr( get( printf(“获取数组中第二个元素：%dn“ ,val); / printf(“%dn“
11、 ,arr.len); return 0; /数组初始化 void init_arr(struct Arr *pArr,int length) pArr-pBase=(int *)malloc(sizeof(int)*length); if(NULL=pArr-pBase) printf(“动态内存分配不成功“); exit(-1);/终止整个程序 else pArr-len=length; pArr-cnt=0; return; /表明函数运行终止 void show_arr(struct Arr *pArr) if(is_empty(pArr) printf(“数组为空！n“); else
12、 for (int i=0;icnt;+i) printf(“%d “,pArr-pBasei); printf(“n“); bool is_empty(struct Arr *pArr) if(pArr-cnt = 0) return true; else return false; bool append_arr(struct Arr *pArr,int val)/追加 /满则返回 false if (is_full(pArr) return false; else pArr-pBasepArr-cnt=val; (pArr-cnt)+; return true; /判断数组是否已满 bo
13、ol is_full(struct Arr *pArr) if(pArr-cnt = pArr-len) return true; else return false; /在第 pos 位置后插入 val bool insert_arr(struct Arr *pArr,int pos,int val) if(pospArr-cnt+1|poscnt-1;i=pos-1;i-) pArr-pBasei+1=pArr-pBasei; pArr-pBasepos=val; pArr-cnt+; return true; /删除 bool delect_arr(struct Arr *pArr,in
14、t pos,int * pval) if( (is_empty(pArr) return false; if(pospArr-cnt)/1 2 3 4 5 return false; *pval=pArr-pBasepos-1; for(int i=pos;icnt;+i) pArr-pBasei-1=pArr-pBasei; pArr-cnt-; return true; /倒置 void inversion_arr(struct Arr *pArr)/5 4 3 2 1 int i=0; int j=pArr-cnt-1; int t; while (ipBasei; pArr-pBase
15、i=pArr-pBasej; pArr-pBasej=t; +i; -j; return; /排序 冒泡 升序 void sort_arr(struct Arr *pArr) int i,j; int t; for(i=0; icnt-1; +i) for(j=i+1; jcnt; +j) if(pArr-pBaseipArr-pBasej) t=pArr-pBasei; pArr-pBasei=pArr-pBasej; pArr-pBasej=t; /get 某个值 123456 int get(struct Arr *pArr, int pos, int *pval) * pval=pArr-pBasepos-1; return * pval; /数组的举例 typedef 的用法 #include typedef struct Student int sid; char name100; char sex; STU,*PSTU; int main(void) STU st;/
