The Note based on Data Structures and Algorithm Analysis in C CHAPTER 3 P1

The Note based on Data Structures and Algorithm Analysis in C

CHAPTER 3: Lists, Stacks, and Queues - Intro && List

1.1.Abstract Data Types (ADTs)

Definition:

An abstract data type (ADT) is a set of objects together with a set of operations.

Objects such as lists, sets, and graphs(and class in C++), along with their operations, can be viewed as ADTs, just as integers, reals, and booleans are data types. Integers, reals, and booleans have operations associated with them, and so do ADTs. For the set ADT, we might have such operations as add, remove, size, and contains. Alternatively, we might only want the two operations union and find, which would define a different ADT on the set.

2.1. The list ADT

Definition:

We will deal with a general list of the form A0, A1, A2, …, AN-1. We say that the size of this list is N. We will call the special list of size 0 an empty list.

For any list except the empty list, we say that Ai follows (or succeeds) Ai-1 (i < N)

and that Ai-1 precedes Ai (i > 0). The first element of the list is A0, and the last element

is AN-1.

Associated with these “definitions” is a set of operations that we would like to perform

on the List ADT.( PrintList && MakeEmpty, Find, Insert && Delete, Next && Previous….)

2.2. Simple Array Implementation of Lists

All these instructions can be implemented just by using an array. Although arrays are created with a fixed capacity, the vector class, which internally stores an array, allows the array to grow by doubling its capacity when needed.

An array implementation allows printList to be carried out in linear time, and the

findKth operation takes constant time, which is as good as can be expected. However,

insertion and deletion are potentially expensive, depending on where the insertions and

deletions occur. In the worst case, inserting into position 0 (in other words, at the front

of the list) requires pushing the entire array down one spot to make room, and deleting

the first element requires shifting all the elements in the list up one spot, so the worst

case for these operations is O(N).

2.3. Simple Linked Lists

In order to avoid the linear cost of insertion and deletion, we need to ensure that the list is not stored contiguously, since otherwise entire parts of the list will need to be moved.

èThe linked list: The linked list consists of a series of nodes, which are not necessarily adjacent in memory. Each node contains the element and a link to a node containing its successor. We call this the next link. The last cell’s next link points to nullptr.

Figure 2.3.1 A linked list

To execute printList() or find(x), we merely start at the first node in the list and then traverse the list by following the next links. This operation is clearly linear-time. (although, the constant is likely to be larger than if an array implementation were used)

The findKth operation is no longer quite as efficient as an array implementation; findKth(i) takes O(i) time and works by traversing down the list in the obvious manner.(however, don’t worry)

The delete method can be executed in one next pointer change.

Figure 2.3.2 Deletion from a linked list

The insert method requires obtaining a new node from the system by using a new call

and then executing two next pointer maneuvers.

Figure 2.3.3 Insertion from a linked list

The special case of adding to the front or removing the first item is thus a constant time operation, presuming of course that a link to the front of the linked list is maintained. The special case of adding at the end (i.e., making the new item the last item) can be

constant-time, as long as we maintain a link to the last node.

However, removing the last item is trickier, because we have to find the next-to-last item, change its next link to nullptr, and then update the link that maintains the last node. In the classic linked list, where each node stores a link to its next node, having a link to the last node provides no information about the next-to-last node. (unidirectional ) So,We have every node maintain a link to its previous node in the list.

Figure 2.3.4 Doubly linked list

2.4. vector and list in the STL – some details in the program design

The C++ language includes, in its library, an implementation of common data structures. This part of the language is popularly known as the Standard Template Library (STL). The List ADT is one of the data structures implemented in the STL.

//declear the linked list(in the .h file)

#ifndef _List_H

struct Node;

typedf struct Node *PtrToNode;

typedf PtrToNode List;

typedf PtrToNode Position;

List MakeEmpty(List L);

int IsEmpty(List L);

in IsLast(Position P, List L);

Position Find(Element, List L);

void Delete(ElementType X, List L);

Position FindPrevious(ElementType X, List L);

void Insert(ElementType X, List L, Position P);

void DeleteList(List L);

Position Header(List L);

Position First(List L);

Position Advance(Position P);

ElementType Retrieve(Position P);

#endif /* _List_H */

/* Place in the implementationb file */

struct Node{

ElementType Element;

Position Next;

};

