diff options
| -rw-r--r-- | assignment3.tex | 43 |
1 files changed, 36 insertions, 7 deletions
diff --git a/assignment3.tex b/assignment3.tex index 29d6fae..ffaa2af 100644 --- a/assignment3.tex +++ b/assignment3.tex @@ -62,7 +62,38 @@ Obviously, \texttt{enqueue} and \texttt{empty} need constant time. The \texttt{dequeue} method is in $\pazocal O(n)$ where $n$ is the size of \texttt{s1} or \texttt{q}: every element needs to popped and pushed twice, which can be done in constant time. - \item %todo + \item Using a circular buffer: + + \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c} + typedef struct dequeue { + size_t head; + size_t tail; + int* array; + size_t size; + } dequeue; + + void enqueueFront(dequeue q, int e) { + q.array[q.head] = e; + q.head = (q.head - 1) % q.size; + } + + void enqueueEnd(dequeue q, int e) { + q.array[q.tail] = e; + q.tail = (q.tail + 1) % q.size; + } + + int dequeueFront(dequeue q) { + q.head = (q.head + 1) % q.size; + return q.array[q.head]; + } + + int dequeueEnd(dequeue q, int e) { + q.tail = (q.tail - 1) % q.size; + return q.array[q.tail]; + } + \end{minted} + + Obviously, we can lose data with this when the array is full. For this should be checked in the \texttt{enqueue} methods, and if necessary more space should be allocated for \texttt{q.array}. I did not include that in the example since it's not the point and a straightforward addition. \item We could use doubly-linked circular unsorted lists, say \texttt{l1} and \texttt{l2}. Then simply remap: @@ -78,10 +109,9 @@ \item \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c} List* reverse(List* list, int n) { - int i; Item prev = list.head Item cur = prev.next; - for (i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { Item next = cur.next; cur.next = prev; prev = cur; @@ -90,13 +120,12 @@ } \end{minted} - \item %todo + \item We could implement \texttt{allocate-object} as \texttt{push} and \texttt{free-object} as \texttt{pop}. This will always occupy one block of memory (i.e. never different blocks spread over the memory). \item \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c} int max(int* list, int m) { - int i; int max = INT_MIN; - for (i = 0; i < m; i++) + for (int i = 0; i < m; i++) if (list[i] > max) max = list[i]; return max; @@ -110,7 +139,7 @@ \begin{minipage}{\linewidth} \centering \footnotesize - \begin{tabular}{| l | l | l | l | l |}\hline + \begin{tabular}{| r | l | l | l | l |}\hline & 12,44,13 & 88,23,94 & 11,39,20,16 & 5 \\\hhline{|=|=|=|=|=|} 0 & & & \textbf{20} & 20 \\\hline 1 & & & & \\\hline |