Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Course Outlines
• Basic data structures and abstract data types (ADT)
...

• Searching algorithms
• Sorting algorithms
(Selection Sort, Bubble Sort, Insertion Sort, Quick Sort,
Merge Sort)

2

Pointer and struct
• For example, consider the following structure for storing
information about an airline passenger
...

• We create an enumerated type to handle meal preferences
enum MealType { NOPREF, REGULAR, LOWFAT, VEGETARIAN };
struct Passenger
{ string name;
// passenger name
MealType mealPref;
// meal preference
string freqFlyerNo;
// the passenger’s freq
...
Let us declare and
initialize a variable named “pass” of this type
...

• For example, suppose that in our airline system we encounter
a new passenger
...
Let p be a pointer to a
Passenger structure
...
mealPref
...
mealPref
complex objects like structures are often allocated
dynamically, C++ provides a shorter way to access members
using the “->” operator
...
member;
4

Pointer and struct, cont
...

Passenger *p;
p = new Passenger;
// p points to the new
Passenger
p−>name = "Pocahontas"; // set the structure
members
p−>mealPref = REGULAR;
p−>freqFlyerNo = "NONE";
5

Some Possible Data structures for a linear
collection
• fixed-size array (static array)
– capacity decided at compile-time
– size may be less than or equal to the capacity
• dynamic array
– capacity decided at run-time
– size may be less than or equal to the capacity
– need to learn about pointers and the heap
• linked list
– capacity and size are always the same
– capacity changes as needed during program
execution
– also uses pointers and the heap

linked List
• A linked list is a collection of nodes; each node has
– zero or more data fields and
– one or more link or pointer fields
...

– With each node we store the address of location of the
next node

7

Singly Linked Lists
• In a singly linked list, each node has exactly one pointer field
...

• The first and last nodes of a linked list are called the head and
tail of the list, respectively
...

 The first contains the user’s data
...

struct NodeType
{
ItemType info;
NodeType* next;
};
10

Unsorted singly linked List, cont
...

struct NodeType
{
ItemType info;
NodeType* next;
};
NodeType*
int

listData;
length;

Note: replace ItemType by int, char, float, …

11 11

LINKED LIST operations
void create ( ) ;
int

LengthIs ( ) ;

void

MakeEmpty ( ) ;

bool

IsFull (NodeType*

void

InsertItem ( ItemType

item ) ;

void

DeleteItem ( ItemType

item ) ;

void

FindItem(ItemType item, bool &found,

location) ;

NodeType* currentPos);

12 12

Implementation
1- implement Create of Constructor & LengthIs
and LengthIs
Void create ( )
{
length = 0 ;
listData = NULL;
}
int LengthIs ( )
{
return length;
}
13 13

Implementation of
2- implement IsFull Function IsFull()
Bool IsFull(NodeType* location)
{
if(location == NULL)
{
return true;
}
else
return false;
}

14

3- implement InsertItem
“Insertion to the Front of a Singly Linked List”
 In the array-based implementation a new item was
arrayimplementation,
inserted at the end of the list because that was the
easiest place to put it
...


15

3- implement InsertItem,an Unsorted List
Inserting ‘B’ into cont
...

Step 1: We first create a new node
item

Nodetype* location;
location = new NodeType;

‘B’

location

length
listData

3
‘X’

‘C’

‘L’

17

3- implement InsertItem, cont
...

Step 3: set its next link to point to the current head of the list
...

Step 4: We then set listData (head) to point to the new node
...

Step 5: increment length
...

Void InsertItem ( ItemType item )
{
NodeType* location ;
location = new NodeType;
if (IsFull(location ))
cout<< "the memory is full";
else
{
location->info = item ;
location->next = listData ;
listData = location ;
length++ ;
}
}

22 22

The Function DeleteItem()
4- implement delete
 To delete an item,
1
...


2
...

node
 That is, we must change the next data member of the
previous node to the next data member of the one
being deleted
...



When the item is found , one pointer points to the node
containing the item to be deleted

 and the other pointer points to the previous node
...


 Removing the first node is a special case because we must change the
head pointer to the list (listData)
...

4- implement delete,of DeleteItem()
void DeleteItem(ItemType item)
{
NodeType* preLocation = NULL;
NodeType* location = listData;
if(item == location->info)
// delete first node
listData = location->next;
else
{
do
{
preLocation = location;
location = location->next;
if (location== NULL)
{
cout<< item <<" not found";
return;
}
} while(item != location->info);
//Delete node at location
preLocation->next = location->next;
}
delete location;
length--;
}

25

Implementation of Function MakeEmpty
5- implement MakeEmpty
Remove all nodes in the list
Void MakeEmpty( )
{
NodeType* tempPtr;
while(listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
Length--;
}
}

26

Implementation of RetrieveItem()
6- implement FindItem
The Function FindItem()
 The algorithm for the linked implementation is the
same as for the array-based implementation
...

 The element is found, in this case the element
is found and currentPos refers to the location of
item
...

Void RetrieveItem(ItemType item, bool& found,
NodeType* currentPos)
//Pre: Key member of item is initialized
...

{
bool moreToSearch ;
currentPos = listData;
found = false ;
moreToSearch = ( currentPos != NULL ) ;
28 28

Implementation of RetrieveItem()
6- implement FindItem, cont
...

Indeed, it is time consuming to remove any node other
than the head in a singly linked list, since we do not
have a quick way of accessing the node immediately
preceding the one we want to remove
...
For such applications, it
would be nice to have a way of going both directions in
a linked list
...
It is
the doubly linked list
...

• a node in a doubly linked list stores two pointers, a next link
and a prev link, which point to the next node in the list and
the previous node in the list, respectively

---