当前位置: 首页 > news >正文

实验报告5(链栈基本操作,数制转换,匹配算法,伴舞问题)

一、实验目的:

1.学会进行链栈的基本操作。

2.进行数制的转换,将十进制整数转换为十六进制数。

3.实现的匹配算法。

4.实现舞伴问题。

二、实验仪器或设备:

操作系统:Windows11

编程环境:Dev-cpp 5.11

三、算法总体设计

(一) 链队列和链栈的基本操作。

(1)链队列初始化

(2)为入队元素分配结点空间,用指针p指向。将新结点数据域置为e,新结点插入到队尾,修改队尾指针。

(3)出队,判断队列是否为空,临时保存队头元素的值。修改头结点指针域指向下一个结点。判断出队元素是否为最后一个元素,若是则将队尾元素重新赋值,指向头结点。释放元头元素的空间。

(1)链栈初始化是构造一个空栈。

(2)为入栈元素分配空间,将新结点数据域置为e,将新结点插入栈顶,修改栈顶指针。

(3)链栈的出栈,判断栈是否为空,将栈顶元素赋给e。临时保存栈顶元素空间,修改栈顶指针,指向新的栈顶元素。释放原栈顶元素空间。

(4)取栈顶元素。

(二)算法数制的转换,将十进制整数转换为十六进制数。

(1) 数据结构定义

(2)初始化栈

(3)入栈操作

(4)出栈操作

(三)实现的匹配算法

(1)链栈的初始化

(2)元素的入栈,元素的出栈,获取栈顶元素,检查栈是否为空。

(3)括号匹配算法

当遇到左括号[或(时,直接将其压入栈中。

当遇到右括号)或]时,程序会检查栈是否为空以及栈顶的左括号是否与当前右括号匹配。如果匹配,则执行出栈操作;否则,设置不匹配标志flag为0。

匹配结果判定:在读取完所有字符后,程序会检查栈是否为空以及是否在整个过程中都保持了匹配状态(即flag保持为1)。只有当栈为空且没有遇到不匹配的情况时,才认为括号是匹配的。

(四)舞伴问题

(1)链式队列的使用,初始化队列,入队操作,出队操作,队列空检查。

(2)文件读取

(3)舞伴配对逻辑

四、实验步骤(包括主要步骤、命令分析等)

(一)  链队列和链栈的基本操作。

//使用链栈

 1 #define MAXSIZE 100
 2 #define OK 1
 3 #define ERROR 0
 4 #define OVERFLOW -2
 5 #include<iostream>
 6 using namespace std;
 7 typedef char ElemType;
 8 typedef int Status;
 9 //链栈 
10 typedef struct StackNode {
11     ElemType data;
12     struct StackNode *next;
13 } StackNode,*LinkStack;
14 Status InitStack (LinkStack &S) {
15     S=NULL;
16     return OK;
17 }
18 Status Push(LinkStack &S,ElemType e) 
19 {StackNode *p = new StackNode;
20 
21     p->data=e;
22     p->next=S;
23     S=p;
24     return OK;
25 }
26 Status Pop(LinkStack &S,ElemType &e) {
27     StackNode*p;
28     if(S==NULL)
29         return ERROR;
30     e=S->data ;
31     p=S;
32     S=S->next;
33     delete p;
34     return OK;
35 }
36 ElemType GetTop(LinkStack S)
37 {
38     if(S!=NULL)
39     return S->data;
40  } 
41  int main()
42  {LinkStack S; 
43  ElemType e;
44      InitStack (S);
45      char a;
46      int i;
47      cout<<"输入5个字母"<<endl; 
48      for(i=1;i<=5;i++)
49      {cin>>a;
50          Push(S,a);
51      }
52 
53      cout<<"取出栈顶元素"<<endl;
54     cout<<GetTop(S)<<endl;    
55      cout<<"取出5个字母"<<endl; 
56          while(S != NULL) {
57         Pop(S,a);
58         cout<<a;
59     }
60      return 0;
61  }

