一:数据结构基本术语
/*
数据: 程序的操作对象,用于描述客观事物.
数据的特点: 1️⃣ 可以输入到计算机 2️⃣ 可以被计算机处理
数据项: 元素点,数据元素的最基本单位;
数据元素: 一个数据元素由若干数据项组成, 组成数据的对象的基本单位;
数据对象: 性质相同的数据元素的集合(类似于数组)
结构: 数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
数据结构:指的数据对象中的数据元素之间的关系
*/
代码示例:
#include <stdio.h>
//声明一个结构体类型
struct Teacher
{ //一种数据结构
char *name; //数据项--名字 1字节 [1]
char *title; //数据项--职称 1字节 [2,3]
int age; //数据项--年龄 4字节 [4,7]
};
int main(int argc, const char * argv[]) {
struct Teacher t1; //数据元素;
t1.name = "CC"; //数据项
t1.title = "讲师"; //数据项
t1.age = 18; //数据项
printf("老师姓名:%s\n",t1.name);
printf("老师年龄:%d\n",t1.age);
printf("老师职称:%s\n",t1.title);
struct Teacher tArray[10]; //数据对象;
printf("首地址: %p\n",tArray); //0x7ffeefbff3a0
printf("数组整个地址: %p\n",&tArray); //0x7ffeefbff3a0
printf("首地址 + 1: %p\n",tArray + 1); //array + 1 -> 表⽰数组首地址 ＋ sizeof(数组元素类型) -> 0x7ffeefbff3b8
printf("数组整个地址 + 1: %p\n",&tArray + 1); //数据类型为:Teacher (*)[10] 表⽰示长度为10的⼀维整型数组指针类型，&array + 1 -> 表⽰示数组首地址 ＋ 数组总⼤⼩ -> 0x7ffeefbff490
// 注意：数组名是⼀一个符号地址常量，不是变量，所以不能⾃自增，⾃自减
return 0;
}
总结:
数据包含数据对象
数据对象包含数据元素
数据元素包含数据项
截屏2020-03-31 下午5.24.50.png
二:1.数据结构->逻辑结构
逻辑结构:数据与数据之间的逻辑关系
(1)集合结构
特点:无序,唯一,平等,所有的数据都属于集合,没有先后顺序
常见:
NSSet
截屏2020-03-31 下午5.36.44.png
(2)线性结构
特点:
1.数据与数据都是一对一的关系;
2.所有符合数据关系是一对一的都是线性结构;
常见:
字符串,数组,字典,队列(先进先出),栈(先进后出),线性表,链表
截屏2020-03-31 下午5.37.11.png
(3)树形结构
特点:
数据关系是一对多的都是树形结构
常见:
二叉树,B树,B+树,B-树,多路树,哈弗曼树,红黑树,平衡二叉树
截屏2020-03-31 下午5.37.37.png
(4)图形结构
特点:
数据关系是多对多都是图形结构
截屏2020-03-31 下午5.40.22.png
总结:
数据与数据逻辑之间的关系有四种:
1.集合结构
2.线性结构
3.树形结构
4.图形结构
二:2.数据结构->物理结构
物理结构 : 数据存储在内存的方式
(1)顺序存储结构
需要先开辟一段连续的内存空间,依次存储进去;
截屏2020-04-01 上午10.21.53.png
(2)链式存储结构
不需要先开辟一段连续的内存空间,需要时,再需要几个就开辟几个 ;
截屏2020-04-01 上午10.22.06.png
总结:
截屏2020-04-01 上午10.29.57.png
三:算法与数据结构的关系
(1)算法是解决问题的一种方法;
算法是解决特定问题求解步鄹的描述,在计算机中表现为指令的有限序列,并且每个指令表示一个或多个操作;
(2)问题就是:
1.先准备数据
2.设计数据结构,先设计逻辑结构,在设计存储结构
3.使用算法解决问题
比如:
截屏2020-04-01 上午10.39.11.png
比如:
求1+2+3+..+100的值?
int sum = 0;
int n = 100;
sum = (1+n)*n/2; //算法:等差数列
printf(%d, sum);
这就是一个算法
(3)算法的特性
输入输出
有穷性
确定性
可行性
(4)算法的设计要求(衡量一个算法的要求)
1.正确性
2.可读性
3.健壮性
4.高效性(时间)
5.低存储性(空间)
四:时间复杂度计算
大O表示法:
1. 用常数1取代运行时间中所有常数 3->1 -> O(1)
2. 在修改运行次数函数中,只保留最高阶项 n^3+2n^2+5 ->n^3 -> O(n^3)
3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 ->n^3 -> o(n^3)
时间复杂度术语:
1. 常数阶 (1,2,3...都是常数) O(1)
2. 线性阶 (2x,3y 线性函数) O(n)
3. 平方阶 (n^2) O(n^2)
4. 对数阶 (2的x方等于n) O(logn)
5. 立方阶 (n^3) O(n^3)
6. nlog阶
7. 指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!
1.时间复杂度-常数阶计算 O(1)
/* 1. 常数阶时间复杂度计算 O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}
//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum);//执行1次
}
//x=x+1 O(1)
void add(int x){
x = x+1; // 执行1次
}
2.时间复杂度-线性阶计算 O(n)
/*2.线性阶时间复杂度*/
//n + n = 2n -> O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) { //执行n此
x = x+1; //执行n此
}
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
int i,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}
3.时间复杂度-对数阶阶计算 O(logn)
/*3.对数阶*/
/*2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) { //
count = count * 2;
}
}
4.时间复杂度-平方阶计算 O(n^2)
/*4.平方阶*/
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) { //执行n次
for (int j = 0; j < n ; j++) { //执行n*n次
x=x+1;
}
}
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2 等差算法
void testSum4(int n){
int sum = 0; //1次
for(int i = 0; i < n;i++) //n次
for (int j = i; j < n; j++) { //n+(n-1)+(n-2)+...+1 = n(n-1)/2 次
sum += j; //n+(n-1)+(n-2)+...+1 = n(n-1)/2 次
}
printf("textSum4:%d",sum);
}
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
int i,j,x=0,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
for (j = 1; j <= n; j++) { //执行n(n+1)
x++; //执行n*n次
sum = sum + x; //执行n*n次
}
}
printf("testSum5:%d\n",sum);
}
5.时间复杂度-立方阶计算 O(n^3)
/*5.立方阶 O(n^3)*/
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}
总结:
截屏2020-04-01 上午11.22.18.png
五:空间复杂度计算
/*
算法的空间复杂度通过计算算法所需要的存储空间实现,算法空间复杂度的计算公式:
S(n) = n((f(n))),其中,n为问的的规模,f(n)为语句关于n所占存储空间的函数
*/
/*
程序空间计算因素:
1. 寄存本身的指令
2. 常数
3. 变量
4. 输入
5. 对数据进行操作的辅助空间
在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间
*/
//空间复杂度计算:
//问题: 数组逆序,将一维数组a中的n个数逆序存放在原数组中.
//(1)算法实现 O(1) 常数介
void reverse1(int *a,int n)
{
int temp;//开辟了一次空间
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
}
//(2)算法实现 O(n) 线性介
void reverse2(int *a,int n)
{
int b[n] = {0};//开辟了n个空间
for(int i = 0; i < n;i++)
{
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++)
{
a[i] = b[i];
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
reverse1(a, n);
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
int m = 5;
int b[10] = {1,2,3,4,5,6,7,8,9,10};
reverse2(b, m);
for(int i = 0;i < 10;i++)
{
printf("%d\n",b[i]);
}
return 0;
}
注意:算法应该以最坏情况考虑,没有最坏,只用更坏;
总结:
截屏2020-04-01 下午5.01.32.png
