数据结构入门
- 2019 年 11 月 3 日
- 筆記
定义：我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主内存器中(内存)，以及在此基础上为实现某个功能(比如查找某个元素，删除某个元素，对所有元素进行排序)而执行的相应操作，这个相应的操作也叫算法
数据结构 = 个体 + 个体的关系
算法 = 对存储结构的操作
算法：解题的方法和步骤
衡量算法的标准：
- 时间复杂度：大概程序执行要执行的次数，而非执行的时间
- 空间复杂度：算法执行过程中大概所占用的最大内存
- 难易程度
- 建壮性
一、指针
地址：内存单元的编号，从0开始的非负整数
指针：指针就是地址，指针变量是存放内存单元地址的变量，指针的本质是一个操作受限的非负整数
分类：
- 基本类型指针(重点看注释)
#include <stdio.h> int main(void) { // p是一个变量名字，int * 表示p变量只能存储int类型变量的地址 int *p; int i = 10; int j; p = &i; // p保存了i的地址，p指向i // 修改p的值不影响i的值，修改i的值不影响p的值 // *p等于i j = *p; // 等价于 j = i printf("%dn", *p); printf("%dn", j); return 0; }- 指针与函数
#include <stdio.h> // 不是定义了一个名字叫做 *p的形参，而是定义了一个形参，该形参的名字p，它的类型是int * void f(int *p) { *p = 100; } int main(void) { int i = 9; int *p = &i; f(p); printf("%dn", i ); return 0; }- 指针与数组(重点看注释)
#include <stdio.h> void show_array(int *p , int len) { // p[0] == *p p[0] = -1; // p[i]就是主函数a[i] int i = 0; for (i = 0; i < len; i++) { printf("%dn",p[i] ); } } int main(void) { /* 一唯数组名是个指针常量，它存放的是一唯数组第一个元素的地址， 它的值不能改变，一唯数组名指向的是数组的第一个元素，也就是 a执向a[0] 下标和指针的关系 a[i] <==> *(a+i) */ int a[5] = {1,2.3,4,5,}; // a等价于&a[0] , &a[0]本身就是int * 类型 show_array(a,5); printf("%dn", a[0]); return 0; }所有的指针变量只占4个字节，用第一个字节的地址表示整个变量的地址
#include <stdio.h> int main(void) { double *p; double x = 99.9; // x占8个字节，1字节是8位，1字节一个地址 ，p里面存放了首地址 p = &x; double arr[3] = {1.1,2.2,3.3,}; double *q; double *q1; q = &arr[0]; printf("%pn", q); // %p实际就是以十六进制输出 q1 = &arr[1]; printf("%pn", q1); // 相差了8个字节 return 0; }二、如何通过函数修改实参的值
#include <stdio.h> void f(int **q); int main(int argc, char const *argv[]) { int i = 9; int *p = &i; // int *p , p = &i; printf("%pn",p ); f(&p); printf("%pn",p ); return 0; } void f(int **q) { *q = (int*)0XFFFFF; }这样写是不安全的，但是这个理是这样的，不是修改指针的很简单，
#include <stdio.h> void f(int *p); int main(void) { int i =10; f(&i); printf("%dn", i); return 0; } void f(int *p) { *p = 20; }三、结构体
为什么会出现结构体
为了表示一些复杂的数据，而普通的基本类型变量无法满足要求
什么叫结构体
结构体是用户根据实际需要，自己定义的复合数据类型
如何使用结构体
#include <stdio.h> #include <string.h> struct Student { int sid; char name[200]; int age; }; // 分号不能省 int main(void) { // 第一种方式，但是这样很麻烦 struct Student st = {10 , "张三" ,20}; printf("%d %s %dn", st.sid , st.name , st.age); // 字符串不能直接赋值，必须调用相应的函数 st.sid = 20; strcpy(st.name , "李四"); st.age = 21; printf("%d %s %dn", st.sid , st.name , st.age); // 第二种方式，这个最常用 struct Student *pst; pst = &st; pst -> sid = 99; // pst->sid 等价于 (*pst).sid 等价于 st.sid return 0; }pst -> sid : pst所指向的结构体中变量中的sid这个成员
注意事项
- 结构体变量不能加减乘除，但是可以相互赋值
- 普通结构体变量和结构体指针变量作为函数传参的问题
#include <stdio.h> #include <string.h> struct Student { int sid; char name[200]; int age; }; void f(struct Student * pst); void g(struct Student st); void g1(struct Student * pst); int main(void) { struct Student st; f(&st); //printf("%d %s %dn", st.sid , st.name , st.age); //g(st); g1(&st); return 0; } // 用于数据的输入 void f(struct Student * pst) { (*pst).sid = 99; strcpy(pst -> name , "张三"); pst -> age = 30; } // 用于数据的输出,但是这种方法费时间，不推荐 void g(struct Student st) { printf("%d %s %dn", st.sid , st.name , st.age); } // 用于数据的输出，推荐使用这种方式 void g1(struct Student * pst) { printf("%d %s %dn", pst->sid , pst->name , pst->age); }四、动态内存的分配和释放
重点看代码和注释
#include <stdio.h> #include <stdlib.h> int main(void) { int a[5] = {3,9,5,6,2}; int len; printf("请输入你需要的分配数组的长度：n"); scanf("%d" , &len); int * PArr = (int *)malloc(sizeof(int)*len); // *PArr = 3; //类似于a[0] = 3 // PArr[1] = 9; //类似于a[1] = 9 // printf("%d %dn", *PArr , PArr[1]); // 当然了，这个时候我们可以把pArr当作一个普通的数组来使用 int i; for (i = 0; i < len; ++i) { scanf("%d" , &PArr[i]); } int j; for (j = 0; j < len; ++j) { printf("%dn", PArr[j]); } free(PArr); // 把Parr所代表的动态分配的20个字节内存释放 return 0; }五、跨函数使用内存
重点看代码和注释
#include <stdio.h> #include <stdlib.h> struct Student { int sid; int age; }; struct Student * CreateStudent(void); void ShowStudent(struct Student * ps); int main(void) { struct Student * ps; ps = CreateStudent(); ShowStudent(ps); return 0; } struct Student * CreateStudent(void) { // 开辟一个新空间，使用malloc函数，类型是我们想要的类型 struct Student * p = (struct Student * )malloc(sizeof(struct Student)); p->sid = 88; p->age = 99; return p; } void ShowStudent(struct Student * pst) { printf("%d %dn", pst->sid , pst->age); }
