第一章 绪论
1.1 什么是数据结构
1.1.1 数据结构的定义
数据：描述客观事物的数和字符的集合
数据元素：数据的基本单位
数据对象：性质相同的数据元素的集合，是数据的一个子集
数据结构：数据元素以及数据元素之间的关系，可以看作互相之间有着特定关系的集合
1.1.2 逻辑结构
1.逻辑结构的表示
一 、 图标表示
采用图表来进行表示逻辑关系
二、 二元组
一种数据逻辑结构表示方式
B=（D, R )
D ：数据元素的集合
R ：关系的集合
在R之中有一个关系r是序偶的集合，对于r中任意序偶<x , y>，表示 x 与 y 相邻
x 为 y 的前驱元素
y 为 x 的后继元素
x没有前驱元素为开始元素
y没有后继元素为终端元素
注意：矩阵中r进行的描述需要特别注意 设r1为行 r2为列，进行的排列需要注意
2.逻辑结构的类型
一、集合
二、线性结构
线性结构是指该结构中数据元素之间存在一对一的关系，开始元素何终端元素都是唯一的，其余元素有且只有一个前驱和终端元素
三、树形结构
树形结构是指该结构中元素存在单对多的关系，每个元素有一个或者多个后继元素，二叉树就是一个经典的树形结构
1.1.3存储结构
数据的逻辑结构在计算机存储器中的存储表示称为数据的存储结构（也成为映像）也就是逻辑结构在计算机中的存储实现
一、顺序储存结构
采用一组连续的存储单元存放所有的数据元素，即顺序储存结构将数据的逻辑结构直接映射到存储结构（特点：储存效率高，但不便于修改数据）
二、链式存储结构
每个逻辑元素用一个内存结点存储，每个节点单独分配，所有节点地址不一定连续，无需占用一整块的存储空间，给每个节点添加指针域，用于存放相邻节点的存储地址，也就是通过指针域将所有的节点链接起来
三、索引存储结构 P8
四、哈希存储结构 P8
1.1.4 数据运算
数据运算是指对数据实施操作，同样的运算在不同存储结构中，其实现过程不同
1.1.5 数据类型与抽象数据类型
一、数据类型
二、抽象数据类型
1.2 算法及其描述
1.2.1算法的定义
对特定的问题求解步骤的描述，是指令的有限序列，它满足以下几点
（1）有穷性
（2）确定性
（3）可行性
（4）有输入输出
算法与程序的区别
程序：计算机语言对一个算法具体实现 算法：侧重于解决问题的方法描述
1.2.2算法设计的目标
算法设计应该满足以下特点
（1）正确性
（2）可使用性
（3）可读性
（4）强壮性
（5）高效率与低存储量需求
1.2.3算法的描述
详情见书P16页
1.3算法分析
1.3.1算法分析概述
分析算法占用的资源
1、cpu时间
2、内存空间
1.3.2算法的时间性能分析
一个算法是由控制结构（顺序、分支、循环）和原操作构成的
一、衡量算法时间性能的方法
（1）事后统计法
（2）事前估算法
二、算法时间复杂度的分析
（1）计算算法的频度
void fun (int a[],int n){
int i; //1
for (i=0;i<n;i++){ //2
a[i]=2*1; //3
}
for(i=0;i<n;i++){ //4
printf("%d", a[i]); //5
}
printf("\n"); //6
}程序中1,3,5,6为原操作
原操作的执行次数（也成为频度），他是问题规模n的函数，用T（n）表示
算法执行的时间估计 = 原操作所需要的时间 * T（n），所以T（n）与算法执行的时间成正比
通过比较T（n)的大小可以得出算法执行时间的好坏
分析程序时间复杂度
【例1-6】求两个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度
#define MAX 20
void matirxadd(int n,int A[MAX][MAX],int B[MAX][MAX],int C[MAX][MAX]){
int i,j;
for(i=0;i<n;i++){ //频度为n+1 循环次数为n
for(j=0;j<n;j++){ //频度为n(n+1)
C[i][j]=A[i][j]+B[i][j] //频度为n^2
}
}
}所以该程序的频度和为 T（n）=2n^2+2n+1
(2)时间复杂度的的表示
算法中执行实时间T（n）是问题规模n的某个函数f（n），T(n) = Of(n)
也就是说 T（n）<=cf(n)
三、简化算法时间复杂度分析
算法中的基本操作一般是最深层循环内的原操作
算法执行时间大致=原操作所需要的时间*其运算次数
void func(int n){
int i=0, s=0;
while(s<n){
i++;
s=s+i;
}
}分析其时间复杂度
S=m(m+1)/2>=n
m(m+1)/2+k=n
此处使用韦达定理进行运算得到的时间复杂度为O sqrt（n）
题目练习
一、采用二元组表示的数据逻辑结构S=<D,R>,其中D={a,b,c,......,i},R={r},r={<a,b>,<a,c>,<c,d>, <c,f>,<f,h>,<d,e>,<f,g>,<h,i>}请问r是什么类型的数据结构？哪些节点是开始节点？哪些节点是终端节点？
r是树形结构，每个元素有一个或者多个后继元素，其中a节点是开始节点，b，e，i，g节点是终端节点
二、简述数据逻辑结构与存储结构的关系
数据的逻辑结构在计算机存储器中的存储表示称为数据的存储结构（也成为映像）也就是逻辑结构在计算机中的存储实现
三、有以下用C/C++语言描述的算法，说明其功能:
void fun(double &y,double &x,int n){
y=x;
while(n>1){
y=y*x;
n--;
}
}由题可知，语句二将x的值赋给了引用的y，之后开始循环，第一次y=y*x不难发现是x*x，n--，可以发现该代码是在求x^n
四、分析下面程序段中循环语句的执行次数
int j=0,s=0,n=100{
do{
j=j+1;
s=s+10*j;
}while(j<n && s<n) //代码中&&表与运算由题可知，while语句中（j<n && s<n)要同时满足j<n 和 s<n的时候，循环才会继续， 第一次执行时j=1 s=10 第二次执行 j=2 s=30 第三次执行 j=3 s=60 第四次执行j=4 s=100 ，到此不满足while条件不继续进行循环，可知循环语句执行了4次
五、设n为正整数，给出下列3个算法关于问题规模n的时间复杂度
（1）算法1
void fun1(int n){
i=1,k=100;
while(i<=n){
k=k+1;
i+=2;
}
}由题可知，循环的结束是由i来决定，所以 i=1+2T(n)<=n 加上一个补平的K， 1+2T(n)+K=n
2T(n)=n-K-1 （n-K-1）/2=T(n) 可以得知算法一时间复杂度为 O(n）
(2)算法2
void fun2(int n){
int i=0,s=0;
while(s<=n){
i++;
s=s+i;
}
}由题可知，循环的结束是由s来决定，所以可以得到以下式子 1+2+3+......+T(n)<=n,通过公式可得到 （1+T(n))T(n)/2+k=n T(n)^2+T(n)=2n-2k 可以得出时间复杂度为O(sqrt(n))
附件1 常见时间复杂度对照表
第二章 线性表
2.1线性表及其逻辑结构
2.1.1线性表的定义
线性表是具有相同特性的数据元素的一个有限序列，该序列中所包含的元素的个数叫线性表的长度，用n表示，n>=0，当n=0时，表示线性表为一个空表
线性表有以下特征
（1）有穷性：线性表元素个数有限
（2）一致性：一个线性表中元素性质相同
（3）序列性：线性表中所有元素的位置是线性的
2.1.2线性表抽象类型描述
线性表有以下九个重要的基本运算
[例 2-2]初始化线性表LC，即创建一个空的线性表LC，将LA的所有元素复制到LC中，然后遍历线性表LB，将LB中不属于LA的元素插入LC中
2.2线性表的顺序储存结构
2.2.1线性表的顺序储存结构----顺序表
线性表顺序储存结构：把线性表中的所有元素按照顺序储存方法进行存储，也就是按照逻辑顺序依次存储到一篇连续的存储空间之中，这种映射称为直接映射
顺序表类型的声明
#define MaxSize 50
//设置MaxSize的大小为50
typedef struct{
ElemType data[MaxSize];
int length;
}SqList //顺序表的类型逻辑位序与物理位序相差1
2.2.2顺序表基本运算的实现
详情见书P34-P42 不做细节概述
题目练习
2.2线性表的链式储存结构
2.3.1线性表的链式储存结构----链表
线性表的链式存储结构称为链表，线性表的每一个元素用一个节点储存，每个内存节点不仅仅包含元素本身的信息，也包含表示每个节点之间逻辑关系的信息，在C/C++中用指针来表示，被称为指针域
线性表每个元素仅有一个前驱元素和一个后继元素，所以在每个节点外只设置一个指针指向后继节点，构成线性单向链接表，称为单链表，而设置两个指针域分别指向前驱节点和后继节点构成线性双向链接表，称为双链表
指向头节点的指针---头指针
指向开始节点/首节点的指针---首指针
指向尾节点的指针---尾指针
储存密度=节点中数据元素所占的存储量/节点所占的存储量
一般来说存储密越大，存储空间利用率越高，显然顺序表的利用率为100%，而链表小于100%,单链表存储密度为50%
2.3.2单链表
在单链表中节点类型用LinkNode来表示，它应包含存储元素的数据域，类型使用通用类型=标识符ElemType表示，包含的指针用next表示
typedef struct LNode{
ElemType date;
struct LNode *next;
}LinkNode //单链表节点类型LinkNode
重点：插入节点与删除节点
循环链表的概念
题目练习
void fun1(LinkNode *&L1,LinkNode *&L2) {
int n=0,i;
LinkNode *p=L1;
while (p!=NULL)
{
n++;
p=p->next;
}
p=L1;
for (i=1;i<n/2;i++)
p=p->next;
L2=p->next;
p->next=NULL;
}
对于含有 n 个结点的单链表 L1，将 L1 拆分成两个不带头结点的单链表 L1 和 L2，其中 L1 含有原来的前 n/2 个结点，L2 含有余下的结点。
实验题一
//实现顺序表的各种基本运算的算法
#include<stdio.h>
#include<malloc.h>
//线性表的顺序存储结构
#define MaxSize 50
typedef char ElemType;
char ch;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
//(1)初始化顺序表
void InitList(SqList * &L)
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
//(2)依次插入a,b,c,d,e元素
bool ListInsert(SqList * &L,int i,ElemType e)
{
int j;
if(i<1 || i>L->length+1)
return false;
i--;
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return true;
}
//(3)输出顺序表
void DisplayList(SqList * L)
{
for(int i=0;i<L->length;i++)
printf("%c",L->data[i]);
printf("\n");
}
//(4)求线性表的长度
int ListLength(SqList * L)
{
return (L->length);
}
//(5)判断顺序表L是否为空
bool ListEmpty(SqList * L)
{
return (L->length==0);
}
//(6)输出顺序表L的三个元素
bool GetElem(SqList * L,int i,ElemType e)
{
if(i<1||i>L->length)
return false;
e=L->data[i-1];
ch=e;
return true;
}
//(7)查找顺序表所在位置
int LocateElem(SqList * L,ElemType e)
{
int i=0;
while(i<L->length&&L->data[i]!=e)
i++;
if(i>=L->length)
return 0;
else
return i+1;
}
//(10)删除顺序表上的第三个元素
bool ListDelete(SqList * &L,int i,ElemType e)
{
int j;
if(i<1 ||i>L->length)
return false;
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return true;
}
//(12)释放线性表
void DestroyList(SqList * &L)
{
free(L);
}
//主函数
int main()
{
SqList *L;
printf("(1)初始化顺序表L.\n");
InitList(L);
printf("(2)依次插入a,b,c,d,e元素.\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("(3)输出顺序表L：");
DisplayList(L);
printf("(4)输出顺序表L的长度：%d\n",ListLength(L));
printf("(5)判断顺序表L是否为空：%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,'e');
printf("(6)输出顺序表L的第3个元素：%c\n",ch);
printf("(7)输出元素a的位置：%d\n",LocateElem(L,'a'));
printf("(8)在第4个元素位置上插入f元素.\n");
ListInsert(L,4,'f');
printf("(9)输出顺序表L：");
DisplayList(L);
printf("(10)删除顺序表L的第3个元素.\n");
ListDelete(L,3,'e');
printf("(11)输出顺序表L：");
DisplayList(L);
printf("(12)释放顺序表L\n");
DestroyList(L);
return 0;
}第三章 栈和队列
栈和队列基础知识
栈的基础知识
栈是一种只能在一端进行插入或删除操作的线性表，表中允许进行插入删除操作的一端叫做栈顶，表的另外一端叫做栈底，栈顶的位置是动态的，当栈中没有元素的时候称为空栈
栈的插入操作被称为入栈或进栈(push)，栈的删除操作被称为出栈或者退栈(pop)
栈的主要特点是后进先出，所以栈也被称为后进先出表
采用顺序储存结构的的栈被称为顺序栈，元素最大的个数不超过MaxSize，单条顺序栈有以下几个特点
1)栈空的条件是s->top==-1 当top指针在-1也就是栈外的时候表面栈是空的
2)栈满的条件是s->top==MaxSize-1 (data数组最大下标）
3)元素e入栈的操作流程：
将栈顶指针top+1，将元素e放在栈顶指针处
4)出栈的操作：
将栈顶指针top的元素去出放在e中，然后将栈顶指针top-1
共享栈有以下几个特点
1）栈空的条件是 栈1空 top1==-1 栈2空 top2==MaxSize
2）栈满的条件 top1==top2-1
3）元素x进栈的操作
进栈1 top++；data[top1]=x
进栈2 top--； data[top2]=x
4)出栈的操作
出栈1 x=data[top1]; top1--;
出栈2 x=data[top2]; top++;
队列的基础知识
对列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另外一端只能够进行删除操作
我们通常把插入的一端称为队尾（rear），把进行删除操作的一端称为队头或者队首（front），新元素入队之后成为新的队尾元素，从队列中删除元素称为出队或者离队，元素出队后，下一个元素成为新的队首元素
由于队列的删除和插入在表的不同两端进行，队列也被称为先进先出表
队列有以下特点
1）队空的条件 q->front==q->rear=-1
2）队满的条件 q->rear==MaxSize-1 (data数组最大下标）
3）元素e入队的操作 将rear+1，将元素放在rear指针处
4）出队的操作 将front+1,取出data数组中front位置的元素
环形队列的几种状态
为了增加空间利用率，防止队列假溢出问题的发生，产生了环形队列
环形队列/循环队列
空栈的条件 q->rear==q->front
队满的条件 （q->rear+1）%MaxSize==q->front
出队操作和入队操作将队尾和队首指针都循环进1
题目练习
第四章 串
4.1串的基本概念
串是由零个或者多个字符组成的有限序列，含零个字符称为空串，串包含的字符个数称为该串的长度
两个串相等当且仅当两个串的长度相等，且各个对应位置上的字符相同，一个串中任意连续两个字符组成的序列称为该串的子串
4.2串的储存结构
和线性表一样，串的顺序储存结构和链式结构，前者称为顺序串，后者称为链串
4.2.1 串的顺序储存结构----顺序串
顺序串中的字符被依次存放在一组连续的存储单元里，与顺序表类似
4.2.2 串的链式储存结构----链串
采用链式存储结构的串被称为链串，链串的组织形式与一般的单链表类似，区别在于链串中的一个节点可以存放多个字符
4.3 串的模式匹配
设置两个串s和t，s称为目标串，t称为模式串，在串s中找到一个与t相等的子串称为模式匹配
4.3.1BF算法
BF算法也成为暴力算法，简单匹配算法主要在于采用穷举法进行计算
4.3.2KMP算法
重难点：在BF算法上从串中提取出来有用的匹配信息进行计算
题目练习
一、KMP算法是BF算法的改进，以目标串s="aabaaabc"、模式串t="aaabc"为例说明next的作用
二、给出以下模式串next的值和nextval的值
nextval[0]=-1
t j=t next[j]时 nextval[j]=nextval[next[j]]
否则nextval[j]=next[j]
第五章 递归
5.1 什么是递归
5.1.1递归的定义
在定义一个过程或函数时出现调用自身过程或者本函数成分的称为递归，若是自己调用自己，则被称为直接递归，若是函数f1调用f2，f2调用f1则被称为间接递归
例[5-1]求解N！
int fact(int n){
if(n==1){
return 1;
}else{
return n*fact(n-1);
}
}递归算法经常把一个大的复杂的问题层层转化为一个或者多个原问题相似的规模较小的问题来进行求解
5.1.2何时使用递归
1、定义是递归的
2、数据结构是递归的
3、问题求解的方法是递归的
5.1.3递归模型
一般情况下，一个递归模型由递归出口和递归体两部分组成，递归出口确定递归何时结束，指出明确的递归结束条件，递归体是确定递归求解的递推关系
实际上递归就是将一个大问题转化成几个小问题
5.2 栈和递归 递归算法的设计
在此不做详细解释，详情见书P145-156
题目练习
一、有以下递归函数,分析调用fun(5)的输出结果
void fun(int n){
if(n==1){
printf("a:%d\n",n)
}else{
printf("b:%d\n",n)
fun(n-1);
printf("c:%d\n",n)
}
}由题可知，该递归函数由f5->f4->f3->f2->f1->f2->f3->f4->f5
输出的结果依次是
b=5 b=4 b=3 b=2 a=1 c=1 c=2 c=3 c=4 c=5文章来源：https://www.toymoban.com/news/detail-809702.html
第六章 数组和广义表
6.1数组
6.1.1数组的基本概念
从逻辑结构上面来看，一堆数组A是n(n>1)个相同类型的数据元素a1、a2、a3、......、an构成的有限序列，其逻辑结构表示 A=(a1,a2,a3,......,an)文章来源地址https://www.toymoban.com/news/detail-809702.html
到了这里，关于数据结构（期末复习篇） 清华大学出版社的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
