1. Toy模板网首页
  2. > Toy博客

【头歌】顺序表的基本操作

8月前 作者：大数据秃头族 分类：Toy博客 阅读(80) 违法举报

这篇具有很好参考价值的文章主要介绍了【头歌】顺序表的基本操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第1关：顺序表的插入操作

任务描述

本关任务：编写顺序表的初始化、插入、遍历三个基本操作函数。

相关知识

顺序表的存储结构

顺序表的存储结构可以借助于高级程序设计语言中的数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言中动态分配的一维数组定义如下：

/*线性表的动态分配顺序存储结构（用一维数组）*/
#define INIT_SIZE 100       
//线性表存储空间的初始分配量
#define INCREMENT 10      
//线性表存储空间的分配增量
typedef  struct{  
    ElemType *elem;     //存储空间基地址  
    int     length;    //当前长度  
    int  listsize;     //当前分配的存储容量
}SqList;

在上述定义中，ElemType为顺序表中数据元素的类型，SqList是顺序表类型。

为了令算法具有通用性，使其尽可能地适用于各种可能的场合，将要处理的数据类型加以抽象，使其适用于不同类型的数据，是提高代码通用性的重要手段。

ElemType类型根据实际问题需要灵活定义：

/* 定义ElemType为int类型 */
typedef int ElemType;

或者，有学生数据类型定义如下：

typedef struct date
{  
    int year;    
    int month;    
    int day;
}DATE;
typedef struct student
{     int num;     
    char name[20];     
    char sex;     
    DATE birthday;     
    float score;
 }STUDENT;
/* 定义ElemType为STUDENT类型 */
typedef STUDENT ElemType;

顺序表中数据类型ElemType可以多种多样，但是在编程实现算法时针对不同数据类型，每类数据元素的输入输出是有区别的，顺序表的基本操作算法要在计算机上执行，须针对ElemType类型数据编写输入、输出、比较等函数：

void input(ElemType &s);void output(ElemType s);int equals(ElemType a,ElemType b);

C语言函数基本的参数传递机制是值传递，被调函数对形式参数的任何操作都是作为局部变量进行，不会影响主调函数的实参变量的值。如果需要将函数中变化的形式参数的值反映在实际参数中，在C语言的实现中，就需要通过指针变量作形式参数，接收变量的地址，达到修改实参变量值的目的。

C++语言中用引用作函数的形参，被调函数对形参做的任何操作都影响了主调函数中的实参变量值，而操作一个变量比操作一个指针要简单的多，为了便于算法描述，本书函数参数传递机制采用有两种方式：值传递和引用传递。如果不想修改实参的值，函数参数传递按值传递；如果需要修改实参的值，则使用引用传递。

举例说明，在定义输入函数void input(ElemType &s);时，在函数体内需要输入主调函数中的实参变量的值，也就是说要改变主调函数中的实参变量的值，因此函数形参定义为引用；在定义输出函数void output(ElemType s);时，在函数体内不需要改变主调函数中的实参变量的值，只需读取主调函数中的实参变量的值，因此函数形参定义为变量，采用值传递。

顺序表的初始化操作、销毁操作、插入操作和删除操作，在函数体内改变了顺序表L的数据成员的值，因此函数形参为引用。顺序表的查找操作、遍历操作，在函数体内不改变顺序表L的数据成员的值，函数形参为变量，采用值传递。

下面举例说明如何在线性表的顺序存储结构上实现线性表的基本操作。

顺序表的初始化操作
void InitList(SqList&L)
{ // 操作结果：构造一个空的顺序线性表
    L  L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));  
    if(!L.elem)  exit(-1); 
    // 存储分配失败  
    L.length=0; 
    // 空表长度为0  
    L.listsize=INIT_SIZE; // 初始存储容量
}
顺序表的遍历操作
void ListTraverse(SqList L,void(*vi)(ElemType ))
{   // 初始条件：顺序线性表L已存在    
	// 操作结果：依次对L的每个数据元素调用函数vi()      
    ElemType *p;       
    int i;       	
    p=L.elem;       
    for(i=1; i<=L.length; i++)         
        vi(*p++);       
    printf("\n");
}

在执行ListTraverse()函数输出顺序表的所有数据元素时，用函数指针vi来实现对output()函数的调用。

