数据结构学习

你挡我一时,挡不了我一世

发布日期: 2019-01-22 13:02:28 浏览量: 1000
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

学习的过程更新中。。。这里我是个弟弟,先写着看。

  • 书籍:严蔚敏、吴伟民

  • 代码:高一凡(C、C++)

一、概述

1.1 定义

如何把现实中的大量而复杂的问题,以特定的数据类型 (个体存储)和存储结构(个体和个体的关系),保存到主存储器(内存)中。

1.2 算法

狭义的算法:依附于某种数据结构(范型就是广义的)

以及在此基础上为实现某个功能(比如删除、查找、排序元素等等)而对存储数据的相应操作(算法)。

1.3 解题算法和步骤

  • 衡量算法标准

  • 时间复杂度:

    • 程序大概执行次数,而非执行的时间time(时间—-次数)
    • 运行次数最多的步骤到底运行了几次
  • 空间复杂度:

    • 算法执行过程中大概所占用最大内存
  • 难易程度:易看懂

  • 健壮性:容错

1.4 地位

核心、内功

  • 比如语言:内存概念表示栈和堆只是分配内存的算法不一样。并不是内存中有一块内存叫栈或堆内存,再比如说函数:是按照压栈出栈的方式实现的。

  • 比如操作系统:线程:队列

  • 比如编译原理:语法树概念:树

  • 比如数据库:数据结构的简化版,解决数据存储问题:字段(事物属性)、记录(整体事物)、表(同一事物的集合)、外键(事物和事物的关系)、视图(简化查询)

程序 = 数据存储 + 数据操作 + 可执行语言

二、预备知识

指针——核心

指针是C的灵魂:

地址:内存单元的编号

内存是cpu唯一可以访问的大容量设备,不能访问硬盘,所以要把硬盘数据先导入内存。

cpu与内存间三条线(地址线、控制线、数据线)

  • 内存编号:0-FFFFFFFF(4G-1)———地址线(32位)2^32——编号不变,内容随意

  • 内存的基本划分单位:字节。

所谓的32位,是指机器字长32位,你可以简单的理解成CPU一次能处理的数据的长度是32位,也就是CPU的数据总线是32位。一般对应地址总线也就是32位,32位的地址总线能够索引2^32这么多个的存储单元的个数。数据线是32位,那么一个存储单元一般也是32位,也就是4Byte。

32位内存:32位最大内存为4G,但是由于主板等其实硬件还须要系统给予地址分配,实际最高约(3.25g)3.5G左右。

32位支持的内存:

  • 32位数的系统只能识别4G以下的内存。

  • 可以安装64位数,可以识别4G以上的内存。

  • 内存是计算机中重要的部件之一,它是与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的,因此内存的性能对计算机的影响非常大。内存(Memory)也被称为内存储器,其作用是用于暂时存放CPU中的运算数据,以及与硬盘等外部存储器交换的数据。只要计算机在运行中,CPU就会把需要运算的数据调到内存中进行运算,当运算完成后CPU再将结果传送出来,内存的运行也决定了计算机的稳定运行。

内存释放:操作系统回收了程序对此块内存使用权限,并非销毁。垃圾数据还在里面保存着。

内存是在操作系统统一管理下使用的:

  • 软件运行前需要向操作系统申请存储空间,在内存空闲空间足够时,操作系统将分配一段内存空间并将外存软件数据拷贝到内存中,启动运行。

  • 软件运行期间,该软件所占空间不再分配给其他软件。

  • 软件运行完毕,操作系统将回收该内存空间(不清空遗留数据),以便再次分配给其他软件使用。—-为什么很多语言中变量必须初始化的原因

读写控制—-控制线

数据传输—-数据线

  • 指针:指针=地址

  • 指针变量:存放内存单元地址(编号)的变量

  • 本质:操作受限的非负整数

  • 分类

    • 基本类型的指针:只能加减
    • 指针变量
  1. #include <stdio.h>
  2. int main(void)
  3. {
  4. int *p;//p是个变量名字(指针变量),int *表示p变量只能存储int类型变量的地址
  5. //普通变量前不能加*,常量和表达式前不能加&
  6. int i=10;//i的内容为10
  7. int j;//存放垃圾数字
  8. //j=*p;//error,p是个空指针,没有保存变量地址,*p代表了不确定单元的地址
  9. p=&i;//把i的地址发送给p,p的内容存的就是i的地址,就是p指向了i---*p就代表了i变量--修改p和i的值时互不影响
  10. //char ch='A';
  11. //p=&ch;//error,非int类型
  12. //p=10;//error,10是个整数,不是地址
  13. j=*p;//等价于j=i
  14. printf("%d,%d,%d\n",j,i,*p);// 10 10 10
  15. return 0;
  16. }

