数据结构实验三：栈与队列

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 6.9k | 阅读时长 ≈ 12 分钟

实验三 栈与队列

1、实验目的

（1）熟悉将算法转换为程序代码的过程。

（2）熟悉栈与队列的定义和表示

（3）熟练掌握顺序栈和链栈的基本操作。

（4）掌握循环队列的结构和基本实现

（5) 熟习循环队列的基本操作。

2、实验内容

（1）顺序栈应用：编制一C++ 程序prog_stack，实现如下功能：

  1. 定义一顺序栈（动态栈）名为 TranSqstack, 实现如下基本操作：

InitStack：构造一空栈，初始大小STACK_INIT_SIZE 设置为10, 及增量STACK_INCREMENT设置为5 基本数据类型（ElemType）设为 int。

DestroyStack:

IsEmpty:

GetTop:

Push:

Pop:

  1. 使用TranSqstack构造一函数实现10进制数转化为

他进制数（二进制，八进制，及十六进制）的功能，注意十六进制的数字字符为：0,1,2,3,4,5,6,7,8,9，A,B,C,D，E,F （其中A，B,C, D，E,F分别代表十进制的 10,11,12,13,14,15， 例如十进制26用十六进制表示为 0x1A）

  1. 程序从键盘读入十进制数：123,1234,12345， 123456， 1234567,12345768， 然后显示该十进制数转换所得二进制，八进制和十六进制数（注意，八进制数要加前缀0，十六进制数前要加前缀0x）。

4）GetTop函数取得当前栈中的栈顶元素，然后用DestroyStack 函数消除该栈。

  1. 循环队列应用：编制一C++ 程序prog_queue，实现如下功能：

1）构造一循环队列SqQueue，满足如下要求：

（a） 本队列最大长度（MAXQSIZE)设为10; 基本数据类型(ElemType)定为字符型：

（b）实现队列的如下操作：

InitQueue—- –构造一空队列

QueueLength—–返回队列的长度