在执行遍历函数输出顺序表的所有数据元素时，用函数指针vi来实现对output()函数的调用。

顺序表的插入运算

线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素x，使长度为n的线性表 ( a1，…，ai−1，ai，…，an) 变成长度为n+1的线性表( a1，…，ai−1，x，ai+1，…，an) 。

算法思想：用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n-1，n-2，…，i-1上的结点，依次后移到位置n，n-1，…，i上，空出第i-1个位置，然后在该位置上插入新结点x。当i=n+1时，是指在线性表的末尾插入结点，所以无需移动结点，直接将x插入表的末尾即可。

任务描述 本关任务:编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识,【头歌】数据结构,数据结构,算法,Powered by 金山文档

算法分析：

  1. 最好的情况：当i=n+1时（插入尾元素），移动次数为0；

  1. 最坏的情况：当i=1时（插入第一个元素），移动次数为n；

平均情况：在位置i插入新元素x，需要将ai～an的元素均后移一次，移动次数为n-i+1。假设在等概率下pi（pi=1/(n+1)），移动元素的平均次数为：

任务描述 本关任务:编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识,【头歌】数据结构,数据结构,算法,Powered by 金山文档

插入算法的主要时间花费在元素移动上，所以算法平均时间复杂度为O(n)。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成顺序表的初始化操作，遍历操作及插入操作三个子函数的定义，具体要求如下：

  • void InitList(SqList &L); //构造一个空的顺序表L

  • void ListTraverse(SqList L,void(*vi)(ElemType ));// 依次调用函数vi()输出顺序表L的每个数据元素

  • int ListInsert(SqList &L,int i,ElemType e);//在顺序表L中第i个位置之前插入新的数据元素

测试说明

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

输入说明 第一行输入顺序表的长度M； 第二行输入顺序表的M个整数； 第三行输入要插入元素的位置； 第四行输入要插入的数据元素的值。
输出说明 第一行输出插入是否成功的提示信息； 如果插入成功，第二行输出插入元素后的顺序表所有元素；如果插入失败，则不输出第二行。

测试输入： 5 12 47 5 8 69 1 99 预期输出： 插入成功，插入后顺序表如下： 99 12 47 5 8 69

测试输入： 5 12 47 5 8 69 7 99 预期输出： 插入位置不合法，插入失败！

开始你的任务吧，祝你成功！文章来源地址https://www.toymoban.com/news/detail-844637.html

实例代码

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define INIT_SIZE 5
#define INCREMENT 10
# define OK 1
# define ERROR 0

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 顺序表类型定义 */
typedef  struct
{
	ElemType *elem; 	//存储空间基地址
	int 	length; 	//当前长度
	int  listsize; 	//当前分配的存储容量
}SqList;
void InitList(SqList&L); 
int ListInsert(SqList &L,int i,ElemType e);
void ListTraverse(SqList L,void(*vi)(ElemType ) );

int main()               //main() function 
{	
     SqList A;
     ElemType e;
     InitList(A);
      int n,i;
     // cout<<"Please input the list number ";
     cin>>n;
     for(i=1;i<=n;i++)
        { 
		   cin>>e;
         ListInsert(A, i, e);
       }
	//cout<<"请输入插入的位置："<<endl;
	cin>>i;
	//cout<<"请输入插入的值："<<endl;
	input(e);
	if(  ListInsert(A,i,e) )
   {
        cout<<"插入成功，插入后顺序表如下："<<endl;
        ListTraverse(A,output) ;
    }
    else
    	cout<<"插入位置不合法，插入失败！"<<endl;
    return 0;
}


/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
 {
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****顺序表的基本操作*****/
void InitList(SqList&L) 
{	// 操作结果：构造一个空的顺序线性表L 	
    /********** Begin **********/ 
     L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));
    if(!L.elem)
    exit(-1); 
    L.length=0; 
    L.listsize=INIT_SIZE; 

	/********** End **********/
}


int  ListInsert(SqList &L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
    if(L.length>=INIT_SIZE*sizeof(ElemType)||L.length<i-1||i<=0)
		return 0;
    
	for(int j=L.length-1;j>=i-1;j--)
    {
		L.elem[j+1]=L.elem[j];
	}
	L.elem[i-1]=e;
	L.length++;
	return 1;


	
	/********** End **********/
}

