【SEU 数据结构课笔记】 02 - 2021/03/08 - LaTeX Code of Assignment
柳飞飙
% !TeX spellcheck = en_EN-EnglishUnitedKingdom
\documentclass{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{fancyhdr}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{titlesec}
\usepackage{titletoc}
\usepackage{listings}
\usepackage{appendix}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{multirow}
\usepackage{hyperref}
\usepackage{subfig}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{booktabs}
\usepackage[most]{tcolorbox}
\usepackage[a4paper, left=2.5cm, right=2.5cm, top=2.65cm, bottom=2.54cm]{geometry}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newcommand\rem{{\rm rem}}
% set the code style
\RequirePackage{listings}
\RequirePackage{xcolor}
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\lstset{
numbers=left,
frame=tb,
aboveskip=3mm,
belowskip=3mm,
showstringspaces=false,
columns=flexible,
framerule=1pt,
rulecolor=\color{gray!35},
backgroundcolor=\color{gray!5},
basicstyle={\ttfamily},
numberstyle=\tiny\color{gray},
morekeywords={},
keywordstyle=\color{blue},
commentstyle=\color{dkgreen},
stringstyle=\color{mauve},
breaklines=true,
breakatwhitespace=true,
tabsize=4
}
\title{\Huge \bfseries Data Structure (2021 Spring)\\Report for Assignment 2}
\author{\Large $<$ID Number$>$ $<$Name$>$}
\date{\today}
\pagestyle{fancy}
\fancyhf{}
\cfoot{\thepage}
\chead{Data Structure (2021 Spring) - Assignment 2}
\begin{document}
\maketitle
\begin{center}
\begin{tcolorbox}[colback=gray!10, %gray background
colframe=black, % black frame colour
width=12cm, % Use 8cm total width,
arc=1mm, auto outer arc,
boxrule=0.5pt,
]
\textsc{Note}
\textcolor[rgb]{0.1,0.3,0.7}{Teddy van Jerry} is the alias for \textcolor[rgb]{0.1,0.3,0.7}{$<$Name$>$}
in GitHub and CSDN.
\end{tcolorbox}
\end{center}
\section{Problem}
Use Seqlists to merge two arrays $L_a$, $L_b$ (no duplicate elements), sort $L_a$ and $L_b$ in the ascending order. Merge them in $L_c$. Analyze the time and space complexity.
\section{Main Ideas}
To merge two arrays (here I use \texttt{Vector} inherited from \texttt{Heap\_Vector} which I wrote that supports limited functions including \texttt{iterator}s.)
Since $L_a$ and $L_b$ are already sorted, the element of $L_c$ can be chosen from the smaller one of the current unmerged smallest $L_a$ and $L_b$ elements.
Another thing is that it is needed to check if there are duplicate elements. We can not add those elements twice.
Here I use the function \texttt{merge}, which first sorts the two \texttt{Vector}s (actually uses \texttt{quick\_sort\_pro\_safe} defined in \texttt{TVJ\_Sort.h}), then use \texttt{push\_back} to add elements to $L_c$.
\section{Core Code}
\subsection{TVJ\_Sort.h}
See my GitHub repository \textbf{TVJ\_Sort}: \url{https://github.com/Teddy-van-Jerry/TVJ_Sort},
or in my CSDN blog: \url{https://blog.csdn.net/weixin_50012998/article/details/114628102}.\\
Current Version: v2.2 updated in 2021/03/10.
\subsection{Main.cpp}
\begin{lstlisting}[language=C++,escapeinside=``]
/*
* File: Main.cpp
* Project: Data Structure - Assignment 2
* --------------------
*
* @author: Teddy van Jerry
* @licence: The MIT Licence
* @compiler: At least C++/11
*
* @version 1.0 2020/03/10
* - Initial version
*
*/
#include <iostream>
#include <iterator>
#include <random>
#include "TVJ_Sort.h"
#define print(Vec__) \
for (const auto& c : Vec__) \
{ \
std::cout << c << ' '; \
}
/**
* Vector class
* A class inherited from Heap_Vector defined in TVJ_Sort
* that supports iterator and const_iterator
*/
template<typename T>
class Vector : public Heap_Vector<T>
{
using iterator = T*;
using const_iterator = const T*;
public:
Vector(size_t n = 32) : Heap_Vector<T>(n) { }
Vector(const Vector<T>& vec) : Heap_Vector<T>(vec.size())
{
this->content_number = 0; // clear first
for (int i = 0; i != vec.size(); i++)
{
this->push_back(vec[i]);
}
}
inline iterator begin()
{
return &((*this)[0]);
}
inline iterator end()
{
return &((*this)[this->size()]);
}
inline const_iterator cbegin() const
{
return &((*this)[0]);
}
inline const_iterator cend() const
{
return &((*this)[this->size()]);
}
inline bool empty() const
{
return !(cend() - cbegin());
}
inline void clear()
{
this->content_number = 0;
}
void sort()
{
quick_sort_pro_safe(this->begin(), this->end());
}
void pop_back()
{
if(this->size()) this->content_number--;
}
// Using this function will sort this Vector
// and the parameter Vector at the same time.
auto merge(Vector<T>& vec)
{
this->sort();
vec.sort();
Vector<T> merged(this->size() + vec.size());
auto i = this->cbegin(), j = vec.cbegin();
while (1)
{
T to_push_value = 0;
if (i == this->cend())
{
if (j == vec.cend()) break;
else to_push_value = *j++;
}
else
{
if (j == vec.cend()) to_push_value = *i++;
else
{
to_push_value = *i < *j ? *i++ : *j++;
}
}
if (merged.empty() || to_push_value != *(merged.cend() - 1)) merged.push_back(to_push_value);
}
return merged;
}
};
void randomUniqueInt(int start_number, int last_number, unsigned step, Vector<int>& ran)
{
for (int i = start_number; i <= last_number; i += step)
{
ran.push_back(i);
}
std::random_shuffle(ran.begin(), ran.end());
}
int main(int argc, char** argv)
{
Vector<int> La, Lb;
// generate random sequences
randomUniqueInt(-20, 100, 10, La);
randomUniqueInt(-12, 33, 3, Lb);
std::cout << "La: ";
print(La);
std::cout << "\nLb: ";
print(Lb);
// merge
Vector<int> Lc = Lb.merge(La);
std::cout << "\nLc: ";
print(Lc);
return 0;
}
\end{lstlisting}
\section{Result and Analysis}
\subsection{Result}
\begin{figure}[hbtp]
\centering
\includegraphics[width = \linewidth]{Console.jpg}
\caption{Console Output}
\end{figure}
It is apparent that $L_a$ and $L_b$ are merged successfully.
\subsection{Time Complexity}
Here we do not consider the use of \texttt{sort} in function \texttt{merge}. (But we know that the average time complexity of quick sort (here is \texttt{quick\_sort\_pro\_safe}) is $O(n\log n)$.)
Let $n_a$ and $n_b$ denote the \texttt{size} of $L_a$ and $L_b$.
In function \texttt{merge} in \texttt{Main.cpp}, every time the \texttt{while} loop goes, either of the \texttt{iterator}s of \texttt{La} and \texttt{Lb} get incremented by one (\texttt{++}), until the \texttt{while} loop \texttt{break}s when both \texttt{iterator}s go to \texttt{end} (here is the \texttt{const\_iterator} \texttt{cend}).
Therefore, the time used is in proportion to the total size of $L_a$ and $L_b$. Thus the time complexity is
$$O(n_a+n_b)$$
\subsection{Space Complexity}
Here we do not consider the use of \texttt{sort} in function \texttt{merge}. (But we know that the average space complexity of quick sort (here is \texttt{quick\_sort\_pro\_safe}) is $O(\log n)$.)
Let $n_a$ and $n_b$ denote the \texttt{size} of $L_a$ and $L_b$.
In function \texttt{merge} in \texttt{Main.cpp}, the new \texttt{Vector} has to be copied to be assigned (not by a reference), so it can not reach the complexity of $O(1)$ which can be attained by doing so outside of the \texttt{class} directly on \texttt{Lc}.
Therefore, the temporary space used is in proportion to the total size of $L_a$ and $L_b$ (and because we reckon shared elements by $L_a$ and $L_b$ is much smaller than their total \texttt{size}). Thus the space complexity is
$$O(n_a+n_b)$$
\section{Conclusion}
With a simple \texttt{class Vector} using \texttt{template}, we can achieve functions like \texttt{sort} and \texttt{merge}. Having analyzed its time and space complexity, we can have a deeper understanding of \texttt{Seqlist}s.
\section*{Appendix}
~
This assignment is written in \LaTeX.
\LaTeX\ code in my blog:
\url{https://blog.csdn.net/weixin_50012998/article/details/114651347}\\
The Chinese version of the report:
\url{https://blog.csdn.net/weixin_50012998/article/details/114651339}\\
\begin{itemize}
\item GitHub Homepage: \url{https://github.com/Teddy-van-Jerry}
\item CSDN Hoempage:\ \, \url{https://blog.csdn.net/weixin_50012998/article/details/108270307}
\end{itemize}
\end{document}
% Copyright 2021 Teddy van Jerry
报告中文版详见我的博客： 【SEU 数据结构课笔记】 02 - 2021/03/08 - Assignment。
See also
类似资料：