顺序表，单链表

1.线性表

1.1 定义

由n(n≥0)个数据类型相同的元素构成的有限序列，称为线性表

线性表中元素的个数n定义为线性表的长度，当n=0时称为空表

对于非空的线性表或线性结构，存在唯一的一个被称为“第一个”的数据元素；存在唯一的一个被称为“最后一个”的数据元素

除了第一个元素外，结构中的每一个数据元素均只有一个前驱

除了最后一个元素外，结构中的每一个数据元素均只有一个后继

前驱：前一个元素
后继：后一个元素

2.顺序表

2.1 定义

用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的

2.2 初始化

#include<stdio.h>
#define MAXSIZE 100
typedef int ElemType;			//为int数据类型起别名

typedef struct{					//声明一个结构体
    ElemType data[MAXSIZE];		//声明了一个整数类型的数组，起别名是为了方便之后大量的修改
    int length;					//声明了一个整数类型的变量，用于存储顺序表中数据的个数
}SeqList;

//以下为初始化函数代码
void initList(SeqList *L){		//声明了一个函数，传入一个指针，初始化一个顺序表
    L->length = 0;
}

int main(){
    //以下声明一个顺序表并初始化
    SeqList list;
    initList(&list);
    printf("初始化成功，目前长度占用%d\n", list.length);
    printf("目前占用内存%zu字节\n", sizeof(list.data));
  
    return 0;
}

2.3 在尾部添加元素

int appendElem(SeqList *L, ElemType e){		//在尾部添加元素的函数
	if(L->length >= MAXSIZE){
		printf("顺序表已满")；
            return 0；
    }
    L->data[L->length] = e;
    L->length++;
    return 1;
}

int main(){
    //声明一个顺序表并初始化
    SeqList list;
    initList(&list);
    printf("初始化成功，目前长度占用%d\n", list.length);
    printf("目前占用内存%zu字节\n", sizeof(list.data));
  
    //在尾部添加代码
    appendElem(&list, 88);
    return 0;
}

2.4 遍历

void listElem(SeqList *L){
    //遍历顺序表的函数
    for(int i = 0; i < L->length; i++){
        printf("%d", L->data[i]);
    }
    printf("\n");
}

2.5 插入元素

int insertElem(SeqList *L, int pos, ElemType e){
    //插入元素的函数，其中pos(position)是插入的位置，即第pos个数据
	if(pos <= L->length){
        for(int i = L->length - 1; i >= pos-1； i--){
            L->data[i+1] = L->data[i];
        }
        L->data[pos-1] = e;
        L->length++;
    }
    return 1;
}

最好时间复杂度：O(1)
最坏时间复杂度：O(n)

2.6 删除元素

int deleteElem(SeqList *L, int pos, ElemType e){
    //删除元素的函数，其中pos(position)是删除的位置，即第pos个数据
	*e = L->data[pos-1];	//记录删除的东西
    if(pos < L->length){
        for(int i = pos; i < L->length; i++){
            L->data[i-1] = L->data[i];
        }
    }
    L->length--;
    return 1;
}

2.7 查找元素

int findElem(SeqList *L, ElemType e){
    //查找元素的函数
    for(int i = 0; i < L->length; i++){
        if(L->data[i] == e){
            return i + 1;
        }
	}
    return 0;
}

2.8 动态分配内存地址初始化

typedef struct{
    ElemType *data;
    int length;
}SeqList;

SeqList* initList(SeqList *L){
    SeqList *L = (SeqList*)malloc(sizeof(SeqList));				//开辟一个顺序表类型的空间，返回指针
    L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);	//开辟一百个整数的空间
    L->length = 0;												//初始化length
    return L;
}

3.单链表

线性表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这
组存储单元可以是连续的，也可以是不连续的)。

为了表示每个数据元素 a_i 与其直接后继数据元素 a_(i+1) 之间的逻辑关系，
对数据元素a_i来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息
(直接后继的存储位置)。这两部分信息组成数据元素 a_i 的存储映像，称为节点(node)。

