[TOC] # 线性表的逻辑结构 **线性表**：由n(n>=0)个数据元素`a1, a2, a3 ... an`组成的有序数列。 + n： 表示数据元素的个数，也是表的长度； + n=0时称为空表； + 将非空的线性表(n>0)记做：`(a1, a2, a3 ... an)`。 常见的线性表的基本运算： + InitList(L) 构造一个空的线性表L，即表的初始化。 + ListLength(L) 求线性表L中的节点个数，即求表的表长。 + GetNode(L, i) 取线性表L中的第 i 个节点，要求：`1<=i<= ListLength(L)` + LocateNode(L, x) 在L中间查找**值为x**的节点，并返回该节点在L中的位置。 若L中有多个节点的值和x相同，则返回首次查找到的节点位置； 若L中没有节点的值想x，则返回一个特殊值表示查找失败。 + InsertList(L, x, i) 在线性表L的第i个位置上插入一个值为x的新节点，使得原编号i,i+1.... ，n的节点变为i+1,i+2.....n+1的结点。要求：`1<=i<=n+1`，`n`是原表L的长度。插入后表L的长度+1。 + DeleteList(L, i) 删除线性表L的第i个结点，使得原编号i+1，i+2 ，...... ，n的结点变成i，i+1，...... n-1的结点。要求：`1<=i<=n`，n是原表L的长度。删除后表L的长度-1。 # 线性表的顺序存储结构 ## 顺序表 顺序表：把线性表的结点按照逻辑次序存放在一组地址连续的单元里。 第一个存储单元的地址是该结点的存储地址，若开始节点`a1`的存储地址（基地址）是`LOC(a1)`，那么结点`ai`的存储单元地址： > LOC(ai) = LOC(a1) + (i-1)*c 1<= i <= n ## 顺序表上实现的基本运算 # 线性表的链式存储结构 ## 单链表 单链表由头指针唯一确定，因此单链表可以用指针来命名。即头指针是head，则链表称为head。  ~~~ typedef char DataType; typedef struct node{ DataType data; // 数据 struct node *next; // 下一个节点的指针 }ListNode; typedef ListNode * LinkList; // 给ListNode定义别名LinkList；为了**概念上更明确** ListNode * p; // 指向某一节点的指针 LinkList head; // 单链表的头指针，等价于 ListNode * head ~~~ + `p`是类型`ListNode *`的指针变量，如果`p!=NULL`，那么它的值是类型为`ListNode`的某一个结点的地址 ### 1. 建立单链表 + 头插法建表 + 尾插法建表 **头插法建表** ~~~ LinkList CreateListF(void){ char ch; LinkList head; // 头指针 ListNode *s; // 工作指针 head = NULL; // 链表开始为空 ch = getchar(); // 读取第 1 个字符 while (ch != '\n') { // 生成新结点 ① s = (ListNode *) malloc(sizeof(ListNode)); // 将读入的数据放入新结点的数据域中 ② s->data = ch; // ③ s->next = head; // ④ head = s; ch = getchar(); // 读入下一个字节 } return head; // 返回头指针 } ~~~  **尾插法建表** > **头插法**生成的链表中的结点的次序和输入的顺序相反。 ~~~ /** * 尾部插入法 * @return */ LinkList CreateListR(void){ char ch; LinkList head; // 头指针 ListNode *s , *r; // 申请的结点，保存尾部指针 head = NULL; // 链表初始值为空 r = NULL; // 尾指针初始值为空 while( (ch = getchar()) != '\n'){ s = (LinkList *) malloc(sizeof(ListNode)); // ① s->data = ch; // ② if (head == NULL) head = s; // 新节点插入空表 else r->next = s; // 新节点插入非空表结点 *r 之后 r = s; // 尾指针指向新表尾 } if (r != NULL) { r->next = NULL; // 对于非空表，将尾指针指针域置空 } return head; } ~~~  ~~~ LinkList CreateListR1(void){ char ch; LinkList head = (LinkList)malloc(sizeof(ListNode)); ListNode *s, *r; r = head; while ( (ch = getchar()) != '\n') { s = (ListNode *)malloc(sizeof(ListNode)); s->data = ch; s->next = s; r = s; } r->next = NULL; // 终端节点的指针域置空，或空表的头结点置空 return head; } ~~~  ### 2. 查找运算 **按序号查找** ~~~ /** * 再带头结点的单链表 head 中查找第 i 个结点，若找到，则返回该结点的存储位置，否则返回NULL * @param head 头结点 * @param i 位置 * @return 找到的位置或NULL */ ListNode * GetNode(LinkList head, int i){ int j; // 从头结点开始扫描 p = head; j = 0; // 顺指针向后扫描，直到p->next && j < i或 i== j为止 while (p->next && j < i) { p = p->next; j++; } if (i == j) { return p; } else { return NULL; } } ~~~ 时间复杂度为： `O(n)` **按值查找** ~~~ /** * 带头结点的单链表 head 中查找其值为 key 的结点 * @param head 单链表 head * @param key 值为 key * @return */ ListNode* LocateNode(LinkList head, DataType key){ // 从开始结点比较，表非空时，p初始值指向开始结点 ListNode *p = head->next; // 直到 p 为 NULL或者p->data为key为止 while (p && p->data != key) { p = p->next; } // 若p=NULL，则查找失败，否则p指向找到的值为key的结点 return p; } ~~~ ### 3. 插入运算 ~~~ /** * 将值为x的新结点插入到带结点的单链表head的第 i 个结点的位置上。 * @param head * @param x * @param i */ void InsertList(LinkList head, DataType x, int i){ ListNode *p, *s; // 寻找第 i-1个结点 p = GetNode(head, i -1); // i<1或i>n+1时插入位置 i 有错 if (p == NULL) { // 插入位置有错 } s = (ListNode *)malloc(sizeof(ListNode)); s->data = x; s->next = p->next; p->next = s; } ~~~  ### 4. 删除运算 ~~~ /** * 删除带头结点的单链表head上的第 i 个结点 * @param head * @param i */ void DeleteList(LinkList head, int i){ ListNode *p, *r; p = GetNode(head, i - 1); // 找出第 i - 1个结点 if (p == NULL || p->next == NULL) { // error 删除位置有错 } r = p->next; //令 r 指向被删除结点 ai p->next = r->next; // 将 ai 从链上摘下 free(r); // 释放结点 ai ， 将所占用的空间归还给存储池 } ~~~  ## 循环链表 概念：一种首尾相连的链表。其特点是：无须增加存储量，仅对表的链接方式稍作改变。 将终端节点的指针域 NULL 改为指向头结点或开始节点，就可得到单链形式的循环链表，称为**单循环链表**。  在实际应用中采用**尾指针**表示循环链表。  ~~~ /** * 链接两个链表 * @param A、B 非空循环链表的尾指针 * @return 新循环链表的尾指针 */ LinkList Connect(LinkList A, LinkList B){ LinkList p = A->next; // 保存A表的头结点位置 ① A->next = B->next->next; // B表的开始节点链接到A表尾 ② free(B->next); // 释放B表的头结点 ③ B->next = p; // ④ return B; // 新循环链表的尾指针 } ~~~  ## 双链表 概念：由头指针**head**唯一确定的，头结点和尾节点链接起来也能构成循环链表，称之为**双向循环链表**。  双链表的对称性： ~~~ // 假设 *p 的直接前趋和直接后继均存在 p->prior->next = p = p->next->prior ~~~ ### 双链表的**前插**操作  ~~~ /** * 在带头结点的链表中，将值为 x 的新结点插入 *p 之前，设 p != NULL * @param p 插入的位置 * @param x 需要插入的值 */ void DInsertBefore(DListNode *p, DataType x) { DListNode *s = malloc(sizeof(DListNode)); //① s->data = x; // ② s->prior = p->prior; // ③ s->next = p; // ④ p->prior->next = s; // ⑤ p->prior = s; // ⑥ } ~~~ ### 删除节点***p**  ~~~ /** * 删除结点 *p * @param p 需要删除的结点 *p */ void DDeleteNode (DListNode *p) { p->prior->next = p->next; p->next->prior = p->prior; free(p); } ~~~ # 顺序表和链表的比较 实际开发中，顺序表和链表的选择。 + 基于空间的考虑 + 基于时间的考虑 ## 基于空间的考虑 顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。 > 当线性表的长度变化不大，易于事先确定其大小时，为了节省空间，宜采用顺序表作为存储结构。 ## 基于时间的考虑 顺序表是由**向量**实现的，它是一种随机存取结构，对表中任一结点都可以在`O(1)`时间内存取； 链表中的结点需要从头开始遍历才能取得。 > 若线性表的主要操作是为了进行查找，很少做插入和删除操作时，顺序表作存储结构比较好。