一、数据结构相关名词解释
数据
数据(data)是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整形、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。 数据必须具备两个前提：
1.可以输入到计算机中
2.能被计算机程序处理
数据对象
数据对象(data Object)是性质相同的数据元素的集合，是数据的子集。比如人 这个例子，都有姓名、生日、性别等相同的数据项。
数据元素
数据元素(data element)是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。 比如 车类 汽车、火车、卡车、挂车等车当然就是车类的数据元素。
数据项
数据项(data item)一个数据元素可以由若干个数据项组成。比如人有眼、耳、鼻、嘴等数据项，也可以有姓名、年龄、性别等数据项。数据项是数据不可分割的最小单位
二、数据结构
数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系
“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构
2.1 数据的逻辑结构
指反映数据元素其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。
逻辑结构包括：
- 集合：数据结构中的元素之间除了
同属一个集合的相互关系外，别无其他关系；- 线性结构：数据结构中的元素存在
一对一的相互关系；- 树形结构：数据结构中的元素存在
一对多的相互关系；- 图形结构：数据结构中的元素存在
多对多的相互关系。
2.2 数据的物理结构
数据的逻辑结构在计算机存储空间的存放形式，数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有
顺序存储、链式存储等
三、数据结构和算法的关系
两个是相互依赖的关系。数据结构是为算法服务的，算法要作用在特定的数据结构之上。下面的图很好的说明了数据结构和算法的关系
数据结构和算法的关系.png
从图中可以看出算法的4大特性：
输入输出有穷性确定性可行性
算法的设计也需要遵守正确性可读性健壮性时间效率高低储存的五大原则，
日常中算法设计中在保证算法的正确性的前提下最体现算法优劣的是:
时间复杂度：同样输入规模花费多少时间(时间效率高)空间复杂度：同样输入规模花费多少空间(低储存)
3.1 如何计算时间复杂度和空间复杂度
我们常用大O表示法表示时间复杂度和空间复杂度
时间复杂度有以下七种，算法时间复杂度依次增加：O(1)常数型、O(n)线性型、O(log2 n)对数型、O(nlog2n)二维型、O(n2)平方型、O(n3)立方型、O(2^n)指数型.
| 执行次数函数 | 阶 | 术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n2+2n+1 | O(n2) | 平方阶 |
| 5log2n + 20 | O(log n) | 对数阶 |
| 2n+3nlog2n+19 | O(nlog n) | nlogn阶 |
| 6n3+2n2+3n+4 | O(n3) | ⽴⽅阶 |
| 2n | O(2n) | 指数阶 |
我们通过下面的例子来说明大O表示法如何计算时间复杂度：
- 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次
}
- O(n)— 线性型时间复杂度
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
- O (log n)— 对数型时间复杂度
/*2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
- O(n²) — 二次方阶
/*二次方阶*/
//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;
}
}
}
- O(n3)—立方阶
/*立方阶*/
//sum = sum * 2; 执行n*n*n次 ->O(n3)
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次
}
}
}
}
- 指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!
空间复杂度主要考虑算法执行时所需要额辅助空间
计算公式：S(n)=n(f(n))
其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法(1) 需要用到辅助空间temp，所以空间复杂度为O(1) O(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) 需要用到b(n）的辅助空间，所以空间复杂度为O(n)
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]);
}
衡量一个算法的时候是描述最坏的情况，如果最坏情况一致，那么再比较平均值
四、线性表
4.1线性表-顺序表
使用线性表的顺序存储结构生成的表，称为顺序表。顺序存储就是将数据元素按照前后的次序全部存储在一整块连续的内存空间中。
对于⾮非空的线性表和线性结构,其特点如下:
- 存在唯一的一个被称作
第一个的数据元素;- 存在唯一的一个被称作
最后⼀个的数据元素- 除了了第⼀个之外,结构中的每个数据元素均有
一个前驱- 除了了最后一个之外,结构中的每个数据元素都有
一个后继.
- 4.1.1 顺序表初始化
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
/*线性结构使用顺序表的方式存储*/
//顺序表结构设计
typedef struct {
ElemType *data;
int length;
}Sqlist;
//1.1 顺序表初始化
Status InitList(Sqlist *L){
//为顺序表分配一个大小为MAXSIZE 的数组空间
L->data = malloc(sizeof(ElemType) * MAXSIZE);
//存储分配失败退出
if(!L->data) exit(ERROR);
//空表长度为0
L->length = 0;
return OK;
}
- 4.1.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;
}
- 4.1.3 顺序表的查找
Status GetElem(Sqlist L,int i, ElemType *e){
//判断i值是否合理, 若不合理,返回ERROR
if(i<1 || i > L.length) return ERROR;
//data[i-1]单元存储第i个数据元素.
*e = L.data[i-1];
return OK;
}
- 4.1.4 顺序表删除
/*
初始条件：顺序线性表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;
}
- 4.1.5 清空顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L)
{
L->length=0;
return OK;
}
- 4.1.6 判断顺序表清空
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(Sqlist L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
- 4.1.7 获取顺序表长度ListEmpty元素个数
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
int ListLength(Sqlist L)
{
return L.length;
}
- 4.1.8 顺序输出List
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
int i;
for(i=0;i<L.length;i++)
printf("%d\n",L.data[i]);
printf("\n");
return OK;
}
- 4.1.9 顺序表查找元素并返回位置
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
int i;
for(i=0;i<L.length;i++)
printf("%d\n",L.data[i]);
printf("\n");
return OK;
}
4.2线性单链表
使用链式存储结构生成的表，称为链式表。
链表的具体存储表示为：
用一组任意的存储单元来存放线性表的结点
链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针域)
单链表的重要组成为结点
头指针head和终端结点
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向首元结点结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。
一般我们创建单链表时会增加一个头结点，并使单链表(指针)指向头结点，这样做的好处有两点：
1.便于首元结点的处理
2.便于空表和非空表的统一处理
单链表的创建方法
不管是前插法还是后插法：都是先处理要插入的结点（要插入的的结点需要一个指针域next去指向它，防止丢失），再更新新结点的指针域next的指向，最后更新首元结点的指向或者表尾终端结点的指向
- 单链表前插入法
/* 随机产生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;
}
}
- 单链表后插入法
/* 随机产生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;
}
- 单链表插入
/*
初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
*/
Status ListInsert(LinkList *L,int i,ElemType e){
int j;
LinkList p,s;
p = *L;
j = 1;
//寻找第i-1个结点
while (p && j<i) {
p = p->next;
++j;
}
//第i个元素不存在
if(!p || j>i) return ERROR;
//生成新结点s
s = (LinkList)malloc(sizeof(Node));
//将e赋值给s的数值域
s->data = e;
//将p的后继结点赋值给s的后继
s->next = p->next;
//将s赋值给p的后继
p->next = s;
return OK;
}
- 单链表取值
/*
初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：用e返回L中第i个数据元素的值
*/
Status GetElem(LinkList L,int i,ElemType *e){
//j: 计数.
int j;
//声明结点p;
LinkList p;
//将结点p 指向链表L的第一个结点;
p = L->next;
//j计算=1;
j = 1;
//p不为空,且计算j不等于i,则循环继续
while (p && j<i) {
//p指向下一个结点
p = p->next;
++j;
}
//如果p为空或者j>i,则返回error
if(!p || j > i) return ERROR;
//e = p所指的结点的data
*e = p->data;
return OK;
}
- 单链表删除元素
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
*/
Status ListDelete(LinkList *L,int i,ElemType *e){
int j;
LinkList p,q;
p = (*L)->next;
j = 1;
//查找第i-1个结点,p指向该结点
while (p->next && j<(i-1)) {
p = p->next;
++j;
}
//当i>n 或者 i<1 时,删除位置不合理
if (!(p->next) || (j>i-1)) return ERROR;
//q指向要删除的结点
q = p->next;
//将q的后继赋值给p的后继
p->next = q->next;
//将q结点中的数据给e
*e = q->data;
//让系统回收此结点,释放内存;
free(q);
return OK;
}