函数

如何通过被调函数修改主调函数中普通变量的值?

  • 实参为相关变量的地址—-&i

  • 形参为以该变量的类型为类型的指针变量—-int

  • 在被调函数中,通过*变量名的方式就可以修改主函数中变量的值—-*i

  1. #include <stdio.h>
  2. void f(int *i)//不是定义了*i的形参,而是定义一个形参名字为i,类型为int * ---存放整型变量地址---局部指针变量
  3. {
  4. *i=100;//地址
  5. }
  6. int main(void)
  7. {
  8. int i=9;
  9. f(&i);
  10. printf("i=%d\n",i);
  11. return 0;
  12. }

指针和数组

如何通过被调函数修改主调函数中一位数组的内容(参数)

p+i的值是p+i*(p所指向的变量所占的字节数)

  1. #include <stdio.h>
  2. void show_array(int * p,int len)//任意修改主函数中数组的值
  3. {
  4. int i=0;
  5. //p[2]=-1;//p[0]==*p---p指向的元素 p[2]==*(p+2)==*(a+2)==a[2]
  6. //p[i]就是主函数的a[i]
  7. for(i=0;i<len;i++)
  8. printf("%d\n",p[i]);
  9. }
  10. int main(void)
  11. {
  12. int a[5]={1,2,3,4,5};//a存放的是数组的第一个元素的地址,一维数组名是个指针常量,
  13. //它的值不能被改变,一维数组名指向的是数组的第一个元素。--a[0]
  14. //下标和指针关系:a[i]<==>*(a+i)
  15. a[3]==*(3+a);//----可以这样写3[a]----a(偏移地址)
  16. printf("%p\n",a+1);//地址连续,a指向第一个元素,a+1指向第二个元素(1下标)
  17. printf("%p\n",a+2);
  18. printf("%d\n",*a+3);//等价于a[0]+3=4
  19. show_array(a,5);//a等价于&a[0],&a[0]本身就是int*类型。
  20. //printf("%d\n",a[2]);// -1
  21. return 0;
  22. }
  1. #include <stido.h>
  2. int main()
  3. {
  4. double *p;//指针变量统一占4个字节
  5. double x=66;
  6. p=&x;//x占8个字节,1个字节是8位,1个字节一个地址,使用第一个字节的地址代表整体地址
  7. double arr[3]={12.12,123.1,3.2};
  8. double *q;
  9. q=&arr[0];
  10. printf("%p\n",q);//%p实际上就是以十六进制输出
  11. q=&arr[1];
  12. printf("%p\n",q);//与上面差8位
  13. return 0;
  14. }

指针的指针

同样改写值。——-发送地址就可以了。

  1. #include <stdio.h>
  2. void f(int **p)
  3. {
  4. *p= (int *) 0xFFFF5c77;//不安全
  5. }
  6. int main(void)
  7. {
  8. int i=9;
  9. int *p=&i;
  10. f(&p);
  11. printf("%p\n",p);
  12. return 0;
  13. }

结构体—-或类

  • 为什么会出现结构体?

    • 可以类比Java类的属性,为了表示复杂数据,普通的基本数据类型变量无法满足要求。
  • 什么叫结构体?

    • 结构体是用户根据实际需要自定义的一个数据类型
  • 如何使用结构体?

  1. #include <stdio.h>
  2. struct Student
  3. {
  4. int sid;
  5. char name[20];
  6. int age;
  7. };
  8. int main(void)
  9. {
  10. struct Student st={108472,"zhangsan",20};
  11. printf("%d,%s,%d\n",st.sid,st.name,st.age);
  12. st.sid=99;
  13. //st.name="lisi";//error 不能直接string赋值
  14. strcpy(st.name,"lisi");
  15. st.age=20;
  16. //printf("%d %s %d \n",st);//error
  17. struct Student * pst;//4字节,地址总线32位
  18. pst=&st;
  19. pst->sid=909;//等价于 (*pst).sid 等价于 st.sid
  20. //pst所指向的结构体变量中的sid这个成员
  21. return 0;
  22. }
  • 注意事项
    • 结构体变量中,不能四则运算,但可以相互赋值