void ListTraverse(SqList L,void(*vi)(ElemType ) )
{ 	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出	
    /********** Begin **********/ 
    ElemType *p;
       int i;
       p=L.elem;
       for(i=1; i<=L.length; i++)
         vi(*p++);
      cout<<endl;
	
	/********** End **********/
}

第2关：顺序表的删除操作

任务描述

本关任务：编写顺序表的删除操作函数。

相关知识

线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表 ( a1，…，ai−1，ai，ai+1，…，an)，变成长度为n-1的线性表( a1，…，ai−1，ai+1，…，an)。

算法思想：在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1位置上，以填补删除操作造成的空缺。

任务描述 本关任务:编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识,【头歌】数据结构,数据结构,算法,Powered by 金山文档

算法分析：

  1. 最好的情况：当i=n时（删除尾元素），移动次数为0；

  1. 最坏的情况：当i=1时（删除第一个元素），移动次数为n-1；

  1. 平均情况：删除位置i的元素ai，需要将ai+1～an的元素均前移一次，移动次数为n-(i+1)+1=n-i。假设在等概率下pi（pi=1/n），移动元素的平均次数为：

任务描述 本关任务:编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识,【头歌】数据结构,数据结构,算法,Powered by 金山文档

删除算法的主要时间花费在元素移动上，所以算法的平均时间复杂度为O(n)。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成顺序表的删除操作函数的定义，具体要求如下：

  • int ListDelete(SqList &L,int i,ElemType &e) //删除顺序表L的第i个数据元素，并用e返回其值，L的长度减1

测试说明

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

测试输入： 5 12 47 5 8 69 1 预期输出： 删除成功，删除后顺序表如下： 47 5 8 69 删除元素的值：12

测试输入： 5 12 47 5 8 69 6 预期输出： 删除位置不合法，删除失败！

输入说明 第一行输入顺序表的长度M； 第二行输入顺序表的M个整数； 第三行输入要删除元素的位置；
输出说明 第一行输出删除是否成功的提示信息； 如果删除成功，第二行输出删除元素后的顺序表；第三行输出删除的数据元素；如果删除位置不合法，不输出第二行和第三行。

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

实例代码

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define INIT_SIZE 5
#define INCREMENT 10

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 顺序表类型定义 */
typedef  struct
{
	ElemType *elem; 	//存储空间基地址
	int 	length; 	//当前长度
	int  listsize; 	//当前分配的存储容量
}SqList;

void InitList(SqList&L); 
int  ListInsert(SqList &L,int i,ElemType e);
int  ListDelete(SqList &L,int i,ElemType&e) ;
void ListTraverse(SqList L,void(*vi)(ElemType ) );

int main()               //main() function 
{	
	SqList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//cout<<"请输入删除的位置："<<endl;
	cin>>i;	
	if(  ListDelete(A,i,e) )
	{
		cout<<"删除成功，删除后顺序表如下："<<endl;
		ListTraverse(A,output) ;
		cout<<"删除元素的值：";
	    output(e);
    	cout<<endl;
	}
	else
		cout<<"删除位置不合法，删除失败！"<<endl;
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****顺序表的基本操作*****/

void InitList(SqList&L) 
{	// 操作结果：构造一个空的顺序线性表L
 	/********** Begin **********/ 
	L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		return; // 存储分配失败
	L.length=0; // 空表长度为0
	L.listsize=INIT_SIZE; // 初始存储容量
	/********** End **********/
}


int  ListInsert(SqList &L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
	ElemType *newbase,*q,*p;
	if(i<1||i>L.length+1) // i值不合法
		return 0;
	if(L.length>=L.listsize)
    { // 当前存储空间已满，增加分配
		if(!(newbase=(ElemType*)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(ElemType))))
			return(0); ; // 存储分配失败
		L.elem=newbase; // 新基址
		L.listsize+= INCREMENT; // 增加存储容量
	}
	q=L.elem+i-1; // q为插入位置
	for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移
		*(p+1)=*p;
	*q=e;            // 插入e
	++L.length;      // 表长增1
	return 1;
	/********** End **********/
}

void ListTraverse(SqList L,void(*vi)(ElemType ) )
{ 
	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出
	/********** Begin **********/ 
	ElemType *p;
	int i;
	p=L.elem;
	for(i=1;i<=L.length;i++)
		vi(*p++);
	printf("\n");
	/********** End **********/
}

