程序设计 - zhc
type: channel
link: https://cxsj.yizuodi.cn/author/3/
description: zhc
items: 数据结构期末复习题集8~12
items: 数据结构期末复习题集1~7
items: Query
items: [软工初级实训]中山大学_软工初级实训参考资料
items: [软工初级实训]Meeting
items: [软工初级实训]User
items: [软工初级实训]storage
items: [软工初级实训]Date
items: 最大值最小化
items: Binary Search

数据结构期末复习题集8~12
type: item
date: 2022-01-17T22:00:00+08:00
description: 本文由zhc撰写小测8 - 最短路径 实时评测问题描述：唐僧被妖怪关在迷宫中。孙悟空好不容易找到一张迷宫地图，并通过一个魔法门来到来到迷宫某个位置。假设迷宫是一个n * m的矩阵，它有两种地形，0表示平地，1表示沼泽，孙悟空只能停留在平地上。孙悟空目前的位置在坐标(sx,sy)处，他可以向上下左右四个方向移动。请你帮助孙悟空计算一下，迷宫中是否存在一条路从他所在位置(sx,sy)到达唐僧所在位置(tx,ty)，如果有，请计算出最短的一条路径。输入描述：每个测试样例的第1行是2个正整数n (1≤n≤100)，m (1≤m≤100)，表示迷宫是n * m的矩阵。接下来的n行输入迷宫，每行有m个数字（0或者1），数字之间用一个空格间隔。接下来的1行是4个整数sx,sy,tx,ty，1≤sx,tx≤n，1≤sy,ty≤m，表示孙悟空所在位置为第sx行第sy列，唐僧所在位置为第tx行第tx列。迷宫左上角编号是(1,1)，右下角编号是(n, m)。数据保证(sx,sy)格和(tx,ty)必定为平地，且孙悟空的初始位置(sx, sy)并不在唐僧所在格(tx, ty)。输出描述：输出孙悟空到达唐僧处所需经过的最短路径，如果不能到达，请输出“No”输入样例1：2 20 11 01 1 2 2输出样例1：No输入样例2：4 40 0 0 10 1 0 00 1 0 00 0 0 11 1 3 4输出样例2：5#include <iostream> #include<vector> #include<cstring> using namespace std; int n,m; int near[4][2]={0,1,0,-1,1,0,-1,0}; int d[101][101]; int best[101][101]; int vis[101][101]; void refresh(int x,int y){ for(int i=0;i<4;++i){ int x0=x+near[i][0]; int y0=y+near[i][1]; if(x0<1||x0>n||y0<1||y0>m) continue; if(d[x0][y0]==1&&best[x0][y0]>(best[x][y]+d[x0][y0])){ best[x0][y0]=best[x][y]+d[x0][y0]; } } } int main(){ cin>>n>>m; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ int t; cin>>t; d[i][j]=1-t; best[i][j]=9999; vis[i][j]=0; } } int sx,sy,tx,ty; cin>>sx>>sy>>tx>>ty; if(sx==tx&&sy==ty){ cout<<0; return 0; } best[sx][sy]=0; vis[sx][sy]=1; refresh(sx,sy); while(true){ int min=9999; int x,y; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(d[i][j]==1&&vis[i][j]==0&&min>best[i][j]){ min=best[i][j]; x=i; y=j; } } } if(min==9999) break; if(x==tx&&y==ty) break; vis[x][y]=1; refresh(x,y); } if(best[tx][ty]==9999) cout<<"No"; else cout<<best[tx][ty]; return 0; } 小测9 - 简单哈希 实时评测题目描述使用线性探测法(Linear Probing)可以解决哈希中的冲突问题，其基本思想是：设哈希函数为h(key) = d, 并且假定哈希的存储结构是循环数组, 则当冲突发生时, 继续探测d+1, d+2…, 直到冲突得到解决.例如, 现有关键码集为 {47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；采用线性探测法处理冲突。建哈希表如下：现在给定哈希函数为Hash(key)= key mod m，要求按照上述规则, 使用线性探测法处理冲突.要求建立起相应哈希表，并按要求打印。输入描述仅有一个测试用例, 第1行为整数n与m（1 <= n, m <= 10000）， n代表key的总数, m代表哈希表的长度, 并且令哈希函数为: Hash(key) = key mod m.接下来n行，每行一个整数，代表一个key。Key与key两两不相同 ( …

