首页 > 其他分享 >顺序表与链表

顺序表与链表

时间：2023-08-16 22:44:49浏览次数：47  
标签：顺序 return val int len next 链表 表与 ind

顺序表与链表

前言

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

顺序表

【概念】

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

【结构特点】

  • 支持随机存取

  • 插入删除不方便

  • 存储密度高

【结构操作】

  • 初始化【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;
}

标签：顺序,return,val,int,len,next,链表,表与,ind
From： https://www.cnblogs.com/wDao1/p/17609231.html

相关文章

  • c/c++参数入栈顺序和参数计算顺序
    如果大家细心的话应该知道c/c++语言函数参数入栈顺序为从右至左，那么为什么这样呢？来看看两个知识点：参数的计算顺序与压栈顺序。参数入栈顺序c/c++中规定了函数参数的压栈顺序是从右至左，函数调用协议会影响函数参数的入栈方式、栈内数据的清除方式、编译器函数名的修饰规则等。参......
  • 1.C++入门以及简单顺序结构
    C++入门以及简单顺序结构一.编写一个简单的C++程序#include<iostream>usingnamespacestd;intmain(){ return0;}二.基础语法变量1.变量的概念变量本质上是一个装东西的盒子，并且只能存放一个值。2.变量的定义变量必须先定义，才可以使用inta=5;3.变量......
  • 《安富莱嵌入式周报》第320期：键盘敲击声解码, 军工级boot设计，开源CNC运动控制器，C语言
    周报汇总地址：http://www.armbbs.cn/forum.php?mod=forumdisplay&fid=12&filter=typeid&typeid=104 视频版：https://www.bilibili.com/video/BV1Cr4y1d7Mp/1、键盘敲击声解码https://arxiv.org/abs/2308.01074键盘敲击声被解码的话，我们使用键盘输入密码将被方便的解码出......
  • 4.1 C++ STL 动态链表容器
    List和SList都是C++STL中的容器，都是基于双向链表实现的，可以存储可重复元素的特点。其中，List内部的节点结构包含两个指针一个指向前一个节点，一个指向后一个节点，而SList只有一个指针指向后一个节点，因此相对来说更节省存储空间，但不支持反向遍历，同时也没有List的排序功能。双向链表的......
  • 4.1 C++ STL 动态链表容器
    List和SList都是C++STL中的容器，都是基于双向链表实现的，可以存储可重复元素的特点。其中，List内部的节点结构包含两个指针一个指向前一个节点，一个指向后一个节点，而SList只有一个指针指向后一个节点，因此相对来说更节省存储空间，但不支持反向遍历，同时也没有List的排序功能。双向链表......
  • LeetCode -- 19. 删除链表的倒数第 N 个结点
     一般的删除问题，可以直接删除（找符合条件的，找到了直接删掉），延迟删除（打标记，找完了再删除），栈，双指针 在链表中删除一个节点，要找到其前面一个节点cur,然后cur->next=cur->next->next即可 方法一：直接删除我们先算出链表长度len，要删除倒第n个节点就是删除第len-n......
  • RabbitMQ如何保证顺序消费
    面试官：你能说说RabbitMQ是如何保证消息顺序消费的吗？老任：如果我们想要保证消息是按照顺序进行发送的，发送到队列后，队列的消息应该是先进先出的，我们只需要一个队列配置一个消费者即可(窃喜中......)。面试官：我们的项目一般都是集群部署的，一个队列就会有多个消费者，怎么实现一个队列中所......
  • 《高级程序员 面试攻略 》RocketMQ 如何保证顺序性
    RocketMQ提供了一种称为顺序消息的机制来确保消息的顺序性。下面是一些关键的方法和概念：1.顺序消息：顺序消息是指在发送和消费过程中，消息按照特定的顺序进行处理。RocketMQ通过将消息发送到同一个消息队列（MessageQueue）来实现顺序消息。每个消息队列都有一个全局唯一的标识符（Me......
  • 7.2 C/C++ 实现动态链表
    动态链表是一种常用的动态数据结构，可以在运行时动态地申请内存空间来存储数据，相比于静态数组和静态链表，更加灵活和高效。在动态链表中，数据元素被组织成一条链表，每个元素包含了指向下一个元素的指针，这样就可以通过指针将所有元素串联起来。使用动态链表存储数据时，不需要预先申请内......
  • 7.3 C/C++ 实现顺序栈
    顺序栈是一种基于数组实现的栈结构，它的数据元素存储在一段连续的内存空间中。在顺序栈中，栈顶元素的下标是固定的，而栈底元素的下标则随着入栈和出栈操作的进行而变化。通常，我们把栈底位置设置在数组空间的起始处，这样在进行入栈和出栈操作时，只需要维护栈顶指针即可。顺序栈的实现比......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99