2023计算机考研初试在即，在最后阶段建议各位同学将知识点再系统复习一遍，以免有所遗漏！2022计算机考研数据结构第二单元知识点包含顺序表、单向链表、单向循环链表、双向循环链表。高顿考研为大家整理了2022计算机考研数据结构第二单元知识点的详细内容，供大家参考复习！
顺序表：顺序存储表示的线性表称为顺序表
地址计算公式：loc(ai)=loc(a0)+i*k
只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址。
顺序表是一种随机存取结构。
相关运算：
Find(i,x):查找下标为i的元素a<i>。在x中返回表中下标为i的元素a<i>(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。
Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true。
Delete(i)：删除元素a<i>。
优点：随机存取;存储空间利用率高。
缺点：插入、删除效率低;必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大。
单向链表
·表头指针first是指向链表的头结点的指针
相关运算：
Find(i,x):必须从表头指针开始沿链逐个计数查找，称为顺序查找。搜索运算的平均、最坏的渐近时间复杂度都是O(n)。
Insert(i,x)：生成数据域为x的新结点，q指向新结点;从first开始找第i+1个结点，p指向该结点;将q插入p之后，表长加1。
·注意区分插在头结点和一般节点的情况
Delete(i)：从first开始找第i+1个结点，p指向该结点，q指向p之前驱结点;从单链表中删除p;放p之空间(delete p);表长减1。
优点:单链表插入和删除只需修改一两个指针，无需移动元素。可以动态分配结点空间，线性表的长度只受内存大小限制。
缺点:查找运算费时，只能顺序查找，不能随机查找。
带表头结点的单向链表
注意区分“表头结点”和“头结点”。
头结点：线性表中下标为0的元素、第1个元素;
表头结点：为简化算法而附加的结点，不是线性表中的元素。
·在算法中无需将头结点和一般节点的情况分开讨论。
单向循环链表
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
双向循环链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

展开全文