线性表复习知识点.docx

线性表的两种存储方式（原理，特点、各自的优缺点）知识点：顺序存储结构：原理：使用数组，数组把线性表的数据元素存储在一块连续地址空间的内存单位中特点：线性表中逻辑上相邻的数据元素在物理地址上也相邻。优点：算法简单，存储密度大，空间单位利用效率高缺点：需要预先确定数据元素的最大个数，并且插入和删除操作时需要移动较多的数据元素。（可简化为：插入或删除元素时不方便）链式存储结构：原理：把存放数据元素的结点用指针域构造成链。特点：数据元素间的逻辑关系表现在结点的连接关系上优点：不需要预先确定数据元素的最大个数，插入和删除操作是不需要移动数据元素（可简化为：插入或删除元素时很方便，使用灵活。）缺点：存储密度小，空间单位利用效率低头指针、头结点、首元结点（第一个元素结点）的含义？头结点的作用是什么？知识点:头指针：指向链表中第一个结点(或为头结点或为首元结点)的指针。头结点：链表的首元结点之前附设的一个结点。即头指针所指的不存放数据元素的第一个结点。首结点：链表中存储线性表中第一个数据元素的结点。头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。若设计的链表中带头结点，则无论插入或删除的位置是首元结点还是其他结点，都不会改变头指针的数值，即算法步骤都相同。；若设计的链表中不带头结点，则算法步骤要分别考虑插入或删除的位置是首元结点还是其他结点，因为两种情况的算法步骤不同。总结为：头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。线性表上定义的基本运算：构造空表：Initlist（L）求表长：Listlength（L）取结点：GetNode（L，i）查找：LocateNode（L，x）插入：InsertList（L，x，i）删除：Delete（L，i）在顺序表中实现的基本运算：插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构假定指针p指向线性链表中的第i个数据元素，则p-next为指向线性链表中第i+1个数据元素的指针。即p-data为ai，p-next-data为ai+1。(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域头指针、头结点、首元结点（第一个元素结点）的含义？头结点的作用是什么？知识点:头指针：指向链表中第一个结点(或为头结点或为首元结点)的指针。头结点：链表的首元结点之前附设的一个结点。即头指针所指的不存放数据元素的第一个结点。首结点：链表中存储线性表中第一个数据元素的结点。头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。若设计的链表中带头结点，则无论插入或删除的位置是首元结点还是其他结点，都不会改变头指针的数值，即算法步骤都相同。；若设计的链表中不带头结点，则算法步骤要分别考虑插入或删除的位置是首元结点还是其他结点，因为两种情况的算法步骤不同