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