Transcript CPSC 111

Review of Class on Nov 23:
1
Chapter 12: Structures and ADTs
Outline
 Declaring Structures
 Accessing a Member in a structure variable
 Initialization of Structures
 The use of typedef
 Self-Referential Structures
 Linear Linked Lists
2
Declaring Structures
How to declare a structure data type?
 Example: a structure type to represent a date:
Components: day, month, year
struct date_str{
int day;
structure tag name
int month;
int year;
members of the structure
};
 This declaration creates the derived date type
struct date_str.
3
Declaring Structures
 How to declare variables of a structure type?
 Declare variables in declaration of a structure type
 struct date_str{
int day;
int month;
int year;
} date1, date2;
 Declare variables “struct str_name variable_list;”
 struct date_str{
int day;
int month;
int year;
};
struct date_str date3, date4;
4
Chapter 12: Structures and ADTs
Outline
 Declaring Structures
 Accessing a Member in a structure variable
 Initialization of Structures
 The use of typedef
 Self-Referential Structures
 Linear Linked Lists
5
Access a member
How to access a member?
 member operator “.”
structure_variable.member_name
 Example:
struct date_str{
int day;
int month;
int year;
} date1, date2;
date1.year = 2000;
data2.year= 2005;
date1.day = date2.day = 10;
date1.month = date2.month = 11;
6
Accessing a Member
How to access a member?
 structure pointer operator ->
access the members of a structure via a pointer.
pointer_to_structure -> member_name
 (*pointer_to_structure).member_name
 Example:
struct date_str *pDate = &date1;
(*pDate).day

pDate->day
7
Chapter 12: Structures and ADTs
Outline
 Declaring Structures
 Accessing a Member in a structure variable
 Initialization of Structures
 The use of typedef
 Self-Referential Structures
 Linear Linked Lists
8
Initialization of Structures
Initialization
 A structure variable can be followed by
an equal sign = and
a list of constants contained within braces
 Example:
struct date_str{
int day;
int month;
int year;
};
struct date_str date={12, 12, 2000};
9
Initialization of Structures
 Initialization
 If there are not enough values, the remaining members are
assigned the value zero.
 Example:
struct student_str{
char last_name[15];
char first_name[15];
int UIN;
int assign[6];
int midterm[3];
int final;
}
strcut student_str s1={“Bush”, “Jenny”, 80002211};
10
Chapter 12: Structures and ADTs
 Summary
 Declaring Structures
 Accessing a Member in a structure variable
 member operator “.”:
o structure_variable.member_name
 structure pointer operator “ -> ” :
o pointer_to_structure -> member_name
 Initialization of Structures
 A structure variable can be followed by
o an equal sign = and
o a list of constants contained within braces
o If there are not enough values, the remaining members
are assigned the value zero.
Read Chapter 12.1 – 12. 6
11
Class on Nov. 30
12
Chapter 12: Structures and ADTs
Outline
 Declaring Structures
 Accessing a Member in a structure variable
 Initialization of Structures
 Self-Referential Structures
 Linear Linked Lists
 The use of typedef
13
include <stdio.h>
int main(void){
struct list{
int data;
struct list *pNext;
} a, b, c;
struct list* p=&a;
a.data=1;
b.data=2;
c.data=3;
a.pNext = &b;
b.pNext = &c;
c.pNext = NULL;
}
while (p!=NULL){
printf("%2d ", p->data);
p = p->pNext;
}
14
Self-Referential Structures
self-referential structures
 structures with pointer members that point to the
structure type containing them.
 Example:
struct list{
int data;
struct list *pNext;
} a, b, c;
member pNext points to the structure type struct list, which
contains pNext as a member 
struct list is a self-referential structure.
15
Self-Referential Structures
Using self-referential structures to implement
linear linked lists
struct list{
int
data;
struct
list
*pNext;
} a, b, c;
a.data=1;
b.data=2;
c.data=3;
a.pNext = &b;
b.pNext = &c;
c.pNext = NULL;
data
pNext
1
2
3
&b
&c
NULL
a
b
c
16
Chapter 12: Structures and ADTs
Outline
 Declaring Structures
 Accessing a Member in a structure variable
 Initialization of Structures
 Self-Referential Structures
 Linear Linked Lists
 The use of typedef