节点包括两个域：其中存储数据元素信息的称为数据域;存储直接后继存储位置有域称为指针域。
指针域中存储的信息称作指针或链

n个结点[a_i(1≤i≤n) 的存储映像]链接成一个链表，即为线性表(a_1,a_2,…,a_n)

typedef int ElemType;

typedef struct node{
    ElemType data;
    struct node *next;	//存储下一个数据的地址
}Node;

3.1 单链表的初始化

接上方代码：

Node* initList(){								//初始化链表的函数
    Node *head = (Node*)malloc(sizeof(Node));	//构建一个节点大小的空间，初始化头节点，返回Node类型的指针
    head->data = 0;								//数据域为0
    head->next = NULL;							//指针域为NULL
    return head;								//返回Node类型的指针
}

int main(){
    Node *list = initList();
    return 1;
}

3.2 单链表-头插法

头插法指的是每一次把数据插在头节点的后面

int insertHead(Node* L, ElemType e){
    Node *p = (Node*)malloc(sizeof(Node));		//构建一个节点大小的空间，初始化p节点，返回Node类型的指针
    p->data = e;								//地址为p的节点的int类型为e
    p->next = L->next;							//地址为p的节点的指针域为头节点的指针域
    L->next = p;								//头节点的指针域为节点p的地址
}				
//注意：一定要先让新的节点指向头节点指向的节点，再让头节点指向新的节点

int main(){
    Node *list = initList();
    insertHead(list, 10);
    insertHead(list, 20);
}

3.3 单链表-遍历

void listNode(Node* L){
    Node *p = L->next;
    while(p != NULL){
        printf("%d\n", p->data);
        p = p->next;
    }
    printf("\n");
}

3.4 单链表-尾插法

先获取尾节点的地址，再把新节点插在后面

//1.获取尾节点地址
Node* get_tail(Node *L){
    Node *p = L;
    while(p->next != NULL){
        p = p->next;
    }
    return p;
}

//2.插入数据
Node* insertTail(Node* tail, ElemType e){
    Node *p = (Node*)malloc(sizeof(Node));		//创建空间
    p->data = e;
    tail->next = p;								//尾节点指向p
    p->next = NULL;								//新节点指向NULL
    return p;									//返回尾节点
}

3.5 单链表-在指定位置插入数据

找到插入节点的前置节点
让新节点指向前置节点指向的位置
让前置节点指向新节点的位置

int insertNode(Node *L, int pos, ElemTyoe e){
Node *p = L;
int i = 0;
while(i < pos-1){
p = p->next;
i++;
if(p == NULL){
return 0;
}
}
```
Node *q = (Node*)malloc(sizeof(Node));
q->data = e;
q->next = p->next;
p->next = q;
return 1;
```
}

3.6 单链表-删除节点

找到要删除的前置节点
用指针记录要删除的节点
通过改变前置节点的后继节点实现删除

释放删除节点的空间

int deleteNode(Node *L, int pos){
Node *p = L;
int i = 0;
//1.找到要删除节点的前驱
while(i < pos-1){
p = p->next;
i++;
if(p->next == NULL){
return 0;
}
}

if(p->next == NULL){
    printf("要删除的位置错误\n");
    return 0;
}
//2.用指针记录要删除的节点
Node *q = p->next;
//3.通过改变前置节点的后继节点实现删除
p->next = q->next;
//4.释放删除节点的空间
free(q);

return 1;

}

3.7 单链表-获取链表长度

int listLength(Node *L){
    Node *p = L;
    int len = 1;
    while(p != NULL){
        p = p->next;
        len++;
    }
    return len;
}

3.8 释放链表

把头节点除外的每一个节点的内存都释放掉

void freeList(Node *L){
    Node *p = L->next;
    Node *q;
  
    while(p != NULL){
        q = p->next;
        free(p);
        p = q;
    }
  
    L->next = NULL;
}