是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存储）物理结构和数据的运算三个部分.
数据结构与算法.jpg
核心术语
• 通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机课实现的物理结构，从而便于计算机处理
• 数据: 是可以被自算计处理的符号或符号集合(原材料)
• 数据对象: 性质相同的数据元素的集合(一个公司人的集合)
• 数据元素: 数据的基本单位(每一个个体)
• 数据项: 组成数据元素的最小单位(姓名、性别、)
图片.png
数据类型: 是指⼀组性质相同值的集合以及定义在此集合的⼀些操作的总称.
在C语⾔中,按照取值不同,数据类型可以分为2类:
• 原⼦类型: 是不可以在分解的基本数据类型,包含整型,浮点型,字符型等;
• 结构类型: 由若⼲类型组合⽽成,是可以再分解的.例如,整型数组就是由若⼲整型数据组成的.
逻辑结构和物理结构的区别
• 逻辑结构：指在数据中数据元素之间的相互关系。分为：线性结构和非线性结构
1. 线性结构：结构关系是一对一的，并且是一种先后的次序
• 主要特征为存在唯一的被叫做第一个和最后一个数据，
• 除第一个元素之外每个数据元素均有⼀个前驱。
• 除最后一个元素之外每个数据元素均有一个后继。
• 表现形式为：线性表、栈和队列、字符串（特殊的线性结构）
2. 非线性结构：
• 表现形式为: 集合结构、树形结构、图形结构
• 集合结构: 元素之间没有特殊的关系，只是属于一个集合
• 树形结构: 元素结构关系是一对多，比如公司的人员架构图( CEO)
• 图形结构: 结构关系是多对多的，比如铁路网
• 数据的物理结构:数据的逻辑结构在计算机中的存储形式
1.顺序存储结构: 数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的
2.链式存储结构: 数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的
算法特性
• 有穷行: 算法可以在某一个条件下自动结束而不是出现无限循环
• 确定性: 算法执行的每一步骤在一定条件下只有一条执行路径，一个相同的输入对应相同的一个输出
• 可行性: 算法每一步骤都必须可行，能够通过有限的执行次数完成
• 输入: 算法具有零个或多个输入
• 输出: 算法至少有一个或多个输出
算法效率衡量方法
• 正确性
• 可读性
• 健壮性
• 高效性
算法时间复杂度:大O表示法
• 用常数1取代运行时间中所有常数 3->1 O(1)
• 在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
• 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
常见的算法复杂度
• 常数阶
//1常数阶 执行3次。O(1)
void testNum1(int n){
int sum = 0 ;//执行一次
sum = (n+1)*n/2; //执行一次
printf("sum=%d\n",sum);//执行一次
}
• 线性阶
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
• 平方阶
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
• 对数阶
/* 2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
• 立方阶
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次
}
}
}
}
• nlog阶
• 指数阶（不考虑）
常见的算法的时间复杂度.png
0(1) < 0(logn) < 0(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
算法空间复杂度计算
在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间.
- 数组逆序,将一维数组a中的n个数逆序存放在原数组中
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(1)
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];//中间变量
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
{
printf("--%d\n",a[i]);
}
//算法实现(2)
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
for(int i = 0;i < 10;i++)
{
printf("++%d\n",a[i]);
}
- 交换两个数
// 中间变量
int a = 10 ;
int b = 20 ;
int e ;
e = a ;
a = b ;
b = e ;
// 叠加
a = a+b;
b = a-b;
a = a-b;
// 异或
a = a ^ b;
b = a ^ b;
a = a ^ b;
线性表
ADT List {
Data: 线性表的数据对象集合为{a1,a2,......an},每个元素的类型均为DataType. 其中,除了第⼀个元素a1外,每⼀个元素有且
只有⼀个直接前驱元素,除了最后⼀个元素an外,每个元素有且只有⼀个直接后继元素. 数据元素之间的关系是⼀对⼀的关系.
Operation
InitList(&L)
操作结果:初始化操作,建⽴⼀个空的线性表L.
DestroyList(&L)
初始条件: 线性表L已存在
操作结果: 销毁线性表L.
ClearList(&L)
初始条件: 线性表L已存在
操作结果: 将L重置为空表.
ListEmpty(L)
初始条件: 线性表L已存在
操作结果: 若L为空表,则返回true,否则返回false.
ListLength(L)
初始条件: 线性表L已存在
操作结果: 返回L中数据元素的个数
……
GetElem(L,i,&e)
初始条件: 线性表L已存在,且1<=i<ListLength(L)
操作结果: ⽤e返回L中第i个数据元素的值;
LocateElem(L,e)
初始条件: 线性表L已存在
操作结果: 返回L中第1个值与e相同的元素在L中的位置. 若数据不存在则返回0;
PriorElem(L, cur_e,&pre_e);
初始条件: 线性表L已存在
操作结果: 若cur_e是L的数据元素,且不是第⼀个,则⽤pre_e返回其前驱,否则操作失败.
NextElem(L, cur_e,&next_e);
初始条件: 线性表L已存在
操作结果: 若cur_e是L的数据元素,且不是最后⼀个,则⽤next_e返回其后继,否则操作失败.
……
ListInsert(L,i,e);
初始条件: 线性表L已存在,且1<=i<=listLength(L)
操作结果: 在L中第i个位置之前插⼊新的数据元素e,L⻓度加1.
ListDelete(L,i);
初始条件: 线性表L已存在,且1<=i<=listLength(L)
操作结果: 删除L的第i个元素,L的⻓度减1.
TraverseList(L);
初始条件: 线性表L已存在
操作结果: 对线性表L进⾏遍历,在遍历的过程中对L的每个结点访问1次.
}ADT List.
• 单链表的节点：是由数据域和指针域组成
图片.png
• 单链表的首指针指向首元结点（第一个节点）,最后一个节点的指针域为空，其余节点的指针域指向下一个节点
图片.png
• 单链表的头结点
1.便于首元结点的处理
2.便于空表和非空表的统一处理
头结点.jpeg
关于顺序存储的实现
• 顺序表的结构设计
/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//顺序表结构设计
typedef struct {
ElemType *data;
int length;
}Sqlist;
length是作为一个线性表判断的依据
1.初始化
Status InitList (Sqlist *L){
//为顺序表分配一个大小为MAXSIZE 的数组空间
L->data = malloc(sizeof(ElemType)* MAXSIZE);
if(!L->data) exit(ERROR);
//空表长度为0
L->length = 0;
return OK;
}
2.数据插入
/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
Status ListInsert(Sqlist *L,int i,ElemType e){
//i值不合法判断
if((i<1) || (i>L->length+1)) return ERROR;//因为 习惯。是从第一位开始存储的
//存储空间已满
if(L->length == MAXSIZE) return ERROR;
//插入数据不在表尾,则先移动出空余位置
if(i <= L->length){
for(int j = L->length-1; j>=i-1;j--){
//插入位置以及之后的位置后移动1位
L->data[j+1] = L->data[j];
}
}
//将新元素e 放入第i个位置上
L->data[i-1] = e;
//长度+1;
++L->length;
return OK;
}
- 顺序表的删除
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果: 删除L的第i个数据元素,L的长度减1
*/
Status ListDelete(Sqlist *L,int i){
//线性表为空
if(L->length == 0) return ERROR;
//i值不合法判断
if((i<1) || (i>L->length+1)) return ERROR;
for(int j = i; j < L->length;j++){
//被删除元素之后的元素向前移动
L->data[j-1] = L->data[j];
}
//表长度-1;
L->length --;
return OK;
}
- 删除顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
L->length=0;
5.顺序表查找元素并返回位置
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(Sqlist L,ElemType e)
{
int i;
if (L.length==0) return 0;
for(i=0;i<L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length) return 0;
return i+1;
}
线性表-关于链式存储的设计
单向链表：新建一个节点->将原链表最后的一个节点的指针域指向新建节点->新建节点的指针域置为NULL作为新链表的最后一个节点
• 单链表的插入（前插法和后插法）
在单链表的的两个数据元素a,b之间插入一个元素c ，p是单链表存储结构中指向结点a的指针
-
找到插入结点之前的结点的指针p
2.创建一个新的结点s
3.给s的数据域赋值
4.把s的指针域next指向要插入的结点之后的结点，就是b
5.把a的指针指向s
单链表的插入.png
• 单链表的删除（a,b,c）删除b
1.找到删除结点之前的结点的指针p
2.创建一个指针s指向要删除的结点b
3.把a的指针域的next指向b的next
4.把s结点释放free
单链表的删除.png
（如果不是放会一直占用这块内存）
//3.1 单链表前插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(LinkList *L, int n){
LinkList p;
//建立1个带头结点的单链表
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
//循环前插入随机数据
for(int i = 0; i < n;i++)
{
//生成新结点
p = (LinkList)malloc(sizeof(Node));
//i赋值给新结点的data
p->data = i;
//p->next = 头结点的L->next
p->next = (*L)->next;
//将结点P插入到头结点之后;
(*L)->next = p;
}
}
//3.2 单链表后插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListTail(LinkList *L, int n){
LinkList p,r;
//建立1个带头结点的单链表
*L = (LinkList)malloc(sizeof(Node));
//r指向尾部的结点
r = *L;
for (int i=0; i<n; i++) {
//生成新结点
p = (Node *)malloc(sizeof(Node));
p->data = i;
//将表尾终端结点的指针指向新结点
r->next = p;
//将当前的新结点定义为表尾终端结点
r = p;
}
//将尾指针的next = null
r->next = NULL;
}
网友评论