数据结构
数据结构是一门研究数据组织存储和运算的一般方法的学科。
数据结构中有几种类型
逻辑特征：一对一
直接前驱，直接后驱，开始结点，终端结点
树
逻辑特征：一对多
有且只有一个根节点，
除根节点外，每个节点都有且只有一个唯一的前驱
除叶子结点外，每个节点都有后继结点
图
逻辑结构：多对多
数据结构的存储类型分类：
顺序存储：按照给定的顺序进行存储
链式存储：使用链的形式进行存储
散列存储
索引存储
算法
一个算法是由若干的指令组成的有序数组
性质
- 有穷性：算法在有穷的步数中结束，每一步都在有穷的时间内完成
- 确定性：每条指令的含义都必须明确
- 可行性：能够由机器人或者计算机或者人完成
检验一个算法的好坏
- 正确性：能否满足预先的功能和性能要求
- 可读性：算法是够可读，易读
- 健壮性：当输入非法时，算法是否能及时给出反馈
- 时间效率和空间效率：两个复杂度
时间复杂度和空间复杂度
时间复杂度：执行当前算法所消耗的时间
空间复杂度：执行当前算法所占用的内存
https://www.yuque.com/vernus-u2vmo/tgvyrt/to9tln8g55kvhl0y?singleDoc#
线性表和链表
线性表
基本概念：一个数据元素的有序集，其基本特征
- 集合中存在唯一的一个第一个元素
- 集合中存在唯一的一个最后一个元素
- 除第一个元素外都存在为一个直接前驱
- 除最后一个元素外都存在唯一的一个直接后驱
顺序表的建立
1
2
3
4
5
6
7
8
9
10
| #include<stdio.h>
#include<stdlib.h>
typedef int Datatype；
struct List
{
int MAX;
int n;
DataType *elem;
};
typedef struct List*SeqList;
|
顺序表的判空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| SeqList SetNullList_seq(int m)
{
SeqList slist=(SeqList)malloc(sizeof(struct List));
if(slist!=NULL)
{
slist->elem=(DataType*)malloc(sizeof(DataType)*m);
if(slist->elem)
{
slist->Max=m;
slist->n=0;
return(slist);
}
else free(slist);
}
printf("ALLoc failure!\n");
return NULL;
}
|
顺序表的插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int InsertPre_seq(SeqList slist,int p,DataType x)
{
int q;
if(slist->n>=slist->Max)
{
printf("overflow");
return 0;
}
if(p<0||p>slist->n)
{
printf("not exist!\n");
return 0;
}
for(q=slist->n-1;q>=p;q--)
slist->elem[q+1]=slist->elem[q];
slist->elem[p]=x;
slist->n=slist->n+1;
return 1;
}
|
顺序表的删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int DelIndex_seq(SeqList slist,int p)
{
int q;
if(p<0||p>=slist->n)
{
printf("Not exist");
return 0;
}
for(q=p;q<slist->n-1;q++)
{
slist ->elem[q]=slist ->elem[q+1];
}
slist ->n=slist->n-1;
return 1;
}
|
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int binsearch(SeqList slist,int key,int *pos)
{
int index=1;int mid;
int low = 0;int high=slist->n-1;
while(low<=high)
{
if(slist->ekem[mid]==key)
{
*pos=mid;
printf("已经找到，共进行%d次比较\n"，index);
printf("要找到的数据%d在位置%d上\n"，key,mid);
return 1;
}
else if (slist->elem[mid]>key)
{
high = mid -1;
}
else low = mid + 1;
index++;
}
*pos = llow;
printf("没找到，共进行%d次比较\n"，index-1)；
printf("可以在%d上插入位置\n"，*pos);
}
|
栈
特性：
后进先出
分类：
顺序栈
链栈
应用：
前缀中缀表达式
https://www.yuque.com/vernus-u2vmo/tgvyrt/zh4geied5wd2ldpm?singleDoc# 《栈的应用》
计算器
单调栈（例题——洛谷《音乐会的等待》）
队列
特性：
先进先出，跟栈相反
分类
单队列
假溢出
循环队列
需要一个闲置的空区
可以解决顺序队列中的假溢出和越界问题
