您的位置：首页 >资讯 >

顺序表与链表

2023-08-17 05:37:25 来源：博客园

【资料图】

顺序表与链表

前言

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

顺序表

【概念】

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

【结构特点】

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

【结构操作】

初始化【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.size2.若len 等于 size 则触发扩容操作，将原始空间大小 size 保存下即：tmp_size = size;3.为了防止重新分配空间失败，申请指针p , 采用while循环通过不断缩减temp_size的大小（tmp_size /= 2）申请重新分配地址空间。4.退出循环后判断p是否为NULL，不为空就将p赋值给原始指针。并更新空间大小。
顺序表数组空间销毁的思路：1.首先判断vector是否为NULL2.不为空则销毁数据空间3.最后销毁vector
顺序表查询指定位置元素的思路：1.判断查询位置是否合法（即：0 ≤ ind < vector.len）2.直接根据索引即可查询到（即：return vector.data[ind]）

顺序表完整代码

点击查看代码

#include#include#include/*顺序表：初始化、插入、删除、销毁、扩容、查找*/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#include#include/*单链表:初始化、获取新节点、插入新节点、删除结点、销毁链表、遍历结点*/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#include#includetypedef 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;}

标签：