数据结构 - 基本数据单位
1.数据结构概念：
通过图解释：
数据结构图.png
数据：程序的操作对象，用于描述客观事物。（如 二进制数据、整型数据等）
- 数据的特点：1.可以输入到计算机。2.可以被计算机处理。
数据对象: 性质相同的数据元素的集合(类似于数组)
数据元素: 组成数据的对象的基本单位
数据项: 一个数据元素由若干数据项组成
结构: 数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
数据结构:指的数据对象中的数据元素之间的关系
2.数据结构代码举例：
- 声明一个结构体：
struct Teacher{
char * name;
char * title;
int age;
}
解释：
-
struct Teacher{}是一种数据结构 -
char * name;数据项--名字
char * title;数据项 -- 职称
int age;数据项 -- 年龄
2.使用结构体：
int main(int argc, const char * argv[]) {
struct Teacher t1; //数据元素;
struct Teacher tArray[10]; //数据对象;
t1.age = 18; //数据项
t1.name = "GC"; //数据项
t1.title = "搬砖工"; //数据项
return 0;
}
解释：
-
struct Teacher t1;数据元素 -
struct Teacher tArray[10];数据对象 -
t1.age = 18;数据项
t1.name = "GC";数据项
数据结构
1.逻辑结构
根据元素之间的关系可以分为： 线性结构 和 非线性结构
-
线性结构
特点：- 存在唯一的一个被称作"第一个"的数据元素
- 存在唯一的一个呗称作"最后一个"的数据元素
- 除了第一个之外,结构中的每个数据元素均有一个前驱
- 除了最后一个之外,结构中的每个数据元素都有一个后继.
- 线性结构：（队列（先进先出 FIFO）、栈（先进后出）、字符串、数组等）
-
非线性结构
- 集合结构：所有数据属于同一个集合
- 树形结构：存在的关系是 -> 一对多 （二叉树、红黑树、平衡二叉树等）
- 图形结构：存在的关系是 -> 多对多
逻辑结构最终也是存在内存中，内存中的存储结构是物理结构。
2.物理结构
- 顺序存储结构：
- 链式存储结构：不需要提前开辟一段内存空间
数据结构与算法
1.算法特征
• 有穷行: 算法可以在某一个条件下自动结束而不是出现无限循环
• 确定性: 算法执行的每一步骤在一定条件下只有一条执行路径，一个相同的输入对应相同的一个输出
• 可行性: 算法每一步骤都必须可行，能够通过有限的执行次数完成
• 输入: 算法具有零个或多个输入
• 输出: 算法至少有一个或多个输出
2.算法设计要求
• 正确性
• 可读性
• 健壮性
• 时间效率高和存储量低
算法 时间复杂度
1.时间复杂度：使用大O表示法
- 用常数1取代运行时间中所有常数 3->1 O(1)
- 在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
- 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
2.时间复杂度术语:
- 常数阶
- 线性阶
- 平方阶
- 对数阶
- 立方阶
- nlog阶
- 指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!
- 常数阶
// 执行3次。表示为 O(1)
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}
- 线性阶
//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
复杂度排序：
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
空间复杂度
1.程序空间计算因素:
•寄存本身的指令
• 常数
• 变量
• 输入
• 对数据进行操作的辅助空间
注意：在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间
2.空间复杂度计算
通过一个问题引出 空间复杂度的计算
问题：数组逆序,将一维数组a中的n个数逆序存放在原数组中.
- 算法1 :使用中间变量
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
//算法实现(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]);
}
线性表
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.
线性表 -> 顺序存储
特点：逻辑相邻，物理存储地址也相邻
代码实现：
#define MAXSIZE 100 // size的最大值
#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.顺序表的初始化
// 修改链表本身，需要传入指针
Status InitList(sqlist *L){
//为顺序表分配一个大小为MAXSIZE 的数组空间
L->data = malloc(sizeof(ElemType) * MAXSIZE);
//存储分配失败退出
if(!L->data) exit(ERROR);
//空表长度为0
L->length = 0;
return OK;
}
main函数中调用：
int main(int argc, const char * argv[]) {
Sqlist L;
Sqlist Lb;
ElemType e;
Status iStatus;
//1.1 顺序表初始化
iStatus = InitList(&L);
printf("初始化L后: L.Length = %d\n", L.length);
}
- 2.数据插入
注意事项：1.判断线性表是否存在 2.插入的位置是否合法 3.修改length
//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;
}
- 3.顺序表的删除
顺序表删除
/*
初始条件：顺序线性表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)) return ERROR;
for(int j = i; j < L->length;j++){
//被删除元素之后的元素向前移动
L->data[j-1] = L->data[j];
}
//表长度-1;
L->length --;
return OK;
}
- 4.清空顺序表（链表）
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L)
{
L->length=0;
return OK;
}
线性表 -> 单链表结点
单链表结点结构：是由数据域和指针域组成
单链表结点结构.png
单链表的结构.png
注意：1.便于首元结点的处理 2.便于空表和非空表的统一处理
单链表的头结点：
头结点的作用：
1.便于首元结点的处理
2.便于空表和非空表的统一处理
单链表的头结点.png
线性表 -> 链式存储
-
单链表的插入
单链表的插入方式分为
前插法和后插法。-
在单链表的两个数据a、b中间插入一个结点c，插入一个元素。（流程如下）
1、找到插入结点之前的结点指针P。
2、创建一个新的结点c。
3、给新的结点c数据域赋值。
4、把c的指针域next指向要插入的结点之后的结点，就是b。
5、把a的指针指向c
单链表的插入.png
-
单链表的删除（a,b,c）删除b
1.找到删除结点之前的结点的指针p
2.创建一个指针s指向要删除的结点b
3.把a的指针域的next指向b的next
4.把s结点释放free
单链表的删除.png 代码实现
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
1.初始化单链表线性表
// 初始化单链表线性表
Status InitList(LinkList *L){
//产生头结点,并使用L指向此头结点
*L = (LinkList)malloc(sizeof(Node));
//存储空间分配失败
if(*L == NULL) return ERROR;
//将头结点的指针域置空
(*L)->next = NULL;
return OK;
}
2.单链表的插入
/*
初始条件:顺序线性表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;
}
3.单链表删除元素
/*
初始条件：顺序线性表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;
}
4.单链表的前插入
/* 随机产生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;
}
}
5.单链表的后插入
/* 随机产生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;
}
main方法中的函数调用
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
Status iStatus;
LinkList L1,L;
struct Node *L2;
ElemType e;
// 单链表初始化
iStatus = InitList(&L);
printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
// 单链表插入数据
for(int j = 1;j<=10;j++)
{
iStatus = ListInsert(&L, 1, j);
}
// 删除第5个元素
iStatus = ListDelete(&L, 5, &e);
printf("删除第5个元素值为:%d\n",e);
ListTraverse(L);
// 前插法整理创建链表L
iStatus = ClearList(&L);
CreateListHead(&L, 20);
printf("整理创建L的元素(前插法):\n");
ListTraverse(L);
// 后插法整理创建链表L
iStatus = ClearList(&L);
CreateListTail(&L, 20);
printf("整理创建L的元素(后插法):\n");
ListTraverse(L);
不管是前插法还是后插法：都是先处理要插入的结点（要插入的的结点需要一个指针域next去指向它，防止丢失），再更新新结点的指针域next的指向，最后更新首元结点的指向或者表尾终端结点的指向。