//使用链队列

 1 #define OK 1
 2 #define ERROR 0
 3 #include<iostream>
 4 using namespace std;
 5 typedef char QElemType;  
 6 typedef int Status; 
 7 typedef struct QNode
 8  {
 9      QElemType data;
10      struct QNode *next;
11      
12   } QNode,*QueuePter;
13   
14   typedef struct
15   {
16       QueuePter front;
17       QueuePter rear;    
18   }LinkQueue;
19  Status InitQueue(LinkQueue &Q)
20  {
21      Q.front=Q.rear=new QNode;
22      Q.front->next=NULL;
23      return OK; 
24  }
25  Status EnQueue(LinkQueue &Q,QElemType e)
26  {
27      QueuePter p=new QNode;
28      p->data=e;
29      p->next=NULL;
30 Q.rear->next =p;
31 Q.rear =p;
32 return OK;
33  }
34  Status DeQueue(LinkQueue &Q,QElemType &e)
35  {
36      if(Q.front==Q.rear )
37      return ERROR;
38      QueuePter p=Q.front->next;
39      e=p->data;
40      Q.front ->next=p->next;
41      if(Q.rear ==p)
42      Q.rear=Q.front ;
43      delete p;
44      return OK;
45  
46      
47  }
48  QElemType GetHead(LinkQueue Q)
49  {
50      if(Q.front !=Q.rear )
51      return Q.front ->next->data;
52  }
53  int main()
54  {
55     LinkQueue S;  
56     QElemType e;  
57     InitQueue(S);  
58     char a;  
59     int i;   
60  cout << "输入5个字母" << endl; 
61      for(i=1;i<=5;i++)
62      {cin>>a;
63          EnQueue(S,a);
64      }
65 
66      cout<<"取出栈顶元素"<<endl;
67         if (DeQueue(S, e) == OK) {  
68         cout << e << endl;  
69     } else {  
70         cout << "队列为空,无法取出元素" << endl;  
71     }      
72       cout << "取出并打印剩余4个字母" << endl;  
73             while (DeQueue(S,e) == OK) {  
74         cout << e;  
75     } 
76      return 0;
77  }

(二)将十进制整数转换为十六进制数。

 1 #define MAXSIZE 100
 2 #define OK 1
 3 #define ERROR 0
 4 #define OVERFLOW -2
 5 #include<iostream>
 6 using namespace std;
 7 typedef char ElemType;
 8 typedef int Status;
 9 
10 typedef struct StackNode {
11     ElemType data;
12     struct StackNode *next;
13 } StackNode,*LinkStack;
14 Status InitStack (LinkStack &S) {
15     S=NULL;
16     return OK;
17 }
18 Status Push(LinkStack &S, int e) { 
19     StackNode *p = new StackNode;
20     if (!p)
21         return OVERFLOW;
22     if(e < 10)
23         p->data = '0' + e; 
24     else
25         p->data = 'A' + (e - 10); 
26     p->next = S;
27     S = p;
28     return OK;
29 }
30 Status Pop(LinkStack &S,ElemType &e) {
31     StackNode*p;
32     if(S==NULL)
33         return ERROR;
34     e=S->data ;
35     p=S;
36     S=S->next;
37     delete p;
38     return OK;
39 
40 }
41 int main() {
42     int N;
43     cout<<"输入一个十进制数:"<<endl ;
44     cin>>N;
45     LinkStack S;
46     ElemType e;
47     InitStack(S);
48     while(N) {
49         Push(S,N%16);
50         N=N/16;
51     }
52     cout<<"转化为十六进制为:"<<endl; 
53     ElemType temp;
54     while(S != NULL) {
55         Pop(S,temp);
56         cout<<temp;
57     }
58     cout<<endl;
59     return 0;
60 }

(三)括号的匹配算法

