数据结构与算法 - 线性表

文章目录

  • 第1关：实现一个顺序存储的线性表
  • 第2关：实现一个链接存储的线性表

第1关：实现一个顺序存储的线性表

编程要求
本关任务是实现 step1/Seqlist.cpp 中的SL_InsAt、SL_DelAt和SL_DelValue三个操作函数，以实现线性表中数据的插入、删除与查找等功能。具体要求如下：

SL_InsAT: 在顺序表的位置i插入结点x，即插入d[i]之前，i的有效范围[0,slist->len]；

SL_DelAt：删除顺序表slist的第i号结点， i的有效范围应在[0,slist->len)内，否则会产生异常或错误。返回被删除的数据元素的值；

SL_DelValue：删除第一个值为x的结点，存在值为x的结点则返回结点编号，未找到返回－1；

输入输出格式请参见后续测试样例。

注意：本关必读中提及的其他操作已经由平台实现，你在实现本关任务的三个操作函数时，在函数体内可调用其他操作。

/*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 顺序表操作实现文件
//
#include <stdio.h>
#include <stdlib.h>
#include "Seqlist.h"
SeqList* SL_Create(int maxlen)
// 创建一个顺序表
// 与SqLst_Free()配对
{
    SeqList* slist=(SeqList*)malloc(sizeof(SeqList));
    slist->data = (T*)malloc(sizeof(T)*maxlen);
    slist->max=maxlen;
    slist->len=0;
    return slist;
}
void SL_Free(SeqList* slist)
// 释放/删除 顺序表
// 与SqLst_Create()配对
{
    free(slist->data);
    free(slist);
}
void SL_MakeEmpty(SeqList* slist)
// 置为空表
{
    slist->len=0;
}
int SL_Length(SeqList* slist)
// 获取长度
{
    return slist->len;
}
bool SL_IsEmpty(SeqList* slist)
// 判断顺序表是否空
{
    return 0==slist->len;
}
bool SL_IsFull(SeqList* slist)
// 判断顺序表是否满
{
    return slist->len==slist->max;
}
T SL_GetAt(SeqList* slist, int i)
// 获取顺序表slist的第i号结点数据
// 返回第i号结点的值
{
    if(i<0||i>=slist->len) {
        printf("SL_GetAt(): location error when reading elements of the slist!\n");        
        SL_Free(slist);
        exit(0);
    }
    else 
        return slist->data[i];
}
void SL_SetAt(SeqList* slist, int i, T x)
// 设置第i号结点的值（对第i号结点的数据进行写）
{
    if(i<0||i>=slist->len) {
        printf("SL_SetAt(): location error when setting elements of the slist!\n");        
        SL_Free(slist);
        exit(0);
    }
    else 
        slist->data[i]=x;
}
bool SL_InsAt(SeqList* slist, int i, T x)
// 在顺序表的位置i插入结点x, 插入d[i]之前
// i的有效范围[0,plist->len]
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if (i<0 || i>slist->len || slist->len==slist->max) {
        printf("SL_InsAt(): location error, or slist full.\n");
        return false;
    }
    for (int j=slist->len; j>=i+1; j--) {
        slist->data[j]=slist->data[j-1];
    }
    slist->data[i]=x;
    slist->len++;
    return true;
    /********** End **********/
}
T SL_DelAt(SeqList* slist, int i)
// 删除顺序表plist的第i号结点
// i的有效范围应在[0,plist->len)内，否则会产生异常或错误。
// 返回被删除的数据元素的值。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
     if (i<0 || i>=slist->len) {
        printf("SL_DelAt(): location error!\n");
        SL_Free(slist);
        exit(0);
    }
    T res=slist->data[i];
    for (int j=i; j<slist->len-1; j++) {
        slist->data[j] = slist->data[j+1];
    }
    slist->len--;
    return res;
    /********** End **********/
}
int SL_FindValue(SeqList* slist, T x)
// 在顺序表表中查找第一个值为x的结点，返回结点的编号
// 返回值大于等于0时表示找到值为x的结点的编号，-1表示没有找到
{
    int i=0;
    while(i<slist->len && slist->data[i]!=x) i++;
    if (i<slist->len) return i;
    else return -1;
}
int SL_DelValue(SeqList* slist, T x)
// 删除第一个值为x的结点,
// 存在值为x的结点则返回结点编号, 未找到返回－1
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int i=SL_FindValue(slist, x);
    if (i>=0) SL_DelAt(slist, i);
    return i;
    /********** End **********/
}
void SL_Print(SeqList* slist)
// 打印整个顺序表
{
    if (slist->len==0) {
        printf("The slist is empty.\n");        
        return;
    }
    //printf("The slist contains: ");
    for (int i=0; i<slist->len; i++) {
        printf("%d  ", slist->data[i]);
    }
    printf("\n");    
    
}

