图解数据结构---绪论
🌞欢迎来到图解数据结构的世界
🌈博客主页：卿云阁💌欢迎关注🎉点赞👍收藏⭐️留言📝
🌟本文由卿云阁原创！
📆首发时间：🌹2024年7月12日🌹
✉️希望可以和大家一起完成进阶之路！
🙏作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢！
目录
必备知识
知识框架
宏定义
元素类型说明
数组定义
参数传递
内存结构
数据结构基本概念
基本概念
逻辑结构
编辑物理结构
时间复杂度
空间复杂度
必备知识
知识框架
本节一共有4个点，分别是宏定义、元素类型说明、数组定义、参数传递。
宏定义
#define PI 3.14159 在这个例子中，PI是一个宏常量，表示圆周率。在代码的其他地方，所有出现 PI 的地方都会被替换为 3.14159。
常用到的预定义常量和类型
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0元素类型说明
typedef char ElemType;其中ElemType就相当与char。
typedef struct{ int data[2];int length; //当前长度}SqList; //定义顺序表类型这段代码，我们定义了一个顺序表的类型，它包含了两个元素，一个有两个元素的数组和一个便是当前长度的数据。
数组定义
- 静态分配：固定大小，编译时确定，内存放在栈上。
- 动态分配：灵活大小，运行时确定，内存放在堆上。
数组静态分配
#include<stdio.h>
#define MAXSIZE 10 //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ DataType data[MAXSIZE];int length; }SqList; //定义顺序表类型int main() {SqList L;return 0;
}
数组动态分配
#include<stdio.h>
#define MAXSIZE 10 //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{ DataType *data;//定义了一个指针变量存放地址int length; }SqList; //定义顺序表类型int main() {SqList L;
L.data=(DataType*)malloc(sizeof(DataType)*MAXSIZE);//在C++中也可以使用new,和delete
free(L.data); //释放空间
L.data=NULL;return 0;
}
参数传递
- 传值调用：传变量的值，函数内修改不会影响原变量。
- 传址调用：传变量的地址，函数内修改会直接影响原变量。
传值调用
#include<iostream>
using namespace std;
void swap(int m,int n){
int temp;
temp=m;
m=n;
n=temp;
}
int main()
{ int a=5,b=10;
cout<<"a="<<a<<"b="<<b<<endl;
swap(a,b);
cout<<"a="<<a<<"b="<<b<<endl;
return 0;}
传址调用--指针变量作为参数
#include<iostream>
using namespace std;
void swap(int* m,int* n){
int temp;
temp=*m;
*m=*n;
*n=temp;
} int main()
{ int a=5,b=10;
cout<<"a="<<a<<"b="<<b<<endl;
swap(&a,&b);
cout<<"a="<<a<<"b="<<b<<endl;
return 0;} 
传址调用--引用作为参数
#include<iostream>
using namespace std;
void swap(int &m,int &n){
int temp;
temp=m;
m=n;
n=temp;
} int main()
{ int a=5,b=10;
cout<<"a="<<a<<"b="<<b<<endl;
swap(a,b);
cout<<"a="<<a<<"b="<<b<<endl;
return 0;}
传址调用--数组名作为参数
#include<iostream>
using namespace std;
void swap(int m[],int n[]){
int temp;
temp=m[0];
m[0]=n[0];
n[0]=temp;
} int main()
{ int a=5,b=10;
cout<<"a="<<a<<"b="<<b<<endl;
swap(&a,&b);
cout<<"a="<<a<<"b="<<b<<endl;
return 0;}
内存结构
数据结构基本概念
基本概念
逻辑结构
- 集合：各个元素同属于一个集合（微信中的好友的名单）
- 线性结构：一对一的关系（排队买票）
- 树形结构：一对多的关系（文件系统）
- 图形结构：多对一的关系（微信中好友的关系图）
物理结构
- 顺序存储结构：连续存储，按照顺序排列，像书架上的书籍。
- 链式存储结构：非连续存储，通过指针连接，像项链上的珠子。
- 索引存储结构：通过索引表快速定位，像书的目录。
- 散列存储结构：通过哈希函数直接定位，像快递柜的取件码。
时间复杂度
逐步递增型爱你
//算法一 逐步递增型爱你
void loveYou(int n) //n为时间规模
{int i=1;while(i<=n) {i++;printf("I Love You %d\n",i);}printf("I Love You More Than %d\n",n);
}
int main()
{loveYou(3000);
}
嵌套循环增型爱你
//算法2 嵌套循环增型爱你
void loveYou(int n) //n为时间规模
{int i=1;while(i<=n) {i++;printf("I Love You %d\n",i);for(int j=1;j<=n;j++)printf("I am Iron man");}printf("I Love You More Than %d\n",n);
}
int main()
{loveYou(3000);
}
指数递增型爱你
//算法3 指数递增型爱你
void loveYou(int n) //n为时间规模
{int i=1;while(i<=n) {i=i*2;printf("I Love You %d\n",i);}printf("I Love You More Than %d\n",n);
}
int main()
{loveYou(3000);
}
搜索数字型爱你
//算法4 搜索数字型爱你
for(int i=0;i<n;i++) {if(flag[i]==n) {printf("I Love You");break;}}
空间复杂度
void loveYou(int n) //n为时间规模
{int i=1;while(i<=n) {i++;printf("I Love You %d\n",i);}printf("I Love You More Than %d\n",n);
}
int main()
{loveYou(3000);
}
void test(int n){int flag[n][n];//声明n*n的二维数组 int other[n];//声明长度n的二维数组int i;
}
//算法一 逐步递增型爱你
void loveYou(int n) //n为时间规模
{int flag[n]; //n是问题规模，n在递归中是变化的 if(n>1) {loveYou(n-1);}printf("I Love You %d\n",n);
}
int main()
{loveYou(5);
}