int  ListDelete(SqList &L,int i,ElemType&e) 
{
	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
	// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
	/********** Begin **********/ 
	if(i<1||i>L.length+1)
    {
		return 0;
	}
	e = L.elem[i-1];	
	for(int j = i;j<L.length;j++)
    {
		L.elem[j-1] = L.elem[j];
	}
	L.length--;		
	return e;
	/********** End **********/
}

第3关：顺序表的按照序号查找值操作

任务描述

本关任务：编写顺序表的按照序号i查找数据元素值的操作函数。

相关知识

顺序表L已存在，先判断i值是否合法，如果合法，将顺序表L中第i个数据元素的值赋给e，e要带出函数体，类型声明为引用。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成顺序表的按照序号查找操作函数的定义，具体要求如下：

  • int GetElem(SqList L,int i,ElemType &e);//用e返回顺序表L中第i个数据元素的值

测试说明

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

测试输入： 10 12 47 5 8 6 92 45 63 75 38 8

预期输出： 查找成功！ 第8个元素的值： 63

测试输入： 10 12 47 5 8 6 92 45 63 75 38 11

预期输出： 查找失败！

输入说明 第一行输入顺序表的长度M； 第二行输入顺序表的M个整数； 第三行输入要查找的序号；
输出说明 第一行输出按照序号查找是否成功的提示信息； 如果查找成功，输出查找的元素的值；如果查找失败，则不输出。

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

实例代码

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define INIT_SIZE 5
#define INCREMENT 10
# define OK 1
# define ERROR 0

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 顺序表类型定义 */
typedef  struct
{
	ElemType *elem; 	//存储空间基地址
	int 	length; 	//当前长度
	int  listsize; 	//当前分配的存储容量
}SqList;
void InitList(SqList&L); 
int ListInsert(SqList &L,int i,ElemType e);
void ListTraverse(SqList L,void(*vi)(ElemType ) );
int GetElem(SqList L,int i,ElemType&e);

