数据结构与算法
数据结构与算法是北京大学于2018年02月26日首次在中国大学MOOC开设的慕课课程，是国家精品在线开放课程。该课程授课教师为张铭、陈斌、卢宗青、刘云淮、赵海燕、宋国杰、黄骏、邹磊、王腾蛟。据2021年2月中国大学MOOC官网显示，该课程已开课4次。
数据结构与算法课程内容包括数据结构与抽象数据类型、算法特性及分类、算法效率与度量、线性结构、顺序表、链表、栈与队列、栈与递归、递归转非递归、字符串的存储结构、字符串运算的算法实现、字符串的快速模式匹配、二叉树的抽象数据类型、二叉树的搜索、二叉树的存储结构、树与二叉树的等价转换、树的抽象数据类型及树的遍历、树的链式存储结构、树的父指针表示法、树的顺序存储和K叉树、图的概念和抽象数据类型、图的存储结构、图的遍历、内排序、检索等内容。
课程性质:
课程背景
计算机是现代社会中用于解决问题的重要工具，支撑这个工具高效运转的就是其后的各种系统程序、应用程序。数据结构，是抽象的表示数据的方式；算法，则是计算的一系列有效、通用的步骤。算法与数据结构是程序设计中相辅相成的两个方面，是计算机学科的重要基石。
课程定位
数据结构与算法是介绍基本数据结构以及相关的经典算法，强调问题-数据-算法的抽象过程，关注数据结构与算法的时间空间效率，培养学生编写出高效程序从而解决实际问题的综合能力的一门课程。 适应对象
数据结构与算法适合计算机以及相关理工专业的本科生学习。对于具有C语言结构化程序设计基础的学生，该课程第0章补充了一些面向对象的基本内容。
课程简介:
数据结构与算法围绕着“算法+数据结构=程序”的思路，以问题求解为导向进行学习，运用问题抽象、数据抽象、算法抽象来分析问题，应用适当的数据结构和算法来设计和实现相应的程序。在求解实际问题方面，该课程会学习到通过权衡时空和其他资源开销，利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。课程所学到的内容会被利用到计算机科学后续的各个课程中，如操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等。
数据结构考研笔记整理（全）
一、 第二章 线性表
● 考纲内容
● 一、线性表的基本概念
● 线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑
结构，实现线性表的存储结构为顺序表或者链表
● 二、线性表的实现
● 1、顺序表
● 定义(静态分配)
● #define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ int
length;\\ }SqList;
● 定义(动态分配)
● #define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配
数组的指针\\ int MaxSize,length;\\ }SqList;
● c的动态分配语句为
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
● c++动态分配语句为L.data=new ElemType[InitSize];
● 插入操作
● 删除操作
● 按值寻找
● 2、链表
● 单链表
● 单链表的定义
●
● 头插法建立单链表
●
● 尾插法建立单链表
●
● 按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkList
L,ElemType e)
● 插入结点（后插）
● p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\
p.next=s;
● 将前插操作转化为后插操作,即先将s插入的p的后面然后调换s
和p的数据域
● s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\
s.data=temp;
● 删除结点
● p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);
1 / 13
十万种考研考证电子书、题库视频学习平台 圣才电子书
第12章 文 件
12.1 复习笔记
一、文件的基本概念
1．文件概述
（1）定义
文件是性质相同的记录的集合。
（2）按关键字划分
①单关键字文件
若文件中的记录只有一个惟一标识记录的主关键字，则称之为单关键字文件；
②多关键字文件
若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称之为多关键字
文件。
（3）按是否定长划分
①定长文件
若文件中各记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成
的文件称作定长文件；
②不定长文件
若文件中各记录含有的信息长度不等，则称作不定长文件。
2．文件的逻辑结构及操作
2 / 13
十万种考研考证电子书、题库视频学习平台 圣才电子书
（1）文件的逻辑结构
文件中各记录之间存在着逻辑关系，当一个文件的各个记录按照某种次序排列起来时，
各记录之间就自然地形成了一种线性关系。在这种次序下，文件中每个记录最多只有一个直
接后继记录和一个直接前驱记录，而文件的第一个记录只有直接后继没有直接前驱，文件的
最后一个记录只有直接前驱而没有直接后继。此时，文件可看成是一种线性结构。
（2）文件操作
①检索
文件检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号（即记录存
入文件时的顺序编号）查找，也可以按关键字查找。
②维护
文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。此外，为提高文件
的效率，还要进行再组织操作、文件被破坏后的恢复操作以及文件中数据的安全保护等。
3．文件的存储结构
（1）概念
文件的存储结构是指文件在外存上的组织方式。采用不同的组织方式就得到不同的存储
结构。
（2）基本的组织方式
①顺序组织；
②索引组织；
③哈希组织；
④链组织。
文件组织的各种方式往往是这四种基本方式的结合。
第一章 绪论
第一节 什么是数据结构？
估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。
数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。
信息模型：信息处理领域中的数学模型。
数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。
忽略数据的具体含义，研究信息模型的结构特性、处理方法。
第二节 概念、术语
一、有关数据结构的概念
数据：对客观事物的符号表示。
例：生活中还有什么信息没有被数字化？
身份证，汽车牌号，电话号码，条形代码……
数据元素：数据的基本单位。相当于"记录"。
一个数据元素由若干个数据项组成，相当于"域"。
数据对象：性质相同的数据元素的集合。
数据结构：相互之间存在特定关系的数据集合。
四种结构形式：集合、线性、树形、图(网)状
形式定义：(D，S，P)
D：数据元素的集合(数据对象)
S：D上关系的有限集
P：D上的基本操作集
逻辑结构：关系S描述的是数据元素之间的逻辑关系。
存储结构：数据结构在计算机中的存储形式。
顺序映象、非顺序映象、索引存储、哈希存储
逻辑结构与存储结构的关系：
逻辑结构：描述、理解问题，面向问题。
存储结构：便于机器运算，面向机器。
程序设计中的基本问题：逻辑结构如何转换为存储结构？
二、有关数据类型的概念
数据类型：值的集合和定义在该值集上的一组操作的总称。
包括：原子类型、结构类型。
抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。 核心：是逻辑特性，而非具体表示、实现。
课程任务：
学习ADT、实践ADT。
如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……
