没有合适的资源?快使用搜索试试~ 我知道了~
考研数据结构-学习笔记
资源推荐
资源详情
资源评论
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![audio/mpeg](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![emmx](https://img-home.csdnimg.cn/images/20210720083646.png)
![m](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/89320462/bg1.jpg)
绪论
(1)掌握数据结构的基本概念,数据的逻辑结构、存储结构以及二者之间的关系。
(2)掌握计算语句频度和估算算法时间复杂度的方法。
(3)理解算法五个要素的确切含义。
(4)了解抽象数据类型的定义、表示和实现方法。
数据结构:相互之间存在一种或者多种特定关系的数据元素的集合。
数据结构三要素:逻辑结构、存储结构、运算。
逻辑结构:包括线性结构和非线性结构;线性结构包括一般线性表、受限制的线性表(栈、队列、
串)、数组。
存储结构:包括顺序存储、链式存储、散列存储和索引存储。
运算:运算的定义是针对逻辑结构,实现针对存储结构。
逻辑结构和物理结构之间的关系:逻辑结构可以独立于存储结构,存储结构不能独立于逻辑结构。
算法五要素:有穷性、确定性、可行性、输入、输出。
设计链式存储时,不同结点存储空间可以不连续,但结点内存储单元必须连续。
数据元素:数据的基本单位
数据项:构成数据元素、有独立含义、不可分割的最小单位。
数据对象:性质相同的数据元素的集合,是数据的子集。
线性结构
(1)掌握线性表的顺序存储结构和链式存储结构定义及其各种基本运算。
(2)掌握栈的顺序存储结构和链式存储结构以及基本操作的实现。
(3)掌握队列的顺序存储结构和链式存储结构及其基本操作的实现。
(4)了解串的基本概念及其存储结构。
(5)理解稀疏矩阵和特殊矩阵的压缩方法。
(6)理解广义表的基本概念,掌握广义表的特点及基本操作;
(7)掌握数组的存储表示方法和地址计算方法。
线性表的特点:
元素个数有限
元素都是数据元素
元素有先后次序
元素的数据类型都相同
顺序表——线性表的顺序存储
定义:
静态分配(使用数组):
![](https://csdnimg.cn/release/download_crawler_static/89320462/bg2.jpg)
动态分配(使用指针):
初始化:
静态数组:1、将所有元素初始化为0(防止脏数据);2、将初始长度设为0;
动态数组:1、使用malloc函数动态申请内存;2、将初始长度设为0;
动态增加数组长度:
先将数组中的元素暂存到指针p;
重新申请内存;
将数据复制到新的内存中;
修改顺序表最大容量;
释放指针p;
插入:首先判断存储空间是否已满,若已满返回false;未满情况下检查元素插入位置是否合法
(i<1||i>L.length+1视为不合法);在合法的情况下进行元素插入:将插入位置i以及之后的元素依
次向后移动一个单位,并将元素e插入位置i,最后线性表长度+1。
typedef struct{
int data[MaxSize]; //使用数组存放数据元素
int length; //顺序表当前的长度
}SqList;
typedef struct{
int *data; //指示动态数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
void InitList(SqList &L){ //参数为SqList类型,需要&
for(int i=0;i<MaxSize;i++)
L.data[i]=0; //将顺序表的所有数据元素初始化为0
L.length=0; //将顺序表的初始长度设为0
}
void InitList(SeqList &L){
L.data=(int *)malloc(InitSize*sizeof(int)); //使用malloc函数动
态申请内存,InitSize为默认最大长度
L.length=0; //当前长度设为0
L.MaxSize=InitSize; //默认最大长度
}
void IncreaseList(SqlList &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;
free(p);
}
![](https://csdnimg.cn/release/download_crawler_static/89320462/bg3.jpg)
时间复杂度:
最好:O(1)
最坏和平均:O(n)
删除:首先判断删除元素位置是否合法,如果合法将被删元素的值赋给e,然后将被删元素位置后
面的所有元素向前移动一位,最后线性表长度-1。
时间复杂度:
最好:O(1)
最坏和平均:O(n)
按值查找:查找第一个值为e的元素
时间复杂度:
最好:O(1)
最坏和平均:O(n)
单链表
定义:包括数据域和指针域,指针域是struct LNode类型
bool ListInsert(SqlList &L,int i,int e){
if(L.length>=MaxSize)
return false;
if(i<1||i>L.length+1)
return false;
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;
}
bool ListDelete(SqList &L,int i,int e){
if(i<1||i>L.length)
return false;
e=L.data[i-1];
for(int j=i,j<L.length;j++) //因为最后一个元素没有后继,所以j不能=L.length
L.data[j-1]=L.data[j];
L.length--;
return false;
}
int LocateElem(SqList L,int e){
for(int i=0;j<L.length;j++){
if(L.data[i]==e)
return i+1;
}
return 0;
}
typedef struct LNode{
int data;
struct LNode *next; //指针域指向下一个结点,所以是 struct LNode类型
}LNode,*LinkList; //*LinkList用于表示这是一个指向 struct LNode类型的指针
![](https://csdnimg.cn/release/download_crawler_static/89320462/bg4.jpg)
初始化:
带头结点:给头结点分配内存
不带头结点:直接将L设为NULL
头插法建立单链表:
1. 创建头结点L
2. 输入结点的值
3. 创建新结点*s
4. 将结点的值赋予新结点
5. 将新结点插入到单链表头部
尾插法建立单链表(与头插法相比多了尾指针*r,用于始终指向最后一个结点)
1. 创建头结点
2. 输入结点的值后进入while循环
3. 创建新结点*s,尾指针r
4. 将结点的值赋予新结点
5. 将新结点插入到单链表尾部
bool InitList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next=NULL;
return true;
}
bool InitList(LinkList &L){
L=NULL; //空表,暂时没有任何结点
return true;
}
LinkList List_HeadInsert(LinkList &L){
int x;
LNode *s;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
scanf("%d",&x);
while(x!=999){
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
LinkList List_TailInsert(LinkList &L){
int x;
![](https://csdnimg.cn/release/download_crawler_static/89320462/bg5.jpg)
按位查找(p初始指向头结点)
按值查找(p初始指向第一个结点)
指定结点后插操作
插入,在位置i插入结点e
LNode *s,*r=L;
L=(LinkList)malloc(sizeof(LNode));
scanf("%d",&x);
while(x!=999){
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL;
return L;
}
LNode *GetElem(LinkList L,int i){
int j=0; //j代表当前扫描到第几个结点
LNode *p; //p代表当前扫描到的结点
p=L;
if(i<0)
return NULL;
while(p!=NULL&&j<i){
p=p->next;
j++;
}
return p;
}
LNode *LocateElem(LinkList L,int e){
LNode *p=L->next; //p指向第一个结点
while(p!=NULL&&p->data!=e){
p=p->next;
}
return p;
}
bool InsertNextNode(LNode *p,int e){
if(p=NULL)
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s=NULL)
return false;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
剩余43页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/87a0f86e1fc24ce99aabf708b37d5560_qq_46137895.jpg!1)
CherriesOvO
- 粉丝: 396
- 资源: 5
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)