郝斌数据结构自学笔记--知识点+程序源代码

郝斌数据结构自学笔记

--知识点+程序源代码

2015.12 By-HZM

1_什么叫做数据结构 数据结构概述 定义

我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。

数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作

2_衡量算法的标准 算法

解题的方法和步骤

衡量算法的标准

1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性

3_数据结构的特点 数据结构的地位

数据结构是软件中最核心的课程

程序=数据的存储+数据的操作+可以被计算机执行的语言

4_预备知识_指针_1 5_预备知识_指针_2 指针的重要性：

指针是C语言的灵魂 定义： 地址：

地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】 CPU=====地址线，控制线，数据线=====内存 指针：

指针就是地址，地址就是指针。

指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。

分类：

1.基本类型的指针 2.指针和数组的关系

变量并不一定连续分配，随机分配内存。

内存：

内存是多字节组成的线性一维存储空间。 内存的基本划分单位是字节。

每个字节含有8位，每一位存放1个0或1个1. 内存和编号是一一对应的。

软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。

NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。

2）局部变量只在本函数内部使用。

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

1）实参为相关变量的地址；

2）形参为以该变量的类型为类型的指针变量；

3）在被调函数中通过 *形参变量名的形式的形式就可以修改主函数。 CASE 1

#include

int main(void) { //

int *p; //p是个变量名字，int*表示该p变量只能存储int类型变量的地址 int i=10; int j; j=*p;

//error,p未指定

// printf(\

// char ch='A';

// p=&ch; //error，类型不一致 p=&i; //p保存i的地址，p指向i；修改p的值不影响i的值，修改i的值不影响p的值；任何场合下，*p和i可以互换。*p等价于i。 //p=10; //error j=*p;//等价于j=i; printf(\ return 0;

}

CASE 2

#include

void f(int * i)//不是定义了一个名字叫做*i的形参，而是定义了一个形参，该形参名字叫做i，它的类型是int* { *i=100; }

int main(void) { int i=9; f(&i); //局部变量只在本函数内部使用。 printf(\}

指针和数字

数组名：一维数组名是个指针变量，它存放的是一维数组第一个元素的地址，它的值不能被改变，一维数组名指向的是数组的第一个元素。 CASE 1

a[3]==*(3+a); 3[a] ==*(a+3)==*(3+a); int a[5]={1,2,3,4,5};

Show_Aarry(a,5);//a等价于&a[0],&a[0]本身就是int*类型

void Show_Array(int * p,int len) { Int I; //P[2]=-1;// p[0]=*p ; p[2]==*(p+2)==*(a+2)==a[2] ; p[i]就是主函数的a[i]

for (i=0;i

指针变量的运算

指针变量不能相加，不能相乘，不能相除。 如果两指针变量属于同一数组，则可以相减。

指针变量可以加减一整数，前提是最终结果不能超过指针变量 p+i的值是p+i*(p所指向的变量所占的字节数) p-i的值是p-i*(p所指向的变量所占的字节数) p++<==>p+1 p--<==>P-1

6_所有的指针变量只占4个子节用第一个字节的地址表示整个变量的地址 CASE 1 double *p;

double x=66.6; //一个double占8个字节

p=&x;//x占8个字节，1个字节是8位，1个字节一个地址，p内只存放了一个地址，通常是字节的首地址

double arr[3]={1.1,2.2,3.3}; double *q; q=&arr[0];

printf(“%p\\n”,q); //%p实际就是以十六进制输出 q=&arr[1];

q=printf(“%p\\n”,q); //p,q相差8

无论指针指向的变量占多少个字节，指针变量统一都只占4个字节

7_如何通过函数修改实参的值 发送地址

CASE 1 修改指针变量的值，只能修改地址 void f(int **); int main(void) { int i=9; int *p=&i;// *p;p=&i; printf(“%p\\n”,p); f(&p);

printf(“%p\\n”,p); return 0; }

//void f(int *q) //{

// q=(int *)0xffffffff; //错误，不会改变p的值 //}

void f(int ** q) { *q=(int *)0xffffffff; }

8_结构体的使用概述 结构体

为什么会出现结构体：

为了表示一些复杂的数据，而普通的基本类型变量无法满足要求 什么叫做结构体：

结构体是用户根据实际需要自己定义的复合数据类型 如何使用结构体：

两种方式——