线性表

分类

区别

​ 顺序表一般是使用数组存储的，存储空间是连续的；

​ 链式表一般是使用指针，将一个个结点联系起来。结点有数据域和指针域，数据域用来存储数据，指针域用来存储下一个结点的地址。链式表在存储空间（物理上）上不是连续的，在逻辑上是连续的，通过指针的指向连接起来，看起来是线性的。

优缺点

顺序表：插入删除速度慢，查询速度快，可随机访问

链式表：插入删除速度快，查询速度慢，不可随机访问

适用场景：在需要大量的插入和删除操作时使用链式表，需要随机访问时使用顺序表

链式表

注意：以下的几种链表都会用到头结点。头结点不储存数据，只是统一操作。

​ 头结点可以是和普通结点一样的结构体类型，也可以是其他的结构体类型。

单链表

//结点结构
typedef struct Node{
    int data;//数据
    struct Node * next;//指向下一个结点
}Node,*LinkList;

单链表有两种建立方法：头插法和尾插法

//头插
void head(LinkList headNode){
    Node* p = (Node*)malloc(sizeof(Node));//分配空间
	if (!p){
		printf("内存不足");
		exit(1);
	}
    int number = 0;
    printf("请输入一个数据：\n");
    scanf("%d",&number);
	p->value = number;
   	p->next = headNode-next;
    headNode->next = p;
}

//尾插
void tail(LinkList headNode){
    Node* p = (Node*)malloc(sizeof(Node));//分配空间
	if (!p){
		printf("内存不足");
		exit(1);
	}
    int number = 0;
    printf("请输入一个数据：\n");
    scanf("%d",&number);
	p->value = number;
    //遍历到最后一个结点
    while(headNode->next != NULL){
        headNode = headNode->next;
    }
    headNode->next = p;
    p->next = NULL;
}

注意：如果是头插法的话，你输入 1，2，3，4，5时，实际上链表为：head-->5-->4-->3-->2-->1-->NULL

​ 我碰到这样一个题目：反转一个单链表。

​ 有些人直接输入1，2，3，4，5，然后遍历链表输出5，4，3，2，1就结束了。对知识点的理解不透彻。

循环链表

循环链表的尾指针指向的是链表的开头

注意：在创建头结点时，要把头结点的next指向自身

双向链表

typedef struct Node{
    struct line * prior; //指向直接前趋
    int data;
    struct line * next; //指向直接后继
}Node,*List;

查找效率更高，空间换时间，比单链表更复杂，多了prior指针，在删除和插入的时候，要注意。先解决待插入结点，在解决其他的问题。

插入操作

//把p赋值给s的前驱，① 
s->prior = p;
//把p->next赋值给s的后继，② 
s->next = p->next;
//把s赋值给p->next的前驱，③
p->next->prior = s;
//把s赋值给p的后继，④
p->next = s;

注意：这里只是在链表的中间插入结点，还有在链表的头部插入，尾部插入，要在插入前做些判断。

删除操作

//把p->next赋值给p->prior的后继，①
p->prior->next = p->next;
//把p->prior赋值给p->next的前驱，②
p->next->prior = p->prior;
//释放结点
free(p);