结构体变量和结构体指针变量作为函数传参的问题

  1. #include <stdio.h>
  2. struct Student{
  3. int sid;
  4. char name[200];
  5. int age;
  6. }
  7. void f(struct Student *pst){
  8. (*pst).sid=890;
  9. strcpy(pst->name,"lisi");
  10. pst->age=22;
  11. }
  12. void g(st){
  13. printf("%d,%s,%d\n",st.sid,st.name,st.age);
  14. }
  15. void g2(struct Student *pst){
  16. printf("%d,%s,%d\n",st.sid,st.name,st.age);
  17. }
  18. int main(void){
  19. struct Student st;
  20. int i;
  21. f(&st);
  22. g(st);//耗内存和时间成本
  23. g2(&st);//只传首地址
  24. printf("%d,%s,%d\n",st.sid,st.name,st.age);
  25. return 0;
  26. }

动态内存的分配和释放

  1. //malloc
  2. #include<stdio.h>
  3. #include<malloc.h>
  4. int main(void){
  5. int a[5]={2,4,5,6,3};//静态分配
  6. int length;
  7. int i;
  8. printf("请输入需要数组长度:len=");
  9. scanf("%d",&length);
  10. int * pArr=(int*)malloc(sizeof(int)*length);//把这些字节的空间的控制权限求取到,并只返回第一个字节地址
  11. *pArr =4;//a[0]=4
  12. pArr[1]=10;
  13. printf("%d %d\n",*pArr,pArr[i]);
  14. for(i=0;i<length;i++)
  15. {
  16. scanf("%d",&pArr[i]);
  17. }
  18. for(i=0;i<length;i++)
  19. {
  20. printf("%d\n",*(pArr+i));
  21. }
  22. free(pArr);//释放:控制权限还给操作系统
  23. return 0;
  24. }

malloc 只有一个int型的形参,表示要求系统分配的字节数。

malloc函数的功能是请求系统len个字节的内存空间,如果请求分配成功,则返回第一个字节的地址,不成功,返回NULL。这里强转成指针变量类型赋值,这里的赋值是为了将这个无实际意义的地址转化为有实际意义的地址。

free(p):释放p所指向的内存,而不是释放p本身所占用的内存

跨函数使用内存问题

动态分配的内存必须调用free函数才能释放,而局部静态变量一旦跳出代码作用范围,由编译器自动释放掉。比如在链表中,通过CreateList函数创建了一个链表,并返回首地址赋值给指针变量,虽然这个函数在这一句赋值结束后结束周期,但因动态分配需要手动释放内存才会释放,这里展现了跨函数使用内存。

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. struct Student{
  4. char name[20];
  5. int age;
  6. };
  7. struct Student *CreateList(void){
  8. struct Student *p=(struct Student*)malloc(sizeof(struct Student));
  9. strcpy(pst->name,"lisi");
  10. pst->age=89;
  11. return p;
  12. }
  13. void showList(struct Student *pst){
  14. printf("%s %d\n",pst->name,pst->age);
  15. }
  16. int main(void){
  17. struct Student *ps;
  18. ps=CreateList();
  19. showList(ps);
  20. free(p);
  21. return 0;
  22. }

注意:Java的new,跨函数使用内存。

  1. A aa =new A();
  2. => A *pa= (A*)malloc (sizeof(A));

线性结构—-所有的结点可以用一根直线串起来

