数据结构预备知识
一、数据结构概述
1.什么是数据结构？
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法
数据结构 = 个体的存储 + 个体的关系存储；
算法 = 对存储数据的操作；
2.衡量算法的标准
1）时间复杂度：大概程序执行的次数，而非执行的时间
2）空间复杂度： 算法执行过程中大概所占用的最大内存
3）难易程度
4）健壮性
3.预备知识——指针
指针的重要性： 指针是C语言的灵魂
地址：地址是内存单元的编号，从0开始的非负整数，范围：0-FFFFFF【0-4 G-1】
CPU==========-地址线，控制线，数据线 ===========内存
指针： 指针就是地址，地址就是指针。 指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。
分类
1.基本类型指针
Int *p; //*p要保存一个内存地址（p是个变量名字，int *表示该p变量只能存储int类型变量的地址）
Int i = 10;
Int j;
j=*p;
char ch = 'A';
// p =&ch;//error
// p =10；//error
p = &i;//正确
*p =i;//error 等价于i=i
//上行代码表示p指向i，则p就是i
j = *p; //等价于j=i
Printf(“%d\n”,j)
函数
void f(int *p){ //不是定义一个名字*p的形参，而是定义了一个形参，该形参的名字叫做p，它的类型是int *(p指向了i,p就是i)
*p = 100;
}
main{
int i =9;
f(&i);
}
如何通过被调函数修改主调函数中普通变量的值？
1.实参为相关变量的地址
2.形参为以该变量类型为类型的指针变量
3.在被调函数中通过 *形参变量名 的方式就可以修改主调函数的值
指针和数组
Show_Array(int *p, int len){
int i =0;
for
//p[0] = -1; //p[0] == *p
//p[2] = -1; //p[2] == *(p+2) == *(a+2) ==a[2]
}
main(void){
int a[5] = {1,2,3,4,5,}; //
Show_Array(a,5) //数组名表示的就是第一个元素的地址,a==&a[0]
}
数组名：
一维数组名是个指针常量，
它存放的是一维数组第一个元素的地址
它的值不能被变
一维数组名指向的就数组的第一个元素
下标和指针的关系
a[i] <<==>> *(a+i)
指针变量所占的字节关系
double * p;
doubl x = 66.6;
p = &x;//x占8个字节 1个字节是8(#`O′)，1个字节一个地址,p存放的是x的首地址
//不论指针变量指向的地址占多少个字节，指针变量都统一占4个字节
如何以过函数修改实参的值
main(void){
int i=0;
int * p = &i;
f(&p);
}
f(int **p){
*p=(int *)OxFFFFFF;
}
结构体：
1).为什么会出现结构体？
为了表示一些复杂的数据，而基本的数据类型变量无法满足要求
2）什么叫结构体？
结构体是用户根据实际需要自己定义的复合数据类型
3）结构体的定义方法
Strcut 结构体名{
内容：例如：int name
}; //分号不能省
//例如：该下列代码：定义了一个 strucut Student类型，该类型有三个成员
strcut Student{
int sid;
char name[200];
int age;
}
main(void){
//第一个赋值方法和定义
struct Student st = {1000."zhangsan",20};
st.sid = 99;
strcopy(st.name,"list");
st.age = 33;
}
第二种赋值方法
main(void){
struct Student st = {100,"zhangsan",20};
struct Student * pst = &st;
pst->sid = 99； //pst->等价于(*pst).sid 而(*pst).sid等价于st.sid，使用pst->sid 等价于st.sid
// pst所指向的结构体变量中的sid这个成员
}
注意事项:
/**1)结构体变量不能加减乘除，但可以相互赋值。
*2)普通结构体变量和结构体指针变量作为函数传参问题
*/
main(void){
struct Student st; //静态变量
f(&st);
g(&st);
}
void g(struct Student * st){
printf(*(st).sid);
printf(st->name);
}
void f(struct Student * pst){
(*pst).sid = 99;
strcpy(pst->name,"zhangsan");
pst->age = 22;
}
C语言字符串赋值要使用：
strcpy(st.name,”list”);
动态内存的分配和释放
main(void){
int a[5] = {4,2,4,5,6};
int len = 5;
printf("请输入你需要分配的数组的长度：len=");
scanf("%d", len);
//把你请求需要的字节的地址赋给pArr malloc只返回第一个字节的地址 sizeof(int)表示返回int类型所占字节
//下述代码表示：总共分配了20个字节，pArr指向的前四个字节 pArr+1指向的后四个字节 和a[5]意思相同，a[5]
//静态变量，下述代码表示动态变量
int * pArr = (int *)malloc(sizeof(int) * len);
*pArr = 4; //等价于 a[0] =4;
pArr[1] = 10; //等价于a[1] = 10;
//下述代码：把pArr所代表的动态分配的20个字节的内存释放
free(pArr);
return 0;
}
