本次继续更新数据结构与算法这门课的上机实验，主要涉及顺序表这一数据结构。
特此感谢， 实验过程中邓老师的指导和帮助！

对于想要获取此实验报告和源代码的同学，欢迎光顾小生寒舍 GitHub：https://github.com/ChromeWei?tab=repositories

实验内容：
一、参考教材，编写顺序表的相关程序（定义，初始化，插入，删除，取值，赋值等等）
二、编写main函数，利用已有的函数，构造一个数据元素值依次为1-50的顺序表，并逐个输出，即输出1,2,3……49,50。
三、编写函数，将表倒序，并在main函数中调用，再次输出，也就是输出50,49,48……2,1。
四、说明你的倒序程序的时间复杂度是多少？用O(f(n))表示。

备注：exp3_1.cpp和exp3_2.cpp 实现的是相同的功能，但是不同点在于函数采用宏定义的方式实现了代码的通用，我在程序注释中也写了详细的comment，希望能帮到大家。

#define sqstack SqList
#define Initstack(S) InitList_Sq(S)
#define stackempty(S) (S.length == 0)
#define Stacklength(S) (S.length)
#define gettop(s,e) Get(S,S.length,e)
#define push(S,e) ListInsert_Sq(S, S.length+1,e)
#define pop(S,e) ListDelete_Sq(S,S.length,e)

附件： 源代码
测试环境：Win10，Dev-C++

exp3_1.cpp

#include "iostream"
#include "stdlib.h"
#include "stdio.h"

using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define ElemType int
#define OVERFLOW 1
#define Status bool
#define OK true
#define ERROR false

typedef struct
{
	ElemType  *base; //在栈构造之前和销毁之后，base值为NULL
	ElemType  *top; //栈顶指针
	int   stacksize; //栈的当前已分配的存储空间
}sqstack;

Status Initstack(sqstack &s)
{
	s.base=(ElemType*)malloc((STACK_INIT_SIZE+1)*sizeof(ElemType));
	if (!s.base)
		exit (OVERFLOW);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return OK;
}

Status stackempty (sqstack s)
{
	if(s.top==s.base)
		return true;
	else
		return false;
}

int Stacklength(sqstack s)
{
     return(s.top-s.base);
}

Status gettop(sqstack s,ElemType &e) //得到栈顶元素值，但不出栈
{
	if (s.top==s.base)
		return ERROR;
	e=*(s.top-1);
    return OK;
}

Status push(sqstack &s, ElemType e)//入栈
{ 
	if (s.top-s.base>=s.stacksize) 
	{
		s.base=(ElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT+1)*sizeof(ElemType));
		if(!s.base) exit(OVERFLOW);
		s.top=s.base+s.stacksize;
		s.stacksize += STACKINCREMENT;
	}
	
	*s.top++=e;
	return OK;
}

Status pop(sqstack  &s,ElemType &e) //出栈
{  
	if(s.top ==s.base)  
		return ERROR;
	e=*--s.top;
	return OK;
}

Status conversion(ElemType N, ElemType M){
    //栈 对于输入的任意一个非负十进制整数，打印输出等M制的进制数
    sqstack S;
	ElemType e;

    if(!Initstack(S)) return ERROR; //栈的初始化 
    while(N){
       //取余数入栈	 
       push(S,N % M);
	   N = N / M;
    } 
 
    while(!stackempty(S)){
	  pop(S,e);
	  cout<<e;	
	}
	return OK;
}//conversion 

int main()
{
	ElemType n;
	cout<<"请输入一个10进制数: ";
	scanf("%d",&n);cout<<endl;

	cout<<" 2进制:";
	conversion(n,2);
	cout<<endl;

	cout<<" 8进制:";
	conversion(n,8);
	cout<<endl;

	cout<<"16进制:";
	conversion(n,16);
	cout<<endl;
	return 0; 

}

exp3_2.cpp

#include "iostream"
#include "stdlib.h"
#include "stdio.h"

using namespace std;

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表存储空间的分配增量

#define ElemType int

#define OVERFLOW 1
#define Status bool
#define OK true
#define ERROR false