数据结构期末复习题集1~7
type: item
date: 2022-01-17T21:34:00+08:00
description: 本文由zhc撰写小测1 - 字符串的反转 问题描述：给定一个字符串，你需要颠倒一个句子中每个单词中的字符顺序，同时保留空格和初始单词顺序。输入样例：Let's take the contest输出样例：s'teL ekat eht tsetnoc #include<iostream> using namespace std; // #include<string> int main(){ string s=""; while(cin>>s){ for(int j = s.size()-1 ; j >= 0 ; j--) cout<<s.at(j); cout<<" " ; } return 0; }小测2 - 数一数叶数问题：请你实现下列函数，计算给定二叉树的叶数：#include "BinaryNode.h" int leaves(const BinaryNode* root); #include "BinaryNode.h" int leaves(const BinaryNode* root); //BinaryNode.h #include <iostream> using namespace std; typedef int T; struct BinaryNode{ T data; BinaryNode *left, *right; BinaryNode(T d, BinaryNode *l=NULL, BinaryNode* r=NULL):data(d), left(l), right(r) {}; };//num_leaves.cpp #include "BinaryNode.h" int leaves(const BinaryNode* root){ if(root==NULL) return 0; if(root->left==NULL&&root->right==NULL) return 1; return leaves(root->left)+leaves(root->right); }小测3 - 求两个集合的交集假定用下列顺序结构存储一个集合，集合元素按照从小到大顺序存储：typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; // 线性表占用的数组空间 int last; /*记录线性表中最后一个元素在数组 elem[ ] 中的位置（下标值），空表置为-1*/ } SeqList;请实现下面求集合交集的函数：//LC是LA和LB表示集合的交集void merge(SeqList LA, SeqList LB, SeqList *LC);\\SeqList.h #include "stdio.h" #include "stdlib.h" #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; // 线性表占用的数组空间 int last; /*记录线性表中最后一个元素在数组 elem[ ] 中的位置（下标值），空表置为-1*/ } SeqList;#include"SeqList.h" void merge(SeqList *LA, SeqList *LB, SeqList *LC){ int len1 = LA->last; int len2 = LB->last; int i=0; int j=0; int k=-1; while(true){ while(LA->elem[i]<LB->elem[j]&&LA->elem[i]!=-1) ++i; while(LA->elem[i]>LB->elem[j]&&LB->elem[i]!=-1) ++j; if(i>len1||j>len2||LA->elem[i]==-1||LB->elem[j]==-1) break; if(LA->elem[i]==LB->elem[j]){ ++k; LC->elem[k]=LA->elem[i]; ++i; ++j; } } LC->last=k; }小测4 - 检查一个序列是否构成堆 实时评测问题描述：给定一个整数序列，请检查该序列是否构成堆。问题补充：输入: 第一行是一个整数n(0 < n < 10000)，第二行是n个整数。输出: 如果序列是极小堆，即堆顶是最小元，则输出"min heap"；如果是极大堆，即堆顶是最大元，则输出“max heap”； 否则不是堆，则输出“no”。如果既是极大堆，又是极小堆，则输出“both”。输出包括一行，最后有换行。输入输出格式样例：输…

