数据结构学习笔记
第一章 绪论
1.1课程介绍
--逻辑结构：数据与数据之间的关系
--存储结构：存储数据的方法
--算法：解决问题的方法
1.2基本概念
1.按某种逻辑关系组织起来的一批数据 例如：线性表、树、图。
2.以一定的方式存于计算机中 例如：数组、链表等。
3.在这组数据上定义了运算的集合 例如：插入、删除、查找、排序等。
数据与数据元素
数据（data）：能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图像等，都称为数据。
数据元素（data element）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
一个数据元素包括若干个数据项（data item）。
数据元素、数据项和数据的逻辑结构在计算机中的表示又称为结点、数据域和存储（物质）结构。
数据的逻辑关系
---数据元素之间的逻辑关系
线性结构
元素之间的关系是一对一的。
树型结构
元素之间的关系是一对多的。
图状结构
元素之间的关系是多对多的。
数据的存储结构
---数据在计算机中的存储表示
1.顺序存储（数组）
例如：long a[20];
2.非顺序存储
3.索引存储
4.散列存储
数据的运算
插入、删除、查找、排序等。
数据类型（Data Type）
一个值的集合及定义在这个集合上的一组操作的总称。
关键码（key）
数据元素中能起作用的数据项，其中，能起唯一标识作用的关键码称为“主关键码（主码）“
1.3算法分析
算法与程序
算法（Algorithm）：是解决问题的一种方法（策略）或一个过程。
程序：用计算机语言实现算法。
算法设计的要求
（1）正确性（correctness）
（2）可读性（readablility）
（3）健壮性（robustness）
（4）高效率与低存储量
算法分析
（1）时间复杂度 --指算法中各语句执行时间的总和
（2）空间复杂度 --算法中所需占用的空间
第二章 线性表
2.1线性表的定义
定义
n（n>=0）个数据元素的有限序列。可表示为：(a1,a2,a3,...,an)
a1~an是n个数据元素 n表示线性表的长度，n=0时为空表
表示形式
可表示为：(a1,a2,a3,...,an)
还可以表示为二元组形式：(D,S) {D表示元素集合，S表示关系集合：前驱后继}
D={a1,a2,a3,...,an}
S={(a1,a2),(a2,a3),...,(an-1,an)}
元素关系
对于非空线性表(a1,a2,a3,...,an)
- 有且仅有一个开始节点a1，它没有前驱，而仅有一个后继a2
- 有且仅有一个中端节点an，它没有后继，而仅有一个前驱an-1
- 其余的内部节点ai(i>=2&&i<=n-1)都有且仅有一个前驱节点ai-1和一个后继节点ai+1
2.2顺序表
顺序存储结构
存储结构
数据结构在计算机中的表示，包括数据元素的表示和关系的表示。
数据元素之间的关系在计算机中有两种不同的表示方法
- 顺序存储结构----顺序表
- 链式存储结构----链表
顺序存储
#define MAXSIZE 100 //数组最大下标
typedef struct
{
ElemType a[MAXSIZE+1]; //线性表的存储空间
int n; //线性表的长度
}sqlist; //线性表类型 顺序表算法
常用操作：插入、删除、查找、排序
插入算法
算法功能：在线性表的第i出插入新元素x
算法思想：
（1）入口判断
存储容量够吗？(n<MAXSIZE)
插入位置正确吗？(i>=1&&i<=n+1)
if(L.n==MAXSIZE) error("溢出");
if(i<1||i>L.n+1) error("插入位置错"); （2）元素ai-an后移 （注意移动次序，应该从后往前移动）
for(j=n;j>=i;j--)
{
L.a[j+1]=l.a[j];
} （3）在线性表的第i出插入新元素x
L.a[i]=x;
（4）表长加1
L.n++;
算法设计
#define MAXSIZE 100
typedef struct
{
ElemType a[MAXSIZE+1]; //线性表的容量
int n; //线性表的表长
}sqlist;
void sq_ins(sqlist &L,int i,ElemType x) //线性表L的第i出插入新元素x
{
int j;
if(L.n==MAXSIZE) error("溢出");
else if(i<1||i>L.n+1) error("插入位置错");
else
{
for(j=L.n;j>=i;j--)
{
L.a[j+1]=L.a[j]; //元素后移
}
L.a[i]=x; //在i处插入元素x
L.n++; //表长加1
}
} 删除算法
算法功能：删除线性表中的第i个元素，并用x返回其值。
算法思想：
（1）入口判断
线性表时空的吗？删除位置正确吗？
if(i<1||i>L.n) error("删除位置错");
else if(L.n==0) error("表空"); （2）将第i个元素的值放进x（有时可以省略)
x=L.a[i];
（3）元素ai+1-an前移（注意次序）
for(int j=i+1;j<=L.n;j++)
{
L.a[j-1]=L.a[j];
} （4）表长-1
L.n--;
算法设计
#define MAXSIZE 100
typedef struct
{
ElemType a[MAXSIZE+1]; //线性表的容量
int n; //线性表的表长
}sqlist;
void sq_del(sqlist &L,int i,ElemType x) //删除线性表L中的第i个元素
{
if(i<1||i>L.n) error("删除位置错");
else if(L.n==0) error("表空");
else
{
for(int j=i+1;j<=L.n;j++)
{
L.a[j-1]=L.a[j]; //元素前移
}
L.n--; //表长-1
}
} 
SHEIN希音公司福利 294人发布