数据结构的定义和简介
1. 概述
数据结构定义:
我们如何把现实中⼤量⽽复杂的问题以特定的和特定的存储结构保存到主存储器(内存)中，以及在此基础上为实现某个功能(如元素的CURD、排序等)⽽执⾏的相应操作，这个相应的操作也叫算法。
= 元素 + 元素的关系
算法 = 对数据结构的操作
算法:
算法就是：解决问题的⽅法和步骤
衡量算法有如下标准:
时间复杂度
程序要执⾏的次数，并⾮执⾏时间
空间复杂度
算法执⾏过程中⼤概要占⽤的最⼤内存
难易程度(可读性)
健壮性
2. 数据结构的特点和地位
地位:
数据结构处于软件中核⼼的地位。
如计算机内存中栈和堆的区别，不懂数据结构的⼈可能会认为内存就是分两⼤部分，⼀块叫栈，⼀块叫堆，显然这是⾮常肤浅且不正确的结论。
实际上如果⼀块内存是以压栈出栈的⽅式分配的内存，那么这块内存就叫栈内存，如果是以堆排序的⽅式分配的内存，那么这块内存就叫堆内存，其最根本的区别还是其内存分配算法的不同。
例如，函数的调⽤⽅式也是通过压栈出栈的⽅式来调⽤的，或者操作系统中多线程操作有队列的概念，
队列⽤于保证多线程的操作顺序，这也是数据结构⾥⾯的内容、或者计算机编译原理⾥⾯有语法树的概念，这实际上就是数据结构⾥⾯的树，⽐如软件⼯程、数据库之类都有数据结构的影⼦。
特点:
数据结构修炼的是内功，并不能直接⽴竿见影的可以解决现实问题，但是有了这门内功会在其他⽅⾯的学习中对你⼤有益处。
预备知识（C语⾔）
学习数据结构应该具备如下知识：
指针
结构体
动态内存的分配和释放
跨函数使⽤内存
本⼩节主要介绍学习数据结构应该有的基础，并对相关知识稍作讲解。
指针
指针是 C语⾔ 的灵魂，重要性不需多⾔。
指针定义
地址：
地址是内存单元的编号
其编号是从 0 开始的⾮负整数
范围： 0 – 0xFFFFFFFF (232 - 1) 注：此指x86平台，x64平台下最⼤内存地址为 (264 - 1)
指针：
指针就是地址，地址就是指针。
指针变量是存放内存单元地址的变量，它内部保存的值是对应的地址，地址就是内存单元的编号(如内存地址值：0xffc0)。
指针的本质是⼀个操作受限的⾮负整数
在计算机系统中，CPU 可以直接操作内存，关于 CPU 对内存的操作与控制原理可以简单理解如下图
地址线 ： 确定操作哪个地址单元
控制线 ： 控制该数据单元的读写属性
数据线 ： 传输 CPU 和内存之间的数据
指针的分类
基本类型的指针
int i = 10; // 定义⼀个 ×××变量 i 初始值 10
int *p = i; // 定义⼀个 ×××的指针变量 p , 变量 p 指向 i 的地址
int *p; // 这两⾏等价于上⾯⼀⾏
p = &i;
p 存放了 i 的地址，我们就可以说“ p 指向了 i” ，但 p 和 i 是两个不同的变量，修改⼀⽅不会影响另⼀个的值。
*p 等价于 i ，i 等价于 *p；两者是⼀块内存空间，⾥⾯的值⼀变具变。
指针和函数
// 修改外部实参的值
void func(int * p)
{
*p = 100; // 函数内修改外部变量的值
}
// 修改外部实参的值，⼆级指针的值
void func2(int ** p)
{
*p = 100;
/
/ 函数内修改外部变量的值 ，这⾥实际修改的是指针的内部的地址，这⾥直接⾃⼰修改并不严谨也不安全，只是为了表达意思}
{
// 修改外部实参
int i = 10;
func(&i);
printf(“i = %d”,i);
// 修改外部⼆级指针
int *p = i; // 等价于 int *p; p = &i;
func(&p);
printf(“i = %d”,i);
return 0;
}
// 通过函数调⽤，改变函数外部变量（实参）的值
指针和数组
【指针】 和 【⼀维数组】
int a[5] = {1,2,3,4,5 };
a[3] == *(a + 3)
// 等价于 a[3] == *(3 + a) == 3[a];
// 3[a] 这种写法只是不常⽤，从原理上来说是正确的 a 等价于 a[0];
// a 是数组中第⼀个元素，每个元素占⽤内存单位长度相同，
// a[i] 中的 i 实际代表的是单位长度的倍数
数组名:
⼀维数组名是个指针常量(它的值不可变)
它存放的是该⼀维数组的第⼀个元素的地址(⼀维数组名指向其第⼀个元素)
下标和指针的关系:
(1)、 a[i] 等价于 *(a + i)
(2)、假设指针变量的名字为 p,
则 p + i 的值为 p + i * (p 所指向的变量所占字节数)
(3)、每个下标表⽰的是第 i+1 个元素，根据元素类型分配的字节长度不同(int 类型4个字节)，每个字节都有对应的内存地址编号，指针变量 p 保存的是该元素⾸字节的地址。
指针变量的运算:
指针变量不能相加、相乘、相除
如果两指针变量属于同⼀数组，则可以相减
指针变量可以加减⼀个整数，前提是最终结果不能超过指针最⼤可访问范围
p + i 的值是 p + i*(所指向的变量所占字节数)
p - i 的值是 p - i*(所指向的变量所占字节数)
p++ 等价于 p + 1
p– 等价于 p - 1
// 下⾯是⼀个通过函数修改数组内部元素
void my_Array(int *a , int length)
{
for(int i = 0; i < length; i++)
{
*a[i]++; // 给每个元素加 1
}
}
int main(void){
int a[5] = {1,2,3,4,5};
my_Array(a , 5); // 调⽤
}
结构体
为什么会出现结构体?
为了表⽰⼀些复杂的数据，⽽普通的基本数据⽆法满⾜要求.
什么叫结构体
结构体是⽤户根据实际需要，⾃⼰定义的复合数据类型
// 如学⽣类型
struct Student{
int age;
char * name; // name 不同，赋值⽅法不同
char name2[100]; // 这个只能 strcpy(s.name2, “zhangwangdsd”); 字符串拷贝double height;
};
如何使⽤结构体
总结起来有两种结构体的使⽤⽅式：直接使⽤ && 通过指针使⽤
struct Student ss = {12,”xiaoyou”,1.73,”xiaozhang”};
struct Student *pst = &ss;
ss.name ; 这⾥直接操作结构体本⾝
pst -> name ; 这⾥通过指针地址操作，更加节省空间
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 \n name = %s \n height = %.2f \n”,s.age,s.name,s.height);
s.age = 21;
s.name = “xiaozhu”;
strcpy(s.name2, “zhangwangdsd”); // 字符串拷贝
s.height = 1.70;
printf(” age = %d \n name = %s \n height = %.2f \n %s \n”,s.age,s.name,s.height,s.name2); // 以指针的⽅式使⽤
struct Student *pst = &ss;
pst -> name = “my new name”;
printf(” name = %s\n”,pst->name);
printf(” name = %s\n”,(*pst)->name);
// pst -> name 等价于 (*pst).name ,
// ⽽(*pst).name ⼜等价于 ss.name
// 所以 pst -> name 等价于 ss.name
return 0;
}
注意事项
结构体变量的类型为： struct Student
结构体变量不能加减乘除，但是能够相互赋值
普通结构体变量和结构体指针变量作为函数传参的问题
typedef struct Student{ // 结构体定义
int age;
molloc函数char * name;
char name2[100];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。