数据结构与算法-头歌【1】顺序线性表--课上练

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

 本意是整理和复习,理解不深或者有错误的评论区提出即可。

只有第一关的代码里面有结构体的定义,其余我只放了功能函数。

初始代码

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

/*此处是顺序线性表数据结构定义*/
typedef int DataType;
struct seqList
{//有3个数据成员
  int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM   
  int curNum;//用于存放顺序线性表中数据元素的个数  整型  curNum
  DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址  
};

typedef struct seqList *PseqList;
//第一关
PseqList createNullList_seq(int m)
{//此处填写代码,创建一个空的顺序线性表,能存放的最大元素个数为 m
 //若m=0,则返回NULL 
    
}

//第二关
int isFullList_seq(PseqList L)
{
  //判断顺序线性表是否已满,若已满,返回值为1,否则返回值为0
 
 

}

int insertP_seq(PseqList L , int p ,int x)
{// 在线性表L中下标为p的位置插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
   //如果线性表满了, 还需输"list is full"的提示
  //如果插入位置非法,需输出提示"position is illegel" 
    
}

int insertPre_seq(PseqList L , int p ,int x)
{
 // 在线性表L中下标为p的位置的前面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可    
    
    
}

int insertPost_seq(PseqList L , int p ,int x)
{
 // 在线性表L中下标为p的位置的后面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可    
    
    
}

void printList_seq(PseqList L)
{//逐个输出线性表的元素,相邻的两个数据元素之间以一个空格为分隔符隔开

}

//第三关
int destroyList_seq(PseqList L)
{
    //返回值为销毁的线性表中现有数据元素的个数,若待销毁的线性表不存在,则返回0
    
}

//第四关
int locate_seq(PseqList L,int x)
{//在顺序表L中查找给定值x首次出现的位置,若不存在给定值,则返回-1
    
}

DataType locatePos_seq(PseqList L,int pos)
{// 在顺序表L中查找指定位置pos处的数据元素,若位置非法,则返回第0个数据元素
    
}

//第五关
int deletePos_seq(PseqList L,int pos)
{//在顺序表L中删除与下标pos处的数据元素,若pos非法,则返回-1;否则返回1
    
}

int delete_seq(PseqList L,int x)
{//在顺序表L中删除与参数x值相同的数据元素,返回删除数据元素的个数
  //可以使用之前已完成的操作
  
  
}

//第六关
void replace_seq(PseqList L,int x,int y)
{//将顺序表L中值为x的数据元素替换为y


}

void delDuplicate_seq(PseqList L)
{//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
  //使用常规删除即可,已修改测试用例

}

1.创建空顺序线性表

题目

任务描述

本关要求按照完成顺序表数据类型定义,并初始化一个顺序线性表。

编程要求

顺序线性表数据结构定义如下:

typedef int DataType; 
struct seqList { 
    int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM 
    int curNum;//用于存放顺序线性表中数据元素的个数 整型 curNum 
    DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址
};

本关的编程任务是补全文件中createNullList_seq函数,以实现初始化一个空的顺序线性表的要求。

开始你的任务吧,祝你成功!

测试

输入:4

输出:success to create a seqlist of 4 elements,current item 0

输入:0

输出:fail to create

输入:6

输出:success to create a seqlist of 6 elements,current item 0

已通过代码

功能函数

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

/*此处是顺序线性表数据结构定义*/
typedef int DataType;
struct seqList
{            //有3个数据成员
  int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM   
  int curNum;//用于存放顺序线性表中数据元素的个数  整型  curNum
  DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址  
};

typedef struct seqList *PseqList;
//第一关
PseqList createNullList_seq(int m)
{//此处填写代码,创建一个空的顺序线性表,能存放的最大元素个数为 m
 //若m=0,则返回NULL 
 if(m == 0){
  return NULL;
  }
 else{
    PseqList palist = (PseqList)malloc(sizeof(struct seqList));
    if(palist != NULL){//判断创建是否成功
        palist->element = (DataType *)malloc(sizeof(DataType)*m);//创建m个元素的空间
        if(palist->element){//判断创建是否成功
          palist->MAXNUM = m;
          palist->curNum = 0;
          return palist;
        }
        else
          free(palist);  //如果创建元素空间失败则要释放线性表空间
          //指针的空间释放之后,指针的值没有改变
    }
  }    
}

 main函数

