顺序表与链表

wDao / 2023-08-16 / 原文

顺序表与链表

前言

基础数据结构的学习主要包括两个部分，即【结构定义】与【结构操作】。顾名思义，结构定义就是定义某种或多种性质，再通过相关的结构操作去维护这种性质。对于初学者来说数据结构的学习不能抽象的理解，还需要结合动态的、可视化的工具去理解。下面给出美国旧金山大学数据结构可视化的网站，帮助理解。
美国旧金山大学数据结构可视化网站

顺序表

【概念】

顺序表就是线性表的顺序存储形式，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

【结构特点】

支持随机存取
插入删除不方便
存储密度高

【结构操作】

初始化【init】

Vector *init(int n) {
    Vector *v = (Vector *)malloc(sizeof(Vector));
    v->data = (int *)malloc(sizeof(int) * n);
    v->len = 0;
    v->size = n;
    return v;
}//数组空间初始化

删除【delete】

int delete(Vector *v, int ind) {
    if (v == NULL) return 0;
    if (ind < 0 || ind >= v->len) return 0;
    for (int i = ind; i < v->len; i++) {
        v->data[i] = v->data[i + 1];    
    }
    v->len--;
    return 1;
}//删除指定位置的元素

销毁【clear】

void clear(Vector *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}//销毁顺序表

插入【insert】

int insert(Vector *v, int ind, int val) {
    if (v == NULL) return 0;
    if (ind < 0 || ind > v->len) return 0;
    if (v->len == v->size) {
        //扩容操作
        if (!expand(v)) return 0;//扩容失败
        printf("expand is successfuly ~~~\n");
    }

    for (int i = v->len; i > ind; i--) {
        v->data[i] = v->data[i - 1];
    }
    v->data[ind] = val;
    v->len++;
    return 1;
}//插入元素

扩容【expand】

int expand(Vector *v) {
    int tmp_size = v->size;
    int *p;
    while (tmp_size) {
        p = (int *)realloc(v->data, sizeof(int) * (tmp_size + v->size));//重新分配空间
        if (p) break;
        tmp_size /= 2;
    }
    if (p == NULL) return 0;
    v->data = p;
    v->size += tmp_size;
    return 1;
}//扩容操作

查找【search】

int search(Vector *v, int ind) {
    if (v == NULL) return 0;
    if (ind < 0 || ind >= v->len) return 0;
    return v->data[ind];
}//获取指定位置元素的值

【问题记录】

当使用realloc重新分配数组空间失败后，返回的是什么值？【NULL】
当calloc、malloc、realloc申请的空间为0个能不能申请成功？
- 可以申请成功，并且不为空。
- 注意：但是此时申请的地址空间不可使用
顺序表插入一个新元素val到ind位置的思路：
1.判断ind是否合法，即0 ≤ ind < vector.len;
2.判断顺序表的长度是否大于空间大小（vector.len ≥ vector.size）
3.从顺序表最后一个元素开始向后移动一位，直到移动到下标为ind位置为止
4.将vector[ind] = val; 完成顺序表元素插入
5.vector.len += 1;
顺序表删除指定位置ind的思路:
1.判断要删除的位置ind是否合法，即 0 ≤ ind < vector.len;
2.指针走到下标为ind的位置，将ind + 1的元素复制到ind位置，直到指针走到顺序表最后一个元素。
3.vector.len -= 1;
顺序表数组空间扩容的思路：
1.判断顺序表长度是否等于数组空间的大小，即 vector.len ?= vector.size
2.若len 等于 size 则触发扩容操作，将原始空间大小 size 保存下即：tmp_size = size;
3.为了防止重新分配空间失败，申请指针p , 采用while循环通过不断缩减temp_size的大小（tmp_size /= 2）申请重新分配地址空间。
4.退出循环后判断p是否为NULL，不为空就将p赋值给原始指针。并更新空间大小。
顺序表数组空间销毁的思路：
1.首先判断vector是否为NULL
2.不为空则销毁数据空间
3.最后销毁vector
顺序表查询指定位置元素的思路：
1.判断查询位置是否合法（即：0 ≤ ind < vector.len）
2.直接根据索引即可查询到（即：return vector.data[ind]）