Query
type: item
date: 2021-10-29T17:34:00+08:00
description: 题目描述We have a set of strings (set A) and a set of queries (set B). Each query is to check whether a string exists in set A or not. If yes, output this string.Your task is to implement the following function:void query(string A[], int n, string B[], int m);Here, n is the number of strings in set A, m is the number of strings in set B. 1<=n,m<=500,000.Submit the function only.输入描述No input.输出描述Output the strings in set B which exist in set A. The output should follow the original order of the strings in set B.提示For example,A[0]=“ABC”, A[1]=“CD”, A[2]=“D”B[0] = “A”, B[1] =“CD”, B[2]=“BC”, B[3]=“ABC”,then you should output:CDABCZHC的答案#include"query.h" using namespace std; #include<iostream> int myhash(const string s,int n){ int hash = 13; int i = 0 ; while(s[i]){ hash += (int)(s[i]); hash =(hash*13)%n; ++i; } return hash%n; } void query(string A[], int n, string B[], int m){ int N=2*n; string hash_A[N]; for(int i = 0 ; i < n ; ++i){ int key = myhash(A[i],N); if(hash_A[key] == "") hash_A[key]=A[i] ; else{ int k = 0; while(hash_A[(key+k*k)%N]!=""){//平方探测法 ++k; } hash_A[(key+k*k)%N]=A[i] ; } } for(int i = 0 ; i < m ; ++i){ int key = myhash(B[i],N); int k = 0; while(hash_A[(key+k*k)%N]!= ""){ if(B[i]==hash_A[(key+k*k)%N]){ cout<<B[i]<<endl; break; } ++k; } } }Yizuodi的答案#include <iostream> using namespace std; int get_hash(const string s,int n){ int hash = 0; for(int i=0;i<s.size();++i){ hash += s[i]-'A'+1; hash = (hash*26)%n; } return hash%n; } void query(string A[], int n, string B[], int m){ string hashtable[2*n]; for(int i = 0 ; i < n ; ++i){ int key = get_hash(A[i],2*n)%(2*n); if(hashtable[key].size() == 0){ hashtable[key]=A[i]; } else{ int j = 0; while(hashtable[(key+j*j)%(2*n)].size() != 0){ ++j; } hashtable[(key+j*j)%(2*n)]=A[i]; } } for(int i = 0 ; i < m ; ++i){ int key = get_hash(B[i],2*n)%(2*n); int j = 0; while(hashtable[(key+j*j)%(2*n)].size() != 0){ if(B[i]==hashtable[(key+j*j)%(2*n)]){ cout<<B[i]<<endl; break; } ++j; } } }

[软工初级实训]中山大学_软工初级实训参考资料
type: item
date: 2021-10-17T17:14:00+08:00
description: CSDN参考中山大学2018年软件工程专业初级实训2017中山大学软件工程初级实训

[软工初级实训]Meeting
type: item
date: 2021-10-17T16:59:00+08:00
description: 温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#ifndef MEETING_H #define MEETING_H #include <vector> #include "Date.cpp" //改了 class Meeting { public: /** * @brief default constructor */ Meeting() = default; /** * @brief constructor with argument */ Meeting(const std::string &t_sponsor, const std::vector<std::string> &t_participator, const Date &t_startTime, const Date &t_endTime, const std::string &t_title) { std::string m_sponsor = t_sponsor; std::vector<std::string> m_participators = t_participator; Date m_startDate = t_startTime; Date m_endDate = t_endTime; std::string m_title = t_title; } /** * @brief copy constructor of left value */ Meeting(const Meeting &t_meeting){ std::string m_sponsor = t_meeting.getSponsor(); std::vector<std::string> m_participators = t_meeting.getParticipator(); Date m_startDate = t_meeting.getStartDate(); Date m_endDate = t_meeting.getEndDate(); std::string m_title = t_meeting.getTitle(); } /** * @brief get the meeting's sponsor * @return a string indicate sponsor */ std::string getSponsor(void) const{ return m_sponsor; } /** * @brief set the sponsor of a meeting * @param the new sponsor string */ void setSponsor(const std::string &t_sponsor){ m_sponsor = t_sponsor; } /** * @brief get the participators of a meeting * @return return a string vector indicate participators */ std::vector<std::string> getParticipator(void) const{ return m_participators ; } /** * @brief set the new participators of a meeting * @param the new participators vector */ void setParticipator(const std::vector<std::string> &t_participators){ m_participators = t_participators ; } /** * @brief add a new participator to the meeting * @param the new participator */ void addParticipator(const std::string &t_participator){ m_participators.push_back(t_participator); } /** * @brief remove a participator of the meeting * @param the participator to be removed */ void removeParticipator(const std::string &t_participator){ std::vector<std::string> ::iterator itor ; for(itor = m_participat…

