【SEU 数据结构课笔记】 03 - 2021/03/15 - 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={noexcept},
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 3}
\author{\Large $<$ID Number$>$ $<$Name$>$}
\date{\today}
\pagestyle{fancy}
\fancyhf{}
\cfoot{\thepage}
\chead{Data Structure (2021 Spring) - Assignment 3}
\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 forward lists to merge two sets $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 sets in a forward list, I use \texttt{forward\_list} in the namespace \texttt{tvj} which I wrote that supports functions similar to \texttt{std::forward\_list} 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}, in the debug mode, it checks if the two lists are sorted, if not sorted, it will sort them first. This step was skipped in the release mode.
\section{Core Code}
\subsection{TVJ\_Sort.h}
See my GitHub repository \textbf{TVJ\_Forward\_List}: \url{https://github.com/Teddy-van-Jerry/TVJ_Forward_List},
or in my CSDN blog: \url{https://blog.csdn.net/weixin_50012998/article/details/115029881}.\\
Current Version: v1.1 updated in 2021/03/20.\\
Here I provide function definitions relating to \texttt{merge}.
\subsubsection{sorted}
\begin{lstlisting}[language=C++,escapeinside=``]
template<typename Elem>
bool forward_list<Elem>::sorted(bool is_ascending) const noexcept
{
if (size_ < 2) return true;
for (auto iter = cbegin(); iter + 1 != cend(); ++iter)
{
if (*iter == *(iter + 1)) continue;
if ((*iter < *(iter + 1)) ^ is_ascending) return false;
}
return true;
}
\end{lstlisting}
\subsubsection{sort}
\begin{lstlisting}[language=C++,escapeinside=``]
template<typename Elem>
typename forward_list<Elem>::Node* forward_list<Elem>::_inplace_merge(Node* first_, Node* mid_, Node* last_, bool is_ascending)
{
auto i = first_->succ;
auto j = mid_->succ;
auto pre_end = last_->succ;
auto h = first_;
while (i && i != mid_->succ && j && j != last_->succ)
{
if ((i->data < j->data) ^ !is_ascending)
{
h = h->succ = i;
i = i->succ;
}
else
{
h = h->succ = j;
j = j->succ;
}
}
while (i && i != mid_->succ)
{
h = h->succ = i;
i = i->succ;
}
while (j && j != last_->succ)
{
h = h->succ = j;
j = j->succ;
}
h = pre_end;
return (last_->data < mid_->data) ^ !is_ascending ? mid_ : last_;
}
template<typename Elem>
typename forward_list<Elem>::Node* forward_list<Elem>::_sort2(Node* first, bool is_ascending)
{
if (is_ascending ^ (first->succ->data < first->succ->succ->data))
{
auto tmp = first->succ->data;
first->succ->data = first->succ->succ->data;
first->succ->succ->data = tmp;
}
return first->succ->succ;
}
template<typename Elem>
typename forward_list<Elem>::Node* forward_list<Elem>::_sort(Node* first, size_t bound, bool is_ascending)
{
if (bound == 0) return nullptr;
if (bound == 1) return first->succ;
if (bound == 2) return _sort2(first, is_ascending);
const auto half_bound = bound / 2;
const auto mid_node = _sort(first, half_bound, is_ascending);
const auto last_node = _sort(mid_node, bound - half_bound, is_ascending);
return _inplace_merge(first, mid_node, last_node, is_ascending);
}
template<typename Elem>
void forward_list<Elem>::sort(bool is_ascending)
{
_sort(head, size_, is_ascending);
}
\end{lstlisting}
\subsubsection{merge}
\begin{lstlisting}[language=C++,escapeinside=``]
template<typename Elem>
void forward_list<Elem>::merge(const forward_list& list_, bool is_ascending)
{
if (list_.empty()) return;
// copy the list first otherwise it uses nodes in list_ which is unsafe
forward_list<Elem> new_list = list_;
#ifndef NDEBUG
if (!this->sorted(is_ascending)) this->sort(is_ascending);
if (!list_.sorted(is_ascending)) new_list.sort(is_ascending);
#endif
auto first_1 = this->head;
auto end_1 = this->tail;
auto first_2 = new_list.head;
auto end_2 = new_list.tail;
auto i = first_1->succ;
auto j = first_2->succ;
auto h = this->head;
bool label = true; // true for i, false for j
size_t new_size = 0;
while (i && i != end_1 && j && j != end_2)
{
if (i->data == j->data)
{
h = h->succ = i;
i = i->succ;
j = j->succ;
label = true;
}
else if ((i->data < j->data) ^ !is_ascending)
{
h = h->succ = i;
i = i->succ;
label = true;
}
else
{
h = h->succ = j;
j = j->succ;
}
new_size++;
}
while (i && i != end_1)
{
h = h->succ = i;
i = i->succ;
label = true;
new_size++;
}
while (j && j != end_2)
{
h = h->succ = j;
j = j->succ;
label = false;
new_size++;
}
tail = h->succ;
size_ = new_size;
}
\end{lstlisting}
\subsection{Sample.cpp}
\begin{lstlisting}[language=C++,escapeinside=``]
/*
* File: Sample.cpp
* Project: TVJ_Forward_List
* --------------------------
*
* @author: Teddy van Jerry
* @licence: The MIT Licence
* @compiler: at least C++/11 (tested on MSVC and MinGW)
*
* @version 1.0 2021/03/20
* - initial version
*
*/
#include <iostream>
#include <vector>
#include "TVJ_Forward_List.h"
using namespace std;
using namespace tvj; // tvj::forward_list
#ifndef printForwardList
#define printForwardList(list__) \
for (const auto& c_ : list__) { \
std::cout << c_ << ' '; \
}
#endif
int main()
{
vector<int> vec{ 10,20,24 };
int arr[9] = { 1, 2, 3, 3, 3, 4, 7, 7, 10 };
tvj::forward_list<int> list1, list2(vec.cbegin(), vec.cend()), list3(arr, arr + 8);
list1.push_front(9);
list1.push_back(-12);
list1.push_back(7);
list1.insert_after(list1.begin() + 1, 1024);
cout << "list1: ";
printForwardList(list1);
cout << "\nlist2: ";
printForwardList(list2);
cout << "\nlist3: ";
printForwardList(list3);
cout << "\nlist1 is " << (list1.sorted() ? "sorted" : "not sorted") << endl;
list1.sort();
cout << "list1: ";
printForwardList(list1);
cout << "\nlist1 is " << (list1.sorted() ? "sorted" : "not sorted") << endl;
list3.unique();
cout << "list3: ";
printForwardList(list3);
cout << endl;
cout << "list1: ";
printForwardList(list1);
auto iter = list1.begin();
list1.merge(list3);
cout << "\nlist1: ";
printForwardList(list1);
// back() is the iterator pointing to the last element
// which is the one before end()
list1.insert_after(list1.cbefore_begin(), *(list2.back()));
list1.insert_after(list1.front() + 4, 9, 5);
cout << "\nlist1: ";
printForwardList(list1);
cout << "\nlist1 contains " << list1.count(9) << " \"9\"s" << endl;
list1.assign(list1.find(1024), 2048);
cout << "list1: ";
printForwardList(list1);
list1.link(list2);
cout << "\nlist1: (size:" << list1.size() << ") ";
printForwardList(list1);
// erase [begin + 4, begin + 8)
list1.erase_after(list1.begin() + 4, list1.begin() + 8);
cout << "\nlist1: (size:" << list1.size() << ") ";
printForwardList(list1);
list1.clear();
cout << "\nlist1: (size:" << list1.size() << ") ";
printForwardList(list1);
cout << endl;
return 0;
}
// ALL RIGHTS RESERVED (C) 2021 Teddy van Jerry
\end{lstlisting}
\newpage
\section{Result and Analysis}
\subsection{Result}
\begin{figure}[hbtp]
\centering
\includegraphics[width = .97\linewidth]{MSVC_output.jpg}
\caption{MSVC Output on Visual Studio 2019}
\end{figure}
\begin{figure}[hbtp]
\centering
\includegraphics[width = .97\linewidth]{MinGW_output.jpg}
\caption{MinGW Output on Qt 6.0.0}
\end{figure}
It is apparent that \texttt{list1} and \texttt{list3} are merged successfully.
\newpage
\subsection{\texttt{tvj::forward\_list} description}
As is shown in Figure \ref{structure}, the \texttt{tvj::forward\_list} has \textbf{head} node (the one before the first element, accessible by iterator \textit{before\_begin}), \textbf{tail} node (the one past the end of the list, accessible by iterator \textit{end}). The first element has iterators \textit{begin} and \textit{front} while the last element has iterator \textit{back}. (Their const version has been omitted.)\footnote{This figure was drawn with \textit{Visio Professional} by Teddy van Jerry.}
To make operations concerning the end easier and to support the iterator \texttt{end}, the tail node is one past the last element.
\begin{figure}[htbp]
\centering
\includegraphics[width = \linewidth]{Forward List.pdf}
\caption{Structure for \texttt{tvj::forward\_list} class}
\label{structure}
\end{figure}
\subsection{Time Complexity}
Let us denote $n_1$ as the length of the list \texttt{this} and $n_2$ as the length of the list to be merged.
\subsubsection{Release Mode}
First, the list to be merged has to be copied first because otherwise \texttt{merge} will destroy that list and even worse, when the destructor for that list is called, it will actually \texttt{delete} those nodes in the merged list.
The time complexity of copying is $O(n_2)$.
To merge the two list, the pointer goes through both lists and the time consumed is in proposition to their total size.
Thus, the complexity of merge itself is $O(n_1+n_2)$.
The total time complexity of merge in the release mode is$$O(n_1+n_2).$$
\subsubsection{Debug Mode}
In addition to the actions done in the release mode, the debug mode has to check whether they are sorted, i.e. iterating through both lists. This time complexity is $O(n_1+n_2)$.
If they are not sorted, either of them can call the \texttt{sort} function (actually using the merge sort), which has the time complexity of $O(n\log n)$.
Thus, the best time complexity is $$O(n_1+n_2)$$ and the worst is $$O(n_1\log n_1 + n_2\log n_2).$$
\subsection{Space Complexity}
Copying, checking whether sorted, sorting and merging all use almost no temporary space thus the space complexity is $$O(1).$$
\section{Conclusion}
The achievement of merging is not that difficult, but to write a complete \texttt{forward\_list} is really demanding and time-consuming. It takes me many days' efforts to write a simple class with a mere more than 1000 lines, during which I have a deeper understanding of inner class, exception throw and iterators. I also learn a lot from the STL code. Its construction is really awesome, for example the implementation of \texttt{sort} inspires me a lot.
As the foundation of data structure, the through insight into \texttt{forward\_list} gives me the opportunity to explore more about the miracle of data structure!
\section*{Appendix}
~
This assignment is written in \LaTeX.
\LaTeX\ code in my blog:
\url{https://blog.csdn.net/weixin_50012998/article/details/115032776}\\
The Chinese version of the report:
\url{https://blog.csdn.net/weixin_50012998/article/details/115032759}\\
\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 数据结构课笔记】 03 - 2021/03/15 - Assignment。
See also
类似资料：