数据结构与算法----链表

在讲链表的时候我们再吧线性表的基本功能说明一下

• **初始化线性表：**将一个线性表进行初始化，得到一个全新的线性表。
• **获取指定位置上的元素：**直接获取线性表指定位置i上的元素。
• **获取元素的位置：**获取某个元素在线性表上的位置i。
• **插入元素：**在指定位置i上插入一个元素。
• **删除元素：**删除指定位置i上的一个元素。
• **获取长度：**返回线性表的长度。

链表与顺序表的区别

1.顺序表：

顺序表底层所采用的是数组形式，所以分配的内存形式是一整块连续的内存地址

即物理上以及逻辑上的连续

所以：顺序表的分配必须是一块连续的内存，条件更加苛刻，

在表中插入新元素或删除无用元素时，为了保持其他元素的相对次序不变，平均需要移动一半元素，运行效率低

扩充时的时间成本更高

好处便是：访问更加方便能够直接通过下标访问元素

2.链表

链表是通过分配零散的内存所以对内存的要求没有那么大

插入和删除的时候不需要进行过多的操作，所以效率更高

坏处是访问的时候需要逐个遍历，效率低下

初始化

我们需要一个变量来存储值，一个变量来存储下一结点的坐标，所以我们开结构体

struct NodeList{
    int element;
    struct NodeList* next;
};

我们建立一个空的头节点来作为链表的开头，当然也可以不这么做，只不过这样做会更加方便

初始时我们默认头节点指向空指针。

void InitList(struct NodeList* head){
    head->next = NULL;
}

插入元素

可以这样理解，插入元素是将插入位置前一个结点指向的下一个坐标更改掉，原本指向的位置由另一个结点来指向

void InsertList(struct NodeList* head , int element , int index){
    if(index < 0) return 0;
    while(index--){ //将head变为前一个元素，注意在函数中head是形参，所以不会影响到原数据
        if(head->next == NULL) return 0; //如果index非法就会直接结束
        head = head->next;
    }
    struct NodeList* New = (struct NodeList *)malloc(sizeof(struct NodeList)); //分配一个新的结点来存储数据
    if(New == NULL) return 0; //分配失败直接返回
    struct NodeList* temp = head->next;
    head->next = New;
    New->element = element;
    New->next = temp;
}

删除元素

删除元素实际上就是将要散出结点的上一个结点所指向的位置指向要删除元素的下一个结点，最后free掉要删除的结点

void DeleteList(struct NodeList* head , int index){
    if(index < 0) return 0;
    while(--index){
        if(head->next == NULL) return 0;
        head = head->next;
    }
    struct NodeList* temp = head->next;
    head->next = head->next->next;
    free(temp);
}

其他操作

1.打印链表

void PrintList(struct NodeList* head){
    while(head->next  != NULL){
        head = head->next;
        printf("%d  ",head->element);
    }
    printf("\n");
}

2.查找元素下标

int SearchIndex(struct NodeList* head , int elememt){
    int index = 0;
    while(head->next != NULL){
        head = head->next;
        if(head->element == elememt)
            return index;
        index++;
    }
    return -1;
}

3.查找下标元素

int SearchElem(struct NodeList* head , int index){
    while(--index){
        if(head->next == NULL) return 0;
        head = head->next;
    }
    return head->next->element;
}

4.获取链表长度

int LenList(struct NodeList* head){
    int length = 0;
    while(head->next != NULL){
        head = head->next;
        length++;
    }
    return length;
}