线性表

• 线性表分为顺序存储结构和链式存储结构

存储方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
• 单链表采⽤用链式存储结构，⽤一组任意的存储单元存放线性表的元素。

时间性能

1. 查找

• 顺序存储 O(1);
• 单链表O(n)。

2. 插⼊入和删除

• 存储结构需要平均移动一个表⻓一半的元素，时间复杂度为 O(n)；
• 单链表查找某位置后的指针后，插⼊入和删除时间复杂度为 O(1)。

空间性能

• 顺序存储结构需要预先分配存储空间，分太大，浪费空间；分⼩了，发⽣上溢出；
• 单链表不需要分配存储空间，只要有就可以分配,，元素个数也不受限制。

单向循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点即可。

空链表

空链表.png

非空链表

非空链表.png

头指针&头结点

链表中第一个结点的存储位置叫做头指针，整个链表的存取必须是从头指针开始进行。之后的每一个结点，就是上一个的后继指针指向的位置。如果链表有头结点，那么头指针就是指向头结点数据域的指针。

头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）；有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了；首元结点也就是第一个元素的结点，它是头结点后边的第一个结点；头结点不是链表所必需的。

在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针；头指针具有标识作用，故常用头指针冠以链表的名字；无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头指针&头结点.jpg

有无头结点的区别

• 不带头结点的单链表对于第一个结点的操作与其他结点不一样，需要特殊处理，这增加了程序的复杂性和出现 bug 的机会，因此，通常在单链表的开始结点之前附设一个头结点；
• 带头结点的单链表，初始时一定返回的是指向头结点的地址，所以一定要用二维指针，否则将导致内存访问失败或异常；
• 带头结点与不带头结点初始化、插入、删除、输出操作都不一样，在遍历输出链表数据时，带头结点的判断条件是while(head->next!=NULL)，而不带头结点是while(head!=NULL)，虽然头指针可以在初始时设定，但是如1所述，对于特殊情况如只有一个结点会出现问题。

无头结点.jpg

单向循环链表代码实现

宏定义

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

//定义结点
typedef struct Node {
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

循环链表创建

/*
是否第一次创建链表
YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
 */
Status CreateList (LinkList *L){
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入结点的值，输入0结束\n");
    while(1) {
        scanf("%d",&item);
        if(item==0) break;
        
        //如果输入的链表是空。则创建一个新的结点，使其next指针指向自己  (*head)->next=*head;
        if (*L == NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if (!L) exit(0);
            (*L)->data = item;
            (*L)->next = *L;
        }
        else {
            //输入的链表不是空的，寻找链表的尾结点，使尾结点的next=新结点。新结点的next指向结点
            for (target = *L; target->next != *L; target = target->next);
            temp = (LinkList)malloc(sizeof(Node));
            if (!temp) return ERROR;
            temp->data = item;
            temp->next = *L; //新结点指向头结点
            target->next = temp; //尾结点指向新结点
        }
    }
    return OK;
}

遍历

//循环链表的遍历最好用do while语句，因为头结点就有值
void show (LinkList p) {
    //如果链表是空
    if(p == NULL){
        printf("打印的链表为空!\n");
        return;
    }
    else {
        LinkList temp;
        temp = p;
        do {
            printf("%5d", temp->data);
            temp = temp->next;
        }while (temp != p);
        printf("\n");
    }
}

插入数据

Status ListInsert (LinkList *L, int place, int num) {
    
    LinkList temp, target;
    int I;
    if (place == 1) {
        //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 找到链表最后的结点_尾结点,
        //3. 让新结点的next 执行头结点.
        //4. 尾结点的next 指向新的头结点;
        //5. 让头指针指向temp(临时的新结点)
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (target = *L; target->next != *L; target = target->next);
        temp->next = *L;
        target->next = temp;
        *L = temp;
    }
    else {
        //如果插入的位置在其他位置;
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
        //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
        //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置;
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++);
        temp->next = target->next;
        target->next = temp;
    }
    return OK;
}

删除数据

Status LinkListDelete (LinkList *L, int place) {
    
    LinkList temp, target;
    int I;
    temp = *L; //temp 指向链表首元结点
    if (temp == NULL) return ERROR;
    if (place == 1) {
        //①.如果删除到只剩下首元结点了,则直接将*L置空;
        if ((*L)->next == (*L)) {
            (*L) = NULL;
            return OK;
        }
        //②.链表还有很多数据,但是删除的是首结点;
        //1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
        //2. 新结点做为头结点,则释放原来的头结点;
        for (target = *L; target->next != *L; target = target->next);
        temp = *L;
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    }
    else {
        //如果删除其他结点--其他结点
        //1. 找到删除结点前一个结点target
        //2. 使得target->next 指向下一个结点
        //3. 释放需要删除的结点temp
        for(i = 1, target = *L; target->next != *L && i != place -1; target = target->next, i++) ;
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}

查询

int findValue (LinkList L, int value) {
    int i = 1;
    LinkList p;
    p = L;
    //寻找链表中的结点 data == value
    while (p->data != value && p->next != L) {
        I++;
        p = p->next;
    }
    //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
    if (p->next == L && p->data != value) {
        return -1;
    }
    return I;
}