int main(void)
{
   int m;
   scanf("%d",&m);
   PseqList head = createNullList_seq(m);
   if(head == NULL)
       printf("fail to create");
    else
       printf("success to create a seqlist of %d elements,current item %d",m,head->curNum); 
}

2.顺序表插入

题目

任务描述

本关任务: 你需要实现不同的插入操作: 在顺序线性表中下标为p位置、p位置之前、p位置之后插入数据元素

编程要求

为了实现线性表插入操作,你需要实现判断线性表是否为满的判断函数,另外你需要根据提示,在右侧编辑器补充代码,完成操作insertP_seq,insertPre_seq,insertPost_seq三个插入函数,以及遍历输出线性表数据元素的操作printList_seq。具体说明见操作注释。


开始你的任务吧,祝你成功!

测试

输入:5 1 2 3 4

输出:position is illegel4 1 4 3 2

输入:2 1 4

输出:position is illegel1 4

输入:6 1 2 3 4 5 6

输出:position is illegellist is fulllist is full5 1 5 4 2 3

已通过代码块

功能函数

//第二关
int isFullList_seq(PseqList L)
{
  //判断顺序线性表是否已满,若已满,返回值为1,否则返回值为0
   return (L->curNum >= L->MAXNUM);
}


int insertP_seq(PseqList L , int p ,int x)
{// 在线性表L中下标为p的位置插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
  //如果线性表满了, 还需输"list is full"的提示
  //如果插入位置非法,需输出提示"position is illegel" 

  int q;//记录p的位置
  if(isFullList_seq(L)){//线性表已满
    printf("list is full");
    return 0;
  }
  else if(p < 0 || p > L->curNum){
    //输入非法
      printf("position is illegel");
      return 0;
  }
  else{
    for(q = L->curNum - 1; q >= p; q--){//q以及q位置以后的元素后移一位    
      L->element[q+1] = L->element[q];
    }
    L->element[p] = x;
    L->curNum ++;
    return 1;
  }    
}

int insertPre_seq(PseqList L , int p ,int x)
{
 // 在线性表L中下标为p的位置的前面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可    
    return insertP_seq(L , p-1 , x);   
}

int insertPost_seq(PseqList L , int p ,int x)
{
 // 在线性表L中下标为p的位置的后面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可    
    return insertP_seq(L , p+1 , x);   
}

void printList_seq(PseqList L)
{//逐个输出线性表的元素,相邻的两个数据元素之间以一个空格为分隔符隔开
  for(int i=0; i < L->curNum; i++){
    printf("%d ", L->element[i]);
  }

}

main函数 

int main(void)
{
     int m ,x;
     scanf("%d",&m);
     PseqList head = createNullList_seq(m);
     for(int i=0;i<m/2;i++)
     {
        scanf("%d",&x);
        insertP_seq(head,i,x);  
         
      }
     for(int i=0;i<m/2;i++)
        {
        scanf("%d",&x);
        insertPre_seq(head,i,x);  
        insertPost_seq(head,i,x);     
        }  
    printList_seq(head);
}

3.销毁线性表

题目

任务描述

本关任务:销毁线性表的实质时实现动态分配的线性表空间回收。

相关知识

使用malloc函数分配的内存空间应该在程序退出时使用free将空间回收还给操作系统。 由于顺序线性表创建时使用了malloc为线性表结构、线性表数据元素动态分配了存储空间,我们应使用free将相应空间回收。

编程要求

根据提示,在右侧编辑器补充代码,实现销毁线性表的功能。


开始你的任务吧,祝你成功!

测试

输入:4 1 3 5 7

输出:4

输入:0

输出:0

输入:5 1 2 3 4 5

输出:5

已通过代码块

功能函数

//第三关
int destroyList_seq(PseqList L)
{
    //返回值为销毁的线性表中现有数据元素的个数,若待销毁的线性表不存在,则返回0
    if(L == NULL)
      return 0;
    else{
      free(L->element);
      return L->curNum;
    }
}

主函数

int main(void)
{
     int m ,x;
     scanf("%d",&m);
     PseqList head = createNullList_seq(m);
     for(int i=0;i<m;i++)
     {
        scanf("%d",&x);
        insertP_seq(head,i,x);  
      }
   printf("%d", destroyList_seq(head));
}

4.查找

题目

任务描述

