本文主要是介绍《从零开始的23年跨考计算机数据结构考研笔记》又名《这么卷还考计算机，跨考的我是否搞错了什么》堂堂连载 绝赞好评更新中，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一章 绪论
1.1数据结构基本概念
1.1.1基本概念
数据:符号的集合
数据元素：由若干数据项组成，是数据的基本单位
数据对象：具有相同性质的数据元素的集合
数据类型：原子类型、结构类型、抽象数据类型（包括逻辑结构和运算）
数据结构：相互之间存在特定关系的数据元素的集合，这种关系叫结构，数据结构包含三方面内容：逻辑结构、存储结构、数据的运算。
1.1.2 数据结构三要素
逻辑结构：线性结构（线性表）、非线性结构（树、图、集合）
存储结构：也叫物理结构。顺序存储、链式存储、索引存储、散列存储。
数据的运算：运算的定义--逻辑结构--运算的功能，运算的实现--存储结构--具体操作步骤。
1.2算法和算法评价
第二章 线性表
2.1线性表的定义
线性表是具有相同数据类型的n（>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表为一个空表。
2.2顺序表的定义
线性表的顺序存储称顺序表，它的特点是表中元素的逻辑顺序与其物理顺序相同。
线性表的顺序存储结构是一种随机存取的存储结构
2.2.1静态分配
//顺序表的实现--静态分配#include<stdio.h>
#define Maxsize 50 //定义表的长度
typedef struct{ //定义一种数据结构int data[Maxsize];//用静态的数组存放数据元素int length;//顺序表的当前长度
}SqList;//顺序表的定义类型（静态分配方式）
void InitList(SqList &L){for(int i=0;i<=Maxsize;i++){ //在for循环里就定义了iL.data[i]=0; //将所有初始元素设为默认值}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;
}2.2.2动态分配
//顺序表的实现--动态分配
#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(sizeof(int)*Initsize); //强制将存储空间转为int型L.Maxsize=Initsize;L.length=0;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){int *p=L.data; //将指针p指向L数组L.data=(int*)malloc(sizeof(int)*(L.MaxSize+len)); //L数组的指针指向另外一片区域，
//并且将存储空间转为int型for(int i=0;i<=L.length;i++){L.data[i]=p[i]; //将数据复制到新区域}L.MaxSize=L.MaxSize+len; //顺序表的最大长度增加lenfree(p); //释放原来的内存空间
}
int main(void){SeqList L; //声明一个顺序表InitList(L); //初始化顺序表//随便插入几个元素IncreaseSize(L,5); //增加顺序表长度
return 0;
}顺序表的特点：
- 随机访问，可以在O（1）时间内找到指定的元素
- 存储密度高，每个结点只存储数据元素
- 拓展容量不方便
- 顺序表逻辑上相邻的元素物理上也相邻，插入，删除操作不方便，需要移动大量元素
2.2.3顺序表的基本操作
1.插入操作：平均时间复杂度O(n)
bool ListInsert(SqList &L,int i int e){ //在顺序表的第i个位置插入新元素eif(i<1||i>L.length+1) //判断i的范围是否有效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[j-1]=e; //在位置i处放e，线性表中元素的位序是从1开始，
//而数组中元素的下标从0开始L.length++;return true;
} //好的算法应该具有健壮性2.删除操作：平均时间复杂度O(n)
bool ListDelete(SqList &L,int i,int &e){ //当需要把参数带回来时，需要在前面加上&if(i<1||i>L.length) //判断i的范围是否有效return false;e=L.data[i-1]; //将被删除的元素赋值给efor(int j=i;j<=L.length;j++){ //将第i个和它之后位置的元素前移L.data[j-1]=L.data[j];}L.length--; //线性表长度减1return true;
} //i对应线性表的位序，j对应数组的下标，注意i和j的对应关系3.按位查找（获取表L中第i个位置的元素的值）：平均时间复杂度O(1)(反映了线性表的随机存取的特点）
#define MaxSize 10
typedef struct{Elemtype data[MaxSize]int length;
}SqList; //顺序表的类型定义（静态分配方式）
//首先定义一个顺序表的数据结构Elemtype GetElem(SqList L,int i){ //和访问普通数组的方法一样//...判断i的值是否合法return L.data[i-1]; //注意线性表的位序和数组的下标之间的关系
}#define InitSize 10 //顺序表的初始长度
typedef struct{Elemtype *data； //指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前容量
}SeqList; //顺序表的类型定义（动态分配方式）
//首先定义一个顺序表的数据结构Elemtype GetElem(SqList L,int i){ //和访问普通数组的方法一样//...判断i的值是否合法return L.data[i-1]; //注意线性表的位序和数组的下标之间的关系
}//返回的是L.data,所以函数类型是Elemtype4.按值查找(在表L中查找具有给定关键字值的元素):平均时间复杂度O(n)
#define InitSize 10 //初始顺序表的长度
typedef struct{ Elemtype* data; //指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前容量
}SeqList; //顺序表的类型定义//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e){//e的类型和数据元素的类型相同，为Elemtypefor(int i=0;i<L.length;i++){if(L.data[i]==e)return i+1; //数组下标为i的元素值等于e，返回其位序i+1}return 0; //退出循环，说明查找失败
}//返回值是整型的值，所以函数名是int按值查找中，基本数据类型：int,char,double,float等可以直接用运算符==比较，结构类型的数据元素需要依次比较结构内各分量来判断两个结构体是否相等。
2.3 线性表的链式表示
2.3.1单链表的定义
线性表的链式存储又称单链表，指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需存放一个指向其后继的指针。单链表是非随机存取的存储结构。
typedef struct LNode{ //定义单链表结点类型Elemtype data; //数据域struct LNode *next; //指针域
}LNode,*LinkList; //LNode和*Linklist部分是数据类型的别名，侧重点不同
可以利用typedef关键字--数据类型重命名：typedef<数据类型><别名>
typedef struct LNode LNode;
LNode *p=(LNode*)malloc(sizeof(LNode));
<==>struct LNode *p=(struct LNode*)malloc(sizeof(struct LNode));
增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点。
要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点。
LNode*L;强调结点 LinkList L;强调单链表
单链表的两种实现方式 头节点：代表链表上头指针指向的第一个结点，不带任何数据
建立一个单链表
- 不带头节点的单链表
typedef struct LNode{Elemtype data;struct LNode *next;
}LNode,*LinkList;//初始化一个空的单链表
bool InitList(LinkList &L){ //注意引用&L=NULL; //空表，暂时没有任何结点return true;
}
void test(){LinkList L; //声明一个指向单链表的指针：头指针//初始化一个空表InitList(L);//...后续代码
}//判断单链表是否为空
bool Empty(LinkList L){if(L==NULL)return true;
elsereturn false;
}2.带头结点的单链表
typedef struct LNode{Elemtype data;struct LNode *next;
}LNode,*LinkList;//初始化一个单链表（带头结点)
bool InitList(LinkList &L){ //注意引用&L=(LNode*)malloc(sizeof(LNode)); //给头指针分配一个头结点（不存储数据）if(L==NULL) //内存不足，分配失败return false; L->next=NULL; //头结点之后暂时没有结点return true;
}
void test(){LinkList L; //声明一个指向单链表的指针：头指针//初始化一个空表InitList(L);//...后续代码...
}//判断单链表是否为空(带头结点)
bool Empty(LinkList L){if(L->next==NULL)return true;
elsereturn false;
}带头结点和不带头结点的比较：
不带头结点，写代码麻烦，对第一个数据节点和后续数据结点/对空表和非空表 的处理需要用不同的代码逻辑，头指针指向的结点用于存放实际数据；
带头结点，头指针指向的结点不存放实际数据，头结点指向的下一个结点才存放实际数据
2.3.2单链表上基本操作的实现
1.按位序插入（带头结点）平均时间复杂度O（n）
ListInsert(&L,i,e):在表L的第i个位置插入指定元素e，找到第i-1个节点，将新结点插入其后。头结点可以看作第0个节点，故i=1时也适用。
//创建一个数据类型
typedef struct LNode{Elemtype data;strct LNode *next;
}LNode,*LinkList;//在第i个位置插入元素e，带头结点
bool ListInsert(LinkList &L,int i,Elemtype e){if(i<1)return false; //判断i的合法性，i从1开始LNode *p //创建一个可以指向结点的指针int j=0; //当前p指向的是第几个结点p=L; //p指向头结点，第0个结点，不存数据while(p!=NULL&&p<i-1){ //循环找到第i -1个结点p=p->next; //如果i>length,p的值最后会等于NULLj++;}if(p==NULL) //i值不合法return false;//在第i-1个结点后插入新结点LNode *s=(LNode *)malloc(sizeof(LNode));//创建新结点s->data=e; //赋值s->next=p->next; //注意这两步不能颠倒p->next=s;return true;
}2.按位序插入（不带头结点）
不存在第0个结点，所以i=1时需要特殊处理插入、删除第一个元素时，需要更改头指针L
bool ListInsert(LinkList &L,int i,Elemtype e){if(i<1)return false;//插入第1个结点的操作不同if(i=1){LNode *s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=L;L=s; //头指针指向新结点return true;}//当不在头部插入时,i>1的情况与带头结点一样，唯一的区别是j的初始值为1LNode*p; //创建一个LNode类型的指针，指针p指向当前扫描到的结点int j=1; //当前p指向的是第几个结点（从1开始）p=L; //p指向L指针指向的结点，即第一个结点（注意，不是头结点，头结点不存数据，要与前面的相区别）//循环找到i-1个结点while(p!=NULL&&j=i-1){ //当i>length,p最后会等于NULLp=p->next; //p指向下一个结点j++;}if(p==NULL) //i值不合法return false;LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return true; //插入成功
}考试中带头、不带头都可能考察
3.指定结点的后插操作 平均时间复杂度O(1)
InsertNextNode(LNode *p,Elemtype e):给定一个结点p，在其之后插入元素e。单链表只能往后查找，故给定结点p之后的结点都可知。
//后插操作：在给定p结点之后插入元素e
bool InsertNextNode(LNode*p,ElemType e){if(p==NULL)return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL) //内存分配失败，如内存不足return false;s->data=e; //用结点s保存数据元素es->next=p->next; //注意这两个步骤的先后关系p->next=s;return true;
}4.指定结点的前插操作
在p结点之前插入元素e。此时没有头指针。
思想：设待插入结点是s,我们可以将s插入p结点的后面，然后将p->data和s->data交换位置，这样满足了逻辑关系，又使时间复杂度为O(1)。
//前插操作
bool InsertPriorNode(LNode*p,Elemtype e){if(p==NULL)return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL) //内存分配失败return false;//重点s->next=p->next; p->next=s;s->data=p->data; //先插入一个结点，再进行赋值操作p->data=e; return true;
}王道书版本
//前插操作
bool InsertPriorNode(LNode*p,LNode *s){//传入的是一个已经赋好值的结点if(p==NULL||s==NULL)return false;//重点s->next=p->next; //s连到p之后p->next=s;Elemtype temp=p->data //存放p的数据p->data=s->data; //将s的数据给ps->data=temp; return true;
}5.按位序删除（带头结点）
ListDelete(&L,i,&e):删除表L中第i个元素，用e返回删除元素的值，头结点视为第0个结点
找到第i-1个结点，将它的指针指向第i+1个结点然后释放第i个结点
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList; //创建数据类型bool LinkDelete(LinkList &L,int i,ElemType &e){if(i<1)return false;LNode *p; //指针p指向当前扫描到的结点int j=0; //当前p指向的是第几个结点p=L; //p和L指向同一个结点（头结点），因为j=0,所以把头结点定义为第0个结点//循环找到第i-1个节点while(p!=NULL||j<i-1){ //如果i>length,p最后会指向NULLp=p->next; //p指向下一个结点j++;} //现在p指向的是第i-1个节点if(p==NULL)return false;if(p->next==NULL) //第i-1个结点是最后一个结点return false;LNode*q=p->next; //令q指向被删除的结点e=q->data; //用e返回被删除的元素的值p->next=q->next; //第i-1个结点的指针域指向第i+1个结点，在逻辑上删除了第i个结点free(q); //释放结点i的存储空间return true;
}最坏，平均时间复杂度O(n)，最好时间复杂度O(1)
6.指定结点的删除
删除结点p,需要修改其前驱结点的next指针
或者对结点p和它的后继结点操作，此时时间复杂度为O(1)
bool DeleteNode(LNode *p){if(p==NULL)return false;LNode *q=p->next; //令指针q指向p结点的后继节点p->data=p->next->data; //将q结点的数据赋给p指针p->next=q->next; //将q结点删去free(q); return true;特殊情况，当p为最后一个结点时，那么这个代码会出错，只能从表头开始找P的前驱，此时算法的时间复杂度为O(n),
7.单链表的查找
- 按位查找 获取表L中第i个位置的元素，函数返回第i个节点的指针 时间复杂度O(n)
LNode *GetElem(LinkList L,int i){ //函数类型是LNode *型，因为返回的是一个指针指向的结点if(i<0)return NULL; //不能 return false.因为函数类型是LNode*型，只能返回结点LNode *p; //指针p指向当前扫描到的结点int j=0; //当前p指向的是第几个结点p=L; //p指向头结点while(p!=NULL&&j<i){ //循环找到第i个结点p=p->next;j++;
}return *p; //返回指针p指向的结点
}
- 按值查找
这篇关于《从零开始的23年跨考计算机数据结构考研笔记》又名《这么卷还考计算机，跨考的我是否搞错了什么》堂堂连载 绝赞好评更新中的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
