# 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

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.

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).

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.

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.

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

and then executing two next pointer maneuvers.

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.

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 First(List L);

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);

}

}

/*Position is NULL*/

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)*/

/*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;

}

}

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.

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).

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.

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;

}

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];

}

Linked list representations of two polynomials

typedef struct Node *PtrToNode;

struct Node

{

int Coefficient;

int Exponent;

PtrToNode Next;

};

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

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.

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];

}

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]);

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.

0 条评论

• ### The Note based on Data Structures and Algorithm Analysis in C,CHAPTER 2: ALGORIT

An algorithm is a clearly specified set of simple instructions to be followed to...

• ### The Note based on Data Structures and Algorithm Analysis in C CHAPTER 3 P2

The Note based on Data Structures and Algorithm Analysis in C

• ### 字符串，字节和字符编码

下载一个名为 languages.txt 的文本文件。（下载地址: https://learnpythonthehardway.org/python3/lang...

• ### ABAP如何在调试查看EXPORT/IMPORT 内存数据

These memory IDs can be accessed in the debugger, but the option isn't accessibl...

• ### CodeForces 665B Shopping

B. Shopping time limit per test 1 second memory limit per test 256 megabyt...

• ### Code forces 719A Vitya in the Countryside

A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

• ### hdu----(1950)Bridging signals(最长递增子序列 (LIS) )

Bridging signals Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65536/3...

• ### Codeforces 1291 Round #616 (Div. 2) C. Mind Control（超级详细）

You and your n−1 friends have found an array of integers a1,a2,…,an. You have de...

• ### 论综合 | 是什么让一个数字前端实现硅农开始学习Floorplan 的？

如题，是什么让一个数字前端实现硅农开始学习Floorplan 的？是制造工艺的进步，是实现方法学的被迫更新，是养家糊口生的本能，正可谓：头发落完终不悔，为伊消得...

• ### How to find “hidden” remote jobs using Google Search.

By using a special search operator with Google search, you can find remote jobs ...