顺序表完整代码

点击查看代码

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

/*顺序表：初始化、插入、删除、销毁、扩容、查找*/
typedef struct Vector {
      int *data;
      int len, size;
}Vector;

Vector *init(int n) {
    Vector *v = (Vector *)malloc(sizeof(Vector));
    v->data = (int *)malloc(sizeof(int) * n);
    v->len = 0;
    v->size = n;
    return v;
}//数组空间初始化

int expand(Vector *v) {
    int tmp_size = v->size;
    int *p;
    while (tmp_size) {
        p = (int *)realloc(v->data, sizeof(int) * (tmp_size + v->size));//重新分配空间
        if (p) break;
        tmp_size /= 2;
    }
    if (p == NULL) return 0;
    v->data = p;
    v->size += tmp_size;
    return 1;
}//扩容操作

int insert(Vector *v, int ind, int val) {
    if (v == NULL) return 0;
    if (ind < 0 || ind > v->len) return 0;
    if (v->len == v->size) {
        //扩容操作
        if (!expand(v)) return 0;//扩容失败
        printf("expand is successfuly ~~~\n");
    }

    for (int i = v->len; i > ind; i--) {
        v->data[i] = v->data[i - 1];
    }
    v->data[ind] = val;
    v->len++;
    return 1;
}//插入元素

int delete(Vector *v, int ind) {
    if (v == NULL) return 0;
    if (ind < 0 || ind >= v->len) return 0;
    for (int i = ind; i < v->len; i++) {
        v->data[i] = v->data[i + 1];    
    }
    v->len--;
    return 1;
}//删除指定位置的元素


int search(Vector *v, int ind) {
    if (v == NULL) return 0;
    if (ind < 0 || ind >= v->len) return 0;
    return v->data[ind];
}//获取指定位置元素的值

void clear(Vector *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}//销毁顺序表

void output(Vector *v) {
    if (v == NULL) return ;
    printf("Vector[%d] ==> [", v->len);
    for (int i = 0; i < v->len; i++) {
        i && printf(",");
        printf("%d", v->data[i]);
    }
    printf("]\n");
    return ;
}//遍历顺序表

int main() {
    #define max_op 10
    Vector *v = init(max_op);/*初始化数组空间*/
    srand(time(0));
    int op, ind, val;
    for (int i = 0; i < max_op; i++) {
        op = rand() % 4;
        ind = rand() % (v->len + 1);
        val = rand() % 100;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                /*插入元素*/
                printf("Vector insert val[%d] into ind[%d] is %s\n", val, ind, insert(v, ind, val) ? "successfully" : "fail");
            } break;
            case 3: {
                /*删除指定位置的元素*/
                printf("Vector delete ind[%d] is %s\n", ind, delete(v, ind) ? "successfully" : "fail");
            } break;
        }
        output(v);    
    }
    
    printf("请输入要查找的位置：");
    while (~scanf("%d", &ind)) {
        val = search(v, ind);
        if (val) printf("search ind[%d] is val[%d]\n", ind, val);
        else printf("对不起, 你查找的位置不合法。请重新输入!\n");
        printf("请输入要查找的位置：");
    }
    putchar(10);
    #undef max_op
    clear(v);/*销毁顺序表*/
    return 0;
}

链表

【概念】

使用任意的存储单元存储线性表的数据元素，该存储单元可以是连续的也可以是不连续的。采用结点表示每一个线性表的元素，结点包括指针域、数据域。数据域存储数据元素的值、指针域存储下一个结点的地址。

【结构特点】

插入删除效率高
内存利用率高
操作灵活

【结构操作】

初始化【init】

