• 数据结构-顺序表及其应用

    第1关：顺序表的实现之查找功能

    任务描述

    本关任务：实现顺序表中数据的查找功能。

    相关知识

    为了完成本关任务，你需要掌握：1. 线性表，2. 顺序表。

    线性表

    线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间通过一对一首尾相接的方式连接起来。具体实现时，线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表（即：顺序表）实现方案：

    该方案将线性表存储在一片连续空间里，并通过elem和length两个属性元素，组织成为一个结构体：

    • elem: 给出线性表存储空间的起始地址
    • length: 当前线性表里的数据元素个数

    为了讨论简化，我们假设每个数据元素是一个整数:

     

    1. typedef int ElemType; // 数据元素的类型
     

    顺序表
     

    顺序表的类型定义如下：
     

     

    1. #define MAXSIZE 100 //最大长度
    2. typedef struct {
    3. ElemType *elem; //指向数据元素的起始地址
    4. int length; //线性表的当前长度
    5. }SqList;
     

    若定义：SqList L，则通过L就可对顺序表进行操作。
     

    对数据元素进行操作处理是一个数据结构的重要组成部分。顺序表涉及的主要操作如下：
     

    •  
      顺序表的初始化：构造一个最多可存储MAXSIZE个数据元素的顺序表，并将其初始状态设置为length=0，即为空表。该操作函数具体定义如下：
       
       
  
      1. void SL_Initiate(SqList &L)
    •  
      释放顺序表：释放L.elem所指向的用于存储数据元素的存储空间。该操作函数具体定义如下：
       
       
  
      1. void SL_Free(SqList &L)
    •  
      判断顺序表是否为空：若为空表，则返回true,否则返回false。该操作函数具体定义如下：
       
       
  
      1. bool SL_IsEmpty(SqList L)
    •  
      判断顺序表是否已满：若顺序表达到最大长度，则返回 true,否则返回false。该操作函数具体定义如下：
       
       
  
      1. bool SL_IsFull(SqList L)
    •  
      创建顺序表：输入n个数据元素，创建一个顺序表。该操作函数具体定义如下：
       
       
  
      1. void SL_Create(SqList &L,int n)
    •  
      输出顺序表： 输出整个顺序表。该操作函数具体定义如下：
       
       
  
      1. void SL_Print(SqList L)
    •  
      获取顺序表的第i个数据元素：获取顺序表的第i个数据元素L.elem[i-1]赋给e，i的有效范围[1,L.length]。该操作函数具体定义如下：
       
       
  
      1. void SL_GetAt(SqList L, int i, ElemType &e)
    •  
      查找顺序表中第一个值为x的数据元素的位置： 在顺序表中查找第一个值为x的元素，找到则返回该元素在表中的位置，否则返回0。该操作函数具体定义如下：
       
       
  
      1. int SL_FindValue(SqList L, ElemType x)
     

    编程要求
     

    在右侧编辑器中补充代码，完成SL_GetAt和SL_FindValue两个操作函数，以实现顺序表中数据的查找功能。具体要求如下：
     

    1. SL_GetAt: 获取顺序表的第i个数据元素L.elem[i-1]，i的有效范围[1,L.length]
    2. SL_FindValue: 在顺序表中查找第一个值为x的元素，找到则返回该元素在表中的位置，否则返回0。
     

    注意：在实现两个操作函数的函数体内可调用其他操作。
     

    测试说明
     

    可在右侧文件夹中查看step1/Main.cpp文件，以便与你的操作。
     

    平台会对你编写的代码进行测试：
     

    测试输入： 5 //输入数据元素的个数 8 9 12 33 45 //输入5个数据元素，创建顺序表 2 //获取第2个数据元素 33 //查找值为33的数据元素 预期输出： 9 //输出第2个数据元素的值 4 //输出值为33的数据元素在表中的位置
     

    开始你的任务吧，祝你成功！
     

    1. /*************************************************************
    2.     顺序表的实现之查找功能  实现文件
    3. **************************************************************/
    4.  
    5. #include <stdio.h>
    6. #include <stdlib.h>
    7. #include "Seqlist.h"
    8.  
    9. void SL_Initiate(SqList &L)
    10. // 顺序表的初始化，即构造一个空的顺序表
    11. {
    12. 	L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    13. 	L.length=0;
    14. }
    15.  
    16. void SL_Free(SqList &L)
    17. // 释放顺序表
    18. {
    19. 	free(L.elem);
    20. }
    21.  
    22. bool SL_IsEmpty(SqList L)
    23. // 判断顺序表是否空
    24. {
    25. 	return L.length==0;
    26. }
    27.  
    28. bool SL_IsFull(SqList L)
    29. // 判断顺序表是否满
    30. {
    31. 	return L.length==MAXSIZE;
    32. }
    33.  
    34. void SL_Create(SqList &L,int n)
    35. // 输入n个数据元素，创建一个顺序表L
    36. {
    37. 	int i;
    38. 	L.length=n;
    39. 	for(i=0; i<n; i++)
    40. 		scanf("%d", &L.elem[i]);		
    41. }
    42.  
    43. void SL_Print(SqList L)
    44. // 输出整个顺序表
    45. {
    46. 	if (L.length==0)
    47. 	{
    48. 		printf("The slist is empty.\n");		
    49. 		return;
    50. 	}
    51.  
    52. 	for (int i=0; i<L.length; i++)
    53. 		printf("%d  ", L.elem[i]);
    54. 	printf("\n");	
    55. }
    56.  
    57. void SL_GetAt(SqList L, int i, ElemType &e)
    58. // 获取顺序表L的第i个元素赋给e，i的有效范围[1,L.length]。
    59. {
    60. 	// 请在这里补充代码，完成本关任务
    61.     /********** Begin *********/
    62. 	e = L.elem[i-1];
    63.  
    64. 	/********** End **********/
    65. }
    66.  
    67. int SL_FindValue(SqList L, ElemType x)
    68. // 在顺序表L中查找第一个值为x的元素，找到则返回该元素在表中的位置，否则返回0。
    69. {
    70. 	// 请在这里补充代码，完成本关任务
    71.     /********** Begin *********/
    72. int i=0;
    73. 	for(i=0;i<L.length;i++){
    74. 		if (L.elem[i]==x)
    75. 			return i+1;	
    76. 	}
    77. 	return 0;
    78.  
    79. 	/********** End **********/
    80. }
    81.  
     

    第2关：顺序表的实现之增删功能
     

    任务描述
     

    本关任务：实现顺序表中数据的插入和删除功能。
     

    相关知识
     

    为了完成本关任务，你需要掌握：1. 顺序表的类型定义，2.顺序表涉及的主要操作。
     

    顺序表的类型定义
     

    定义如下：
     

     

    1. #define MAXSIZE 100 //最大长度
    2. typedef int ElemType; // 数据元素的类型
    3. typedef struct {
    4. ElemType *elem; //指向数据元素的起始地址
    5. int length; //线性表的当前长度
    6. }SqList;
     

    顺序表涉及的主要操作
     

    主要操作如下：
     

    •  
      顺序表的初始化
       
       
  
      1. void SL_Initiate(SqList &L)
    •  
      释放顺序表
       
       
  
      1. void SL_Free(SqList &L)
    •  
      判断顺序表是否为空
       
       
  
      1. bool SL_IsEmpty(SqList L)
    •  
      判断顺序表是否已满
       
       
  
      1. bool SL_IsFull(SqList L)
    •  
      创建顺序表
       
       
  
      1. void SL_Create(SqList &L,int n)
    •  
      输出顺序表
       
       
  
      1. void SL_Print(SqList L)
    •  
      获取顺序表的第i个数据元素
       
       
  
      1. void SL_GetAt(SqList L, int i, ElemType &e)
    •  
      查找顺序表中第一个值为x的数据元素的位置
       
       
  
      1. int SL_FindValue(SqList L, ElemType x)
    •  
      在顺序表第i个位置插入数据元素e： 将e插入L.elem[i-1]之前。参数i范围应在[1,L.length+1]内，否则会产生不能预料的异常或错误。该操作函数具体定义如下：
       
       
  
      1. void SL_InsAt(SqList &L, int i, ElemType e)
    •  
      删除顺序表的第i个数据元素： 删除顺序表的第i个数据元素。参数i范围应在[1,L.length]内，否则会产生不能预料的异常或错误。该操作函数具体定义如下：
       
       
  
      1. void SL_DelAt(SqList &L, int i)
    •  
      删除顺序表中第一个值为x的数据元素： 删除第一个值为x的数据元素。该操作函数具体定义如下：
       
       
  
      1. void SL_DelValue(SqList &L, ElemType x)
     

    编程要求
     

    在右侧编辑器中补充代码，完成SL_InsAt、SL_DelAt和SL_DelValue三个操作函数，以实现顺序表中数据的插入和删除功能。具体要求如下：
     

    1. SL_InsAT: 在顺序表的第i个位置插入新元素e, 即在元素L.elem[i-1]之前插入，i的有效范围[1,L.length+1]，插入之前要判断表满。
    2. SL_DelAt：删除顺序表的第i个元素，i的有效范围[1,L.length]。
    3. SL_DelValue：删除顺序表中第一个值为x的元素。
     

    测试说明
     

    平台会对你编写的代码进行测试，测试文件为step2/Main.cpp，可在右侧文件夹中进行查看：
     

    测试输入: 5 //输入数据元素的个数 8 9 12 33 45 //输入5个数据元素，创建顺序表 4 10 //输入待插入的位置和待插入元素的值，表示在第4个位置插入元素10 2 //删除第2个数据元素 33 //删除值为33的数据元素 预期输出： 8 12 10 45 //输出当前表中的数据元素
     

    开始你的任务吧，祝你成功！
     

    1. /*************************************************************
    2.     顺序表的实现之增删功能 实现文件
    3. **************************************************************/
    4.  
    5. #include <stdio.h>
    6. #include <stdlib.h>
    7. #include "Seqlist.h"
    8.  
    9. void SL_Initiate(SqList &L)
    10. // 顺序表的初始化，即构造一个空的顺序表
    11. {
    12. 	L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    13. 	L.length=0;
    14. }
    15.  
    16. void SL_Free(SqList &L)
    17. // 释放顺序表
    18. {
    19. 	free(L.elem);
    20. }
    21.  
    22. bool SL_IsEmpty(SqList L)
    23. // 判断顺序表是否空
    24. {
    25. 	return L.length==0;
    26. }
    27.  
    28. bool SL_IsFull(SqList L)
    29. // 判断顺序表是否满
    30. {
    31. 	return L.length==MAXSIZE;
    32. }
    33.  
    34. void SL_Create(SqList &L,int n)
    35. // 输入n个数据元素，创建一个顺序表L
    36. {
    37. 	int i;
    38. 	L.length=n;
    39. 	for(i=0; i<n; i++)
    40. 		scanf("%d", &L.elem[i]);		
    41. }
    42.  
    43. void SL_Print(SqList L)
    44. // 输出整个顺序表
    45. {
    46. 	if (L.length==0)
    47. 	{
    48. 		printf("The slist is empty.\n");		
    49. 		return;
    50. 	}
    51.  
    52. 	for (int i=0; i<L.length; i++)
    53. 		printf("%d  ", L.elem[i]);
    54. 	printf("\n");	
    55. }
    56.  
    57. void SL_InsAt(SqList &L, int i, ElemType e)
    58. // 在顺序表的第i个位置插入新元素e, 即在元素L.elem[i-1]之前插入
    59. // i的有效范围[1,L.length+1]
    60. {
    61.     // 请在这里补充代码，完成本关任务
    62.     /********** Begin *********/
    63. 	int  j;
    64. 	for(j=L.length;j>i-2;--j)
    65. 	{
    66. 		L.elem[j+1] = L.elem[j];
    67.  
    68. 	}
    69. 	L.elem[j+1] = e;
    70. 	L.length++;
    71.  
    72.     /********** End **********/
    73. }
    74.  
    75. void SL_DelAt(SqList &L, int i)
    76. // 删除顺序表L的第i个元素
    77. //i的有效范围[1,L.length]
    78. {
    79.     // 请在这里补充代码，完成本关任务
    80.     /********** Begin *********/
    81. 	int j;
    82. 	for (j=i-1;j<=L.length;++j)
    83.         {
    84.           L.elem[j] = L.elem[j+1];
    85. 		}
    86. 		L.length--;
    87.  
    88.     /********** End **********/
    89. }
    90.  
    91. void SL_DelValue(SqList &L, ElemType x)
    92. // 删除第一个值为x的元素
    93. {
    94.     // 请在这里补充代码，完成本关任务
    95.     /********** Begin *********/
    96. 	int i=0;
    97.         while(L.elem[i]!=x&&i<L.length)
    98.                 i++;
    99.  
    100.         if(L.elem[i]==x)
    101.         {
    102.             for (i;i<L.length;i++)
    103.                 L.elem[i] = L.elem[i+1];
    104.  
    105.             L.length--;
    106.         }
    107.     /********** End **********/
    108. }
    109.  
     

    第3关：顺序表的合并
     

    任务描述
     

    本关任务：已知两个顺序表A和B，数据元素按值非递减有序排列，现将A和B归并成一个新的顺序表C，使C中的数据元素仍按值非递减有序排列。 例如： 设 A=(3,5,8,11) B=(2,6,9,15,20) 则 C=(2,3,5,6,8,9,11,15,20)
     

    相关知识
     

    为了完成本关任务，你需要掌握：1. 顺序表的类型定义，2.顺序表涉及的主要操作。
     

    顺序表的类型定义
     

    定义如下：
     

     

    1. #define MAXSIZE 100 //最大长度
    2. typedef int ElemType; // 数据元素的类型
    3. typedef struct {
    4. ElemType *elem; //指向数据元素的起始地址
    5. int length; //线性表的当前长度
    6. }SqList;
     

    顺序表涉及的主要操作
     

    主要操作如下：
     

    •  
      顺序表的初始化：构造一个最多可存储MAXSIZE个数据元素的顺序表，并将其初始状态设置为length=0，即为空表。该操作函数具体定义如下：
       
       
  
      1. void SL_Initiate(SqList &L)
    •  
      释放顺序表：释放L.elem所指向的用于存储数据元素的存储空间。该操作函数具体定义如下：
       
       
  
      1. void SL_Free(SqList &L)
    •  
      判断顺序表是否为空：若为空表，则返回true,否则返回false。该操作函数具体定义如下：
       
       
  
      1. bool SL_IsEmpty(SqList L)
    •  
      判断顺序表是否已满：若顺序表达到最大长度，则返回 true,否则返回false。该操作函数具体定义如下：
       
       
  
      1. bool SL_IsFull(SqList L)
    •  
      创建顺序表：输入n个数据元素，创建一个顺序表。该操作函数具体定义如下：
       
       
  
      1. void SL_Create(SqList &L,int n)
    •  
      输出顺序表： 输出整个顺序表。该操作函数具体定义如下：
       
       
  
      1. void SL_Print(SqList L)
    •  
      顺序表的合并： 已知顺序表LA和LB的元素按值非递减排列，归并LA和LB得到新的顺序表LC，LC的元素也按值非递减排列。该操作函数具体定义如下：
       
       
     

    编程要求
     

    根据提示，在右侧编辑器中补充代码，完成MergeList_Sq操作函数，以实现顺序表的合并。具体要求如下：
     

    MergeList_Sq: 已知顺序表LA和LB的元素按值非递减排列，归并LA和LB得到新的顺序表LC，LC的元素也按值非递减排列。
     

    提示：已知顺序表 A 和 B 中的数据元素按值非递减有序排列，现要求将 A 和 B 归并为一个新的顺序表 C ，且 C 中的数据元素仍按值非递减有序排列。
     

    例如：
     

     

    1. A=(1,7,8)
    2. B=(2,4,6,8,10,11)
    3. 则合并后的C=(1,2,4,6,7,8,8,10,11)
     

    测试说明
     

    平台会对你编写的代码进行评测，测试文件为step2/Main.cpp，可在右侧文件夹中进行查看：
     

    测试输入: 4 //输入A表的元素个数 3 5 8 11 //输入4个数据元素，创建A表 7 //输入B表的元素个数 2 6 8 9 11 15 20 //输入7个数据元素，创建B表
     

    预期输出： 2 3 5 6 8 8 9 11 11 15 20  //输出合并后的C表
     

    开始你的任务吧，祝你成功！
     

    1. /*************************************************************
    2.     顺序表的合并  实现文件
    3. **************************************************************/
    4.  
    5. #include <stdio.h>
    6. #include <stdlib.h>
    7. #include "Seqlist.h"
    8.  
    9. void SL_Initiate(SqList &L)
    10. // 顺序表的初始化，即构造一个空的顺序表
    11. {
    12. 	L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    13. 	L.length=0;
    14. }
    15.  
    16. void SL_Free(SqList &L)
    17. // 释放顺序表
    18. {
    19. 	free(L.elem);
    20. }
    21.  
    22. bool SL_IsEmpty(SqList L)
    23. // 判断顺序表是否空
    24. {
    25. 	return L.length==0;
    26. }
    27.  
    28. bool SL_IsFull(SqList L)
    29. // 判断顺序表是否满
    30. {
    31. 	return L.length==MAXSIZE;
    32. }
    33.  
    34. void SL_Create(SqList &L,int n)
    35. // 输入n个数据元素，创建一个顺序表L
    36. {
    37. 	int i;
    38. 	L.length=n;
    39. 	for(i=0; i<n; i++)
    40. 		scanf("%d", &L.elem[i]);		
    41. }
    42.  
    43. void SL_Print(SqList L)
    44. // 输出整个顺序表
    45. {
    46. 	if (L.length==0)
    47. 	{
    48. 		printf("The slist is empty.\n");		
    49. 		return;
    50. 	}
    51.  
    52. 	for (int i=0; i<L.length; i++)
    53. 		printf("%d  ", L.elem[i]);
    54. 	printf("\n");	
    55. }
    56.  
    57. void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
    58. //已知顺序表LA和LB的元素按值非递减排列
    59. //归并LA和LB得到新的顺序表LC，LC的元素也按值非递减排列。
    60. {
    61. 	// 请在这里补充代码，完成本关任务
    62.     /********** Begin *********/
    63. LC.length =  LA.length + LB.length;
    64. 	int i=0 , j=0,t=0;
    65. 	while(i<LA.length&&j<LB.length)
    66. 		{
    67. 			if(LA.elem[i]<=LB.elem[j])
    68. 				LC.elem[t++] = LA.elem[i++];
    69. 			else
    70. 				LC.elem[t++] = LB.elem[j++];	
    71. 		}
    72. 	if(i==LA.length)
    73. 		{
    74. 			while(t<LC.length)
    75. 			LC.elem[t++] = LB.elem[j++];	
    76. 		}
    77. 	else
    78. 		{
    79. 			while(t<LC.length)
    80. 			LC.elem[t++] = LA.elem[i++];
    81. 		}
    82.  
    83. 	/********** End **********/
    84. } 
    85.  
     

    
                
    
                    
    
                
    • 

                
  • 

                    相关阅读:
    
                    
import机制浅析                            
    
Vue中如何进行拖拽与排序功能实现                            
    
SpringTask ----定时任务框架 ----苍穹外卖day10                            
    
2022年牛客多校第四场补题                            
    
react兄弟组件传值之PubSubJS                            
    
mysql5.7从入门到精通笔记                            
    
华测视频RTK，AR实景导航                            
    
Abnova 血液总核酸纯化试剂盒方案                            
    
通过开发者工具-网络排查响应时间过长的问题                            
    
HTML中已经过时的标签                            
    
                        
                
    • 
                
  • 
                    原文地址：https://blog.csdn.net/weixin_65370416/article/details/136308700
                
    •