顺序表

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

存储结构

#define MAXSIZE 20  //线性表存储空间的初始分配量
#define OK 1    //成功标识
#define ERROR 0 //失败标识

typedef int Status;    //Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int

typedef struct
{
    ElemType *elem; //存储
    int length;
}SqList;

即

其中maxsize为线性表存储空间的初始值

初始化

Status InitList(SqList* L){
    //构造一个空的线性表L
    L -> elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    if(!L -> elem){  // 如果分配失败
        return ERROR;
    }
    L -> length = 0;
    return OK;
}

插入

Status ListInsert(SqList *L, int i, ElemType e){
    int k;
    if (L->length == MAXSIZE){  //线性表已满
        return ERROR;
    }   
    if (i < 1 || i > L->length+1){ //当i不在范围内时
        return ERROR;
    }
    if (i <= L->length){  //若插入位置不在表尾
        for(k = L->length-1;k >= i-1;k--){
            L->elem[k+1] = L->elem[k];
        }
    }   
    L->elem[i-1] = e;   //将新元素插入
    L->length++;    //长度加1
    return OK;
}

插入，即将原来的元素都向后移动一位

删除元素

同理，删除元素即所有元素向左移动一位

Status ListDelete(SqList *L, int i, ElemType *e){
    if(L->length == 0){   //线性表为空
        return ERROR;
    }
    if(i < 1 || i > L->length){ //删除位置不正确
        return ERROR;
    }
    *e = L -> elem[i-1];
    if(i < L->length){  //如果删除位置不在最后位置
        for(int k; = i;k < L->length;k++){
            L->elem[k-1] = L->elem[k];
        }
    }
    L->length--;    //长度减1
    return OK;
}

*e的作用：保存被删除的元素值

查找

Status GetElem(SqList L, int i, ElemType *e){
    if(L.length == 0 || i<1 || i>L.length){
        return ERROR;
    }
    *e = L.elem[i-1];
    return OK;
}

读取所有元素

void OutPut(SqList L){
    printf("当前顺序表的长度:%d\n", L.length);
    for(int i = 0; i < L.length; i++){
        printf("%d ",L.elem[i]);
    }
    printf("\n");
}

小结

线性表的顺序存储结果在读、存数据是的时间复杂度是O(1)，插入、删除操作的时间复杂度是O(n)

无须为表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任一位置的元素

但是当插入和删除操作需要移动大量元素时，若线性表长度较大，难以确定存储空间的容量；造成存储空间的“碎片”

单链表

概念

在链式结构中，除了要存储数据元素的信息外，还要存储它的后继元素的存储地址

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据ai来说

除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域

指针域中存储的信息称做指针或链

这两部分信息组成数据元素ai的存储映像，称为结点（Node）
n个结点（ai的存储映像）链结成一个链表，即为线性表（a1, a2, …, an）的链式存储结构

因为此链表的每个结点中只包含一个指针域，所以叫做单链表

存储结构

typedef int ElemType; 
typedef struct node{ 
    ElemType data; 
    struct node *next; 
}Node

初始化

Node* initList() 
{ 
    Node *head = (Node*)malloc(sizeof(Node)); 
    head->data = 0; 
    head->next = NULL; 
    return head; 
} 
int main() 
{ 
    Node *list = initList(); 
    return 1; 
}

头插法

int insertHead(Node* L, ElemType e) 
{ 
    Node *p = (Node*)malloc(sizeof(Node)); 
    p->data = e; 
    p->next = L->next; 
    L->next = p; 
}

• 先开辟出一个内存空间存储节点p
• p的数据域存入数据
• 将p的指针域指向原来头部的指针域
• 再将头部的指针域指向p

在指定位置插入

int insertNode(Node* L, int pos, ElemType e) {
    Node* p = L;  // p指向头节点（假设L是带头节点的链表）
    int i = 0;
    // 移动p到目标位置的前一个节点（pos-1）
    while (i < pos-1) {  // 循环条件调整为i < pos，确保pos=0时也能正确处理
        p = p->next;
        i++;
        if (p == NULL) {  // 若p提前为空，说明pos超出链表长度
            return 0;
        }
    }

    Node* q = (Node*)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;  // 新节点指向p的下一个节点
    p->next = q;        // p指向新节点，完成插入

    return 1;  // 插入成功
}

删除节点

1. 找到要删除节点的前置节点 p
2. 用指针 q 记录要删除的节点
3. 通过改变 p 的后继节点实现删除
4. 释放删除节点的空间

int deleteNode(Node *L, int pos)
{
    Node *p = L;
    int i = 0;
    while(i < pos-1)
    {
        p = p->next;
        i++;
        if (p == NULL)
        {
            return 0;
        }
    }

    if(p->next == NULL)
    {
        printf("要删除的位置错误\n");
        return 0;
    }

    Node *q = p->next;
    p->next = q->next;
    q->next->prev = p;
    free(q);
    return 1;
}

获取长度

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

释放链表

指针 p 指向头节点后的第一个节点

判断指针 p 是否指向空节点

如果 p 不为空，用指针 q 记录指针 p 的后继节点

释放指针 p 指向的节点

指针 p 和指针 q 指向同一个节点，循环上面的操作

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

循环列表

循环链表（Circular Linked List）是另一种形式的链式存储结构

其特点是表 中最后一个节点的指针域指向头节点，整个链表形成一个环

当链表遍历时，判别当前指针 p 是否指向表尾结点的终止条件不同

在单链表 中，判别条件为 p!=NULL 或 p->next!=NULL

而循环单链表的判别条件为 p!=L 或 p->next!=L。