devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法上机实验一 顺序表_数据结构上机实验

作者：很楠不爱3 | 2024-04-13 14:04:15

赞

踩

数据结构上机实验

GitHub 微信公众号 知乎 B站 CSDN

实验一 顺序表

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


对于想要获取此实验报告和源代码的同学，欢迎光顾小生寒舍 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)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7



附件： 源代码
测试环境：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; 

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114

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; 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138


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

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


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

在这里插入图片描述
在这里插入图片描述

微信扫一扫， 关注我


知识星球

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

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

Click to see the more details

MaiweiAI-com | WeChat ID: Yida_Zhang2

机器学习+计算机视觉

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/416830
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号