数据结构基础第2讲 线性表\(\bigstar \bigstar \bigstar \bigstar \bigstar\)
本讲知识结构
考点一：基本定义和逻辑
线性表具有相同特性的数据元素的有限序列
考点二：线性表的还是顺序结构\(\bigstar \bigstar \bigstar \bigstar\)
存储要点：将线性表中的元素从前往后依次存入一个地址连续的空间中
描述顺序表：
背：
# define MaxSize 100 // 假定最打容量100
typedef int ElemType;
type struct // 定义线性表数据类型
{
ElemType data[MaxSize]; // 存放元素的数组
int length; // 线性表长度
}SeqList;
-
建立顺序表：
-
顺序表指针引用
-
初始化顺序表
-
顺序表判空
-
求顺序表长度
-
输出顺序表：
-
按位置查找：
-
按值查找：
-
顺序表插入
注意边界条件抄代码：
int Insert(SeqList *L, int i, ElemType e) { if(L -> length >= MaxSize) { printf("上溢错误，插入失败\n"); return 0; } if(i < 1 || i > L -> length + 1) { printf("位置错误，插入失败\n"); return 0; } for(int j = L -> length; j >= i; j--) L -> data[j] = L -> data[j - 1]; L -> data[i - 1] = e; L -> length++; return 1; }
时间复杂度：
-
顺序删除
抄代码：
时间复杂度：
查找容易，增删难。
-
按值删除
抄代码：
时间复杂度：
顺序表去重问题算法\(\bigstar\)：
记录当前序列中有多少个被删元素x，从前往后扫描数组，若被记录值k为0，不移动；当为被删元素，删除，记录值为1；当其不是被删除元素，且记录值不为0时，往前移动k个元素。
抄算法代码：
点拨
顺序表归并问题：
\[消除回溯\left \{ \begin{matrix} 1.有序 \\ 2.位置 \end{matrix} \right . \]- 合并
代码：
-
逆置
对位交换法：
总体逆置
部分逆置：
\[\divideontimes \left \{ \begin{matrix} 1.总体逆置：i 与length - i - 1交换 \\ 2.部分逆置：forme + i与 to - i交换 \end{matrix} \right . \]
-
分割
题眼 分开/分割 \(\left \{ \begin{matrix} 1.快排（基准）\rightarrow 无序\\ 2. 二分法（中间）\rightarrow 有序\end{matrix} \right .\)
S = O(1);T = O(n); 当使用二分时间复杂度可以达到O(\(\log n\))
代码：
考点三：线性表的链式结构
运行时动态分配空间
1.单链表结构
背诵单链表结构体：
基本组成：
2. 单链表的基本操作
-
如何向内存申请释放一个节点
-
初始化一个链表
-
插入一个节点
\[\left \{ \begin{matrix} 1.找前驱\\ 2. 防断链 \end{matrix} \right . \]1.先链接后继节点，防断链
2.再将插入节点连上前驱节点
-
删除一个节点
同理
-
指针后移
发挥工作指针作用p = p -> next;
-
赋值操作
对工作指针经过的某一特定点用另外一个指针保存。
2.单链表的实现\(\bigstar \bigstar \bigstar \bigstar \bigstar\)
头插法逆序，尾插法逆序。
-
头插法
创建数据顺序与原始数据顺序相反
-
尾插法
创建尾指针，始终指向尾节点。
代码：
3.链表实现遍历，求长度，查找
-
遍历
代码：
-
求长度
代码：
-
查找
按位置
按值
-
插入与删除
插入：
按位置删除：
按值删除：
4.单链表的应用，去重和逆置等
-
分割问题
问题描述：
思路：
代码：
void split(LNode *L, LNode *L1, LNode *L2) { LNode *p = L -> next, *q, *r1; // p指向第一格数据点 L1 = L; // L1利用原来L的头节点 r1 = L1; //r1始终指向L1的尾节点 L2 = (LNode *)malloc*(szieof(LNode)); // 创建L2的头节点 L2 -> next = NULL; // 置L2的指针域为NULL while(p != NULL) { r1 -> next = p; // 采用尾插法将p(data值为a)插入L1中 r1 = p; p = p -> next; // p移向下一个节点(data值为b) q = p -> next; // 用q保存p的后继节点 p -> next = L2 -> next; // 采用头插法将p插入L2中 L2 -> next = p; p = q; // p重新指向a_i+1的结点 } r1 -> next = NULL; //尾节点next置空 } -
合并
问题描述：
双指针法代码：
LinkList Merge_LinkList(LNode *La, LNode *Lb) { LNode *Lc, *pa, *pb, *pc, *ptr; Lc = La; pc = La; pa = La -> next; pb = Lb -> next; while(pa != NULL && pb != NULL) { // 将pa所指的节点合并，pa指向下一个节点 if(pa -> data < pb -> data) { pc ->next = pa; pa = pa -> nect; } else if(pa -> data > pb -> data) { pc -> next = pb; pc = pb; pb = pb -> next; } else { // 合并以La，Lb为头节点的两个有序单链表 pc -> next = pa; pc = pa; pa = pa -> next; ptr = pb; pb = pb -> next; free(ptr); } // 将pa所指的节点合并，pb所指的节点删除 } if(pa != NULL) pc -> next = pa; if(pb !=NULL) pc -> next =pb; free(Lb); return (Lc); } -
删除重复节点
问题描述：
-
逆转线性单链表
LinkList reverse_list(LNode *head) { if(NULL == head -> next) return NULL; LNode *p = head -> next; head -> next = NULL; LNode *tmp = NULL; while(p) { tmp = p -> next; p -> next = head -> next; head -> next = p; p = tmp; } return head; }
考点五：线性表的其他链式结构
-
双向链表
定义结构体（代码题不要求）
头插法，尾插法，查找删除，去重，知识点拨几个
标签：matrix,基础,next,pb,pa,节点,数据结构,bigstar From： https://www.cnblogs.com/JUANFENHUI/p/18144470