/*return true if L is empty*/

int

IsEmpty(List L){

return L -> Next == NULL;

}

/*return true if P is the last position in the list L*/

/*parameter L is unused in this implemention*/

int

IsLast(Position P, List L){

return P -> Next == NULL;

}

/*return the position of x in L, return NULL if not found*/

Position

Find(ElementType X, List L){

Position P;

P = L -> Next;

while(P != NULL && P -> Element != X)

P = P -> Next;

return P;

}

/*delete the first occurrence of X in the list L*/

/*assume the use of the header node*/

void Delete(ElementType X, List L){

Position P, TmpCell;

P = FindPrevious(X, L);

if(!IsLast(P, L)){

TmpCell = P -> Next;

p -> Next = TmpCell -> Next;//by pass the delete node

free(TmpCell);

}

}

/*if X is not found, then next filed returned*/

/*Position is NULL*/

/*Assumes a header*/

Position

FindPrevious(ElementType X, List L){

Position P;

P = L;

While(P -> Next != NULL && P -> Next -> Element != X)

P = P -> Next;

return P;

}

/*Insert (after legal position P)*/

/*Header implementation assumed*/

/*parameter L is unused in this implementation*/

void

Insert(ElementType X, List L, Position P){

Position TmpCell;

TmpCell = malloc(sizeof(struct Node));

if(TmpCell == NULL)

FatalError("Out of space!!!");

TmpCell -> Element = X;

TmpCell -> Next = P -> Next;

P -> Next = TmpCell;

}

/*Incorrect DeleteList algorithm*/

void

DeleteList(List L){

Position P;

P = L -> Next; //header assumed

L -> Next = NULL;

while(P != NULL){

free(P);

P = P -> Next;//this point is illegal!!!![P is NULL]

}

}

/*Correct DeleteList algorithm*/

void

DeleteList(List L){

Position P, Tmp;

P = L -> Next; //header assumed

L -> Next = NULL;

while(P != NULL){

Tmp = P -> Next;

free(P);

P = Tmp;

}

}

2.5. Doubly linked list

Sometimes it is convenient to traverse lists backwards. The standard implementation does not help here, but the solution is simple. Merely add an extra field to the data structure, containing a pointer to the previous cell. The cost of this is an extra link, which adds to the space requirement and also doubles the cost of insertions and deletions because there are more pointers to fix. On the other hand, it simplifies deletion.

Figure 2.5.1 A Doubly linked list

2.6. Circularly Linked List

A popular convention is to have the last cell keep a pointer back to the first. This can be done with or without a header (if the header is present, the last cell points to it), and can also be done with doubly linked lists (the first cell's previous pointer points to the last cell).

Figure 2.6.1 A Circularly Linked List

2.7. Examples

The first is a simple way to represent single-variable polynomials. The second is a method to sort in linear time, for some special cases. Finally, we show a complicated example of how linked lists might be used to keep track of course registration at a university.

2.7.1. The Polynomial ADT

We can define an abstract data type for single-variable polynomials (with nonnegative exponents) by using a list. Let f (x) = i=0NAiXi . If most of the coefficients

ai are nonzero, we can use a simple array to store the coefficients.

// declear by array

typedef struct{

int CoeffArray[MaxDegree + 1];

int HighPower;

}* Polynomial

//initialize

void

ZeroPolynomial(Polynomial Poly){

int i;

for(i = 0; i <= Maxdegree; i++)

Poly -> CoeffArray[i] = 0;

Poly -> HighPower = 0;

}

//addition

void

AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum){

int i;

ZeroPolynomial(PolySum);

PolySum -> HighPower = Max(Poly1 -> HighPower, Poly2 -> HighPower);

for(i = PolySum -> HighPower; i >= 0; i--){

PolySum -> CoeffArray[i] = Poly1 -> CoeffArray + Poly2 -> CoeffArray;

}

}

//multiplication

void

MultPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd){

int i, j;

ZeroPolynomial(Polyprod);

PolyPord -> Highpoweer = Poly1 -> HighPower + Poly2 -> HighPower;

if(PolyProd -> HighPower > MaxDegree)

error("Exceed array size");

else

for(i = 0; i <= Poly1 -> HighPower; i++)

for(j = 0; j <= Poly2 -> HighPower; j++)

PolyProd -> CoeffArray[i + j] = Poly1 -> CoeffArray[i] + Poly1 -> CoeffArray[j];

}