#define sqstack SqList
#define Initstack(S) InitList_Sq(S)
#define stackempty(S) (S.length == 0)
#define Stacklength(S) (S.length)
#define gettop(s,e) Get(S,S.length,e)
#define push(S,e) ListInsert_Sq(S, S.length+1,e)
#define pop(S,e) ListDelete_Sq(S,S.length,e)

typedef struct {
	ElemType *elem;    // 存储空间基址
	int length;   // 当前长度
	int listsize;  // 当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;  // 俗称 顺序表

Status InitList_Sq(SqList& L) {  // 构造一个空的线性表L
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//为线性表分配大小为LIST_INIT_SIZE*sizeof(ElemType)的数组空间

	if (!L.elem) exit(OVERFLOW);  //存储分配失败
		L.length = 0;  //空表长度为0

	L.listsize = LIST_INIT_SIZE;  //初始存储容量
	return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e,i等于1代表插入在表头，i等于L.length+1代表插入在表尾
	if(i<1||i>L.length+1)//i 的合法范围为1≤i≤L.length+1
		return ERROR;//i值不合法

	if (L.length>=L.listsize){ //当前存储空间已满，增加分配
		ElemType* newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

		if (!newbase) exit(OVERFLOW); //存储分配失败

		L.elem=newbase;//新基址
		L.listsize+=LISTINCREMENT;//增加存储容量
	}

	ElemType* q=&(L.elem[i-1]);//q指示插入位置
	for(ElemType* p=&(L.elem[L.length-1]);p>=q;--p)  
		 *(p+1)=*p;       // 插入位置及之后的元素右移

	*q=e;       // 插入e

	++L.length;   // 表长增1

	return OK;
}// ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {//删除
	
	if ((i<1)||(i> L.length))//删除位置不合法
		return ERROR;
	
	ElemType* p=&(L.elem[i-1]); // p为被删除元素的位置
	e = *p; 
	ElemType* q=L.elem+L.length-1; // 表尾元素的位置
	
	for (++p; p<=q; ++p)
		*(p-1)=*p; 
	
	--L.length; 

	return OK;
} // ListDelete_Sq

Status Get(SqList& L,int i,ElemType &e)//得到顺序表中的第i个元素，用e返回
{
	if(i<1||i>L.length)//i 的合法范围为1≤i≤L.length
		return ERROR;//i值不合法
	e=*(L.elem+i-1);
	return OK;

}

Status Set(SqList& L,int i,ElemType e)//给顺序表中的第i个元素赋值e
{
	if(i<1||i>L.length)//i 的合法范围为1≤i≤L.length
		return ERROR;//i值不合法
	*(L.elem+i-1)=e;
	return OK;

}

Status conversion(ElemType N, ElemType M){
    //栈 对于输入的任意一个非负十进制整数，打印输出等M制的进制数
    sqstack S;
	ElemType e;

    if(!Initstack(S)) return ERROR; //栈的初始化 
    while(N){
       //取余数入栈	 
       push(S,N % M);
	   N = N / M;
    } 
 
    while(!stackempty(S)){
	  pop(S,e);
	  cout<<e;	
	}
	return OK;
}//conversion 

int  main()
{	
	ElemType n;
	cout<<"请输入一个10进制数: ";
	scanf("%d",&n);cout<<endl;

	cout<<" 2进制:";
	conversion(n,2);
	cout<<endl;

	cout<<" 8进制:";
	conversion(n,8);
	cout<<endl;

	cout<<"16进制:";
	conversion(n,16);
	cout<<endl;
	
	return 0; 
}

上一篇：数据结构与算法上机实验专栏

下一篇：数据结构与算法上机实验二 链表

欢迎各位订阅我，谢谢大家的点赞和专注！我会继续给大家分享我大学期间详细的实践项目。

微信扫一扫， 关注我

知识星球

专为求职面试中算法与数据结构的小伙伴，创了学习交流/刷题群（知识星球）！想要最快的提升算法与数据结构技能，和更多小伙伴一起来吧！

进群获取互联网大厂高频coding题库，告别刷题400道，分类整理的题库，算法思路和源代码实现配套，各个类型总结出来的解题模板，远比你一个人要强！

MaiweiAI-com | WeChat ID: Yida_Zhang2

机器学习+计算机视觉