连续存储—数组**

  1. int a[10];
  2. int *pArr=(int*)malloc(sizeof(int)*len);
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <stdlib.h>
  4. struct Arr{//-----定义数据类型
  5. int *pBase;//存储数组第一个元素地址
  6. int len;//数组长度
  7. int cnt;//当前数组有效元素
  8. // int increment;//自动增长因子---增长自定义个数----allocate()
  9. };
  10. void init_arr(struct Arr *pArr,int length);
  11. bool append_arr(struct Arr *pArr,int val);
  12. bool insert_arr(struct Arr*pArr,int pos,int val);
  13. bool delete_arr(struct Arr*pArr,int pos,int *pVal);
  14. int get();
  15. int find_val_arr();
  16. void delete_all(4);
  17. bool is_empty(struct Arr*pArr);
  18. bool is_full(struct Arr*pArr);
  19. void sort_arr(struct Arr*pArr);
  20. void show_arr(struct Arr*pArr);
  21. void inversion_arr(struct Arr*pArr);
  22. int main(){
  23. struct Arr arr;//定义struct Arr类型的变量
  24. int val;
  25. init_arr(&arr,8);
  26. show_arr(&arr);
  27. append_arr(&arr,1);
  28. append_arr(&arr,2);
  29. append_arr(&arr,3);
  30. append_arr(&arr,6);
  31. append_arr(&arr,9);
  32. show_arr(&arr);
  33. if(append_arr(&arr,8))
  34. printf("追加成功\n");
  35. else
  36. printf("追加失败\n");
  37. show_arr(&arr);
  38. insert_arr(&arr,1,32);
  39. show_arr(&arr);
  40. if(delete_arr(&arr,1,&val)){
  41. printf("删除成功,元素为%d:",val);
  42. }
  43. show_arr(&arr);
  44. inversion_arr(&arr);
  45. show_arr(&arr);
  46. sort_arr(&arr);
  47. show_arr(&arr);
  48. return 0;
  49. }
  50. bool is_empty(struct Arr *pArr){
  51. if (pArr->cnt==0)
  52. return true;
  53. else
  54. return false;
  55. }
  56. bool is_full(struct Arr *pArr){
  57. if(pArr->cnt==pArr->len)
  58. return true;
  59. else
  60. return false;
  61. }
  62. void sort_arr(struct Arr *pArr){
  63. //冒泡
  64. int i,j,t;
  65. for(i=0;i<pArr->cnt;++i){
  66. for(j=i+1;j<pArr->cnt;++j){
  67. if(pArr->pBase[i]>pArr->pBase[j]){
  68. t=pArr->pBase[i];
  69. pArr->pBase[i]=pArr->pBase[j];
  70. pArr->pBase[j]=t;
  71. }
  72. }
  73. }
  74. }
  75. void inversion_arr(struct Arr*pArr){
  76. int i=0;
  77. int j=pArr->cnt-1;
  78. int t;
  79. while(i<j){
  80. t=pArr->pBase[i];
  81. pArr->pBase[i]=pArr->pBase[j];
  82. pArr->pBase[j]=t;
  83. ++i;
  84. --j;
  85. }
  86. return;
  87. }
  88. bool delete_arr(struct Arr*pArr,int pos,int *pVal){
  89. int i;
  90. if(is_empty(pArr))
  91. return false;
  92. if(pos<1||pos>pArr->cnt+1)
  93. return false;
  94. *pVal=pArr->pBase[pos-1];
  95. for(i=pos;i<pArr->cnt;++i){
  96. pArr->pBase[i-1]=pArr->pBase[i];
  97. }
  98. pArr->cnt--;
  99. return true;
  100. }
  101. bool insert_arr(struct Arr*pArr,int pos,int val){
  102. int i;
  103. if(pos<1||pos>pArr->cnt+1){
  104. return false;
  105. }
  106. if(is_full(pArr))
  107. return false;
  108. for(i=pArr->cnt-1;i>=pos-1;--i)
  109. pArr->pBase[i+1]=pArr->pBase[i];
  110. pArr->pBase[pos-1]=val;
  111. pArr->cnt++;
  112. return true;
  113. }
  114. bool append_arr(struct Arr *pArr,int val){
  115. if(is_full(pArr))
  116. return false;
  117. pArr->pBase[pArr->cnt]=val;
  118. pArr->cnt++;
  119. return true;
  120. }
  121. void show_arr(struct Arr*pArr){
  122. int i;
  123. if(is_empty(pArr)){
  124. printf("数组为空\n");
  125. }
  126. else{
  127. for(i=0;i<pArr->cnt;++i){
  128. printf("%d ",pArr->pBase[i]);
  129. }
  130. printf("\n");
  131. }
  132. }
  133. void init_arr(struct Arr *pArr,int length){
  134. pArr->pBase=(int*)malloc(sizeof(int)*length);
  135. if(NULL==pArr->pBase){
  136. printf("内存分配失败");
  137. exit(-1);
  138. }
  139. else{
  140. pArr->len=length;
  141. pArr->cnt=0;
  142. }
  143. return;
  144. }
  • 优点:存取速度快

  • 缺点:插入删除元素慢、事先必须知道数组长度、空间通常有限、需要大块连续内存块

  • 读写程序:流程,功能,试数

  • 帮助文档:初始化,参数含义,函数功能