[软工初级实训]User
type: item
date: 2021-10-17T16:59:00+08:00
description: 温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#ifndef USER_H #define USER_H #include <initializer_list> #include <string> class User { public: /** * @brief the default constructor */ User() = default; /** * constructor with arguments */ User(const std::string &t_userName, const std::string &t_userPassword, const std::string &t_userEmail, const std::string &t_userPhone) { std::string m_name = t_userName; std::string m_password = t_userPassword; std::string m_email = t_userEmail; std::string m_phone = t_userPhone; } /** * @brief copy constructor */ User(const User &t_user) { std::string m_name = t_user.getName(); std::string m_password = t_user.getPassword() ; std::string m_email = t_user.getEmail(); std::string m_phone = t_user.getPhone(); } /** * @brief get the name of the user * @return return a string indicate the name of the user */ std::string getName() const{ return m_name ; } /** * @brief set the name of the user * @param a string indicate the new name of the user */ void setName(const std::string &t_name){ std::string m_name = t_name ; } /** * @brief get the password of the user * @return return a string indicate the password of the user */ std::string getPassword() const{ return m_password; } /** * @brief set the password of the user * @param a string indicate the new password of the user */ void setPassword(const std::string &t_password){ std::string m_password = t_password; } /** * @brief get the email of the user * @return return a string indicate the email of the user */ std::string getEmail() const{ return m_email ; } /** * @brief set the email of the user * @param a string indicate the new email of the user */ void setEmail(const std::string &t_email){ std::string m_email = t_email ; } /** * @brief get the phone of the user * @return return a string indicate the phone of the user */ std::string getPhone() const{ return m_phone ; } /** * @brief set the phone of the user * @param a string indicate the new phone of the user */ void setPhone(const std::string &t_phon…

[软工初级实训]storage
type: item
date: 2021-10-17T16:55:00+08:00
description: 温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#include "Storage.hpp" #include "Path.hpp" #include <fstream> using namespace std; std::shared_ptr<Storage> Storage::m_instance = nullptr; Storage::Storage() { m_dirty = false; readFromFile(); }; bool Storage::readFromFile(void) { ifstream fusers(Path::userPath); ifstream fmeetings(Path::meetingPath); if (!(fusers.is_open() && fmeetings.is_open())){ return false; } string str1; while (getline(fusers, str1)) { string name, password, email, phone; if(str1.size() == 0) { continue; } int len=str1.size(); vector<int>pos; for(int i = 0; i < len ; i++){ if(str1[i] == '"') pos.push_back(i); } for(int i = pos[0]+1 ; i < pos[1] ; i++){ name.push_back(str1[i]); } for(int i = pos[2]+1 ; i < pos[3] ; i++){ password.push_back(str1[i]); } for(int i = pos[4]+1 ; i < pos[5] ; i++){ email.push_back(str1[i]); } for(int i = pos[6]+1 ; i < pos[7] ; i++){ phone.push_back(str1[i]); } User u(name, password, email, phone); m_userList.push_back(u); } fusers.close(); string str2; while (getline(fmeetings, str2)) { string sponsor, participators, startDate, endDate, title; if(str2.size() == 0) { continue; } int len=str2.size(); vector<int> pos; for(int i = 0; i < len ; i++){ if(str2[i] == '"') pos.push_back(i); } for(int i = pos[0]+1 ; i < pos[1] ; i++){ sponsor.push_back(str2[i]); } for(int i = pos[2]+1 ; i < pos[3] ; i++){ participators.push_back(str2[i]); } for(int i = pos[4]+1 ; i < pos[5] ; i++){ startDate.push_back(str2[i]); } for(int i = pos[6]+1 ; i < pos[7] ; i++){ endDate.push_back(str2[i]); } for(int i = pos[8]+1 ; i < pos[9] ; i++){ title.push_back(str2[i]); } vector<string> v_participators; int len2=participators.size(); string parti; for(int i=0;i<len2;i++){ if(participators[i]!='&'){ parti.push_back(participators[i]); } else{ string temp=parti; v_participators.push_back(temp); parti.clear(); } } v_participators.push_back(parti); Date start(startDate); Date end(endDate); Meeting meeting(sponsor, v_participators, start, end, title); m_meetingList.…

