数据结构 考研 第二章

### 考研数据结构第二章学习资料与知识点总结

#### 一、线性表的逻辑结构
线性表是由n(n≥0)个相同类型的元素组成的有限序列。当n=0时，称为空表；非空表中每个元素都有唯一的前驱和后继(首元除外)，这种关系称为线性关系。

#### 二、线性表的顺序存储结构
线性表的顺序表示是指用一组地址连续的存储单元依次存放线性表的数据元素。为了方便处理，在实际应用中通常会设置一个附加头结点[^2]。

typedef struct {
    ElemType *elem;     // 存储空间基址, elem[0]一般不用来存储有效数据
    int length;         // 当前线性表长度
} SqList;

#### 三、顺序表上基本运算实现
1. **查找**
查找分为按序号查找和按值查找两种方式。前者通过下标直接访问数组对应位置即可获得所需元素；后者则需遍历整个列表直至找到目标项或到达末尾为止。

2. **插入**
插入操作是在指定位置i处加入新元素e。这之前要先检查容量是否足够并移动后续所有记录以便腾出空隙供待插入对象占用。如果原容器已满，则应考虑动态扩展其大小以容纳更多成员。

3. **删除**
删除动作涉及移除位于给定索引上的项目并将后面剩余部分向前挪动一位覆盖掉被删去的位置从而保持整体连贯性不变形。同样需要注意边界条件防止越界错误发生。

#### 四、单链表及其特点
不同于静态分配内存空间构建起来的一维数组形式——即所谓的“顺序表”，另一种常见的线性表表现形态叫做“链接表”。它由若干个节点组成，其中每一个都含有指向下一个相邻伙伴的信息字段next以及自身携带的有效载荷data两大部分构成。由于不再依赖固定尺寸预先开辟好的缓冲区而是依靠运行期间临时申请释放资源完成增减变动因此具备更好的灵活性适应范围更广但也牺牲了一定程度上的存取效率优势。

typedef struct LNode{
    ElemType data;
    struct LNode* next;
}*Link,*Position;
typedef Link List;