期末复习(数据结构)

《期末复习(数据结构)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构期末复习__________________________by大剑第一章、绪论程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数值性数据非数值性数据数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(DataItem)：数据的不可分割的最小单位，一个数据元素可以由若干个数据项构成。数据对象(DataObject)：性质相同的数据元素的集

2、合，是数据的一个子集。整数数据对象N={0,±1,±2,…}学生数据对象数据结构(DataStructure)：相互间存在一种或多种特定关系的数据元素的集合4种基本结构：集合：数据元素除了同属一个集合，没有别的关系线性结构：数据元素间是一对一的关系树形结构：数据元素间是一对多的关系图状或网状结构数据元素间是多对多的关系数据结构数学定义：数据结构是一个二元组Data_Structure=(D,S)D–数据元素的有限集合S–定义在D上的关系的有限集合逻辑结构和物理结构逻辑结构:数据元素之间的逻辑关系物理结构:数据结构在计算机中的表示,又称存储结构算法

3、的设计取决于选定的逻辑结构物理结构顺序存储结构：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据类型:数据类型是一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。数据类型的作用是：明确地或隐含地规定了在程序执行期间变量、表达式或函数所有可能取值的范围，以及作用在这些取值上的操作。数据类型的分类:基本数据类型构造数据类型抽象数据类型(ADT,AbstractDataTypes)：一个数学模型以及定义在该模型上的一

4、组操作。ADT有两个重要特征：1、数据抽象2、数据封装算法和算法分析算法定义：对特定问题求解步骤的一种描述．算法的特征有穷性确定性：不产生二义性，并且在任何条件下，算法都只有一条执行路径；可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；输入：有零个或多个输入；输出：有一个或多个输出。算法设计原则：正确性可读性健壮性高效性与低存储量运行该算法所需要的计算机资源,包括时间资源与空间(存储器)资源空间复杂度需要空间资源的量S(n)=O(f(n))时间复杂度需要时间资源的量T(n)=O(f(n))指针、结构体指针变量：用来存放地址的

5、变量。取地址运算符&用法：&变量名功能：取变量的地址单目运算符，“右”结合性，优先级2指针变量的定义：类型名*指针变量名；指针变量的赋值：结构体：由不同类型的数据(成员变量)构成，各自占有独立的内存空间。如果需要把一个学生的学号、姓名、性别、年龄、各门功课的考试成绩等不同类型的数据放在一个构造型数据类型中，就需要结构类型或者联合类型。一个结构类型的变量中可以独立存放多种类型的数据。第一章、线性表线性表（linear_-list）是最常用且最简单的一种数据结构。线性结构的特点存在唯一的”第一个”数据元素存在唯一的”最后一个”数据元素除第一个外,每个

6、数据元素均有且只有一个前驱元素除最后一个外,每个数据元素均有且只有一个后继元素。定义：线性表L是n(n>=0)个相同类型数据元素a1,…，an-1,an构成的有限序列。表示成L=(a1,…,an-1,an）n个元素的线性表:(a1,a2,…,ai,ai+1,…,an)a1第一个元素(没有前驱)ai第i个元素(有唯一的前驱和唯一的后继)an最后一个元素(没有后继)线性表举例:字母表(A,B,C,…,X,Y,Z)数据序列(6,17,28,50,92,188)线性表的链式表示与实现顺序表示的优点是随机存取表中的任意元素顺序表示的弱点是在作插入或删除操作

7、时，需移动大量元素链式表示没有顺序表示的弱点,也失去了顺序表示的优点。线性链表建立单链表:逆位序输入n个元素,建立带表头结点的单链表LvoidCreateList_L(LinkList&L,intn){LinkListp;L=(LinkList)malloc(sizeof(LNode));L->next=null;for(inti=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=L->next;//插入表头L->next=p;}}插入结点:指针p所

8、指的结点后插入指针s所指的结点：s->next=p->next;p->next=s;删除结点：删除指针p所指的结点后的结点：p->nex