EnQueue —-向队列插入数据(入队）

DeQueue—-从队列中取出数据（出队）

ShowQueue —显示本队列的中所有数据

注意：对各函数操作的返回信息请用适当的汉字说明，如”数据 A 成功入队”，或”队满，数据A无法入队”等。

2）按顺序实现如下数据操作：

1,2,3,4,5，d, e, b 入队

1,2,3出队

f, g, h, i, j,k ,h 入队

4,5,d,e 出队

n, o, p入队

3）调用ShowQueue显示2）中所有操作完成以后队列中所有字符。

3、实验要求：
（1）实验报告中需要显示所建立的抽象数据模型。
（2）按步骤将程序运行结果截图写入实验报告。
（3）实验需要在两周内按时完成。 学习资料:

  • 相关代码

    顺序栈：

    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
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    #define  STACK\_INIT\_SIZE  10    /*  栈初始向量大小  */
    #define STACKINCREMENT 5   /*  存储空间分配增量  */
    #define OK 1
    #define MAXSIZE 5
    #define ERROR 0
    #define OVERFLOW -1
    //typedef int SElemType;
    typedef  int  ElemType;
    typedef struct
    {   ElemType  \*base;     /\*  栈不存在时值为NULL  */
        ElemType  \*top;      /\*  栈顶指针  */
        int   stacksize ;      
    }TranSqstack;
    int InitStack(TranSqstack &S)    /* 初始化  */
    {
    S.base = (ElemType *)malloc(STACK\_INIT\_SIZE * sizeof(ElemType));
    if(!S.base)exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK\_INIT\_SIZE;
    return OK;
    }
    bool IsEmpty(TranSqstack &S)    /*  判断是否为空栈  */
    {
    if(S.top == S.base)
    return true;
    else
    return false;
    }
    int GetTop(TranSqstack S)    /*  若栈不空，返回S的栈顶元素  */
    {
    if(S.top != S.base)
    return*(S.top - 1);
    }


    int Push(TranSqstack &S,ElemType e)     /*  进栈  */
    {
    if(S.top - S.base >= S.stacksize)
    {
    S.base = (ElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
    if(!S.base)return ERROR;
    S.top = S.base + S.stacksize;
    S.stacksize += STACKINCREMENT;
    }
    *S.top ++ = e;     //元素e压入栈顶，栈顶指针加1 
    return OK;
    }


    int Pop(TranSqstack &S,ElemType e)     /*  弹栈  */
    {
    if(S.top == S.base)return ERROR;
    e = * --S.top;         //栈顶指针减1,将栈顶元素赋给e 
    return e;
    }
    int DestroyStack(TranSqstack &S)     /* 销毁栈S，S不再存在 */
     { 
       free(S.base);
       S.base = NULL;
       S.top = NULL;
       S.stacksize = 0;
       return OK;
     }
     int conversion(TranSqstack &S,long n,int base)     /* 进制转换函数 */
     {   
     	InitStack(S);
        int c,m=0,s\[100\];
        cout<<"("<<n<<")10="<<"("; 
        while (n!=0)
        {
    	//数制转换，结果存入数组s\[m\]    
          
            c=n%base;    
            n=n/base;    
            m++;s\[m\]=c;   //将余数按顺序存入数组s\[m\]中    
        }    
        
        for(int k=m;k>=1;k--)
        {
    	//输出转换后的序列    
           
            if(s\[k\]>=10) //若为十六进制等则输出相对应的字母 
            {
    			Push(S,(char)(s\[k\]+55));
                cout<<(char)(s\[k\]+55);    
            }
            else         //否则直接输出数字 
    		{  
            	Push(S,s\[k\]);
                cout<<s\[k\];    
            }
        }    
        
        cout<<")"<<base<<endl; 
        /*
      while(n > 0)
      {
      //Push(S,digit\[n % base\]);
      //printf("%s",digit\[n % base\]);
      printf("%d",n);
      n /= base;
    }
    */
    	return 0;
    }
    int visit(ElemType c)
    {
    	printf("%d ",c);
    	return OK;
    }
    int StackTraverse(TranSqstack S)
    {
    	int i=0;
    	while(i<=(S.top-S.base)- 1)	/*(S.top-S.bottom)- 1是因为S.top,总是指向队列的队尾*/
    	{
    		visit(S.base\[i++\]);
    	}
    	printf("\\n");
    	return OK;
    }
    int main()
    {
    	TranSqstack MS;
    	int n;
    	scanf("%d", &n);
    	conversion(MS, n, 2);
    	conversion(MS, n, 8);
    	conversion(MS, n, 16);
    	cout<<GetTop(MS);
    	DestroyStack(MS);
    	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
#include <cstdlib>
#include <string>
#include <iostream>
#include <tchar.h>
#include <iostream>
#include <iomanip>
#define MAXQSIZE 10
#define ERROR 0
#define OK 1
using namespace std;
typedef char ElemType;
typedef struct
{
	ElemType *base;
	int front;
	int rear;
}SqQueue;
int InitQueue(SqQueue &Q)
{
	/*构造一个空队列Q*/
	Q.base=new ElemType\[MAXQSIZE\];
	if(!Q.base)exit(ERROR);
	Q.front=Q.rear=0;
	return OK;
}

int QueueLength(SqQueue Q)
{
	/*返回队列的长度*/
	return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

int EnQueue(SqQueue &Q,ElemType e)
{
	/*向队列插入数据(入队）*/
	if((Q.rear+1)%MAXQSIZE==Q.front)
	{
		//尾指针在循环意义上加1后等于头指针，表明队满 
		cout<<"插入数据"<<e<<"错误"<<"因为队满"<<endl; 
		return ERROR;
	}else{
	cout<<"插入数据"<<e<<"成功"<<endl;
	
	Q.base\[Q.rear\]=e;				//新元素插入队尾 
	Q.rear=(Q.rear+1)%MAXQSIZE;		//队尾指针加1 
	return OK;
	}
}

int DeQueue(SqQueue &Q,ElemType &e)
{
	/*从队列中取出数据（出队）*/
	if(Q.front==Q.rear)return ERROR;    //队空 
	e=Q.base\[Q.front\];                  //保存队头元素 
	Q.front=(Q.front+1)%MAXQSIZE;		//队头指针加1 
	return OK;
}

int ShowQueue(SqQueue Q)
{
	SqQueue M;
	if(Q.front==Q.rear)return ERROR;    //队空 
	M=Q;
	while(M.front!=Q.rear)
	{
		cout<<M.base\[M.front\]<<setw(3);
		M.front=(M.front+1)%MAXQSIZE;
	}
	
}
int main()
{
	int i=0;
	char a;
	SqQueue Q;
	InitQueue(Q);
	//1,2,3,4,5，d, e, b 入队
	cout<<"1,2,3,4,5，d, e, b 入队"<<endl;
	char e\[50\]={'1','2','3','4','5','d','e','b'};
	while(e\[i\]!='\\0')
	{
		//cout<<i;
		EnQueue(Q,e\[i\]);
		i++;
	}
	ShowQueue(Q);
	//1,2,3出队
	cout<<endl<<endl<<"1,2,3出队:"<<endl;
	i=0;
	for(int i=0;i<3;i++)
	{
		DeQueue(Q,a);
	}
	ShowQueue(Q);
	//f, g, h, i, i,k ,h 入队
	cout<<endl<<endl<<"f, g, h, i, i,k ,h 入队:"<<endl;
	i=0;
	char c\[50\]={'f','g','h','i','i','k','h'};
	while(c\[i\]!='\\0')
	{
		EnQueue(Q,c\[i\]);
		i++;
	}
	ShowQueue(Q);
	//4,5,d,e 出队
	cout<<endl<<endl<<"4,5,d,e 出队:"<<endl;
	i=0;
	for(int i=0;i<4;i++)
	{
		DeQueue(Q,a);
	}
	ShowQueue(Q);
	//n, o, p入队
	cout<<endl<<endl<<"n, o, p入队:"<<endl;
	i=0;
	char f\[50\]={'n','o','p'};
	while(f\[i\]!='\\0')
	{
		EnQueue(Q,f\[i\]);
		i++;
	}
	ShowQueue(Q);
	return 0;
}

0%