int main()               //main() function 
{	
	SqList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//cout<<"请输入查找的序号："<<endl;
	cin>>i;	
	if(  GetElem(A,i,e) )
	{
		cout<<"查找成功！"<<endl;
		cout<<"第"<<i<<"个元素的值："<<endl;
	    output(e);
        cout<<endl;
	}
	else
		cout<<"查找失败！"<<endl;
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
 {
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****顺序表的基本操作*****/
void InitList(SqList&L) 
{	// 操作结果：构造一个空的顺序线性表L
 	/********** Begin **********/ 
	L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		return; // 存储分配失败
	L.length=0; // 空表长度为0
	L.listsize=INIT_SIZE; // 初始存储容量
	/********** End **********/
}


int  ListInsert(SqList &L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
	ElemType *newbase,*q,*p;
	if(i<1||i>L.length+1) // i值不合法
		return 0;
	if(L.length>=L.listsize)
    { // 当前存储空间已满，增加分配
		if(!(newbase=(ElemType*)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(ElemType))))
			return(0); ; // 存储分配失败
		L.elem=newbase; // 新基址
		L.listsize+= INCREMENT; // 增加存储容量
	}
	q=L.elem+i-1; // q为插入位置
	for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移
		*(p+1)=*p;
	*q=e;            // 插入e
	++L.length;      // 表长增1
	return 1;
	/********** End **********/
}

void ListTraverse(SqList L,void(*vi)(ElemType ) )
{ 
	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出
	/********** Begin **********/ 
	ElemType *p;
	int i;
	p=L.elem;
	for(i=1;i<=L.length;i++)
		vi(*p++);
	printf("\n");
	/********** End **********/
}

int GetElem(SqList L,int i,ElemType&e)
{
	//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)。
	//操作结果：用e返回L中第i个数据元素的值
	/********** Begin **********/ 
	if(i<1||i>L.length)
		return 0;
    e=L.elem[i-1];
	return e;
	/********** End **********/
}

第4关：顺序表的按照值查找序号操作

任务描述

本关任务：编写顺序表按照值查找序号操作的函数。

相关知识

在顺序表L找第一个值为e的元素，找到后返回其逻辑序号，否则返回0。

注意：由于线性表的逻辑序号从1开始，这里用0表示没有找到值为e的元素。

在算法实现时，应根据顺序表数据元素的类型ElemType编写判断两个数据元素是否相等的比较函数equals()。举例说明： （1）数据元素的类型ElemType为int类型

typedef  int  ElemType;
int equals(ElemType a,ElemType b)
{ 
	// 根据两个整数a，b是否相等，分别返回1或0       
    if (a == b)         
    return 1;       
    else           
    return 0;
 }

（2）数据元素的类型ElemType为char [20] 类型

typedef  char  ElemType[20];
int equals (ElemType a,ElemType b)
{ 
    // 根据两个字符串a、b是否相等，分别返回1或0        
    if ( strcmp(a,b) == 0 )         
        return 1;       
    else           
        return 0;
}

（3）数据元素的类型ElemType为自定义结构体变量类型，判断两个数据元素是否相等，就需要比较所有结构体变量成员。

struct student{       
char num[20];      
char name[16];      
int  year;      
float  score;
};
typedef  struct student  ElemType;
int equals (ElemType a,ElemType b) 
{   
    // 如果a,b的所有成员值相等，返回1，否则返回0    
    if ( ( strcmp( a.num, b.num ) != 0 )        
    return 0;    
    else  if ( strcmp( a.name, b.name ) != 0 )        
    return 0;    
    else  if  ( a.year != b.year )         
    return 0;       
    else  if ( a.score != b. score ) )           
    return 0;    
    else        
    return 1;
 }

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成顺序表的按照值查找序号操作函数的定义，具体要求如下：

  • int LocateElem(SqList L,ElemType e,int (*equal) (ElemType , ElemType) );// 返回顺序表L中第1个与e满足相等关系equal()的数据元素的位序，若这样的数据元素不存在，则返回值为0。

测试说明

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

测试输入： 10 12 47 5 8 6 92 45 63 75 38 92

预期输出： 查找成功！ 92 是顺序表第6个元素

测试输入： 10 12 47 5 8 6 92 45 63 75 38 93

预期输出： 查找失败！

输入说明 第一行输入顺序表的长度M； 第二行输入顺序表的M个整数； 第三行输入要查找的数据元素的值。
输出说明 第一行输出按照值查找是否成功的提示信息； 如果查找成功，第二行输出查找元素的逻辑序号；如果查找失败，则不输出。

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

实例代码

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define INIT_SIZE 5
#define INCREMENT 10
# define OK 1
# define ERROR 0

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 顺序表类型定义 */
typedef  struct
{
	ElemType *elem; 	//存储空间基地址
	int 	length; 	//当前长度
	int  listsize; 	//当前分配的存储容量
}SqList;


void InitList(SqList&L); 
int  ListInsert(SqList &L,int i,ElemType e);
void ListTraverse(SqList L,void(*vi)(ElemType ) );
int LocateElem(SqList L,ElemType e,int (*compare) (ElemType , ElemType));

int main()               //main() function 
{	
	SqList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//cout<<"请输入查找的元素："<<endl;
	cin>>e;	
	i=LocateElem(A,e,equals);
	if( i ) 
	{
		cout<<"查找成功！"<<endl;		
	   output(e);
    
		cout<<"是顺序表第"<<i<<"个元素"<<endl;
	}
	else
		cout<<"查找失败！"<<endl;
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****顺序表的基本操作*****/

void InitList(SqList&L) 
{	// 操作结果：构造一个空的顺序线性表L
 	/********** Begin **********/ 
	L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		return; // 存储分配失败
	L.length=0; // 空表长度为0
	L.listsize=INIT_SIZE; // 初始存储容量
	/********** End **********/
}


int  ListInsert(SqList &L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
	ElemType *newbase,*q,*p;
	if(i<1||i>L.length+1) // i值不合法
		return 0;
	if(L.length>=L.listsize)
    { // 当前存储空间已满，增加分配
		if(!(newbase=(ElemType*)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(ElemType))))
			return(0); ; // 存储分配失败
		L.elem=newbase; // 新基址
		L.listsize+= INCREMENT; // 增加存储容量
	}
	q=L.elem+i-1; // q为插入位置
	for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移
		*(p+1)=*p;
	*q=e;            // 插入e
	++L.length;      // 表长增1
	return 1;
	/********** End **********/
}

void ListTraverse(SqList L,void(*vi)(ElemType ) )
{ 
	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出
	/********** Begin **********/ 
	ElemType *p;
	int i;
	p=L.elem;
	for(i=1;i<=L.length;i++)
		vi(*p++);
	printf("\n");
	/********** End **********/
}


int LocateElem(SqList L,ElemType e,int (*compare) (ElemType , ElemType))
{
	// 初始条件：顺序表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
	// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
	// 若这样的数据元素不存在，则返回值为0。
	/********** Begin **********/ 
    int i=0;
    for (i=0;i<L.length;i++)
    {
        if(compare(e,L.elem[i]))
        {
            return i+1; 
          
            
        }
    }
    return 0;
    
    /********** End **********/
	
}

第5关：顺序表的逆置操作

任务描述

本关任务：编写顺序表的逆置操作函数。

相关知识

关于逆置，有一种非常暴力的解决方法，就是单独开辟一个同等大小的顺序表，然后新表从前往后遍历，同时原表从后往前遍历，依次赋值，最后得到的就是逆置后的顺序表。但这种方法的空间复杂度为O(n)，所以并不能这么做。

顺序表的就地逆置，只需让顺序表中的数据元素头尾依次交换即可，即交换第一个元素和最后一个元素，第二个和倒数第二个，依此类推，这种方法的空间复杂度为O(1)。

任务描述 本关任务:编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识,【头歌】数据结构,数据结构,算法,Powered by 金山文档

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成顺序表的逆置操作函数的定义：

  • void reverse(SqList &A); //将顺序表就地逆置

测试说明

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

测试输入： 10 12 47 5 8 6 92 45 63 75 38

预期输出： 逆置顺序表： 38 75 63 45 92 6 8 5 47 12

输入说明 第一行输入顺序表的长度M； 第二行输入顺序表的M个整数；
输出说明 第一行输出提示信息； 第二行输出逆置后的顺序表。

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

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define INIT_SIZE 5
#define INCREMENT 10
# define OK 1
# define ERROR 0

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 顺序表类型定义 */
typedef  struct
{
	ElemType *elem; 	//存储空间基地址
	int 	length; 	//当前长度
	int  listsize; 	//当前分配的存储容量
}SqList;

void InitList(SqList&L); 
int  ListInsert(SqList &L,int i,ElemType e);
void ListTraverse(SqList L,void(*vi)(ElemType ) );
void reverse(SqList &A);
int main()               //main() function 
{	
	SqList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	
	cout<<"逆置顺序表："<<endl;
	reverse(A);
	ListTraverse(A,output) ;	
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****顺序表的基本操作*****/

void InitList(SqList&L) 
{	// 操作结果：构造一个空的顺序线性表L
 	/********** Begin **********/ 
	L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		return; // 存储分配失败
	L.length=0; // 空表长度为0
	L.listsize=INIT_SIZE; // 初始存储容量
	/********** End **********/
}


int  ListInsert(SqList &L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
	ElemType *newbase,*q,*p;
	if(i<1||i>L.length+1) // i值不合法
		return 0;
	if(L.length>=L.listsize)
    { // 当前存储空间已满，增加分配
		if(!(newbase=(ElemType*)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(ElemType))))
			return(0); ; // 存储分配失败
		L.elem=newbase; // 新基址
		L.listsize+= INCREMENT; // 增加存储容量
	}
	q=L.elem+i-1; // q为插入位置
	for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移
		*(p+1)=*p;
	*q=e;            // 插入e
	++L.length;      // 表长增1
	return 1;
	/********** End **********/
}

void ListTraverse(SqList L,void(*vi)(ElemType ) )
{ 
	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出
	/********** Begin **********/ 
	ElemType *p;
	int i;
	p=L.elem;
	for(i=1;i<=L.length;i++)
		vi(*p++);
	printf("\n");
	/********** End **********/
}


/********** 定义 void reverse(SqList &A)函数**********/ 
void reverse(SqList &A)
{
	 /********** Begin **********/ 
	int  temp;
	for (int i = 0; i < (A.length / 2); i++) 
    {
		temp = A.elem[i];
		A.elem[i] = A.elem[A.length - 1 - i];
		A.elem[A.length - 1 - i] = temp;
	}


	/********** End **********/
}

第6关：两个有序顺序表的合并操作

任务描述

本关任务：分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序顺序表，编写将这两个有序顺序表合并成为一个大的有序顺序表的合并操作函数。

相关知识

已知有两个按元素值递增有序的顺序表A和B。设计一个算法将顺序表A和B的全部元素归并到一个按元素递增有序的顺序表C中。

算法思想：用i遍历顺序表A，用j遍历顺序表B。当A和B都未遍历完时，比较两者的当前元素，则将较小者复制到C中，若两者的当前元素相等，则将这两个元素都复制到C中。最后将尚未遍历完的顺序表的余下元素均复制到顺序表C中。

任务描述 本关任务:编写顺序表的初始化、插入、遍历三个基本操作函数。 相关知识,【头歌】数据结构,数据结构,算法,Powered by 金山文档

本算法的空间复杂度为O(1)，时间复杂度为O(n+m)，其中n和m分别为顺序表A和B的长度。

要注意，如果顺序表中数据类型ElemType是结构体类型，结构体变量之间整体是不可以比较大小的，结构体变量之间只能比较某个成员的大小；比较两个结构体变量是否相等与比较两个结构体变量某个成员的大小也是有区别的。

编程要求

根据提示，在右侧编辑器 Begin-End 区间补充代码，完成两个有序顺序表的合并操作函数的定义：

  • int MergeList(SqList La, SqList Lb, SqList &Lc) ;// 归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列。

测试说明

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

测试输入： 5 10 15 20 25 30 6 12 22 32 42 52 62

输入说明 第一行输入有序表A的长度M； 第二行依次输入有序表A的M个有序的整数； 第三行输入有序表B的长度N； 第四行依次输入有序表B的N个有序的整数。

预期输出： 合并两个有序顺序表： 10 12 15 20 22 25 30 32 42 52 62

输出说明 第一行输出提示信息； 第二行输出合并后的有序顺序表所包含的M+N个有序的整数。

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

代码示例

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define INIT_SIZE 5
#define INCREMENT 10

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 顺序表类型定义 */
typedef  struct
{
	ElemType *elem; 	//存储空间基地址
	int 	length; 	//当前长度
	int  listsize; 	//当前分配的存储容量
}SqList;
void InitList(SqList&L); 
int  ListInsert(SqList &L,int i,ElemType e);
void ListTraverse(SqList L,void(*vi)(ElemType ) );
int MergeList(SqList La, SqList Lb, SqList &Lc) ;

int main()               //main() function 
{	
	SqList A,B,C;
	ElemType e;
	InitList(A);
	InitList(B);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(B, i, e);
	}
	cout<<"合并两个有序顺序表："<<endl;
	MergeList(A,B,C);	
	ListTraverse(C,output) ;	
}