[软工初级实训]Date
type: item
date: 2021-10-17T12:22:00+08:00
description: 温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#ifndef DATE_H #define DATE_H #include <initializer_list> #include <string> class Date { public: /** * @brief default constructor */ Date() = default ; /** * @brief constructor with arguments */ Date(int t_year, int t_month, int t_day, int t_hour, int t_minute){ m_year = t_year; m_month = t_month; m_day = t_day; m_hour = t_hour; m_minute = t_minute; } /** * @brief constructor with a string */ Date(const std::string &dateString){ bool ok= true ; if(dateString.size()!=16) ok = false ; else if(dateString[4]!='-'||dateString[7]!='-'||dateString[10]!='/'||dateString[13]!=':') ok = false ; if(ok){ int t = 0; int num = 0; for(int i = 0; i < dateString.size();++i ){ int tmp = (int)dateString[i]; if(tmp>=48 && tmp<=57){ t = 10*t+(tmp-48) ; ++num; } if(num==4){ m_year = t; t = 0 ; } if(num==6){ m_month = t; t = 0 ; } if(num==8){ m_day = t; t = 0 ; } if(num==10){ m_hour = t; t = 0 ; } if(num==12){ m_minute = t; t = 0 ; } } } else{ m_year = 0; m_month = 0; m_day = 0; m_hour = 0; m_minute = 0; } } /** * @brief return the year of a Date * @return a integer indicate the year of a date */ int getYear(void) const{ return m_year ; } /** * @brief set the year of a date * @param a integer indicate the new year of a date */ void setYear(const int t_year){ m_year = t_year ; } /** * @brief return the month of a Date * @return a integer indicate the month of a date */ int getMonth(void) const{ return m_month ; } /** * @brief set the month of a date * @param a integer indicate the new month of a date */ void setMonth(const int t_month){ m_month = t_month ; } /** * @brief return the day of a Date * @return a integer indicate the day of a date */ int getDay(void) const{ return m_day ; } /** * @brief set the day of a date * @param a integer indicate the new day of a date */ void setDay(const int t_day){ m_day = t_day ; } /** * @brief return the hour of a Date * @return a integer indicate the hour of a date */ int getHour(void) const{ return m_hour ; } /** * @…

