List
Objectives Master the concept of data type list Installation linear list, linked list, the operations on the list with a programming language Manipulate the data types list to solve simple problems in practice
Bạn đang xem trước 20 trang tài liệu List, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1
Objectives
Master the concept of data type list
Installation linear list, linked list, the operations
on the list with a programming language
Manipulate the data types list to solve simple
problems in practice.
2/52
Content
Linear list
Concept
Structure
Operations on linear list
Linked List
Concept
Structure
Operations on linked list
3/52
Linear List
The list is a finite sequence of elements of the same
class of any object.
Linear list is a list of its elements are organized
linearly: if n>1 element ai before element ai+1. ai is the
element at position i of the list
4/52
Linear List (cont)
L is a list have n elements (n 0).
L = (a1,a2, ,an)
n is length of the list.
if n = 0:
L is empty
if n1 :
a1 is the first element of the list
an is the last element of the list
5/52
Linear List (cont)
Object can be reperesent one or more in the list.
For example:
1, 1, 2, 3, 5,8,13,21,34,55,89 is the list of fibonaci number
(31,28,31,30,31,30,31,31,30,31,30,31) is the list of days in
month of the year.
6/52
Linear List (cont)
Operators
Init
Get length of the list (count number of element)
Remove element at p from the list
Add x to the list after p
Add x to the list before p
7/52
Linear List (cont)
Operators
Seach whether x element in the list or not?
Check the list is fully or not?
Check the list is empty or not?
Traverse
8/52
Linear List (cont)
Setup by array
Using arrays to store elements of the list.
Each element of the array will store an element of the
list
Consecutive elements of the list is stored in consecutive
elements of array
9/52
10/52
const max =N;
struct List{
Item element[max];
long count;
} L;
Linear List (cont)
Setup by array
11/52
Max is maximum length of the list
List structure consists of two
components
element is an array of elements of the type
of data item
count is storing the last element of the list
Linear List (cont)
Setup by array
12/52
Init empty List
void Init(List &L){
L.count = 0;
}
Linear List (cont)
Setup by array
13/52
Length Function:
Input : L
Output: count
long Length(List L){
return L.count;
}
Linear List (cont)
Setup by array
14/52
isFull Function:
Input : L
Output:
1: L is fully
0: L is not full
int isFull(List L){
if (L.count = = max) return 1;
else return 0;
}
Linear List (cont)
Setup by array
15/52
isEmpty Function:
Input : L
Output:
1: L is empty
0: L is not empty
int isEmpty(List L){
if (L.count = = 0) return 1;
else return 0;
}
Linear List (cont)
Setup by array
16/52
4 8 3 35 10 12 6
4 8 3 10 12 6
Linear List (cont)
Setup by array – Remove p element
17/52
Algorithm:
1: check if the list is not empty and p is only one
element in the list, go to step 2, otherwise stop
2: translational elements in positions p +1, p +2,
... to positions p, p +1 ...
Linear List (cont)
Setup by array – Remove p element
18/52
Delete function
Input:
L
P
q Boolean denote whether remove element
successfully or not?
Output:
q =1 Success
q = 0 Error
Linear List (cont)
Setup by array – Remove p element
19/52
void Delete(List &L, long p, int &q){
int i;
q = 0;
if (p<=L.count){
i = p;
while(i<L.count){
L.element[i] = L.element[i+1];
i++;
}
L.count =L.count -1;
q = 1;
}
}
Linear List (cont)
Setup by array – Remove p element
20/52
4 8 3 35 10 12 6 50
4 8 3 10 12 635 50
Linear List (cont)
Setup by array – Add x after p element
21/52
Algorithm:
1: check if the list is not full and p point to
an element in the list, go to step 2,
otherwise stop.
2: translational elements in positions
L.count, L.count -1 ... to L.count
+1,L.count .. Locations
3: Add x to p position
Linear List (cont)
Setup by array – Add x after p element
22/52
InsertAfter function
Input:
L
P
x is element with Item data
q
Output:
q =1 success
q = 0 error
Linear List (cont)
Setup by array – Add x after p element
23/52
void InsertAfter(List &L, long p,Item x, int &q){
int i;
q = 0;
if (!isFull(L) && (p <= L.count)){
i = L.count+1;
while(i >=p+1){
L.element[i] = L.element[i-1];
i--;
}
L.element[p] = x;
L.count = L.count +1;
q =1;
}
}
Linear List (cont)
Setup by array – Add x after p element
24/52
4 8 3 35 10 12 6 50
4 8 3 10 12 63550
Linear List (cont)
Setup by array – Add x before p element
25/52
Algorithm:
1: check if the list is not full and p
point to an element in the list, go to
step 2, otherwise stop.
2: translational elements in positions
L.count-1, L.count ... to L.count
,L.count +1 .. Locations
3: Add x to p position
Linear List (cont)
Setup by array – Add x before p element
26/52
InsertBefore Function
Input:
L
P
X
q
Output:
q =1 success
q = 0 error
Linear List (cont)
Setup by array – Add x before p element
27/52
void InsertBefore(List &L, long p,Item x, int &q){
int i;
q = 0;
if (!isFull(L) && (p <= L.count)){
i = L.count+1;
while(i >p){
L.element[i] = L.element[i-1];
i--;
}
L.element[p] = x;
L.count = L.count +1;
q =1;
}
}
Linear List (cont)
Setup by array – Add x before p element
28/52
Input:
L
x element
found denote whether x is in the list or not
p denote postion of x in the list incase x in the
list.
Linear List (cont)
Setup by array – Search x
29/52
Output:
Found:
1: if x in the list
0: otherwise
p:
if found =1: p denote x postion
if found =0, p =0;
Linear List (cont)
Setup by array – Search x
30/52
void Search(List &L, item x, int &found,
long &p){
found=0;p=1;
while((!found) && (p<=L.count)){
if (L.element[p] = = x) found =1;
else p++;
}
if(!found) p=0;
}
Linear List (cont)
Setup by array – Search x
31/52
In many problems, need to
manipulate the elements of the list.
Therefore,need to go through the list
from the first element to the end.
Linear List (cont)
Setup by array – Traverse
32/52
Input:
L
Output:
None
void Travese(List &L){
long i = 1;
while(i<=L.count){
Manipulation(L.element[i]);
i++;
}
}
Linear List (cont)
Setup by array – Traverse
33/52
Linked list is a list, each element of its two
components:
Data:
Next: Pointer contains the address of the next element
in list
Linked List
Concept
template
struct List{
Item element;
List *Next;
};
34/52
Linked List (cont)
Stucture
35/52
Next
Linked List (cont)
36/52
Init
Check whether the list is empty or not?
Add element to the list
Remove element from the list
Search
Traverse
Linked List (cont)
Operators
37/52
Init: Head=NULL, Tail=NULL;
void Initial(List *&Head,List *&Tail){
Head=NULL;Tail=NULL;
}
Linked List (cont)
38/52
Input: L
Output: true if empty, false if otherwise
template
// isEmpty funtion
bool IsEmpty(List *Head,List *Tail){
if (Head==NULL) return true;
else return false;
}
Linked List (cont)
Operators
39/52
three cases:
• Add to head of the list
• Add to tail of the list
• Add to position after q element
Linked List (cont)
Add element
Algorithm:
if the list is empty:
11 : Head = p;
12 : Tail = Head;
otherwise
21 : p ->Next = Head;
22 : Head = p ;
40/52
p
Linked List (cont)
Add element head
Algorithm:
if the list is empty:
11 : Head = p;
12 : Tail = Head;
otherwise
21 : Tail ->Next = p;
22 : Tail = p ;
41/52
p
Linked List (cont)
Add element tail
Algorithm:
if ( q != NULL)
1 : p -> Next = q->Next;
2 : q->Next = p ;
42/52
p
Linked List (cont)
Inserted after the element pointed by q
43/52
Two cases:
• Remove head
• Remove element after q in the list
Linked List (cont)
Remove Element
Algorithm:
if (Head != NULL)
1: p = Head; // p is a element need to remove
2:
21 : Head = Head->Next;
22 : delete p
3: if Head=NULL Tail = NULL;
44/52
Linked List (cont)
Remove Head
Algorithm:
if (q!= NULL)
1: p = q->Next;
2: if (p != NULL
21 : q->Next = p->Next;
22 : delete p;
45/52
Linked List (cont)
Remove element after the element pointed by q
Algorithm:
Visit Head
Traverse next elements via Next pointer;
46/52
Linked List (cont)
Traverse
template
void display(List *Head,List *Tail){
List *p;
p=Head;
while (p!=NULL){
coutelement<<" ";
p=p->Next;
}
}
47/52
Linked List (cont)
Traverse