/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****顺序表的基本操作*****/
void InitList(SqList&L) 
{	// 操作结果：构造一个空的顺序线性表L
 	/********** Begin **********/ 
	L.elem=(ElemType*)malloc( INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		return; // 存储分配失败
	L.length=0; // 空表长度为0
	L.listsize=INIT_SIZE; // 初始存储容量
	/********** End **********/
}


int  ListInsert(SqList &L,int i,ElemType e)
{	// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
	// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
	/********** Begin **********/ 
	ElemType *newbase,*q,*p;
	if(i<1||i>L.length+1) // i值不合法
		return 0;
	if(L.length>=L.listsize)
    { // 当前存储空间已满，增加分配
		if(!(newbase=(ElemType*)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(ElemType))))
			return(0); ; // 存储分配失败
		L.elem=newbase; // 新基址
		L.listsize+= INCREMENT; // 增加存储容量
	}
	q=L.elem+i-1; // q为插入位置
	for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移
		*(p+1)=*p;
	*q=e;            // 插入e
	++L.length;      // 表长增1
	return 1;
	/********** End **********/
}

void ListTraverse(SqList L,void(*vi)(ElemType ) )
{ 
	// 初始条件：顺序线性表L已存在
	// 操作结果：依次对L的每个数据元素调用函数vi()输出
	/********** Begin **********/ 
	ElemType *p;
	int i;
	p=L.elem;
	for(i=1;i<=L.length;i++)
		vi(*p++);
	printf("\n");
	/********** End **********/
}