本关任务: 1.在顺序线性表中查找第一个值为x的元素下标。 2.在顺序线性表中查找某个位置pos处的数据元素


开始你的任务吧,祝你成功!

测试

输入:8 12 3 23 -12 89 6 67 123 6

输出:

67

5

输入:4 123 4 45 23 10

输出:

123

-1

已通过代码块

功能函数

//第四关
int locate_seq(PseqList L,int x)
{//在顺序表L中查找给定值x首次出现的位置,若不存在给定值,则返回-1
  for(int i = 0; i < L->curNum; i++){
    if(x == L->element[i])
      return i;
  }
  return -1;
}

DataType locatePos_seq(PseqList L,int pos)
{// 在顺序表L中查找指定位置pos处的数据元素,若位置非法,则返回第0个数据元素

  //位置非法
  if(pos < 0 || pos > L->curNum)
      return L->element[0];
  else
      return L->element[pos]; 
}

主函数

int main(void)
{
     int m ,x;
     scanf("%d",&m);
     PseqList head = createNullList_seq(m);
     for(int i=0;i<m;i++)
     {
        scanf("%d",&x);
        insertP_seq(head,i,x);  
      }
    scanf("%d",&m);
    printf("%d\n",locatePos_seq(head,m));
    printf("%d\n",locate_seq(head,m));
    destroyList_seq(head);
    
}

5.删除

题目

任务描述

本关任务: (1)在顺序表L中删除下标pos处的数据元素 (2)在顺序表L中删除与参数x值相同的数据元素

编程要求

根据提示,在右侧编辑器补充第五关的代码。


开始你的任务吧,祝你成功!

测试

输入:6 12 34 56 3 4 12 3 12

输出:

1

2

34 56 4

已通过代码块

功能函数

//第五关
int deletePos_seq(PseqList L,int pos)
{//在顺序表L中删除下标pos处的数据元素,若pos非法,则返回-1;否则返回1
  //pos非法 
  if(pos < 0 || pos > L->curNum - 1)
    return -1;
  else{
    for(int i = pos; i < L->curNum - 1 ; i++)
      L->element[i] = L->element[i+1];//pos位置后面的元素均前移一位
    L->curNum--;
    return 1;
  }
}

int delete_seq(PseqList L,int x)
{//在顺序表L中删除与参数x值相同的数据元素,返回删除数据元素的个数
  //可以使用之前已完成的操作
  
  int n = 0;//记录删除的元素个数
  int p;
  for(p = 0; p < L->curNum; p++){
    if(L->element[p] == x){
      deletePos_seq(L, p);
      n++;
    }
  }
  return n;
}

主函数

int main(void)
{
     int m ,x;
     scanf("%d",&m);
     PseqList head = createNullList_seq(m);
     for(int i=0;i<m;i++)
     {
        scanf("%d",&x);
        insertP_seq(head,i,x);  
      }
    scanf("%d",&m);
    printf("%d\n",deletePos_seq(head,m));
    scanf("%d",&m);
   printf("%d\n",delete_seq(head,m));
    printList_seq(head);
    destroyList_seq(head);
    
}

6.顺序表应用

题目

任务描述

本关任务: (1)使用将顺序表L中值为x的数据元素替换为y; (2)此处假设线性表中的元素用于表示集合,不考虑线性表中元素的位置,移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

编程要求

根据提示,在右侧编辑器补充代码,完成第六关的两个函数。


开始你的任务吧,祝你成功!

测试

输入:5 1 5 -1 5 9 5 1

输出:-1 9

输入:6 12 4 3 3 3 3 3 12

输出:4

已通过代码块

功能函数

//第六关
void replace_seq(PseqList L,int x,int y)
{//将顺序表L中值为x的数据元素替换为y
  for(int i = 0; i < L->curNum; i++)
    if(L->element[i] == x)
      L->element[i] = y;
}

void delDuplicate_seq(PseqList L)
{//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
  //使用常规删除即可,已修改测试用例

  int t, flag = 0;
  //t:记录最开始用来比较的下标
  //flag:记录有没有与他重复的元素
  for(int i = 0; i < L->curNum; i++){
    t = i;
    for(int j = i + 1; j < L->curNum; j++){
      if(L->element[i] == L->element[j])
        deletePos_seq(L, j);       //删除重复元素   
        flag = 1;
    }
    if(flag)
      deletePos_seq(L, t);         //如果有重复的元素就把原来用来比较的元素也删掉
    flag = 0;                      //flag清零
  }
}