17
Linear Linked Lists
What is linear Linked List?
How to implement linear linked lists
 create a list
 counting and lookup
 insertion
 deletion
18
Linear Linked Lists
What is Linear Linked List?
 data structure hang sequentially.
a head pointer that points to the first element
of the list,
each element points at a successor element,
the last element having a link value NULL.
struct
list{
int
data;
struct
list
data
pNext
1
2
3
&b
&c
NULL
pHead
19
Linear Linked Lists
Linear Linked Lists
 A linked list is a very common data structure.
 It can be used to implement efficient algorithms,
such as sorting, searching.
20
Linear Linked Lists
What is linear Linked List?
How to implement linear linked lists
 create a list
 counting and lookup
 insertion
 deletion
21
Linear Linked Lists
How to implement linear linked lists
 Consider the following list:
data
pHead
data
data
data
data
…………
data
NULL
struct linked_list{
char data;
struct linked_list *pNext;
};
22
Linear Linked Lists
Operations on a linked list
Define functions such that
 create a linked list
from a value of type char
from an array of type char
 counting: the number of elements
 looking up an element
 inserting an element
 deleting an element
23
Linear Linked Lists
struct linked_list{
char data;
struct linked_list *pNext;
};
Operations on a linked list
 create a linked list from a value:
struct linked_list *create_value(char data);
 return the head pointer of a link which contains a single
item; the data field of this item is data.
struct linked_list * pHead;
pHead = create_value(‘A’);
‘A’
NULL
pHead
24
#include <stdio.h>
struct linked_list{
char data;
struct linked_list *pNext;
};
list.h
struct linked_list *create_value(char data);
#include "list.h"
main.c
int main(){
struct linked_list *pHead;
pHead = (struct linked_list *) create_value('A');
…….
}
‘A’
NULL
pHead
#include "list.h"
struct linked_list *create_value(char data){
struct linked_list *pHead = NULL;
pHead = (struct linked_list *) malloc(sizeof(struct linked_list));
pHead->data = data; pHead->pNext = NULL;
return pHead;
}
list.c
25
struct linked_list{
char data;
struct linked_list *pNext;
};
Linear Linked Lists
Operations on a linked list
 create a linked list from an array:
struct linked_list *create_array(char data_array[], int n);
 return the head pointer of a link which contains n items;
the data fields of the items are decided by data_array.
char data_array[]={'a', 'b', 'c', 'd', 'e'};
struct linked_list * pHead;
pHead = create_array(data_array, 5);
‘a’
‘b’
‘c’
‘d’
‘e’
NULL
pHead
26
#include <stdio.h>
list.h
struct linked_list{
char data;
struct linked_list *pNext;
};
struct linked_list *create_array(char data_array[],
int n);
#include "list.h"
main.c
int main(){
struct linked_list *pHead;
char data_array[]={'a', 'b', 'c', 'd', 'e'};
pHead = create_array(data_array, 5);
……
}
struct linked_list *create_array(char data_array[], int n){
struct linked_list *p=NULL, *pHead = NULL;
int i;
if(n==0)
return NULL;
else{
pHead = (struct linked_list *) malloc(sizeof(struct linked_list));
pHead->data = data_array[0];
pHead->pNext = NULL;
p = pHead;
for (i=1; i<n;i++){
p->pNext = (struct linked_list *) malloc(sizeof(struct linked_list));
p->pNext->data = data_array[i];
p->pNext->pNext = NULL;
‘a’
‘b’
‘c’
p = p->pNext;
}
}
return pHead;
}
pHead
list.c
‘d’
‘e’
NULL
27