- Trang Chủ
- Cơ sở dữ liệu
- Bài giảng Cấu trúc dữ liệu: Danh sách liên kết - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết
Xem mẫu
- 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
class List
{
public:
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
bool List::IsEmpty(){
Một số phương thức return count==0;
}
template template
List::List(void) bool List::IsFull()
{ {
count =0; return count==MAX;
} }
template template
T List::GetItem(int pos) void List::SetItem(int pos,
{ const T& item){
if((poscount-1)){ if((poscount-1)){
throw exception("Index is out throw exception("Index is
of range");
out of range");
}else
{ }else
return data[pos]; {
} data[pos]= item;
} }
}
- Thêm vào một danh sách liên tục
z
0 1 2 3 4 5 6 7 8 9
a b c d e f g h
count=9
count=8
InsertAt(3, ‘z’)
- Thêm vào danh sách
template
void List::InsertAt(int pos, const T& item){
if(IsFull()){
throw exception("List is full");
}else
{
if((poscount)){
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
void List::Insert(const T& item){
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 e f g h
count=7
count=8
RemoveAt(3)
- Xóa phần tử từ danh sách
template
void List::RemoveAt(int pos){
if(IsEmpty()){
throw exception("List is empty");
}else
{
if((poscount-1)){
throw exception("Index is out of range");
}else
{
for(int i=pos+1; i
- Duyệt qua các phần tử
template
void List::Traverse(void (*visit)(T& item)){
for(int i=0; i
- template
Thử nghiệm void Inc(T& item){
item ++;
void main(){ }
List list;
for(int i=5;i>=1;i-=2) template
list.Insert(i);
void Print(T& item){
list.InsertAt(1,2);
list.InsertAt(3,4); cout
- Danh sách liên kết đơn (DSLK đơn)
- Thiết kế Node
template
struct Node
{
T item;
Node *next;
Node(void);
Node(T item, Node* ptr=nullptr);
};
template
Node::Node(void)
{ this->next = nullptr; }
template
Node::Node(T item, Node* ptr=nullptr)
{
this->item = item; this -> next = ptr;
}
- Thiết kế Class List
template
class List
{
public:
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* head;
Node* SetPosition(int pos);
int count;
};
- Một số phương thức
template
List::List(void)
{
head=nullptr; count =0;
}
template
int List::GetSize() const{
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 //Thi hành position bước
2.1. advance q to the next element //Trỏ q đến phần tử kế tiếp
3. return q
End Set position
SetPosition(2)
q
index=0 index=1 index=2
head
x y z m
- Phương thức SetPostition
template
Node* List::SetPosition(int pos)
{
Node* q = head;
for(int i=1;inext;
return q;
}
- Thêm vào một DSLK đơn
previous_node following_node
phần tử tại vị trí position
x y
phần tử tại vị trí position-1 bây giờ, phần tử này
có vị trí position+1
new_node
a
bây giờ, phần tử này
có vị trí position
- Phương thức InsertAt
template
void List::InsertAt(int pos, const T& item){
if(poscount){
throw exception("Index is out of range");
}else{
Node* previous, *following, *newNode;
if(pos>0){
previous = SetPosition(pos-1);
following = previous ->next;
}else following = head;
newNode = new(nothrow) Node(item, following);
if(newNode==nullptr){
throw exception("Not enough memory");
}else
{
if(pos==0)head= newNode;
else previous->next = newNode;
count++;
}
}
}
nguon tai.lieu . vn