#define OK 1
#define ERROR 0
#include<iostream>
#include <cstring> 
using namespace std;
typedef char ElemType;
typedef int Status;
//链栈 
typedef struct StackNode {ElemType data;struct StackNode *next;
} StackNode,*LinkStack;
Status InitStack (LinkStack &S) {S=NULL;return OK;
}
Status Push(LinkStack &S,ElemType e) 
{StackNode *p = new StackNode;p->data=e;p->next=S;S=p;return OK;
}
Status Pop(LinkStack &S,ElemType &e) {StackNode*p;if(S==NULL)return ERROR;e=S->data ;p=S;S=S->next;delete p;return OK;
}
ElemType GetTop(LinkStack S)
{if(S!=NULL)return S->data;} Status StackEmpty(LinkStack S){return S == NULL ? OK : ERROR;}Status Matching(){LinkStack S; ElemType e; InitStack(S);int flag=1;char ch;while (cin.get(ch)&& ch != '#'){switch(ch){case '[':case '(':Push(S,ch);break;case ')':if(! StackEmpty(S)&&GetTop(S)=='(')Pop(S,e);else flag=0;break;case ']':if(! StackEmpty(S)&&GetTop(S)=='[')Pop(S,e);else flag=0;break; default:  // 可以选择忽略非括号字符,或者根据需求进行处理  break; }      }if( StackEmpty(S)&&flag)return OK;else return ERROR;}int main(){ cout << "请输入包含括号的字符串(以#结束):";  char input[100];  cin.getline(input, 100); // 使用getline读取整行输入,包括空格  // 移除字符串末尾的#(如果输入了#)   
      Status result = Matching();  if (result == OK)  cout << "括号匹配。" << endl;  else  cout << "括号不匹配。" << endl;  return 0;
}

(四)舞伴问题

  1 #define OK 1
  2 #define ERROR 0
  3 #include <iostream>
  4 #include <vector>
  5 #include <fstream>
  6 #include <string>
  7 using namespace std;
  8 typedef int Status;
  9 typedef struct Person {
 10     string name;
 11     char sex;
 12 } Person;
 13 
 14 typedef struct QNode {
 15     Person data;
 16     struct QNode* next;
 17 } QNode, *QueuePtr;
 18 
 19 typedef struct {
 20     QueuePtr front;
 21     QueuePtr rear;
 22 } LinkQueue;
 23 // 初始化队列
 24 Status InitQueue(LinkQueue& Q) {
 25     Q.front = Q.rear = new QNode;
 26     Q.front->next = NULL;
 27     return OK;
 28 }
 29 
 30 // 入队
 31 Status EnQueue(LinkQueue &Q, const Person &e) {
 32     QueuePtr p = new QNode;
 33     if (!p) return ERROR;  // 检查内存分配是否成功
 34     p->data = e;
 35     p->next = NULL;
 36     Q.rear->next = p;
 37     Q.rear = p;
 38     return OK;
 39 }
 40 // 出队
 41 Status DeQueue(LinkQueue& Q, Person& e) {
 42     if (Q.front == Q.rear)
 43         return ERROR;
 44     QueuePtr p = Q.front->next;
 45     e = p->data;
 46     Q.front->next = p->next;
 47     if (Q.rear == p)
 48         Q.rear = Q.front;
 49     delete p;
 50     return OK;
 51 }
 52 
 53 bool QueueEmpty(LinkQueue Q) {
 54     return Q.front == Q.rear && Q.front->next == NULL;
 55 }
 56 
 57 void DancePartner(Person dancer[], int num) {
 58     LinkQueue Mdancers, Fdancers;
 59     InitQueue(Mdancers);
 60     InitQueue(Fdancers);
 61     for (int i = 0; i < num; i++) {
 62         if (dancer[i].sex == 'F')
 63             EnQueue(Fdancers, dancer[i]);
 64         else
 65             EnQueue(Mdancers, dancer[i]);
 66     }
 67     cout << "这个舞者的舞伴是谁:\n";
 68     while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers)) {
 69         Person female, male;
 70         DeQueue(Fdancers, female);
 71         DeQueue(Mdancers, male);
 72         cout << "女士: " << female.name << " 男士: " << male.name << endl;
 73     }
 74     if (!QueueEmpty(Fdancers)) {
 75         Person head;
 76         DeQueue(Fdancers, head);
 77         cout << "第一位没有舞伴的女生是: " << head.name << endl;
 78     } else if (!QueueEmpty(Mdancers)) {
 79         Person head;
 80         DeQueue(Mdancers, head);
 81         cout << "第一位没有舞伴的男士是: " << head.name << endl;
 82     }
 83 }
 84 
 85 vector<Person> readDancersFromFile(const string& filename) {
 86     vector<Person> dancers;
 87     ifstream file(filename.c_str());
 88     if (!file.is_open()) {
 89         cerr << "Error opening file: " << filename << endl;
 90         return dancers;
 91     }
 92     string name;
 93     char sex;
 94     while (file >> name >> sex) {
 95         Person dancer;
 96         dancer.name = name;
 97         dancer.sex = sex;
 98         dancers.push_back(dancer);
 99     }
100     file.close();
101     return dancers;
102 }
103 
104 int main() {
105     string filename = "DancePartner.txt";
106     vector<Person> dancers = readDancersFromFile(filename);
107     DancePartner(dancers.data(), dancers.size());
108     return 0;
109 }

五、结果分析与总结

(1)  链队列和链栈的基本操作:

//链栈

//链队列

(2)进制数转换:

(3)括号的匹配算法

(4)舞伴问题

总结:本次实验旨在通过实践加深对链队列、链栈、数制转换、括号匹配以及舞伴问题等算法的理解和应用。通过动手实现这些算法,我可以更直观地掌握数据结构的基本操作,提升编程能力和问题解决能力...

http://www.hskmm.com/?act=detail&tid=28999

相关文章:

  • 阅读和提问作业1:《构建之法》提问
  • 企业推行OKR中层领导关注的10个关键问题及解决方案
  • 初四夜间/休息日安排
  • AWS自然语言处理技术实战指南
  • 多线程
  • 三级模式
  • abc427
  • 20232320 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • [HarekazeCTF2019]baby_rop2
  • 开个视频网站很烧钱吧
  • 13. Canvas画布
  • 预训练相关的一些概念
  • 2025/10/11 模拟赛总结 - sb
  • 分布式训练的一些知识
  • Visual Studio 2013 Update 4 中文版安装步骤(带TFS拥护)附安装包​
  • 排列
  • 白纷纷副
  • 低秩适配器(LoRA)
  • ROC曲线
  • 10.12~10.18随笔
  • 面向对象的题目
  • P11229 [CSP-J 2024] 小木棍题解
  • [HZOI] CSP-S模拟29
  • 初识pytorch:数据标准化及数据增强的transforms
  • 谈程序员如何做好业务
  • 10.11 CSP-S模拟29 改题记录
  • 二三阶行列式
  • 2025 年 10 月 8 日 语文作业
  • CHAR与VARCHAR深度解析:MySQL字符类型选择指南与性能对比
  • vivo霸榜背后:以技术打赢用户保卫战