typedef用法

  1. #include <stdio.h>
  2. typedef int SD;//为int再重新多取一个名字
  3. typedef struct Student{
  4. int sid;
  5. char name[100];
  6. char sex;
  7. }ST,*PST;//PST 等价于struct Student *
  8. int main(){
  9. struct Student st;
  10. ST st;
  11. struct Student *pst=&st;
  12. PST ps=&st;
  13. ps->sid=99;
  14. st.sid=200;
  15. int i=10;
  16. SD i=20;
  17. return 0;
  18. }

离散存储—链表

  • 数据量很大时,不需要整块内存空间占用资源

  • 离散:不连续

  • 定义:n个节点离散分配,彼此通过指针相连,每个节点只有一个前驱,只有一个后继,首节点无前驱,尾节点无后继

  • 专业术语:

    • 首节点:第一个存放有效数据节点
    • 尾节点:最后一个存放有效数据节点
    • 头节点:不存放有效数据,指针指向首节点,方便对链表操作,本身无实际含义,数据类型和首节点一样
    • 头指针:指向头结点的指针变量(第一个节点的地址,链表的首地址)
    • 尾指针:指向尾节点的指针变量

确定一个链表,需要几个参数:

  • 头指针—-一个函数对链表进行处理,只需要传入链表地址,也就是头节点的地址,可以推出整个链表

类型理解:前一个节点通过指针域,指向后面一个节点整体,如何指向一个整体呢,也就是后面的整体的数据类型和前面的指针数据类型是一样的,只不过是另外一个节点。

  1. #include<stdio.h>
  2. typedef struct Node{
  3. int data;//数据域
  4. struct Node *pNext;//指针域
  5. }NODE,*PNODE;
  6. int main(){
  7. return 0;
  8. }
  • 分类

    • 单链表
    • 双链表:节点分为三部分,两个指针域
    • 循环链表:能通过任何节点找到其他所有节点
    • 非循环链表
  • 算法—操作

    • 遍历
    • 查找
    • 清空
    • 销毁
    • 长度
    • 排序
    • 删除
  1. r=p->pNext p->pNext=r->pNext;
  2. free(r)
  3. p->pNext=p->pNext->pNext;