int MergeList(SqList La, SqList Lb, SqList &Lc) 
{  
	// 已知顺序线性表La和Lb的元素按值非递减排列。
	// 归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。
	/********** Begin **********/ 
    Lc.length=La.length+Lb.length;
	Lc.elem=new ElemType[Lc.length];
	int *pa=La.elem,*pb=Lb.elem,*pc=Lc.elem;
    int *pa_last=La.elem+La.length-1,*pb_last=Lb.elem+Lb.length-1;
	while((pa<=pa_last)&&(pb<=pb_last))
{
		if(*pa<=*pb)
			*pc++=*pa++;
		else
			*pc++=*pb++;
	}
while(pa<=pa_last)
		*pc++=*pa++;
	while(pb<=pb_last)
		*pc++=*pb++;


	/********** End **********/
}

到了这里，关于【头歌】顺序表的基本操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构：定长顺序串（SString）基本操作的算法描述（C语言）

    作者在学习数据结构时，发现鲜有完全按照 C 语言描述的算法操作，这让习惯于写 .c 而不是 .cpp 的初学者很是头疼。本文将基于 C 语言描述算法操作，如有错漏还望大佬们指正。 本文将按照严惠敏所著《数据结构(C语言版)》所做的函数原型声明进行算法描述，由于C语言不支

    2024年02月07日
    浏览(72)
  • 顺序表的基本操作（初始化，增，删，查，改等等）

    顺序表的基本操作（初始化，增，删，查，改等等）

    1.线性表 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构， 常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性

    2024年02月03日
    浏览(42)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样，但本文并未采用 #define 定义容量的写法，这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟，后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中，重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(62)

  • 对顺序表的基本操作(增删查改),并编写makefile进行编

    1.定义顺序表结构体 2.创建顺序表 3.从尾部插入数据 4.遍历顺序表 5.从尾部删除数据 6.按下标插入数据 7.按下标删除数据 8.按下标修改数据 9.按下标查找数据 10.按数据修改数据 11..按数据查找位置 12.顺序表去重         删除重复数据         (提示：将先出现的数据与后面

    2024年02月20日
    浏览(52)
  • 数据结构 线性表的定义和基本操作（以顺序表为例）

    数据结构 线性表的定义和基本操作（以顺序表为例）

    名人说：一花独放不是春，百花齐放花满园。——《增广贤文》 作者：Code_流苏(CSDN) （一个喜欢古诗词和编程的Coder😊） 以下代码个人分享出来，仅供学习交流，且仅在CSDN平台发布，未经授权禁止二次转发。 〇、线性表是什么？ 1、定义 线性表 是具有 相同数据类型 的 n（

    2024年02月12日
    浏览(63)

  • 线性表的基本操作及在顺序存储及链式存储的实现

    一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过其基本操作来实现。线性表的主要操作如下 注意：1：基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同 2：“” 表示c++中的引用调用。若存入的变量是指针变量，且

    2024年02月13日
    浏览(43)

  • 数据结构（C语言实现）——顺序表的介绍及基本操作的实现

    今天我们来学习数据结构中的线性表，本文主要介绍一种常见的线性表——顺序表。 本文着重介绍顺序表的概念以及顺序表各种基本操作的实现过程（C语言实现），以后会更新更多的数据结构，觉得有用的朋友可以三连关注一波，一起学习。 线性表（linear list）是n个具有相

    2023年04月13日
    浏览(52)
  • 【数据结构】顺序表的实现及基本操作完整代码（C语言实现）

    【数据结构】顺序表的实现及基本操作完整代码（C语言实现）

    顺序表：逻辑上相邻的数据元素，其物理次序也是相邻的 这里之所以要把int分别创建新名字为SqlElemType和Status，是因为实际应用时数据的类型不一定是int型，这样设置方便修改元素类型，提高代码适用性。 LocateElem的时间复杂度为O（n) InsertSq的时间复杂度为O（n) DeleteSq的时间

    2024年04月12日
    浏览(50)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样，但本文并未采用 #define 定义容量的写法，这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟，后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中，重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(70)
  • 数据结构-线性表的顺序表基本操作代码实现（超级详细清晰 C++实现）

    数据结构-线性表的顺序表基本操作代码实现（超级详细清晰 C++实现）

    顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表： 可动态增长的数组，要求数据是连续存储的 特点： 随机访问 顺序既可以 静态分配 ，也可以 动态分配 。在静态分配时，由于数组

    2024年02月07日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包