数据结构与算法第二章知识点.docx

线性表是一种可以在任意位置进行插入和删除数据元素操作的、有n个相同类型数据元素 组成的线性结构。线性结构是除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后 继数据元素，线性表是一种最简单最常用的线性结构，因为线性表满足线性结构的特点。顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据 元素在物理上也相连，数据元素间的逻辑关系表现在数据元素的存储关系上。链式存储结构，是使用指针把直接关联的节点链接起来，其特点是逻辑上相邻的数据元素在 物理上不一定相邻，数据间的逻辑关系表现在节点的链接关系上。线性表抽象数据类型，包括其数据集合和该数据集合上的操作集合。数据集合为n个数据类型为抽象数据类型DataType的数据元素。操作集合为初始化Initiate;求当前数据个数Size插入数据元素Insert;删除数据元素Delete; 取数据元素Getdata.指针是指向物理存储单元地址的变量，把指向单链表的指针称为头指针，头指针所指向的不 存放数据元素的第一个节点称为头结点。若设计的单链表带头节点，则对单链表进行插入或者删除操作都不会改变头指针的值，算法 处理的方法相同，而如果不带头节点，那么进行插入或删除操作，算法的处理方法不相同。 8.C+语言动态申请和动态释放内存功能的new运算符和delete运算符的功能和使用方法。 new在程序执行期间，申请用于存放T类型对象的内存空间，并依据初值列表赋予初值. new类型名T （初始化参数列表）delete释放指针p所指向的内存。p必须是new操作的返回值。delete 指针 p因为在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素集合, 这样任意两个在逻辑上相邻的数据元素在物理上也必然相连，进行删除和插入操作时，必须 要移动数据元素.插入方法和删除方法，移动数据元素的方向不同。顺序表的主要优点是算法简单，空间单元利用效率高，主要缺点是需要预先确定数据元素的 最大个数，并且进行插入和删除操作时需要移动较多的数据元素，而单链表的主要优点是不 需要预先确定数据元素的最大个数，插入删除操作时不需要移动数据元素，主要缺点是每个 节点中要有一个指针域，因此空间单元利用效率不高，算法也比较复杂。总而言之，正如第一章所说的那样，空间效率和时间效率无法同时满足，顺序表满足了高的 空间单元利用效率，单链表满足了高的时间利用效率。