内存泄漏,不能写free(p->pNext),这样节点找不到了!

  • 插入

    • 方式一:r=p->pNext; p->pNext=q; q->pNext=r;
    • 方式二:q->pNext=p->pNext; p->pNext=q;
  • 优缺点

    • 优点:空间无限制、插入删除元素速度快
    • 缺点:存取速度慢
  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdlib.h>
  4. typedef struct Node{
  5. int data;//数据域
  6. struct Node *pNext;//指针域
  7. }NODE,*PNODE;
  8. PNODE create_list();
  9. void traverse_list(PNODE pHead);
  10. bool is_empty(PNODE pHead);
  11. int length_list(PNODE pHead);
  12. bool insert_list(PNODE pHead,int,int);
  13. bool delete_list(PNODE pHead,int ,int*);
  14. void sort_list(PNODE pHead);
  15. int main(){
  16. PNODE pHead=NULL;//头指针
  17. int val;
  18. pHead = create_list();//创建非循环单链表,该链表的头节点地址赋给pHead
  19. traverse_list(pHead);//遍历链表
  20. int len =length_list(pHead);
  21. printf("链表长度:%d",len);
  22. insert_list(pHead,4,32);
  23. if(delete_list(pHead,3,&val))
  24. {printf("删除成功,元素为:%d",val);}
  25. else{printf("删除失败");}
  26. sort_list(pHead);
  27. traverse_list(pHead);
  28. if(is_empty(pHead)){
  29. printf("链表为空");
  30. }
  31. return 0;
  32. }
  33. bool delete_list(PNODE pHead,int pos,int* pVal){
  34. int i=0;
  35. PNODE p=pHead;
  36. while(NULL!=p&&i<pos-1){
  37. p=p->pNext;
  38. ++i;
  39. }
  40. if(i>pos-1||NULL==p){
  41. return false;
  42. }
  43. PNODE q=p->pNext;
  44. *pVal=q->data;
  45. //删除p节点后面的节点
  46. p->pNext=p->pNext->pNext;
  47. free(q);
  48. q=NULL;
  49. return true;
  50. }
  51. bool insert_list(PNODE pHead,int pos,int val){
  52. int i=0;
  53. PNODE p=pHead;
  54. while(NULL!=p&&i<pos-1){
  55. p=p->pNext;
  56. ++i;
  57. }
  58. if(i>pos-1||NULL==p){
  59. return false;
  60. }
  61. PNODE pNew =(PNODE)malloc(sizeof(NODE));
  62. if(NULL==pNew){
  63. printf("动态内存分配失败");
  64. exit(-1);
  65. }
  66. pNew->data = val;
  67. PNODE q=p->pNext;
  68. p->pNext=pNew;
  69. pNew->pNext=q;
  70. return true;
  71. }
  72. void sort_list(PNODE pHead){
  73. /* int i,j,t;
  74. 广义与狭义的区别----------泛型---假象
  75. for(i=0;i<len-1;++i){
  76. for(j=i+1;j<len;++j){
  77. if(a[i]>a[j]){
  78. t=a[i];
  79. a[i]=a[j];
  80. a[j]=t;
  81. }
  82. }
  83. }
  84. 冒泡 */
  85. int i,j,t;
  86. int len = length_list(pHead);
  87. PNODE p,q;
  88. for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext){
  89. for(j=j+1,q=p->pNext;j<len;++j,q=q->pNext){
  90. if(p->data >q->data){
  91. t=p->data;
  92. p->data=q->data;
  93. q->data=t;
  94. }
  95. }
  96. }
  97. return;
  98. }
  99. int length_list(PNODE pHead){
  100. PNODE p = pHead->pNext;
  101. int len=0;
  102. while(NULL!=p){
  103. ++len;
  104. p=p->pNext;
  105. }
  106. printf("\n");
  107. return len;
  108. }
  109. bool is_empty(PNODE pHead){
  110. if(NULL==pHead->pNext){
  111. return true;
  112. }
  113. else
  114. return false;
  115. }
  116. void traverse_list(PNODE pHead){
  117. PNODE p = pHead->pNext;
  118. while(NULL!=p){
  119. printf("%d",p->data);
  120. p=p->pNext;
  121. }
  122. printf("\n");
  123. return;
  124. }
  125. PNODE create_list(){//这里的数据类型和头指针相同,类似于指针域指向下一个节点整体,其实是地址的赋值
  126. int len;//有效节点个数
  127. int i;
  128. int val;//临时存放节点值
  129. //分配了一个不存放有效数据的头节点
  130. PNODE pHead=(PNODE)malloc(sizeof(NODE));
  131. if(NULL==pHead){
  132. printf("分配内存失败。\n");
  133. exit(-1);
  134. }
  135. PNODE pTail=pHead;
  136. pTail->pNext=NULL;
  137. printf("请输入链表节点个数:");
  138. scanf("%d",&len);
  139. for(i=0;i<len;++i){
  140. printf("请输入第%d个节点的值:",i+1);
  141. scanf("%d",&val);
  142. PNODE pNew=(PNODE)malloc(sizeof(NODE));
  143. if(NULL==pNew){
  144. printf("分配内存失败。\n");
  145. exit(-1);
  146. }
  147. pNew->data=val;
  148. //pHead->pNext=pNew;
  149. //pNew->pNext=NULL;
  150. pTail->pNext=pNew;
  151. pNew->pNext=NULL;
  152. pTail=pNew;
  153. }
  154. return pHead;
  155. }

算法

  • 狭义的算法是与数据的存储方式密切相关

  • 广义的算法是与数据的存储无关

  • 泛型:利用某种技术达到的效果为:不同的存储方式,执行的操作是一样的。比如:数组中的p++表示指向下一个元素;如何让p++在链表中达到同样的效果呢?

比如说C++有个操作符重载:

  1. ++{p=p->next;}

如何学习算法?

  • 看懂答案:流程,功能,试数 (高一凡代码)

线性结构的两种常见应用

  • 栈(堆栈)—数据结构中没有堆概念,堆是分配内存的方式,不属于存储数据的结构—函数

  • 队列

专题:递归

  • 1+2+。。。+100的和——递归和循环的转换

  • 阶乘

  • 汉诺塔

  • 走迷宫

非线性排序

  • 树—-从属关系

  • 图—-交通图最短路径

查找和排序

  • 折半查找

  • 排序

    • 冒泡
    • 插入
    • 选择
    • 快速
    • 归并

Java中容器和数据结构相关知识

  • Iterator接口

  • Map

  • 哈希表

上传的附件
最近文章
eject