List *init() {
    List *l = (List *)malloc(sizeof(List));
    l->head = (Node *)malloc(sizeof(Node));
    l->head->next = NULL;
    l->len = 0;
    return l;
}/*初始化链表*/

插入【insert】

int insert(List *l, int ind, int val) {
    if (l == NULL) return 0;
    if (ind < 0 || ind > l->len) return 0; /*插入位置不合法*/
    Node *p = l->head, *q;
    while (ind--) p = p->next;
    q = p->next;
    p->next = getNewNode(val);
    p = p->next;
    p->next = q;
    l->len++;
    return 1;
}/*插入新节点*/

销毁【clear】

void clearNode(Node *head) {
    if (head == NULL) return ;
    clearNode(head->next);
    free(head);
    return ;
}/*销毁结点*/

void clear(List *l) {
    if (l == NULL) return ;
    clearNode(l->head);
    free(l);
    return ;
}/*销毁链表*/

删除【delete】

int delete(List *l, int ind) {
    if (l == NULL) return 0;
    if (ind < 0 || ind >= l->len) return 0;//删除位置不合法
    Node *p = l->head, *q;
    while (ind--) p = p->next;
    q = p->next;
    p->next = q->next;
    free(q);
    l->len--;
    return 1;
}/*删除结点*/

问题记录

链表如何插入一个新节点node到指定位置ind？
- 判断ind是否合法（即 ind > 0 && ind < list.len);
- 申请两个指针p 、q;
- p指向虚拟头结点，根据ind向后迭代 while (ind—）p = p→next;
- q指向p→next(防止内存泄漏)
- 将node插到p→next位置：p→next = node;
- 此时p指向 p→next; p = p→next
- 重新挂载后面的数据 p→next = q;
链表删除指定元素？
- 指针p走到待删除的前一个结点位置。
- 将待删除结点的后面数据使用指针q指向
- 将指针p指向的结点的next指针域覆盖为待删除的结点后面的q;

链表完整代码

点击查看代码【单链表】

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/*单链表:初始化、获取新节点、插入新节点、删除结点、销毁链表、遍历结点*/
typedef struct Node {
    int data;
    struct Node *next;
}Node;

typedef struct List {
    Node *head;//虚拟头结点
    int len;
}List;

/*获取新节点*/
Node *getNewNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->next = NULL;
    return p;
}

List *init() {
    List *l = (List *)malloc(sizeof(List));
    l->head = (Node *)malloc(sizeof(Node));
    l->head->next = NULL;
    l->len = 0;
    return l;
}/*初始化链表*/

int insert(List *l, int ind, int val) {
    if (l == NULL) return 0;
    if (ind < 0 || ind > l->len) return 0; /*插入位置不合法*/
    Node *p = l->head, *q;
    while (ind--) p = p->next;
    q = p->next;
    p->next = getNewNode(val);
    p = p->next;
    p->next = q;
    l->len++;
    return 1;
}/*插入新节点*/

int delete(List *l, int ind) {
    if (l == NULL) return 0;
    if (ind < 0 || ind >= l->len) return 0;//删除位置不合法
    Node *p = l->head, *q;
    while (ind--) p = p->next;
    q = p->next;
    p->next = q->next;
    free(q);
    l->len--;
    return 1;
}/*删除结点*/

void output(List *l) {
    if (l == NULL) return ;
    printf("Linklis[%d] == [", l->len);
    int flag = 0;
    for (Node *p = l->head->next; p; p = p->next) {
        flag && printf("->");
        printf("%d", p->data);
        flag = 1;
    }
    printf("]\n");
    return ;
}/*遍历链表结点*/

void clearNode(Node *head) {
    if (head == NULL) return ;
    clearNode(head->next);
    free(head);
    return ;
}/*销毁结点*/

void clear(List *l) {
    if (l == NULL) return ;
    clearNode(l->head);
    free(l);
    return ;
}/*销毁链表*/

