线性表_链式结构

指针是变量，存的是地址。
结构特点：逻辑上相邻的数据元素在物理上不一定相邻。
设计思想：牺牲空间效率换取时间效率。

malloc()：分配内存空间返回地址
用法：void *malloc(unsigned size)
功能：在内存的动态存储区分配１个长度为 size的连续空间。
返回值：申请成功，则返回新分配内存块的起始地址；否则，返回NULL
注：malloc()函数的返回值是一个无类型指针，其特点是可以指向任何类型的数据。但在实际使用malloc()函数时，必须将其返回值强制转换成被赋值指针变量的数据类型，以免出错。

sizeof() ：获取变量类型长度
·格式：sizeof(变量名／类型名)
·功能：求变量／类型占用的内存字节数（正整数）。

free()：释放内存空间
·用法：void free(void *ptr)
·功能：释放 由ptr指向的内存块（ptr是调用malloc() 函数的返回值）。
·返回值：无。

定义：(存储的数据类型及指向自身类型的指针类型)

//SingleNode是自定义结构类型名称
typedef struct SingleNode 
{
    ElemType data; //数据
    struct SingleNode *next; //指向下个节点指针
}SingleLinkList;

ListInstialize() 初始化：分配头结点空间，头指针指向该空间，头结点的next指向NULL

//申请头结点空间，头指针指向头结点
void ListInstialize(SingleLinkList **head)
{
    *head = (SingleLinkList *)malloc(sizeof(SingleLinkList));
    (*head)->next = NULL;
}

注：因为改变的是头指针（指向头结点的指针），所以需要两个*

ListLength() 求元素个数
步骤：从头结点的next开始，不为空size+1，为空则循环条件不成立，最后返回size

int ListLength(SingleLinkList *head)
{
    SingleLinkList *p = head;
    int size = 0;
    while(p->next != NULL)
    {
        p = p->next;
        size++;
    }
    return size;
}

ListInsert() 插入一个元素
插入：先用插入节点的next指向当前节点的next，再用当前节点的next指向插入节点

//i为0表示从第1个位置插入
int ListInsert(SingleLinkList *head, int i, ElemType x)
{
    SingleLinkList *p = head;
    SingleLinkList *q = (SingleLinkList*)malloc(sizeof(SingleLinkList));
    q->data = x;
    int j = 0;
    while(p->next != NULL)
    {
        if (j == i) break;  //找到i位置对应的p
        p = p->next;
        j++;
    }
    if (j != i) //整个链表遍历完都没找到i的位置
    {
        printf("%s\n","插入位置错误!");
        return 0;
    }   
    
    q->next = p->next;
    p->next = q;
    return 1;
}

ListDelete() 删除一个元素
说明：循环条件添加p->next->next，避免p->next为NULL，且j等于i的情况，执行删除操作，程序奔溃

int ListDelete(SingleLinkList *head, int i, ElemType *x)
{
    SingleLinkList *p = head;
    if (p->next == NULL)
    {
        printf("%s\n", "链表为空，不能删除");
        return 0;
    }

    int j = 0;
    while(p->next != NULL && p->next->next != NULL)
    {
        if(j == i) break;
        j++;
        p = p->next;
    }   
    if (j != i)
    {
        printf("%s\n", "删除位置有错！");  
        return 0;   
    }

    SingleLinkList *s = p->next; *x = s->data;
    p->next = s->next;  //p->next = p->next->next
    free(s);
    return 1;
}

ListGet() 获取元素

//取数据元素
int ListGet(SingleLinkList *head, int i, ElemType *x)
{
    SingleLinkList *p = head;
    int j = 0;
    while(p->next != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    if (j != i)
    {
        printf("%s\n", "取数据元素位置错误！");
        return 0;
    }
    *x = p->data;
    return 1;
}

ListDestroy() 销毁链表：从头往后销毁

void ListDestroy(SingleLinkList **head)
{
    SingleLinkList *p = *head;
    SingleLinkList *p1;

    while(p != NULL)
    {
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}

总结：
1、所有操作都需要while(p->next != null){}这个遍历，因为都需要从头往后找；
2、删除多了p->next->next != null 避免特殊情况；
3、初始化和销毁都需要对头指针本身进行操作，所以形参传入头指针的指针；其他操作都是直接传入头指针。

时间效率分析：
（1） 查找
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。
（2） 插入和删除
操作本身是O(1)，找下标O(n)。

优点：不需要预先设定链表长度。

---

例：
建立一个单链表，首先依次输入数据元素１,２,…,10，然后删除数据元素５，最后依次显示当前表中的数据元素。

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int ElemType;
#include "SingleLinkList.h"
void main(void)
{
    SingleLinkList *head;
    int i, x, y, z;
    ListInstialize(&head);
    for(i=0;i<10;i++)
    {
        ListInsert(head, i, i + 1);
    }
    ListDelete(head, 10, &y);
    printf("删除的元素为：%d\n", y);
    for(i=0; i<ListLength(head);i++)
    {
        ListGet(head, i, &x);
        printf("%d ", x);
    }
    z = ListLength(head);
    printf("\n长度为：%d", z);
    ListDestroy(&head);
}

---

算法练习：
1、在递增的单链表中插入元素，保持链表的递增

//有序插入
void ListInsertOrderly(SingleLinkList *head, ElemType x) 
{
    SingleLinkList *pre = head;
    SingleLinkList *curr = head->next;
    SingleLinkList *q = (SingleLinkList*)malloc(sizeof(SingleLinkList));
    q->data = x;
    while(curr != NULL)
    {
        if(curr->data >= x) break;
        pre = curr;
        curr = curr->next;
    }

    pre->next = q;
    q->next = curr;
}

2、单链表la逆置后存到lb(头插法)

void Converse(SingleLinkList *la, SingleLinkList *lb)
{
    SingleLinkList *p, *q;
    p = la->next;
    while(p != NULL)
    {
        q = (SingleLinkList*)malloc(sizeof(SingleLinkList));
        q->data = p->data;
        
        q->next = lb->next;
        lb->next = q;
        
        p = p->next;
    }
} 

3、就地逆置（自身逆置）

void ConverseItself(SingleLinkList *head)
{
    //空表或只有一个元素直接退出 
    if(head->next == NULL || head->next->next == NULL) return;
    SingleLinkList *first, *mid, *last;
    first = head->next;
    mid = head->next;
    last = head->next->next;
    
    mid->next = NULL;
    mid = last;
    last = last->next;
    
    while(last != NULL)
    {
        mid->next = first;
        first = mid;
        mid = last;
        last = last->next;
    }
    mid->next = first;
    head->next = mid;
}