数据结构与算法——预备知识

本系列的数据结构与算法使用C语言进行编写。在真正开始学数据结构与算法前，应该有良好的C语言基础。

指针

定义

地址：地址就是内存的编号，其值为从0开始的非负整数，范围   X86平台：0 -- 0xFFFFFFFF (2^32 - 1) X64平台：0 -- 2^64 - 1

指针：指针就是地址，地址就是指针。指针变量是存放内存空间地址的变量。指针的值是一个无符号整数。在计算时，指针的值就当做内存地址看待。

基本类型的指针

int i=10;　　//定义了整型变量i,i的值是10
int* p=&i;　　//定义了整型指针变量p，p指向i的地址
//p指向i,p的值就是i的地址，所以修改任意一个的值不会影响另外一个
//但是*p的值就是i的值，任意修改其中一个，另一个也会变

指针与一维数组

int a[5]={1,2,3,4,5};
int* p=a+3;
printf("*p=%d",*p);//*p=4
//a[i]等价于*(a+i)

在一维数组中，数组名是个指针常量(它的值不可变)。数组名的值就是数组第一个元素的地址。

结构体

当已有的数据类型不能满足开发者需求时，可以采用结构体构造自己需要的数据类型

struct Student{ // 自定义结构体
    int age;
    char * name;
    double height;
    char name2[100];
};

int main(void) {

   struct Student s = {12,"xiaoyou",1.73,"xiaozhang"};

// 直接使用
   printf(" age = %d 
 name = %s 
 height = %.2f 
",s.age,s.name,s.height);

   s.age = 21;
   s.name = "xiaozhu";
   strcpy(s.name2, "zhangwangdsd");  // 字符串拷贝
   s.height = 1.70;

   printf(" age = %d 
 name = %s 
 height = %.2f 
 %s 
",s.age,s.name,s.height,s.name2);

   // 以指针的方式使用
   struct Student *pst = &ss;
   pst -> name = "my new name";
   
   printf(" name = %s
",pst->name);
   printf(" name = %s
",(*pst).name);
   
// pst -> name 等价于 (*pst).name ,
// 而(*pst).name 又等价于 ss.name
// 所以 pst -> name 等价于 ss.name

   return 0;
}

动态内存分配和释放

动态构造一个长度为10的整型数组

int* p=(int*)malloc(10*sizeof(int));

使用malloc函数需要引用malloc.h头文件，malloc函数的返回值为一个NULL类型的指针，需要进行强制转换，sizeof是计算数据类型长度的。因为int的长度为4B,所以上面的代码等价于

int* p=(int*)malloc(40);

使用完，应该用free(p)来释放指针。释放的是指针p所指向的内存空间，并非p本身所占内存空间。