没有合适的资源?快使用搜索试试~ 我知道了~
数据结构笔记-《考研王道笔记知识点整理》
需积分: 0 96 下载量 131 浏览量
2023-05-23
22:04:40
上传
评论 8
收藏 2.19MB PDF 举报
温馨提示
试读
70页
数据结构笔记-《考研王道笔记知识点整理》/2024最新版
资源推荐
资源详情
资源评论
@TOC
第一章:绪论
1.1数据结构的基本概念
1.数据:数据是信息的载体,是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别
和处理的符号的集合。
2.数据元素:数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干
数据项组成,数据项是构成数据元素的不可分割的最小单位。例如,学生记录就是一个数据元素,它由
学号、姓名、性别等数据项组成。
3.数据对象:数据对象是具有相同性值的数据元素的集合,是数据的一个子集。
4.数据类型:数据类型是一个值的集合和定义再此集合上的一组操作的总称。
1)原子类型。其值不可再分的数据类型。如bool 和int 类型。
2)结构类型。其值可以再分解为若干成分(分量)的数据类型。
3)抽象数据类型。抽象数据组织及与之相关的操作。
5.数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
1.2数据结构的三要素
1.数据的逻辑结构:
逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。
逻辑结构包括:
1. 集合结构:结构中的数据元素之间除“同属一个集合”外,别无其它关系。
2. 线性结构:结构中的数据元素之间只存在一对一的关系,除了第一个元素,所有元素都有唯一前
驱;除了最后一个元素,所有元素都有唯一后继。
3. 树形结构:结构中数据元素之间存在一对多的关系。
4. 图状结构:数据元素之间是多对多的关系。
2.数据的存储结构(物理结构):
存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构。
存储结构包括:
1. 顺序存储:把逻辑上相邻的元素存储在物理位置也相邻的存储单元中,元素之间的关系由存储单元
的邻接关系来体现。
2. 链式存储:逻辑上相邻的元素在物理位置上可以不相邻,借助指示元素存储地址的指针来表示元素
之间的逻辑关系。
3. 索引存储:在存储元素信息的同时,还建立附加的索引表,索引表中的每项称为索引项,索引项的
一般形式是(关键字,地址)
4. 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。
3.数据的运算:施加在数据上的运算包括运算的定义何实现。运算的定义是针对逻辑结构的,指出运算
的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。
1.3算法的基本概念
程序=数据结构+算法
算法(algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个
或多个操作。
算法的特性:
1.有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。
2.确定性:算法中每条指令必须有确定的含义,对于相同的输入只能得到相同的输出。
3.可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4.输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。
5.输出:一个算法有一个多个输出,这些输出是与输入有着某种特定关系的量。
好的算法达到的目标:
1. 正确性:算法应能够正确的求接问题。
2. 可读性:算法应具有良好的可读性,以帮助人们理解。
3. 健壮性:输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名奇妙地输出结果。
4. 效率与低存储量需求:效率是指算法执行的时间,存储量需求是指算法执行过程中所需要的最大存
储空间,这两者都与问题的规模有关。
1.4算法的时间复杂度
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T
(n)=O(n),它表示随问题规模n的增大而增大,算法执行时间的增长率和f(n)的增长率相同,称作算法
的渐近时间复杂度,简称时间复杂度。
1.5算法的空间复杂度
算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数。记为S(n)=O(g(n))。
第二章:线性表
2.1线性表的定义
线性表是具有相同数据类型的n(n>0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空
表。
2.2顺序表的定义
2.2.1静态分配:
//顺序表的实现--静态分配
#include<stdio.h>
#define MaxSize 10 //定义表的最大长度
typedef struct{
int data[MaxSize];//用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)
void InitList(SqList &L){
for(int i=0;i<MaxSize;i++){
L.data[i]=0; //将所有数据元素设置为默认初始值
}
2.2.2动态分配
顺序表的特点:
1. ==随机访问== ,可以在O(1)时间内找到第i个元素。
2. 存储密度高,每个节点只存储数据元素
3. 拓展容量不方便
4. 插入、删除操作不方便,需要移动大量元素
L.length=0;
}
int main(){
SqList L;//声明一个顺序表
InitList(L);//初始化一个顺序表
for(int i=0;i<MaxSize;i++){
printf("data[%d]=%d\n",i,L.data[i]);
}
return 0;
}
//顺序表的实现——动态分配
#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件
#define InitSize 10 //默认的最大长度
typedef struct{
int *data;//指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
//初始化
void InitList(SeqList &L){
//用malloc 函数申请一片连续的存储空间
L.data =(int*)malloc(InitSize*sizeof(int)) ;
L.length=0;
L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len
free(p); //释放原来的内存空间
}
int main(void){
SeqList L; //声明一个顺序表
InitList(L);//初始化顺序表
IncreaseSize(L,5);
return 0;
}
2.2顺序表的基本操作
1.插入操作 :平均时间复杂度O(n)
2.删除操作:平均时间复杂度O(n)
3.按位查找(获取L表中第i个位置的值):平均时间复杂度O(1)
bool ListInsert(SqList &L, int i, int e){
//判断i的范围是否有效
if(i<1||i>L.length+1)
return false;
if(L.length>MaxSize) //当前存储空间已满,不能插入
return false;
for(int j=L.length; j>i; j--){ //将第i个元素及其之后的元素后移
L.data[j]=L.data[j-1];
}
L.data[i-1]=e; //在位置i处放入e
L.length++; //长度加1
return true;
}
bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数
//判断i的范围是否有效
if(i<1||i>L.length)
return false;
e = L.data[i-1] //将被删除的元素赋值给e
for(int j=L.length; j>i; j--){ //将第i个后的元素前移
L.data[j-1]=L.data[j];
}
L.length--; //长度减1
return true;
}
#define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int Length; //顺序表的当前长度
}SqList; //顺序表的类型定义
ElemType GetElem(SqList L, int i){
// ...判断i的值是否合法
return L.data[i-1]; //注意是i-1
}
4.按值查找:平均时间复杂度O(n)
2.3线性表的链式表示
2.3.1 单链表的定义
定义: 线性表的链式存储又称单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。
可以利用typedef关键字——数据类型重命名:type<数据类型><别名>
单链表的两种实现方式:
1. 不带头结点的单链表
#define InitSize 10 //定义最大长度
typedef struct{
ElemTyp *data; //用静态的“数组”存放数据元素
int Length; //顺序表的当前长度
}SqList;
//在顺序表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SqList L, ElemType e){
for(int i=0; i<L.lengthl i++)
if(L.data[i] == e)
return i+1; //数组下标为i的元素值等于e,返回其位序i+1
return 0; //推出循环,说明查找失败
}
typedef struct LNode{//定义单链表结点类型
ElemType data; //数据域
struct LNode *next;//指针域
}LNode, *LinkList;
```bash
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){ //注意用引用 &
L = NULL; //空表,暂时还没有任何结点;
return true;
}
void test(){
LinkList L; //声明一个指向单链表的指针: 头指针
//初始化一个空表
InitList(L);
//...
}
//判断单链表是否为空
剩余69页未读,继续阅读
资源评论
陈橘又青
- 粉丝: 11w+
- 资源: 18
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功