最大值最小化
type: item
date: 2021-10-04T00:04:00+08:00
description: 题目描述把一个包含n个正整数的序列划分成m个连续的子序列（每个正整数恰好属于一个序列）。设第i个序列的各数之和为S(i)，如何让所有S(i)的最大值尽量小？例如序列1 2 3 2 5 4，划分成3个序列的最优方案为1 2 3 | 2 5 | 4，其中S(1)=6, S(2)=7, S(3)=4，最大值为7；如果划分成1 2 | 3 2 | 5 4，则最大值为9，不如刚才的好。n≤10^6，所有数之和不超过10^9。输入描述可能有多个输入样例。每个样例第一行输入两个整数n和m，第二行输入n个整数。输出描述输出所有子序列划分中子序列和的最大值的最小值。输入样例6 31 2 3 2 5 4输出样例7zhc的code：//最大值最小化 #include<iostream> using namespace std; bool ok(int *data,int num,int groups,int mid);//判断mid是否可以做子序列和的最大值 int main(){ int num;//数字个数 while(cin >> num ){ int groups; //划分数 cin >> groups ; int data[num] ; int sum= 0 ; int min = 0 ;//子序列和的最大值的下界 for(int i = 0 ; i < num ; ++i){ cin>>data[i] ; sum+=data[i] ; if(data[i]>min) min = data[i] ;//子序列和的最大值的下界= max_of_data[i] } int max=sum-groups+1 ;//子序列和的最大值的上界,其余n-1组都只有1个1时 int min_of_max ;//最小的子序列和的最大值 while( min<=max){ int mid = (min+max)/2 ; if(ok(data,num,groups,mid)){ //mid可以做子序列和的最大值时 max=mid-1; min_of_max = mid ; } else min = mid+1 ; //mid不能做子序列和的最大值时 } cout << min_of_max <<endl ; } } bool ok(int *data,int num,int groups,int mid){ int sum = 0 ; int groups0 = 1; //记录按子序列和的最大值为mid时的划分数 for(int i = 0 ; i < num ; ++i){ sum+=data[i] ; if(sum > mid){ //如果sum+data[i]>mid时就 sum=data[i] ; ++groups0 ; } } if(groups0 <= groups) return true ;//组数和小于等于groups，说明可以分组 else return false ; }Yizuodi的答案#include <iostream> using namespace std; bool v(int *data, int size, int partnum, int mid_of_max) //判断mid_of_max是否可以做子序列和的最大值 { int sum = 0; int partnum_new = 1; //记录按子序列和的最大值为mid时的划分数 for (int i = 0; i < size; ++i) { sum += data[i]; if (sum > mid_of_max)//如果sum加上data[i]大于mid_of_max，那么就划分新的子序列 { sum = data[i]; ++partnum_new;//子序列数量+1 } } if (partnum_new <= partnum) return true; //组数和小于等于partnum，说明可以划分出指定子序列 else return false; } int main() { int size, partnum; //整数个数,划分个数 while (cin >> size) { cin >> partnum; int data[size]; //用于存储输入的整数 int sum_of_int = 0; int lowerbound_of_max = 0; //子序列和的最大值的下界 for (int i = 0; i < size; ++i) { cin >> data[i]; sum_of_int += data[i]; if (data[i] > lowerbound_of_max) { lowerbound_of_max = data[i]…

Binary Search
type: item
date: 2021-10-03T23:54:00+08:00
description: 题目描述实现二分查找函数，函数接口如下。#include "binSearch.h" int binSearch(const int s[], const int size, const int target) { // 请将实现代码添加在这里 }size为数组s的实际大小。假定s非递减有序，如果s中存在值为target的元素，则返回最后一次出现的位序号，否则返回-1表示不存在。位序号从0开始计。调用样例int s[8] = {0,1,1,3,3,3,6,6};cout << binSearch(s,8,3) << endl; //输出5cout << binSearch(s,8,4) << endl; //输出-1//"binSearch.h" # ifndef BIN_SEARCH_H # define BIN_SEARCH_H int binSearch(const int s[], const int size, const int target); # endif zhc的answer：//binSearch.cpp int binSearch(const int s[], const int size, const int target) { int bottom = 0 ; int top = size-1 ; int index = -1 ; while(bottom <= top ){ int mid = (bottom+top)/2 ; if( s[mid] > target ) top = mid-1 ; else{ bottom = mid+1 ; if(s[mid] == target) index=mid ; } } return index; }Yizuodi的答案#include "binSearch.h" int binSearch(const int s[], const int size, const int target) { int bottom = 0 ; int top = size - 1 ; int index = -1 ;//默认不存在 while( bottom <= top ){ int mid = (bottom+top)/2 ; if( s[mid] > target ) { top = mid - 1 ; } else { bottom = mid + 1 ; if(s[mid] == target) { index = mid ; } } } return index; }