TS. Lê Minh Trung ThS Lương Trần Ngọc Khiết Khoa Công nghệ Thông tin, Đại học Sư phạm TP. HCM
Danh sách (List)
Sử dụng mảng Sử dụng con trỏ Danh sách liên kết đôi
Thiết kế Class List
const int MAX= 20;
template
List(void); ~List(void); int GetSize(); //trả về số phần tử của list bool IsEmpty(); //kiểm tra list có rỗng không bool IsFull(); //kiểm tra xem list có đầy không void SetItem(int pos, const T& item); //thiết lập giá trị item cho phần tử thứ pos T GetItem(int pos); //truy cập phần tử có vị trí pos void Insert(const T &item); //thêm vào vị trí đầu tiên void InsertAt(int pos, const T& item); //thêm item vào vị trí pos void Remove(const T& item); //xóa phần tử đầu tiên có giá trị item void RemoveAt(int pos); //xóa phần tử tại vị trí pos int IndexOf(const T& item); //trả về vị trí lần đầu tiên tìm thấy item void Traverse(void (*visit)(T& item)); //duyệt qua các phần tử của list và thực
hiện hàm visit với các phần tử
private:
int count; T data[MAX];
};
template
return count==0;
Một số phương thức
}
template
template
return count==MAX;
}
count =0;
template
}
if((pos<0)||(pos>count-1)){
template
throw exception("Index is out
of range");
throw exception("Index is out of range");
}else {
if((pos<0)||(pos>count-1)){
return data[pos];
}else {
}
}
}
data[pos]= item;
}
Thêm vào một danh sách liên tục
z
2
0
1
3
4
5
6
7
8
9
c
a
b
d d
e e
f f
g g
h h
count=9 count=8
InsertAt(3, ‘z’)
Thêm vào danh sách
template
if(IsFull()){
throw exception("List is full");
}else {
if((pos<0)||(pos>count)){
throw exception("Index is out of range");
}else {
for(int i=count -1; i>=pos;i--)data[i+1]=data[i]; data[pos] = item; count ++;
}
}
}
template
InsertAt(0,item);
}
Xóa từ một danh sách liên tục
0
1
2
3
4
5
6
7
8
9
a
b
c
d d
e e
f f
g g
h h
count=7 count=8
RemoveAt(3)
Xóa phần tử từ danh sách
template
if(IsEmpty()){
}else {
throw exception("List is empty");
if((pos<0)||(pos>count-1)){
throw exception("Index is out of range");
}else {
for(int i=pos+1; i } } } template } template item ++; } void main(){ template } List } Danh sách liên kết đơn (DSLK đơn) template T item;
Node };
template template this->item = item; this -> next = ptr; } template List(void);
~List(void);
void InsertAt(int pos, const T& item);
void Insert(const T& item);
void RemoveAt(int pos);
int IndexOf(const T& item);
void Remove(const T& item);
int GetSize() const;
void Clear(); //xóa sạch phần tử của list
void Traverse(void (*visit)(T& item)) const; private: Node }; template head=nullptr; count =0; } template return count; } Giải thuật tìm vị trí trên DSLK đơn Algorithm Set position Input: position là vị trí cần tìm
Output: con trỏ chỉ đến phần tử tại vị trí cần tìm 1. set q to head
2. for index =0 to position 2.1. advance q to the next element //Thi hành position bước
//Trỏ q đến phần tử kế tiếp 3. return q SetPosition(2) End Set position q head index=0 index=1 index=2 x y z m template Node } previous_node following_node x y phần tử tại vị trí position-1 phần tử tại vị trí position bây giờ, phần tử này
có vị trí position+1 a new_node bây giờ, phần tử này
có vị trí position template if(pos<0||pos>count){ throw exception("Index is out of range"); }else{ Node previous = SetPosition(pos-1);
following = previous ->next; }else following = head;
newNode = new(nothrow) Node throw exception("Not enough memory"); }else
{ if(pos==0)head= newNode;
else previous->next = newNode;
count++; } } } template InsertAt(0,item); } x y z phần tử tại vị trí position-1 previous_node following_node phần tử tại vị trí position phần tử tại vị trí position+1 bây giờ, phần tử này
có vị trí position template if(count ==0){ throw exception("List is empty");
return; }
if(pos<0 || pos >count-1){ throw exception("Index is out of range"); }else{ Node previous = SetPosition(pos -1);
following = previous -> next;
previous -> next = following ->next; }else { following = head; head = following ->next; } delete following;
count --; } } Phương thức Clear và destructor template while(count>0)RemoveAt(0); } template Clear(); } template Node (*visit)(q->item);
q = q -> next; } } template cout << item << " "; } void main(){ List } template // Add specications for methods of the list ADT.
// Add methods to replace compiler generated defaults. protected: // Data members for the doubly-linked list implementation follow:
int count;
mutable int current_position;
mutable Node }; Các hàm hằng (const) có thể thay đổi giá trị của các biến mutable này // data members
T item;
Node z }; set_position(8)
set_position(6) current x y z m current_position position = 5 position = 6 position = 7 position = 8 phần tử tại vị trí position-1 previous following x z phần tử tại vị trí position y new_node current phần tử này bây giờ
có vị trí là position+1 phần tử này bây giờ
có vị trí là positionDuyệt qua các phần tử
Thử nghiệm
Thiết kế Node
Thiết kế Class List
Một số phương thức
Phương thức SetPostition
Thêm vào một DSLK đơn
Phương thức InsertAt
Phương thức Insert
Xóa bỏ từ một DSLK đơn
Phương thức RemoveAt
Phương thức Traverse
Thử nghiệm
DSLK kép (Doubly linked list)
Định nghĩa DSLK kép
Định nghĩa Node cho DSLK kép
template
Tìm vị trí trong DSLK kép
Thêm vào trong DSLK kép
CÁM ƠN VÌ ĐÃ
LẮNG NGHE!
