第三章 线性表
2.1. 数组实现线性表
-
线性表操作总览
（1） 数组中的元素类型应该用typedef定义，是的类型可以随时变化
（2）线性表的长度任何时刻应该小于等于数组的长度。因为数组一经初始化，大小不能改变，随着元素的插入和删除，是的数组中有空位，此时，线性表长度就小于数组长度
（3）线性表的操作：“1”代表成功或“OK”，true
（4）线性表的地址计算：线性表中元素的下标从1开始，而存储数据的data数组角标从1开始。
（5）线性表的每个操作都要先对操作位置进行检查 -
线性表的操作
（1）线性表结构：
a. 存储数据的数组
b. 线性表长度字段#include <stdio.h> #define MAXSIZE 20 typedef int ElementType; typedef struct { // 定义线性表 ElementType Data[MAXSIZE]; int length; }SqList; int getElem(SqList list,int i,ElementType *e){ if(list.length ==0 || i <1 || i>list.length) return 0; *e = list.Data[i]; return 1; // 1代表成功 }
（2）插入操作的思想：
a. 检查插入位置
b. 最后一个元素开始，向前知道待查位置的元素，全部向后移位
c. 将元素插入
d. 表厂加1
```c
int insertList(SqList *list,int i, ElementType e){
if (list->length == MAXSIZE || i<1 || i>list->length+1 )
return 0;
// 插入数据时将被查位置后的元素向后移1位,如果是在最后一位操作，则不用这个操作
if(i <= list->length){
for(int j=list->length-1;j>i-1;j--){
list->Data[j+1] = list->Data[j];
}
}
list->Data[i-1] = e; // 线性表角标=数组角标+1
list->length++;
return 0;
}
```
（3）删除操作
a. 检查删除位置
b. 去除删除元素
c. 从删除位置开始，遍历到最后一个元素，分别将他们的位置提前一位
d. 表长减1
c int deleteList(SqList *list,int i,ElementType *e){ if(list->length==0 || i<1 || i>list->length) return 0; if(i<list->length){ for(int k=1;k>list->length;k++){ list->Data[k-1] = list->Data[k]; } } list->length--; return 1; }
（4）当线性表插入或删除都是操作最后一个元素的时候，时间复杂度为O(1),但是当操作的角标在数组中间时，需要把后面的length-i个元素向前或向后移位，所以时间复杂度为O(n)。因此线性表的插入删除操作的平均复杂度为(frac{n-1}{2})
2.2 链表实现线性表
-
链式存储的定义
（1）链式存储的节点定义：数据域和指针域
（2）指针域只包含一个指针的链表叫做单链表 -
存储结构中的重要定义
（1）链表中第一个节点的存储位置叫做头指针
（2）在单链表的第一个节点前附设一个节点，称为头结点。头结点的数据域不存储任何信息，其指针域存储指向第一个头结点的指针 -
头指针和头结点的意义
（1）这两个都不是真正的数据节点
（2）头指针指向第一个节点（如果存在头结点，头指针就只想头结点）。
（3）头指针为了标识一个链表，是传入函数的指针类型行参
（4）头指针永远不会为空，因为他的作用就是声明我是一个链表。
-----------------------------------------------------
（5）头结点的意义在于：有了头结点，对第一个数据元素前插入数据或是删除第一个数据元素，这些操作都和其他数据节点的操作完全一样了
（6）编程中，对链表的操作方法都是传入一个指向头节点的头指针。(如下面函数行参中的* LinkedList是一个二级指针，是头指针。而LinkedList是头结点，是一级指针)
----------------------------------------------------
（7）头结点和头指针在编程上也是Node类型的，整个LinkedList也不在单独声明，LikedList就是Node类型 -
链表的定义
#include <stdio.h> typedef int ElemType typedef struct Node{ ElemType data; // 数据域 Node *next; // 指针域 }Node; typedef struct Node *LinkedList; // 定义LinkedList为一个指针，指向Node类型的数据 -
链表的元素查找：遍历整个链表
/** * 查找第i个元素的值，返回操作是否成功，数据被包在参数e里 */ int getElem(LinkedList list,int i,ElemType *e){ // 这个list就是头结点，指向list的指针是头指针。头指针是行参传入的指针 LinkedList p = list->next; // 声明一个节点p，指向链表的第一个数据节点 int j =1 ; while(p!=NULL && j<i){ // 为了找到第i个节点 p = p->next; ++j; } if(p==NULL || j>i) { return 0; } *e = p->data; return 1; } -
单链表插入和删除
（1）链表的插入和删除操作比线性表要快。
（2）因为，假设我们希望从第i个位置插入10个元素，线性表没插入一个元素都把后面的所有元素移动1个位置，共移动n-1个位置。复杂度为10O(n)
（3）如果是链表插入10个元素，他只需要找到第i个元素，复杂度为O(n),之后的9个元素插入都是在此位置基础上改变指针域的指向。复杂度为O(1)。共O(n)+9O(1)/** * 在第i个位置添加元素 */ int insertList(LinkedList *list,int i,ElemType e){ // 此处的list是二级指针 int j=1; LinkedList p = *list; while(p!=NULL && j<i){ // 找到第i个node p = p ->next; ++j; } if(p == NULL || j>i) return 0; LinkedList newNode = (LinkedList)malloc(sizeof(Node)); newNode->data = e; newNode->next = p->next; p->next = newNode; return 1; } /** * 删除第i个位置的元素 */ int deleteList(LinkedList *list,int i,ElemType *e){ LinkedList p = *list; int j=1; while(p !=NULL && j<i){ p = p->next; j++; } if(p->next==NULL || j>i) // 此时找到p是被删除节点的前一个节点 return 0; LinkedList q = p->next; // q就是要删除的节点 p->next = q->next; *e = q->data; free(q); // 释放q节点所占空间 return 1; } -
单链表的创建过程(头插法)
（1）让链表L的头结点你的指针域指向NULL
（2）生成新节点p，将数据域赋值，将p插入到头结点和前一个节点之间/** * 创建一个有n个数的链表 */ void createList(LinkedList *list,int n){ * list = (LinkedList) malloc(sizeof(Node)); (*list)->next = NULL; // 声明一个头结点 for(int i=0;i<n;i++){ LinkedList p = (LinkedList) malloc(sizeof(Node)); // 创建一个新节点 p->data = i; p->next = (*list)->next; (*list)->next = p; } } int main(){ LinkedList l; createList(& l,10); ElemType a; getElem(l,1,&a); printf("%d",a); } -
尾插法创建链表
void createtailList(LinkedList *list,int n){ *list = (LinkedList) malloc(sizeof(Node)); LinkedList tail = *list ; // 声明tail时，指向头结点，后面改成指向最后一个元素 for (int i = 0; i < n; i++) { LinkedList p = (LinkedList)malloc(sizeof(Node)); p->data = i; tail->next = p; tail = p; // tail指向最后一个元素 } tail->next = NULL; } -
删除整张表
（1）思路：遍历每个数据节点，将数据节点free掉
（2）代码如下：