Transcript Document

COS220 Concepts of PLs
AUBG, COS dept
Lecture 04
Components of Programming
Languages, Part III
(Selected Data Structures)
Reference: R.Sebesta, Chapters 5, 6
7/21/2015
Assoc. Prof. Stoyan Bonev
1
Lecture Contents:
• Structures as opposed to Arrays
– Presentation in C++, VB, C#, Java
• List
• Abstract Data Entities
–
–
–
–
7/21/2015
Stack
Queue
Deque
Binary Tree
Assoc. Prof. Stoyan Bonev
2
Structures as opposed to Arrays
Array: a collection of data items of the same type.
Simple data type: Data type used to store a single value.
Structure: A collection of simple variables.
• Arrays are data structures to store a collection of data
items of the same type.
• Structures as opposed to arrays, are data structures to
store collections of related data items that have different
types. The individual component of a structure is called a
member.
7/21/2015
Assoc. Prof. Stoyan Bonev
3
Structures in C++
• l
7/21/2015
Assoc. Prof. Stoyan Bonev
4
Structure definition (declaration)
structure specifier – no storage occupying sample
struct Person
{
char name[20];// string name;
char gender;
int age;
float grade;
};
7/21/2015
Assoc. Prof. Stoyan Bonev
5
Structure definition (declaration)
OR
7/21/2015
Assoc. Prof. Stoyan Bonev
6
Structure definition (declaration)
Applying typedef reserved word
typedef struct
{
char name[20];// string name;
char gender;
int age;
float grade;
} Person;
7/21/2015
Assoc. Prof. Stoyan Bonev
7
Structure definition (declaration)
structure specifier – applying struct reserved word.
struct Date
{
int day, month, year;
};
Template only which does
not occupy storage /memory cells/.8
Assoc. Prof. Stoyan Bonev
7/21/2015
Referencing a structure type
How to define a structure as a variable to be
a scalar, an array or a pointer?
Date
Date
Date
7/21/2015
a, b;
c[20];
*ptr1;
Assoc. Prof. Stoyan Bonev
9
Referencing a structure type
How to define a structure as a variable to be a
scalar, an array or a pointer?
Person John, Mary;
Person ClsCos220a[23];
Person *ptr2;
7/21/2015
Assoc. Prof. Stoyan Bonev
10
Initializing structure variables
Date today = { 25, 09, 2014 };
Person peter = {“Miller”,‘m’, 19, 3.48 };
7/21/2015
Assoc. Prof. Stoyan Bonev
11
Accessing structure members
Direct component selection operator . (period)
a.day=26;
b.month=11;
c[10].year=2014;
Indirect component selection operator ─>
ptr1 = &a;
ptr1─>month = 3;
7/21/2015
Assoc. Prof. Stoyan Bonev
12
Structures within structures
struct Dimension
{ int feet; float inches; };
struct Room
{ Dimension length, width; };
Room kitchen;
kitchen.length.feet = 12;
kitchen.length.inches = 2.4;
kitchen.width.feet = 10;
kitchen.width.inches = 1.8;
7/21/2015
Assoc. Prof. Stoyan Bonev
13
Functions returning structures
struct Point { int x; int y; };
Point makepoint( int xpar, int ypar)
{
Point temp;
temp.x = xpar;
temp.y = ypar;
return temp;
}
void main()
{
Point a, b;
a = makepoint(0,0);
b = makepoint(350, 200);
7/21/2015
}
…
Assoc. Prof. Stoyan Bonev
14
Passing structure variables as
arguments to functions
struct Point { int x; int y; };
struct Rect { Point pt1, pt2; };
bool isPtinRect( Point p, Rect r)
{
return p.x>=r.pt1.x && p.x<=r.pt2.x &&
p.y>=r.pt1.y && p.y<=r.pt2.y ;
}
7/21/2015
Assoc. Prof. Stoyan Bonev
15
Functions with structures as
arguments returning structures
struct Point { int x; int y; };
Point addpoint( Point p1, Point p2)
{
Point temp;
// alternate version
temp.x = p1.x + p2.x;
// p1.x = p1.x + p1.y;
temp.y = p1.y + p2.y;
// p1.y += p2.y;
return temp;
// return p1;
}
void main() { Point a, b, c; a=makepoint(0,0);
b=makepoint(40, 20); c=addpoint(b,makepoint(20, 40));
. . . }
7/21/2015
Assoc. Prof. Stoyan Bonev
16
Parallel arrays and arrays of
structures
Problem: data base for COS220students
• Solution based on parallel arrays:
• Alternate solution: based on array of
structures:
7/21/2015
Assoc. Prof. Stoyan Bonev
17
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Solution based on parallel arrays:
char *name[23];int id[23];double gpa[23];
Three parallel arrays because data items with same
subscript pertain the same student
7/21/2015
name[I] = “Peter”;
id[I]
= 0100245678;
gpa[I] = 3.68;
Assoc. Prof. Stoyan Bonev
18
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Alternate solution: based on array of structures:
struct Stud{char *name; int id; double gpa;};
Stud ar[23];
. . .
ar[I].name = “Peter”;
ar[I].id = 0100245678;
ar[I].gpa = 3.68;
7/21/2015
Assoc. Prof. Stoyan Bonev
19
Pointers to structures
struct Person { char *name, gender; int age;};
Person Mary, family[5], *ps;
for (ps=family;
ps<family+5; ps++)
// or
for (ps=&family[0]; ps<=&family[4]; ps++)
{
(*ps).name = … or
ps->name = …
(*ps).gender = … or
ps->gender = …
(*ps).age = …
or
ps->age = …
}
7/21/2015
Assoc. Prof. Stoyan Bonev
20
Struct Employee
// Definition of struct employee
struct employee
{
int id;
string name;
char gender;
int numDepend;
money rate;
money totWages;
};
7/21/2015
Assoc. Prof. Stoyan Bonev
21
Employee variables
// Define two struct employee variables
employee organist, janitor;
7/21/2015
Assoc. Prof. Stoyan Bonev
22
Anonymous structure
// Definition of anonymous structure
struct
{
int id;
string name;
char gender;
int numDepend;
money rate;
money totWages;
}
organist, janitor;
7/21/2015
Assoc. Prof. Stoyan Bonev
23
9.8 Structs as Operands and
Arguments
• How to do arithmetic and other operations
using structs
• Process entire struct using programmer
defined functions
• Often better to pass an entire structure
rather than individual elements
7/21/2015
Assoc. Prof. Stoyan Bonev
24
Struct Copy or Assignment
• struct copies
Given employee structure
employee organist, janitor;
organist = janitor;
7/21/2015
Assoc. Prof. Stoyan Bonev
25
Structures in VB
• l
7/21/2015
Assoc. Prof. Stoyan Bonev
26
Structure definition (declaration)
structure specifier
Structure Person
Dim name as String
Dim gender As Char
Dim age As Integer
Dim grade As Single
End Structure
7/21/2015
Assoc. Prof. Stoyan Bonev
27
The structure template
• The structure should be globally defined.
• It is recommended The structure template to be
typed outside any Sub or Function body.
• Globally defined structure template makes it
visible in all Subs/Functions that follow the
definition.
7/21/2015
Assoc. Prof. Stoyan Bonev
28
Accessing structure members
Structure Person
Dim name As String,gender As Char, _
age As Integer, grade As Single
End Structure
Direct component selection operator
. (period)
Dim John, Mary As Person
John.name=“Petersen”:Mary.name=“Brown”
John.gender=‘m’
:Mary.gender=‘f’
John.age=19
:Mary.age=21
John.grade=3.45
:Mary.grade=3.87
7/21/2015
Assoc. Prof. Stoyan Bonev
29
Accessing structure members
Structure Person
Dim name As String, gender As Char, _
age As Integer, grade As Single
End Structure
Direct component selection operator
.
(period)
Dim p(10) As Person
p(5).name = "stoyan"
p(5).gender = ‘m’
p(5).age = 59
p(5).grade = 3.55
Console.WriteLine("{0} {1} {2} {3}",_
p(5).name, p(5).gender, p(5).age,
p(5).grade)
7/21/2015
Assoc. Prof. Stoyan Bonev
30
Functions returning structures
Structure Point
Dim x, y As Integer
End Structure
Sub Main()
Dim a, b As Point
a = makepoint(0, 0)
b = makepoint(350, 200)
Console.WriteLine("Point a coordinates are: {0} , {1}", a.x, a.y)
Console.WriteLine("Point b coordinates are: {0} , {1}", b.x, b.y)
Console.ReadLine()
End Sub
Function makepoint(ByVal px As Integer, ByVal py As Integer) As Point
Dim temp As Point
temp.x = px
temp.y = py
Return temp
End Function
7/21/2015
Assoc. Prof. Stoyan Bonev
31
Functions with structures as arguments
returning structures
Structure Point
Dim x, y As Integer
End Structure
Sub Main()
Dim a, b, c As Point
a = makepoint(20, 30)
:
b = makepoint(350, 200)
c = addpoints(a, b)
Console.WriteLine("Point c coordinates are: {0} , {1}", c.x, c.y)
Console.ReadLine()
End Sub
Function makepoint(ByVal px As Integer, ByVal py As Integer) As Point
Dim temp As Point
temp.x = px
:
temp.y = py
:
Return temp
End Function
Function addpoints(ByVal p1 As Point, ByVal p2 As Point) As Point
Dim temp As Point
temp.x = p1.x + p2.x
temp.y = p1.y + p2.y
Return temp
7/21/2015
Assoc. Prof. Stoyan Bonev
End Function
32
Structure Employee
‘ Definition of structure employee
Structure employee
Dim id As Integer
Dim name, gender As String
Dim Salary As Single
End Structure
‘ Definition of two employee variables
Dim organist, janitor As employee
7/21/2015
Assoc. Prof. Stoyan Bonev
33
Accessing Members of a structure
• Members are accessed using the member
access operator, a period .
• For structure variable s and member
variable m to access m you would use the
following:
– Console.Writeline(“{0}”, s.m)
7/21/2015
Assoc. Prof. Stoyan Bonev
34
Accessing Members of a structure
organist.id = 1234
organist.name = “Noel Goddard”
organist.gender = ‘F’
organist.salary = 500.6
organist.salary = organist.salary + 100
organist.salary += 50
7/21/2015
Assoc. Prof. Stoyan Bonev
35
Structures as Operands and
Arguments
• How to do arithmetic and other operations
using structures
• Process entire structure using programmer
defined functions
• Often better to pass an entire structure
rather than individual elements
7/21/2015
Assoc. Prof. Stoyan Bonev
36
Structure Copy or Assignment
• structure copies
Given employee structure
Dim organist, janitor As employee
organist = janitor
7/21/2015
Assoc. Prof. Stoyan Bonev
37
Structures within structures
Structure Dimension
Dim feet As Integer, inches As Double
End Structure
Structure Room
Dim length, width As Dimension
End Structure
Dim kitchen As Room
kitchen.length.feet = 12
kitchen.length.inches = 2.4
kitchen.width.feet = 10
kitchen.width.inches
=Bonev
1.8
7/21/2015
Assoc. Prof. Stoyan
38
Example
Structure FullName
Dim firstName As String
Dim lastName As String
End Structure
Structure FullName
Structure Student
contained, or nested,
Dim name As FullName
inside Student
Dim credits() As Integer
End Structure
7/21/2015
Assoc. Prof. Stoyan Bonev
39
Private Sub btnGet_Click(...) Handle
btnGet.Click
Dim numYears, i As Integer
Dim person As Student
…
person.name.firstName =
InputBox("First Name:")
person.name.lastName =
InputBox("Second Name:")
…
End
Sub
7/21/2015
Assoc. Prof. Stoyan Bonev
40
Passing structure variables as
arguments to functions
Structure Point
Dim x, y As Integer
End Structure
Structure Rect
Dim pt1, pt2 As Point
End Structure
Function isPtInRect( p As Point, r As Rect) As Boolean
Return
p.x >= r.pt1.x AND p.x <= r.pt2.x AND _
p.y >= r.pt1.y AND p.y <= r.pt2.y
End Function
7/21/2015
Assoc. Prof. Stoyan Bonev
41
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Solution based on simple scalar variables
• Solution based on parallel arrays
• Alternate solution: array of structures
7/21/2015
Assoc. Prof. Stoyan Bonev
42
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Suppose that you want to evaluate the exam
grades for 20 students and to display the names of the
students whose scores are above average.
• Using simple variables would mean declaring 20 variables
for the students’ names and 20 variables for the students’
ids and 20 variables for the students’ scores. Very tedious!
• Dim student1 As String, id1 As Integer, score1 As Double
• Dim student2 As String, id2 As Integer, score2 As Double
•
...
• Dim student20 As String, id20 As Integer, score20 As Double
7/21/2015
Assoc. Prof. Stoyan Bonev
43
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Much easier with arrays – one array variable
for the names, and one array variable for the
ids, and one array variable for the scores.
Dim name(19) As String
Dim id(19) As Integer
Dim score(19) As Double
• Much more convenient with array of structures
7/21/2015
Assoc. Prof. Stoyan Bonev
44
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Solution based on parallel arrays:
Dim name(19) As String
Dim id(19) As Integer
Dim score(19) As Double
Three parallel arrays because data items with same
subscript pertain the same student
name(I)
= “Peter”
id(I)
= 0100245678
7/21/2015 score(I)
Prof. Stoyan Bonev
=Assoc.
3.68
45
Parallel arrays and arrays of
structures
Problem: data base for COS220 students
• Alternate solution: array of structures:
Structure Student
Dim name As String, id As Integer
Dim score As Double
End Structure
Dim ar(19) As Student
. . .
ar(I).name = “Peter”
ar(I).id = 0100245678
ar(I).score =Assoc.
3.68
7/21/2015
Prof. Stoyan Bonev
46
Structures in C#
• l
7/21/2015
Assoc. Prof. Stoyan Bonev
47
how to declare and use structs
public struct DayOfYear
{
public int day;
public int month;
public int year;
public DayOfYear(int a, int b, int c)
{
day = a; month = b; year = c;
}
}
7/21/2015
Assoc. Prof. Stoyan Bonev
48
how to declare and use structs
DayOfYear today = new DayOfYear(24, 9, 2014);
DayOfYear day1;
DayOfYear daylast;
daylast = new DayOfYear();
Console.WriteLine();
Console.WriteLine("{0} {1} {2} {0} {1} {2}",
today.day, today.month, today.year);
Console.WriteLine();
7/21/2015
Assoc. Prof. Stoyan Bonev
49
how to declare and use structs
• Structs vs. Classes
• Structs may seem similar to classes, but there are
important differences that you should be aware of. First
of all, classes are reference types and structs are value
types. By using structs, you can create objects that
behave like the built-in types and enjoy their benefits as
well.
• Heap or Stack?
• When you call the New operator on a class, it will be
allocated on the heap. However, when you instantiate a
struct, it gets created on the stack.
7/21/2015
Assoc. Prof. Stoyan Bonev
50
how to declare and use structs
• This example declares a struct with three
members: a property, a method, and a
private field. It creates an instance of the
struct and puts it to use.
7/21/2015
Assoc. Prof. Stoyan Bonev
51
how to declare and use structs
using System;
struct SimpleStruct
{
private int xval;
public int X
{
get
{
return xval;
}
set
{
if (value < 100)
xval = value;
}
}
public void DisplayX()
{
Console.WriteLine("The stored value is: {0}", xval);
}
}
class TestClass
{
public static void Main()
{
SimpleStruct ss = new SimpleStruct();
ss.X = 5;
ss.DisplayX();
}
}
7/21/2015
Assoc. Prof. Stoyan Bonev
52
Structures in Java
• Not supported in Java!
7/21/2015
Assoc. Prof. Stoyan Bonev
53
Introduction to abstract data
structures
• Arrays and Lists are basic
fundamental data structured
entities.
• Stack, Queue, Deque, Binary Tree
are abstract data structured
entities.
• Arrays and Lists serve as building
elements to create abstract data
structures.
7/21/2015
Assoc. Prof. Stoyan Bonev
54
Data Structures: List
7/21/2015
Assoc. Prof. Stoyan Bonev
55
Data Structures: List
• List or a linked list is a data structure that consists of a
sequence of data records such that in each record or node
there is a field that contains a reference (i.e., a link) to the
next record in the sequence.
•
• A linked list whose nodes contain two fields: an integer
value and a link to the next node
• Linked lists as well as arrays provide an easy
implementation for important abstract data structures,
including stacks, queues, associative arrays
7/21/2015
Assoc. Prof. Stoyan Bonev
56
Data Structures: Stack
7/21/2015
Assoc. Prof. Stoyan Bonev
57
Data Structures: Stack
• stack is a last in, first out (LIFO) data structure. A stack
is characterized by only two operations: push and pop.
The push operation adds an item to the top of the stack,.
The pop operation removes an item from the top of the
stack, and returns this value to the caller.
7/21/2015
Assoc. Prof. Stoyan Bonev
58
Data Structures: Queue
7/21/2015
Assoc. Prof. Stoyan Bonev
59
Data Structures: Queue
• A queue is a First-In-First-Out (FIFO) data structure. In a
FIFO data structure, the first element added to the queue
will be the first one to be removed.
7/21/2015
Assoc. Prof. Stoyan Bonev
60
Data Structures: Queue
• A queue
• A priority queue
7/21/2015
Assoc. Prof. Stoyan Bonev
61
Data Structures: Deque
7/21/2015
Assoc. Prof. Stoyan Bonev
62
Data Structures: Deque
• double-ended queue (or shortly deque, pronounced
deck) is a data structure that implements a queue for
which elements can only be added to or removed from the
front (head) or back (tail). It is also often called a headtail linked list.
7/21/2015
Assoc. Prof. Stoyan Bonev
63
Data Structures: Binary Tree
7/21/2015
Assoc. Prof. Stoyan Bonev
64
Data Structures: Binary Tree
• binary tree is a data structure in which each node has at
most two child nodes, usually distinguished as "left" and
"right". Nodes with children are parent nodes. Outside the
tree, there is often a reference to the "root" node (the
ancestor of all nodes)
7/21/2015
Assoc. Prof. Stoyan Bonev
65
Data Structures: Binary Tree
• Traverse strategies:
• Top-Down
– Root
– Top-Down traverse to Left sub tree
– Top-Down traverse to Right sub tree
• Mixed
– Mixed traverse to Left sub tree
– Root
– Mixed traverse to Right sub tree
• Bottom-Up
– Bottom-Up traverse to Left sub tree
– Bottom-Up traverse to Right sub tree
– Root
7/21/2015
Assoc. Prof. Stoyan Bonev
66
Thank You
for
Your attention