线性表

目录

 线性表

1.掌握线性表的定义、逻辑结构及其抽象数据类型等基本概念。

2.重点掌握线性表的两种存储结构（顺序存储、链式存储）。

 

顺序存储：

链式存储！！！

结点

3.掌握顺序表的各种操作（插入、删除等）实现及算法复杂度。

 

4.掌握单链表的各种操作（插入、删除等）实现及算法复杂度。

 

5.理解带头结点的单链表的头结点的作用。

6.了解循环单链表及其实现。

 循环链表(Circular Linked List)

7.了解双链表的概念及其实现（重点是插入、删除操作的实现）。

8.了解借助于线性表完成一元多项式的表示和运算的基本思想。

9.掌握顺序表和链表的特点，对比它们的优缺点。

---

系列索引：《数据结构》C语言版 (清华严蔚敏考研版） 全书知识梳理

1. 掌握线性表的定义、逻辑结构及其抽象数据类型等基本概念。

线性表的抽象数据类型定义

1. 重点掌握线性表的两种存储结构（顺序存储、链式存储）。

顺序存储：

1. 把线性表的数据元素按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
2. 顺序表是一种随机存取结构。
3. 结构类型

链式存储！！！

• 结点

• 结构体描述结点

1. 结点是通过动态分配内存和释放内存来的实现

动态分配   p=(LNode*)malloc(sizeof(LNode));

函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。

动态释放  free(p) ;

系统回收由指针变量p所指向的内存区。

1. 结点的赋值

1. 掌握顺序表的各种操作（插入、删除等）实现及算法复杂度。

1  顺序表初始化

看实验二！！！！

2 顺序表插入元素

平均需要移动表上一半元素，因此算法的平均时间复杂度为O(n)。

3 顺序表删除元素

平均需要移动表上一半元素。因

此算法的平均时间复杂度为O(n)

1. 掌握单链表的各种操作（插入、删除等）实现及算法复杂度。

1. 单链表

每一个结点只包含一个指针域的链表称为单链表。

1 、建立单链表

⑴ 头插入法建立单链表

每次插入的结点都作为链表的第一个结点。

生成的链表中元素的次序和输入的次序相反

1. 尾插入法建立单链表

新结点插入到当前链表的表尾，使其成为当前链表的尾结点

对于单链表，无论是哪种操作，只要涉及到钩链，如果没有明确给出直接后继，钩链的次序必须是“先右后左”(即先实现插入结点与后继结点的链接关系，再实现插入结点与前驱结点的链接关系)。否则容易造成数据丢失。

2 、单链表的查找

(1)  按序号查找单链表中的第i个元素。

对于单链表，不能像顺序表中那样直接按序号i访问元素，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此链表不是随机存取结构，是顺序存取结构。

(2)  按值查找  

3 、单链表的插入

相当于是一个查找，找完了之后按链表构建时候插入

4 、单链表的删除

基本思想就是

①查找操作将所要删除的结点定位

②建立其前结点和后结点的连接；

③之后删除该位置即可 free（）

需要注意的几点

1. 需要定位两个结点指针p ，q，q->next = p;

一个定位该结点前的结点，一个定位该结点。

1. 需要加几个判断条件，因为无法预知链表的长度，所以在定位的时候直接需要防止操作出链表，

设单链表长度为n，则删除第i个结点仅当1≤i≤n时是合法的。则当i=n+1 时，虽然被删结点不存在，但其前趋结点却存在（即终端结点）。

故判断条件之一是p–>next!=NULL

⑴ 按序号删除

⑵ 按值删除

销毁：是先销毁了链表的头，然后接着一个一个的把后面的销毁了，这样这个链表就不能再使用了，即把包括头的所有节点全部释放。

清空：是先保留了链表的头，然后把头后面的所有的都销毁，最后把头里指向下一个的指针设为空，这样就相当与清空了，但这个链表还在，还可以继续使用；即保留了头，后面的全部释放。

1. 理解带头结点的单链表的头结点的作用。?

对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。

头结点是在链表的开始结点之前附加的一个结点。有了头结点之后头指针指向头结点，不论链表是否为空，头指针总是非空，而且头结点的设置使得对链表的第一个位置上的操作与在表中其它位置上的操作一致，为了使空链表与非空链表处理一致

1. 了解循环单链表及其实现。

 循环链表(Circular Linked List)

最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。

循环链表的操作

⑴ 判断是否是空链表：L->next==L ;

⑵ 判断是否是表尾结点：p->next==L ;

算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。

1. 了解双链表的概念及其实现（重点是插入、删除操作的实现）。

1. 了解借助于线性表完成一元多项式的表示和运算的基本思想。

1. 掌握顺序表和链表的特点，对比它们的优缺点。