主函数文章来源地址https://www.toymoban.com/news/detail-424457.html

int main(void)
{
     int m ,x;
     scanf("%d",&m);
     PseqList head = createNullList_seq(m);
     for(int i=0;i<m;i++)
     {
        scanf("%d",&x);
        insertP_seq(head,i,x);  
      }
    scanf("%d%d",&m,&x);
    replace_seq(head,m,x);
    delDuplicate_seq(head);
    printList_seq(head);
    destroyList_seq(head);
    
}

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

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

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

相关文章

  • 【数据结构】线性结构 之 顺序表

    🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 顺序表概念及结构 静态代码实现: 动态代码实现: SeqList.h文件 SeqList.c文件 test.c文件 本章节博主将会带领大家了解数据结构的 线性结构的顺序表 。 提到线性

    2024年02月06日
    浏览(44)
  • 【玩转408数据结构】线性表——线性表的顺序表示(顺序表)

            通过前文,我们了解到线性表是具有相同数据类型的有限个数据元素序列;并且,线性表只是一种逻辑结构,其不同存储形式所展现出的也略有不同,那么今天我们来了解一下线性表的顺序存储——顺序表。         顺序表指的是将 逻辑上相邻的元素 存储在 物理位

    2024年02月19日
    浏览(52)
  • 数据结构-线性表-顺序表

    线性表的定义:由n(n=0)个数据特性相同的元素构成的有限序列,称为线性表。当n=0时称之为空表。 因为构件线性表时元素数组已经使用静态分配,所以在此只需要对线性表的长度执行初始化即可。 获取数据需要参数: sqList:需要给定一个线性表从而获取数据,因为只是拿值

    2024年02月08日
    浏览(48)
  • 数据结构 · 线性表 | 顺序表

    啊我摔倒了..有没有人扶我起来学习.... 👱 个人主页: 《 C G o d 的 个 人 主 页 》 color{Darkorange}{《CGod的个人主页》} 《 C G o d 的 个 人 主 页 》 交个朋友叭~ 💒 个人社区: 《 编 程 成 神 技 术 交 流 社 区 》 color{Darkorange}{《编程成神技术交流社区》} 《 编 程 成 神 技 术

    2024年02月02日
    浏览(49)
  • 数据结构——线性表①(顺序表)

    线性表是一种数据结构,它是由n个具有 相同数据类型 的数据元素a1,a2,…,an组成的 有限序列 。 其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。 线性表可以用 顺序存储结构 或 链式存储结构

    2024年02月06日
    浏览(53)
  • 数据结构:线性表之-顺序表

    目录 1.线性表概念 1.1 什么是顺序列表 1.2 线性表 2.顺序表实现 将有以下功能: 详细过程 顺序表的动态存储 顺序表初始化 尾插 扩容 头插 更改后的尾插 尾删 头删 打印 释放内存 优化顺序表 (任意位置插入删除) 优化后的头插尾插 优化后的头删尾删 查找和删除 进行装饰(菜单

    2024年02月10日
    浏览(51)
  • 数据结构---顺序表示的线性表

             数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简言之,数据

    2024年02月16日
    浏览(54)
  • 数据结构: 线性表(顺序表实现)

    线性表(linear list)是 n 个具有相同特性的数据元素的有序序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表: 顺序表,链表,栈,队列,字符串… 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删

    2024年02月14日
    浏览(49)
  • C/C++数据结构---顺序表---线性存储结构

    个人主页: 仍有未知等待探索_小项目,洛谷刷题,数据结构-CSDN博客 专题分栏---数据结构: 数据结构_仍有未知等待探索的博客-CSDN博客 目录 一、知识储备 二、引例  三、顺序表 第一步,先创建一个顺序表类型 第二步,定义和初始化顺序表    第三步,顺序表的基本操作

    2024年02月08日
    浏览(41)
  • 数据结构(二)----线性表(顺序表,链表)

    目录 1.线性表的概念 2.线性表的基本操作 3.存储线性表的方式 (1)顺序表 •顺序表的概念 •顺序表的实现 静态分配: 动态分配: 顺序表的插入: 顺序表的删除: 顺序表的按位查找: 顺序表的按值查找: 顺序表的特点: (2)单链表 •单链表的实现 不带头结点的单链表

    2024年04月16日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包