数据结构期末复习资料

第一章 1 、数据结构是 一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 (DataStructure) 数据结构： 相互之间存在一种或多种特定关系的数据元素的集合。 2 、数据结构的形式定义：。 Data_Structure=(D,S)DSD 二元组其中，是数据元素的有限集，是上关系的有限集 3 、数据元素之间关系的映像： () １、顺序映像顺序存储结构：以相对的存储位置表示后继关系。 2() 、非顺序映像链式存储结构：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。 () 任何一个算法的设计取决于数据逻辑结构，其实现取决于物理结构。 4、 算法的定义： 对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 特性： 有穷性、确定性、可行性、输入、输出 5、 —— 算法的评价衡量算法优劣的标准 (correctness): 正确性满足具体问题的需求 (readability) 可读性：易读、易理解 (robustness): 健壮性当输入数据非法时，算法能够做出反应或进行处理 : 效率与低存储量执行时间短、存储空间小 作业的答案：试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 第二章 1 、线性表是一种最简单的线性结构。 线性结构是一个数据元素的有序（次序）关系 “”“” 特点：存在唯一的一个第一个的数据元素；存在唯一的一个最后一个的数据元素；除第一个数据元素外， 均有唯一的前驱；除最后一个数据元素外，均有唯一的后继 2—— 、线性表类型的实现顺序映像定义：用一组地址连续的存储单元依次存放线性表中的数据元素。 ■ aiaiLOCaiLOCaill 其中是一个数据元素所占存 <-1>()=(-1)+ 以存储位置相邻表示有序对，，则有： “” 储量 LOCaiLOCail (1)-1 ()=+()× ■ 1—2 特点：、实现逻辑上相邻物理地址相邻、实现随机存取 3 、若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为： 若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为： 4、 —— 线性表类型的实现链式映像线性链表特点：用一组地址任意的存储单元存放线性表中的数据元素。 5ii-1 、在单链表中第个结点之前进行插入的基本操作为：找到线性表中第个结点，然后修改其指向后继的指 针。 s=(LinkList)malloc(sizeof(LNode));// 生成新结点 s->data=e;s->next=p->next;p->next=s;// 插入 i:i-1 在单链表中删除第个结点的基本操作为找到线性表中第个结点，修改其指向后继的指针。 free(q); q=p->next;p->next=q->next; e=q->data; 5、 循环链表：最后一个结点的指针域的指针又指回第一个结点的链表。 “”“” 和单链表的差别仅在于：判别链表中最后一个结点的条件不再是后继是否为空，而是后继是否为头结点。 6、 1“”2“”“” 双向链表的操作特点：、查询和单链表相同；、插入和删除时需要同时修改两个方向上的指针 “”s->next=p->next;p->next=s;s->next->prior=s;s->prior=p;s 插入：（是插入的结点） p->next=p->next->next;p->next->prior=p;p 删除：（要删除的是的下一个结点） 课后作业 P13:2.32.5 、 P15:2.82.9(2) 、