数据结构与算法分析-C语言(英文版).ppt

文档介绍：CHAPTER 3
Lists, Stacks, and Queues
§1 Abstract Data Type (ADT)
【Definition】Data Type = { Objects } { Operations }
〖Example〗 int = { 0, 1, 2, , INT_MAX, INT_MIN }
{ , , , , , }
【Definition】An Abstract Data Type (ADT) is a data type that anized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations.
§2 The List ADT
Objects: ( item0, item1, , itemN1 )
Operations:
 Finding the length, N, of a list.
 Printing all the items in a list.
 Making an empty list.
 Finding the k-th item from a list, 0  k < N.
 Inserting a new item after the k-th item of a list, 0  k < N.
 Deleting an item from a list.
 Finding next of the current item from a list.
 Finding previous of the current item from a list.
 ADT:
Why after?
1. Simple Array implementation of Lists
§2 The List ADT
array[ i ] = itemi
 MaxSize has to be estimated.
Address
Content
array+i
itemi
array+i+1
itemi+1
……
……
……
……
Sequential mapping
 Find_Kth takes O(1) time.
 Insertion and Deletion not only take O(N) time, but also involve a lot of data movements which takes time.
§2 The List ADT
2. Linked Lists
Address
Data
Pointer
0010
0011
0110
1011
SUN
QIAN
ZHAO
LI
1011
0010
0011
NULL
Head pointer ptr = 0110
ZHAO
QIAN
SUN
LI
ptr
NULL
Initialization:
typedef struct list_node *list_ptr;
typedef struct list_node {
char data [ 4 ] ;
list_ptr next ;
} ;
list_ptr ptr ;
To link ‘ZHAO’ and ‘QIAN’:
list_ptr N1, N2 ;
N1 = (list_ptr)malloc(sizeof(struct list_node));
N2 = (list_ptr)malloc(sizeof(struct list_node));
N1->data = ‘ZHAO’;
N2->data = ‘QIAN’;
N1->next = N2 ;
N2->next = NULL ;
ptr = N1 ;
ZHAO
QIAN
ptr
NULL
Locations of the nodes may
change on different runs.
§2 The List ADT
a1
ptr
NULL
ai
ai+1
an
...
...
Insertion
node
b
temp
 temp->next =
node->next
 node->next = temp
Question: What wil