数据结构与算法 - 线性表

这篇具有很好参考价值的文章主要介绍了数据结构与算法 - 线性表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


第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");    
    
}

数据结构与算法 - 线性表,c语言

第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");
}

数据结构与算法 - 线性表,c语言文章来源地址https://www.toymoban.com/news/detail-791187.html


到了这里,关于数据结构与算法 - 线性表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法_01_线性表】线性表

    定义 ● 线性表 具有相同数据类型**(同类型)**的n个数据元素有限序列 ● 三方面 ● 定义 逻辑结构 ● 相同数据类型 ● 每个数据元素所占的空间相同 ● 有限 ● 有限个元素 ● 序列 ● 是有次序的 ● 基本操作 操作— 基本操作 运算 ● 创建线性表【initList(L)】 ● 初始化线

    2024年02月11日
    浏览(35)
  • 数据结构与算法【02】—线性表

    CSDN系列专栏:数据结构与算法专栏 针对以前写的数据结构与算法系列重写(针对文字描述、图片、错误修复),改动会比较大,一直到更新完为止 通过前面数据结构与算法基础知识我们知道了数据结构的一些概念和重要性,那么本章总结下线性表相关的内容。当然,我用自己

    2024年02月05日
    浏览(48)
  • HNU数据结构与算法分析-作业2-线性结构

      1. (简答题) 4.1 假设一个线性表包含下列元素: |2,23,15,5,9 使用Shaffer编写的教材《数据结构与算法分析》的List ADT编写一些C++语句,删除值为15的元素。 (要求:采用C或C++语言描述算法) 4.6 使用Shaffer编写的教材《数据结构与算法分析》的LList类,给LList类的实现添加一个成

    2024年02月05日
    浏览(52)
  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(51)
  • C语言数据结构(2)——线性表其一(顺序表)

    欢迎来到博主的新专栏——C语言数据结构 博主ID:代码小豪 再开始这篇文章之前,我们假设要对10个数据进行操作。这十个数据全都被声明成10个变量 如果我们准备为这些数据增加功能,将他们进行赋值,打印,交换等。就会发现一个特别棘手的问题,这些程序写起来太繁杂

    2024年01月19日
    浏览(39)
  • 数据结构--》从线性表说起,掌握常用基础算法

    目录 初识线性表 线性表的基本操作 顺序表的定义 顺序表的基本操作 单链表的定义 单链表的基本操作  双链表的介绍 循环链表的介绍 静态链表的介绍 线性表是具有 相同 数据类型的 n (n0) 个数据元素的 有限序列 ,其中n为 表长 ,当n=0时线性表是一个 空表 。若用L命名线性

    2024年02月09日
    浏览(47)
  • C语言数据结构——线性表之栈和队列

    为什么会定义栈和队列这两种数据结构呢? 原因在于: 之所以会定义栈和队列这样的数据结构 是因为他们有两大特性 : 第一: 他们可以保存程序运行路径中各个点的信息,以便用于回溯操作或其他需要访问已经访问过的节点信息的操作。 比如: 栈用于解决迷宫问题,就

    2023年04月11日
    浏览(110)
  • 【Dev-c++】C语言数据结构实验——线性表

    实验一 线性表 一、实验目的     1、深刻理解线性结构的特点,以及在计算机内的两种存储结构。     2、熟练掌握线性表的顺序存储结构和链式存储结构,及其它们的基本操作,重点掌握查找、插入和删除等操作。 二、实验要求     1、认真阅读程序, 将未完成的代码补

    2024年02月07日
    浏览(39)
  • 数据结构与算法-头歌【1】顺序线性表--课上练

      本意是整理和复习,理解不深或者有错误的评论区提出即可。 只有第一关的代码里面有结构体的定义,其余我只放了功能函数。 任务描述 本关要求按照完成顺序表数据类型定义,并初始化一个顺序线性表。 编程要求 顺序线性表数据结构定义如下: 本关的编程任务是补全

    2023年04月25日
    浏览(41)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包