目录
一、数据
二、数据结构
2.1 逻辑结构：数据元素之间一种或多种关系
2.2 存储结构：逻辑结构在计算机的存储形式
三、时间复杂度
四、顺序表
4.1 顺序表的概念
4.2 顺序表的操作
4.2.1 创建顺序表
4.2.2 顺序表的尾插
4.2.3 顺序表的遍历
4.2.4 顺序表尾删
4.2.5 顺序表按下表插入
4.2.6 顺序表按下表删除
4.2.7 顺序表按下表修改
4.2.8 顺序表按下表查找
4.2.9 顺序表按元素查找
4.2.10 顺序表按元素删除
4.2.11 顺序表按元素修改
4.2.12 顺序表去重
4.2.13 顺序表排序 （冒泡、选择排序）
4.2.14 head.h(头文件)、main.c(主函数)、fun.c（自定义函数）
head.h:
main.c:
fun.c:
PS：切勿忘记在头文件中做函数声明，以及在主函数和自定义函数中调用"head.h"
4.2.15 代码执行后结果
一、数据
数据：能被计算机识别，存储，处理的符号
(数据：整数，小数，字符串，声音，图片，视频，文件，app)
数据元素：是由数据项组成，是数据基本单位
数据项：数据的最小单位
数据对象：由多个类型相同的数据元素组成的集合
二、数据结构
数据结构：存储多个数据元素之间一种或多种关系的集合
D_S=(D,R)
2.1 逻辑结构：数据元素之间一种或多种关系
1.集合结构：多个数据元素之间不存在关系
2.线性结构：多个数据元素之间存在一对一的逻辑关系
数据元素存在唯一的直接后继，唯一的直接前驱，第一个元素无前驱，最后一个元素无后继
3.树形结构：数据元素之间存在一对多的逻辑关系
数据元素存在唯一的直接前驱，多个后继，第一个元素无前驱，最后一个元素无后继
4.图形结构：数据元素之间存在多对多的逻辑关系
2.2 存储结构：逻辑结构在计算机的存储形式
1.顺序存储：使用一段连续的存储空间存储类型相同的多个数据(数组)
2.链式存储：使用任意一段存储空间存储类型相同的多个数据元素
3.散列存储：哈希存储，一个关键字通过哈希函数映射在计算机内存的一种存储方式(词典) 查找
4.索引存储：使用索引表和数据文件共同实现的查找方式
三、时间复杂度
时间复杂度：程序的执行次数
T(n)=O(f(n))
T:时间 T(n):时间复杂度
O:大O阶，渐进符
n:问题的规模 f(n):问题规模的函数
注意：时间复杂度需要保留最高阶
f(n)=3*n^2+5*n+100 --->3*n^2 --->n^2
T(n)=O(n^2)
1.O(1)常数阶int t; 1t=a; 1a=b; 1b=t; 1
f(n)=4=4*n^0=n^0-->1
T(n)=O(1)
2.O(n) 线性阶for(i=1;i<=n;i++) n+1{printf("hello\n"); n }
f(n)=2*n+1 --->n
T(n)=O(n)
3.O(n^2) 平方阶for(i=0;i<n;i++) n+1{for(j=0;j<n;j++) n*(n+1){printf("hello\n") ; n*n} }
f(n)=2*n^2+2*n+1---->n^2
T(n)=O(n^2)
4.O(log2n) 对数阶int i=1; 1while(i<n) 1234 (log2 n) +1{i*=2; 3 log2 n}2^3=8 log2 n=3
f(n)=2*log2n +1 ---->log2n
T(n)=O(log2n)四、顺序表
4.1 顺序表的概念
顺序表：线性表的顺序存储，称为顺序表 (数组）
线性表：是由多个类型相同，个数有限的数据元素组成的集合 (属相）
顺序表：逻辑结构线性结构
存储结构：顺序存储
线性表的分类：顺序表，链表，栈，队列，数组，字符串
1.顺序表的本质是数组，所以下表从0开始
2.顺序表长度：实际元素的个数,改变 变量
int arr[10]
for(int i=0;i
3.线性表长度\数组长度: 实际数组的最大空间 ，不可变 #define MAXSIZE 7
4.定义一个顺序表： 数据元素，顺序表长度
4.2 顺序表的操作
本章所有操作皆为多文件编译操作，将分为head.h(头文件)、main.c(主函数)、fun.c(自定义函数)三个文档去编写代码，下面主要为大家展示自定义函数部分。（章尾有三个文档的内容截图）
4.2.1 创建顺序表
Sqlist *creat_Sqlist()
{// 创建顺序表Sqlist *list=(Sqlist*)malloc(sizeof(Sqlist));if(NULL==list){printf("Sqlist creat fales\n");return NULL;}// 对数据元素清零memset(list->data,0,sizeof(list->data));// 对顺序表长度清零list->len=0;return list;
}
4.2.2 顺序表的尾插
int input_list(datetype element,Sqlist *list)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否满if(list==NULL||list->len==MAXSIZE){printf("input list error\n");return FALSE;}// 3.在尾部插入/*for(list->len;list->len<MAXSIZE;list->len++){scanf("%d",&(list->data[list->len]));}list->len--;*/list->data[list->len]=element;list->len++;return SUCCESS;
}
4.2.3 顺序表的遍历
oid output_list(Sqlist *list)
{printf("data=");for(int i=0;i<list->len;i++){printf("%d ",list->data[i]);}putchar(10);
}
4.2.4 顺序表尾删
int delete_list(Sqlist *list)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("delete_list error\n");return FALSE;}// 3.顺表表尾部删除list->data[list->len-1]=0;list->len--;return SUCCESS;
}
4.2.5 顺序表按下表插入
int insert_sub(Sqlist *list,datetype element,int sub)
{if(list==NULL||list->len==MAXSIZE||sub<0||sub>list->len){printf("insert_pos erroe\n");return FALSE;}for(int i=list->len-1;i>=sub;i--){list->data[i+1]=list->data[i];}list->data[sub]=element;list->len++;
}
4.2.6 顺序表按下表删除
int delete_sub(Sqlist *list,int sub)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空// 3.判断下标是否合法if(list==NULL||list->len==0||sub<0||sub>=list->len){printf("delete_element error\n");return FALSE;}// 4.按下标删除for(int i=sub+1;i<list->len;i++){list->data[i-1]=list->data[i];}list->len--;return SUCCESS;
}
4.2.7 顺序表按下表修改
int change_list(Sqlist *list,int sub,datetype element)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空// 3.判断下标是否合法if(list==NULL||list->len==0||sub<0||sub>=list->len){printf("change_list error\n");return FALSE;}// 4.修改指定位置值list->data[sub]=element;return SUCCESS;
}
4.2.8 顺序表按下表查找
int find_list(Sqlist *list,int sub)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空// 3.判断下标是否合法if(list==NULL||list->len==0||sub<0||sub>=list->len){printf("find_list error\n");return FALSE;}// 4.打印下标对应值printf("data[%d]=%d\n",sub,list->data[sub]);return sub;
}
4.2.9 顺序表按元素查找
int find_element(Sqlist *list,datetype element)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("find_element error\n");return FALSE;}// 3.循环列表元素，存在则下标返回sub，不存在则-1；for(int i=0;i<list->len;i++){if(list->data[i]==element){return i;}}return FALSE;
}
4.2.10 顺序表按元素删除
int delete_element(Sqlist *list,datetype element)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("delete_element error\n");return FALSE;}// 3.调用元素查找函数，找到需要删除元素对应下标int delete_element_sub=find_element(list,element);// 4.根据得到下标删除元素delete_sub(list,delete_element_sub);
}
4.2.11 顺序表按元素修改
int change_element(Sqlist *list,datetype element,datetype element2)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("change_element error\n");return FALSE;}// 3.调用“按元素寻找”函数，寻找元素下标int change_element_sub=find_element(list,element);// 4.根据下标，调用“按下标修改”函数，修改值change_list(list,change_element_sub,element2);
}
4.2.12 顺序表去重
int delete_re_element(Sqlist *list)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("delete_re_element error\n");return FALSE;}// 3.从第一个元素开始，对比后面是否有重复元素，有则删除后面元素，无则进行下一个元素对比int re_element;for(int i=0;i<list->len;i++){re_element=list->data[i];for(int j=i+1;j<list->len;j++){if(list->data[j]==re_element){delete_sub(list,j);j--;}}}return SUCCESS;
}
4.2.13 顺序表排序 （冒泡、选择排序）
冒泡排序：
int bubble_sort(Sqlist *list)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("bubble_sort error\n");return FALSE;}// 3.进行冒泡排序int temp;for(int i=0;i<list->len-i;i++){for(int j=0;j<list->len-1;j++){if(list->data[j]>list->data[j+1]){temp=list->data[j];list->data[j]=list->data[j+1];list->data[j+1]=temp;}}}return SUCCESS
}
选择排序：
int selection_sort(Sqlist *list)
{// 1.判断顺序表是否被创建// 2.判断顺序表是否为空if(list==NULL||list->len==0){printf("selection_sort error\n");return FALSE;}// 3.进行选择排序int min_id,temp;for(int i=0;i<list->len-1;i++){min_id=i;for(int j=i+1;j<list->len;j++){if(list->data[j]<list->data[min_id]){min_id=j;}}if(min_id!=i){temp=list->data[i];list->data[i]=list->data[min_id];list->data[min_id]=temp;}}return SUCCESS;
}
4.2.14 head.h(头文件)、main.c(主函数)、fun.c（自定义函数）
head.h:
main.c:
fun.c:
PS：切勿忘记在头文件中做函数声明，以及在主函数和自定义函数中调用"head.h"
eg:
4.2.15 代码执行后结果