int main() {    
    srand(time(0));
    int op, ind, val;
    #define max_op 20
    List *l = init();
    for (int i = 0; i < max_op; i++) {
        op = rand() % 4;
        ind = rand() % (l->len + 1);
        val = rand() % 100;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                printf("Linklist[%d] insert val = %d in the ind = %d is %s\n", l->len, val, ind, insert(l, ind, val) ? "YES" : "NO");
            } break;
            case 3: {
                printf("Linklist[%d] delete the ind = %d is %s\n", l->len, ind, delete(l, ind) ? "YES" : "NO");
            } break;
        }   
        output(l);
    }
    clear(l);
    #undef max_op
    return 0;
}

点击查看代码【双向链表】

//双向链表：初始化、插入、删除、销毁、遍历、获取ind位置的元素
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct Node {
    int data;
    struct Node *next, *pir;
}Node;

typedef struct DLinkList {
    Node *head;
    int len;
}DLinkList;

//获取新节点
Node *getNewNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->next = p->pir = NULL;
    p->data = val;
    return p;
}

//获取新的双链表
DLinkList *getNewDLinkList() {
    DLinkList *DL = (DLinkList *)malloc(sizeof(DLinkList));
    DL->head = getNewNode(0);//头结点
    DL->len = 0;
    return DL;
}

//插入
int insert(DLinkList *DL, int ind, int val) {
    if (DL == NULL) return 0;
    if (ind < 0 || ind > DL->len) return 0;//插入位置不合法
    Node *p = DL->head, *q, *new_node = getNewNode(val);
    while (ind--) p = p->next;
    new_node->next = p->next;
    new_node->pir = p;
    if (p->next) p->next->pir = new_node;
    p->next = new_node;
    DL->len += 1;
    return 1;
}

//删除
int delete(DLinkList *DL, int ind) {
    if (DL == NULL) return 0;
    if (ind < 0 || ind >= DL->len) return 0;//删除的位置不合法
    Node *p = DL->head;
    while (ind--) p = p->next;
    Node *q = p->next;
    p->next = q->next;
    if (q->next) q->next->pir = p;
    DL->len--;
    free(q);
    return 1;
}

//搜索第ind位置的元素
int search(DLinkList *DL, int ind) {
    if (DL == NULL) return 0;
    if (ind < 0 || ind >= DL->len) return 0;
    Node *p = DL->head;
    while (ind--) p = p->next;
    return p->data;
}

//遍历
void output(DLinkList *DL) {
    if (DL == NULL) return ;
    printf("[");
    Node *p = DL->head->next;
    int i = 0;
    for (Node * p = DL->head->next; p; p = p->next) {
        i++ && printf(", ");
        printf("%d", p->data);
    }
    printf("] <== DL[%d]\n", DL->len);
    return ;
}

//销毁双向链表
void clearNode(Node *head) {
    if (head == NULL) return ;
    clearNode(head->next);
    return ;
}

void clear(DLinkList *DL) {
    if (DL == NULL) return ;
    clearNode(DL->head);
    free(DL);
    return ;
}

int main() {
    srand(time(0));
    #define max_op 20
    int op, val, ind;
    DLinkList *DL = getNewDLinkList();//获取一个双向链表
    for (int i = 0; i < max_op; i++) {
        op = rand() % 4;
        ind = rand() % (DL->len + 1);
        val = rand() % 100;
        printf("op = %d ind = %d val = %d\n", op, ind, val);
        switch (op) {
            case 0:
            case 1: {
                //插入
                printf("insert the ind = %d ,val = %d to the DL %s!\n", ind + 1, val, insert(DL, ind, val) ? "YES" : "NO");
            } break;
            case 2: {
                //删除
                printf("delete the element of ind = %d from the DL %s!\n", ind + 1, delete(DL, ind) ? "YES" : "NO");
            } break;
            case 3: {
                //查找
                val = search(DL, ind);
                printf("search the element of ind = %d from the DL is %d!\n", ind + 1, search(DL, ind));
            } break;
        }
        output(DL);
    }
    clear(DL);
    #undef max_op
    return 0;
}