在这里插入图片描述

第2关：实现一个链接存储的线性表

编程要求
本关任务是实现 step2/LinkList.cpp中的LL_InsAfter操作函数，以实现线性表数据插入功能。具体要求如下：

在线性表的当前位置之后插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true；

输入输出格式请参见后续测试样例。

注意：本关必读中提及的其他操作函数已经由平台实现，你在实现操作函数LL_InsAfter时，在函数体内可调用其他操作函数。

/*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 单链表实现文件
#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"
// 1）
LinkList* LL_Create()
// 创建一个链接存储的线性表，初始为空表，返回llist指针。
{
    LinkList* llist=(LinkList*)malloc(sizeof(LinkList));
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
    return llist;
}
// 2）    
void LL_Free(LinkList* llist)
// 释放链表的结点，然后释放llist所指向的结构。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    free(llist);
}
// 3）    
void LL_MakeEmpty(LinkList* llist)
// 将当前线性表变为一个空表，因此需要释放所有结点。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
}
// 4）    
int LL_Length(LinkList* llist)
// 返回线性表的当前长度。
{
    return llist->len;
}
// 5）    
bool LL_IsEmpty(LinkList* llist)
// 若当前线性表是空表，则返回true，否则返回TRUE。
{
    return llist->len==0;
}
// 6）  
bool LL_SetPosition(LinkList* llist, int i)
// 设置线性表的当前位置为i号位置。
// 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
// 假设线性表当前长度为len，那么i的有效范围为[0,len]。
{    
    int k;
    /* 若链表为空，则返回*/
    if (llist->len==0) return false;
    /*若位置越界*/
    if( i < 0 || i > llist->len)
    {    printf("LL_SetPosition(): position error");
        return false;
    }
    /* 寻找对应结点*/
    llist->curr = llist->front;
    llist->pre = NULL;
    llist->position = 0;
    for ( k = 0; k < i; k++)    {
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = (llist->curr)->next;
    }
    
    /* 返回当前结点位置*/
    return true;
}
// 7)    
int LL_GetPosition(LinkList* llist)
// 获取线性表的当前位置结点的编号。
{
    return llist->position;
}
// 8）    
bool LL_NextPosition(LinkList* llist)
// 设置线性表的当前位置的下一个位置为当前位置。
// 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。
{
    if (llist->position >= 0 && llist->position < llist->len)
    /* 若当前结点存在，则将其后继结点设置为当前结点*/
    {
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = llist->curr->next;
        return true;
    }
    else 
        return false;
}
// 9）    
T LL_GetAt(LinkList* llist)
// 返回线性表的当前位置的数据元素的值。
{
    if(llist->curr==NULL)
    {
        printf("LL_GetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
    }
    return llist->curr->data;
}
// 10）    
void LL_SetAt(LinkList* llist, T x)
// 将线性表的当前位置的数据元素的值修改为x。
{
    if(llist->curr==NULL)
    {
        printf("LL_SetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
    }
    llist->curr->data=x;
}
// 11）    
bool LL_InsAt(LinkList* llist, T x)
// 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
// 若插入失败，返回false，否则返回true。
{    
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;
    newNode->data=x;
    if (llist->len==0){
        /* 在空表中插入*/
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
    }
    //当前位置为表头。
    else if (llist->pre==NULL)
    {
        /* 在表头结点处插入*/
        newNode->next = llist->front;
        llist->front = newNode;
    }
    else {  
        /* 在链表的中间位置或表尾后的位置插入*/
        newNode->next = llist->curr;
        llist->pre->next=newNode;
    }
    //插入在表尾后。
    if (llist->pre==llist->rear)
        llist->rear=newNode;
    /* 增加链表的大小*/
    llist->len++;
    /* 新插入的结点为当前结点*/
    llist->curr = newNode;
    return true;
}
// 12）    
bool LL_InsAfter(LinkList* llist, T x)
// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。
{
    // 请在Begin-End之间补充代码，实现结点插入。
    /********** Begin *********/
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;
    newNode->data=x;
    if (llist->len==0)    {
        /* 在空表中插入*/
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
    }
    else if (llist->curr == llist->rear || llist->curr == NULL)    {
        /* 在尾结点后插入*/
        newNode->next = NULL;
        llist->rear->next=newNode;
        llist->pre=llist->rear;
        llist->rear=newNode;
        llist->position=llist->len;
    }
    else{
        /* 在中间位置插入*/
        newNode->next = llist->curr->next;
        llist->curr->next=newNode;
        llist->pre=llist->curr;
        llist->position ++;
    }
    /* 增加链表的大小*/
    llist->len ++;
    /* 新插入的结点为当前结点*/
    llist->curr = newNode;
    return true;
    /********** End **********/
}
// 13）    
bool LL_DelAt(LinkList* llist)
// 删除线性表的当前位置的数据元素结点。
// 若删除失败（为空表，或当前位置为尾结点之后），则返回false，否则返回true。
{    
    LinkNode *oldNode;
    /* 若表为空或已到表尾之后，则给出错误提示并返回*/
    if (llist->curr==NULL)
    {    
        printf("LL_DelAt(): delete a node that does not exist.\n");
        return false;
    }
    oldNode=llist->curr;
    /* 删除的是表头结点*/
    if (llist->pre==NULL)
    {    
        llist->front = oldNode->next;
    }
    /* 删除的是表中或表尾结点*/
    else if(llist->curr!=NULL){
        llist->pre->next = oldNode->next;
    }
    if (oldNode == llist->rear)    {
        /* 删除的是表尾结点，则修改表尾指针和当前结点位置值*/
        llist->rear = llist->pre;
    }
    /* 后继结点作为新的当前结点*/
    llist->curr = oldNode->next;
    /* 释放原当前结点*/
    free(oldNode);
    /* 链表大小减*/
    llist->len --;
    return true;
}
// 14）    
bool LL_DelAfter(LinkList* llist)
// 删除线性表的当前位置的后面那个数据元素。
// 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。
{
    LinkNode *oldNode;
    /* 若表为空或已到表尾，则给出错误提示并返回*/
    if (llist->curr==NULL || llist->curr== llist->rear)
    {
        printf("LL_DelAfter():  delete a node that does not exist.\n");
        return false;
    }
    /* 保存被删除结点的指针并从链表中删除该结点*/
    oldNode = llist->curr->next;
    llist->curr->next=oldNode->next;
    
    if (oldNode == llist->rear)
        /* 删除的是表尾结点*/
        llist->rear = llist->curr;
    /* 释放被删除结点*/
    free(oldNode);
    /* 链表大小减*/
    llist->len --;
    return true;
}
// 15）    
int LL_FindValue(LinkList* llist, T x)
// 找到线性表中第一个值为x的数据元素的编号。
// 返回值-1表示没有找到，返回值>=0表示编号。
{
    LinkNode* p=llist->front;
    int idx=0;
    while(p!=NULL && p->data!=x) {
        idx++;
        p = p->next;
    }
    if (idx>=llist->len) return -1;
    else return idx;
}
// 16）    
int LL_DelValue(LinkList* llist, T x)
// 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。
{
    int idx=LL_FindValue(llist, x);
    if (idx<0) return -1;
    LL_SetPosition(llist, idx);
    LL_DelAt(llist);
    return idx;
}
// 17）    
void LL_Print(LinkList* llist)
// 打印整个线性表。
{
    LinkNode* node=llist->front;
    while (node) {
        printf("%d ", node->data);
        node=node->next;
    }
    printf("\n");
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/304017.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

[答疑]领域特定语言DSL属于伪创新吗（谷爱凌）

[答疑]领域特定语言DSL属于伪创新吗（谷爱凌）

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 Zeyu 2024-1-4 9:20 马丁福勒的领域特定语言DSL是否有阅读的价值&#xff1f;属于伪创新吗&#xff1f; UMLChina潘加宇 这个问题就有点伪创新 &#xff0c;让人误以为DSL是Fowler发…
阅读更多...
本地部署Canal笔记-实现MySQL与ElasticSearch7数据同步

本地部署Canal笔记-实现MySQL与ElasticSearch7数据同步

背景 本地搭建canal实现mysql数据到es的简单的数据同步&#xff0c;仅供学习参考 建议首先熟悉一下canal同步方式&#xff1a;https://github.com/alibaba/canal/wiki 前提条件 本地搭建MySQL数据库本地搭建ElasticSearch本地搭建canal-server本地搭建canal-adapter 操作步骤…
阅读更多...
shp与数据库（插入数据）

shp与数据库（插入数据）

前言 正文 geopandas与shp文件创建表和录入数据 解释一下上面的代码 查询cd2表的geometry字段 查看一下表 前一篇博客的冲突 问题的解决 POLYGON与MUTLIPOLYGON的说明 解决问题的代码 修改表的创建 shapefile和sqlalchemy插入数据 数据库查询 最后 前言 前一篇讲解…
阅读更多...
与AI合作 -- 写一个modern c++单例工厂

与AI合作 -- 写一个modern c++单例工厂

目录 前言 提问 bard给出的答案 AI答案的问题 要求bard改进 人类智能 AI VS 人类 前言 通过本文读者可以学到modern C单例模式工厂模式的混合体&#xff0c;同时也能看到&#xff1a;如今AI发展到了怎样的智能程度&#xff1f;怎样让AI帮助我们快速完成实现头脑中的想法&…
阅读更多...
【hcie-cloud】【17】华为云Stack灾备服务介绍【灾备方案概述、备份解决方案介绍】【上】

【hcie-cloud】【17】华为云Stack灾备服务介绍【灾备方案概述、备份解决方案介绍】【上】

文章目录 前言灾备方案概述灾备的定义灾备的重要性故障和灾难对业务连续性带来的挑战灾备系统的衡量指标RTO与RPO分析 灾备等级标准数据中心容灾解决方案全景图云灾备服务总结架构华为云Stack灾备服务总览 备份解决方案介绍云备份服务介绍备份服务架构介绍云备份服务组件功能介…
阅读更多...
界面原型设计工具有哪些？看看这9个

界面原型设计工具有哪些？看看这9个

界面原型设计是现代设计师必备的技能之一。在设计数字产品或应用程序时&#xff0c;界面原型是将概念转化为具体可交互界面的重要步骤。对于新手小白来说&#xff0c;选择一款易于上手且功能强大的界面原型设计工具至关重要。本文将介绍 9 个常用的界面原型设计工具&#xff0c…
阅读更多...
计算机体系结构动态调度（计分板及Tomasulo）学习记录

计算机体系结构动态调度（计分板及Tomasulo）学习记录

1.动态调度核心思想&#xff1a;允许就绪指令越过前方停顿指令&#xff0c;提前进入运行&#xff08;乱序执行&#xff09; 就绪指令指不存在资源冲突、操作数已就绪的指令&#xff0c;例如&#xff0c;计分板算法使用计分板来实现&#xff0c;Tomasulo使用保留站来实现&#…
阅读更多...
苹果电脑交互式原型设计软件Axure RP 9 mac特色介绍

苹果电脑交互式原型设计软件Axure RP 9 mac特色介绍

Axure RP 9 for Mac是一款交互式原型设计软件&#xff0c;使用axure rp9以最佳的方式展示您的作品&#xff0c;优化现代浏览器并为现代工作流程设计。同时确保您的解决方案正确完整地构建。Axure RP 9 for Mac为您整理笔记&#xff0c;将其分配给UI元素&#xff0c;并合并屏幕注…
阅读更多...
swing快速入门（三十九）进度对话框

swing快速入门（三十九）进度对话框

&#x1f381;注释很详细&#xff0c;直接上代码 上一篇 &#x1f9e7;新增内容 &#x1f9e8;1.模拟耗时操作 &#x1f9e8;2.使用计时器更新进度对话框 &#x1f380;源码&#xff1a; package swing31_40;import javax.swing.*; import java.awt.event.ActionEvent; import …
阅读更多...
【debug】为什么ansible中使用command出错

【debug】为什么ansible中使用command出错

碎碎念 在使用ansible执行command的时候&#xff0c;遇到执行会出错的command 比如执行source打算读取环境变量的时候 错误提示为&#xff1a; 没有那个文件或目录:source 一开始以为是错误提示有问题&#xff0c;一直在testrc的路径上检查&#xff0c;但是同样一行命令使用…
阅读更多...
C++八股学习心得.8

C++八股学习心得.8

1.const知道吗&#xff1f;解释其作用 const 修饰类的成员变量&#xff0c;表示成员常量&#xff0c;不能被修改。 const修饰函数承诺在本函数内部不会修改类内的数据成员&#xff0c;不会调用其它非 const 成员函数。 如果 const 构成函数重载&#xff0c;const 对象只能调…
阅读更多...
聊聊 Java 集合框架中的 ArrayList

聊聊 Java 集合框架中的 ArrayList

其实 Java 集合框架也叫做容器&#xff0c;主要由两大接口派生而来&#xff0c;一个是 collection,主要存放对象的集合。另外一个是Map, 存储着键值对&#xff08;两个对象&#xff09;的映射表。 下面就来说说 List接口&#xff0c;List存储的元素是有序、可重复的。其下有三个…
阅读更多...
配置git服务器

配置git服务器

第一步&#xff1a; jdk环境配置 &#xff08;1&#xff09;搜索【高级系统设置】&#xff0c;选择【高级】选项卡&#xff0c;点【环境变量】 &#xff08;2&#xff09;在【系统变量】里面&#xff0c;点击【新建】 &#xff08;3&#xff09;添加JAVA_HOME环境变量JAVA_HO…
阅读更多...
展台搭建的基本要求

展台搭建的基本要求

一、选址及总平面布置 展厅人流量大&#xff0c;对选址和总平面布置的要求如下:展厅选址应位于市内或郊区交通便利的区域。大型展览馆应有足够的群众活动广场和停车面积 &#xff0c;并应有室外陈列场地。室外场地要考虑环境的绿化和美化。各功能分区之间联系方便又互不干扰。建…
阅读更多...
实现LCM在docker之间的通信

实现LCM在docker之间的通信

目录 1.docker容器互联 新建网络 连接容器 2.设置环境变量 3.在两个docker之间实现通信 1.docker容器互联 新建网络 $ docker network create -d bridge test-net 连接容器 运行一个容器并连接到新建的 test-net 网络: $ docker run -itd --name lcm_1 --network tes…
阅读更多...
极智项目 | 实战Paddle戴口罩检测

极智项目 | 实战Paddle戴口罩检测

欢迎关注我的公众号 [极智视界]&#xff0c;获取我的更多项目分享 大家好&#xff0c;我是极智视界&#xff0c;本文来介绍 实战 Paddle 戴口罩检测项目。 本文介绍的 实战 Paddle 戴口罩检测项目&#xff0c;提供完整的可以一键执行的项目工程源码&#xff0c;获取方式有两个…
阅读更多...
AI红娘开启约会新时代；网易云音乐Agent实践探索；微软生成式AI课程要点笔记；ComfyUI新手教程；图解RAG进阶技术 | ShowMeAI日报

AI红娘开启约会新时代；网易云音乐Agent实践探索；微软生成式AI课程要点笔记；ComfyUI新手教程；图解RAG进阶技术 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f440; Perplexity 官宣 7360 万美元B轮融资&#xff0c;打造世界上最快最准确的答案平台 https://blog.perplexity.ai/blog/perplexity-rais…
阅读更多...
yyds，4 个 Pandas 必备神器！

yyds，4 个 Pandas 必备神器！

Pandas是我们日常处理表格数据最常用的包&#xff0c;但是对于数据分析来说&#xff0c;Pandas的DataFrame还不够直观。 今天我们将介绍4个和Pandas相关的Python包&#xff0c;可以将Pandas的DataFrame转换交互式表格&#xff0c;让我们可以直接在上面进行数据分析的操作。 P…
阅读更多...
天洑软件与常州大学成立电子信息专业学位硕士研究生联合培养基地

天洑软件与常州大学成立电子信息专业学位硕士研究生联合培养基地

2023年12月27日&#xff0c;天洑软件与常州大学微电子与控制工程学院成立电子信息专业学位硕士研究生联合培养基地&#xff0c;授牌及企业导师聘任仪式于常州大学西太湖校区隆重举办。天洑软件前瞻技术研究院院长张儒受邀与会。 开幕式上&#xff0c;微电子与控制工程学院党委书…
阅读更多...
NUXT3学习笔记

NUXT3学习笔记

1.邂逅SPA、SSR 1.1 单页面应用程序 单页应用程序 (SPA) 全称是&#xff1a;Single-page application&#xff0c;SPA应用是在客户端呈现的&#xff08;术语称&#xff1a;CSR&#xff08;Client Side Render&#xff09;&#xff09; SPA的优点 只需加载一次 SPA应用程序只需…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站