Figure 2.7.1.1 Linked list representations of two polynomials

Linked list representations of two polynomials

//declear by linked list

typedef struct Node *PtrToNode;

struct Node

{

int Coefficient;

int Exponent;

PtrToNode Next;

};

typedef PtrToNode Polynomial; /*Node sorted by exponent*/

2.7.2. Radix Sort

A second example where linked lists are used is called radix sort (card sort).

If we have n integers in the range 1 to m (or 0 to m - 1) , we can use this information to obtain a fast sort known as bucket sort. We keep an array called count, of size m, which is initialized to zero. Thus, count has m cells (or buckets), which are initially empty. When ai is read, increment (by one) count[ai]. After all the input is read, scan the count array, printing out a representation of the sorted list. This algorithm takes O(m + n). If m = Θ(n), then bucket sort is O(n).

Suppose we have 10numbers, in the range 0 to 999, that we would like to sort. In general, this is n numbers in the range 0 to np- 1 for some constant p. Obviously, we cannot use bucket sort; there would be too many buckets. The trick is to use several passes of bucket sort. The natural algorithm would be to bucket-sort by the most significant "digit" (digit is taken to base n), then next most significant, and so on. That algorithm does not work, but if we perform bucket sorts by least significant "digit" first, then the algorithm works.

Figure 2.7.2.1 Buckets after first step of radix sort

Figure 2.7.2.2 Buckets after Second step of radix sort

Figure 2.7.2.3 Buckets after the last pass of radix sort

The running time is O(p(n + b)) where p is the number of passes, n is the number of elements to sort, andb is the number of buckets. In our case, b = n.

using namespace std;

//get the maximum of the array

int getMAX(int a[], int length){

int max = a[0];

for (int i = 0; i < length; i++)

if (a[i] > max)

max = a[i];

return max;

}

//get the minimum of the array

int getMIN(int a[], int length) {

int min = a[0];

for (int i = 0; i < length; i++)

if (a[i] < min)

min = a[i];

return min;

}

//sorting by dight bits

void Sort(int a[], int length, int digit) {

int *result = new int[length]; //temp array

int bucket[10] = { 0 }; //0-9 bucket

//counting

for (int i = 0; i < length; i++)

bucket[(a[i] / digit) % 10]++;

//Counts the number of Numbers in each bucket after the array is assigned to the bucket

for (int i = 1; i < 10; i++)

bucket[i] += bucket[i - 1];

//Converts the number of digits in each bucket to the index of the last digit in each bucket

for (int i = length - 1; i >= 0; i--){

result[bucket[(a[i] / digit) % 10] - 1] = a[i];

bucket[(a[i] / digit) % 10]--;

}

//Assigns Numbers from the original array to the secondary array result

for (int i = 0; i < length; i++)

a[i] = result[i];

}

//Radix Sort

void RadixSort(int a[], int length) {

int MAX = getMAX(a, length);

int MIN = getMIN(a, length);

for (int i = 0; i < length; i++)//Handle case that negative Numbers in an array cannot be sorted directly,

a[i] -= MIN; //make sure each element is a natural number

for (int digit = 1; MAX / digit > 0; digit *= 10) //digit express bits

Sort(a, length, digit); //arrange digit bit

for (int i = 0; i < length; i++)

a[i] += MIN;

}

int main() {

int a[N] = { 7, 50, 1, 4, 32, 7, 9, 5, 25, 6 };

int length = sizeof(a) / sizeof(a[0]);

RadixSort(a, length);

for (int i = 0; i < N; i++)

cout << a[i] << " ";

cout << endl;

system("pause");

return 0;

}

2.7.3. Multilists

Our last example shows a more complicated use of linked lists. A university with 40,000 students and 2,500 courses needs to be able to generate two types of reports. The first report lists the class registration for each class, and the second report lists, by student, the classes that each student is registered for.

What is needed is a list for each class, which contains the students in the class. We also need a list for each student, which contains the classes the student is registered for. As the figure shows, we have combined two lists into one. All lists use a header and are circular.

Using a circular list saves space but does so at the expense of time. In the worst case, if the first student was register for every course, then every entry would need to be examined in order to determine all the course names for that student.

Figure 2.7.3.1 Multilist implementation for registration problem