学习笔记0331
第二章 线性表
2.1线性表的定义和特点
线性结构的特点：（一对一）
①只有一个首结点和尾结点;
②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。
线性表的定义:
用数据元素的有限序列表示空表：n=0;
2.2案例引入
案例一：一元多项式
案例二：系数多项式
两个多项式相加【步骤】
2.3线性表的类型定义
线性表的顺序存储
线性表的链式存储
基本操作：初始化、取值、查找、插入、删除
2.4 SqList线性表的顺序表示和实现
逻辑上相邻，物理上也相邻。
用数组来实现线性表的顺序存储结构。
案例：图书表的顺序存储结构类型
C语言的动态分配函数( <stdlib.h> )
malloc(m) :开辟m字节长度的地址空间，并返回这段空间的首地址
sizeof(x) :计算变量x的长度
free(p) :释放指针p所指变量的存储空间,即彻底删除一个变量
补充: C+ +的动态存储分配
申请存放T类型对象的内存空间
释放指针P：
C++的参数传递
（1）值传递
（2）地址传递 *
指针变量做参数（有交换5和7）
没有交换5和7
（3）引用类型作参数 &
交换了5和7
（4）数组名作参数
a 数组名，首地址 a = &a[0];
★ int b[ ] 等价于 int *b;
基本操作：初始化、取值、查找、插入、删除
初始化
函数参数用 引用&
函数参数用 指针*
销毁线性表L
清空线性表L
求线性表的长度
判断线性表L是否为空
取值
查找
插入（插在第i个结点之前）
插入算法分析：
实现代码：
算法时间复杂度分析：平均移动次数AMN
在第i个元素插入，移动 n-i+1 次
删除（删除第i个结点）
插入算法时间复杂度分析
查找、插入、删除算法的平均时间复杂度 O(n);空间复杂度是O（1）。
顺序表的特点：
2.5线性表的链式表示和实现
链式存储：结点 = 数据域 + 指针域
头指针 Head
头结点
首元结点
尾结点的指针域（NULL /Head）
单链表、双链表、循环链表
如何表示空表？
head->next = NULL;
在链表中设置头结点的好处？
头结点的数据域内装的是什么？
链表的特点？ 顺序存取法
链表的优缺点
单链表的定义和实现
单链表用头指针的名字命名
单链表的存储结构定义
1.2表示的内容是一样的。都是定义一个struct LNode 的指针变量p。
相当于 struct LNode *p。
分析如下图：
初始化
函数参数用 引用&
函数参数用 指针*
销毁线性表L
清空线性表L
求线性表的长度
判断线性表L是否为空
取值
查找
need-to-insert-img
执行 圆圈2 是因为没有找到元素e
插入（插在第i个结点之前）
插入算法分析：
2.6顺序表和链表的比较
初始化（构造一个空表）
（1）销毁
（2）清空链表
先删除其他结点，再把头结点的指针域置为NULL。
（3）求表长
（4）判断表是否为空
（5）在链表中取值
分析：
算法步骤：
算法描述：
插入
算法分析
算法描述：
查找
查找成功：返回元素所在的位置
查找返回e的地址
查找返回e的位置序号
删除（画图后较容易理解）
算法分析：
算法分析：
链表——时间、空间复杂度
单链表的创建
（前插法、尾插法）
单链表的创建——前插法
算法描述
单链表的创建——尾插法
算法描述：
循环链表
最后一个结点的指针域指向头指针
尾结点：rear
循环链表的合并
（1）p指向头结点【的地址】 Ta->next（存放在Ta尾结点的指针域内）（p相当于链表的头指针）
（2）Ta的尾指针（Ta->next）指向Tb的首元结点(Tb->next->next)
（3）释放删除Tb的头结点（存放在Tb->next）;
（4）循环链表需要尾指针（Tb->next）指向头指针 (p)
分析心得:弄清楚 头指针、头结点、首元结点，尾结点、尾指针 的表示方式（即，存放在拿个指针域内）
1）头指针 p = Ta->next
2）头结点 Ta->next、 Tb->next
3）首元结点 Ta->next->next 、 Tb->next->next (首元结点的地址存放在头指针Ta->next 的指针域->next 内)
4）尾结点 Ta 、Tb、rear
5）尾指针 Ta->next、Tb->next
双向链表DulNode（一个数据域+两个指针）
指针：一个指向前驱地址，一个指向后继地址
定义双向链表的抽象数据类型：
双向链表的插入
双向链表的删除
双向循环链表
尾结点d的指针域指向头结点
顺序表和链表的对比
2.7线性表的应用
线性表的合并
应用1
运用到了线性表SqList里面定义的函数（可以直接使用）
有序表的合并
有序链表的合并【真难啊】
2.8案例分析与实现
案例一：一元多项式的创建【数组表示】
案例二：稀疏多项式相加【链表】
比较指数部分，插入、删除操作
案例三：图书信息管理系统
顺序表和链表都可以实现
小总结：线性表两种存储结构——顺序表和链表
