Bài giảng Cấu trúc dữ liệu - Chương 5: Danh sách liên kết - Lê Minh Trung

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]; }; Một số phương thức template List::List(void) { count =0; } template bool List::IsEmpty(){ return count==0; } template bool List::IsFull() { return count==MAX; } template T List::GetItem(int pos) { if((poscount-1)){ throw exception("Index is out of range"); }else { return data[pos]; } } template void List::SetItem(int pos, const T& item){ if((poscount-1)){ throw exception("Index is out of range"); }else { data[pos]= item; } } Thêm vào một danh sách liên tục InsertAt(3, ‘z’) da b c 0 1 2 3 4 5 6 7 8 9 e f g h z count=89 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 RemoveAt(3) da b c 0 1 2 3 4 5 6 7 8 9 e f g h count=87 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<count;i++)data[i-1]=data[i]; count --; } } } Duyệt qua các phần tử template void List::Traverse(void (*visit)(T& item)){ for(int i=0; i<count;i++)(*visit)(data[i]); } Thử nghiệm template void Inc(T& item){ item ++; } template void Print(T& item){ cout << item<<" "; } void main(){ List list; for(int i=5;i>=1;i-=2) list.Insert(i); list.InsertAt(1,2); list.InsertAt(3,4); list.RemoveAt(1); list.Traverse(Inc); list.Traverse(Print); cout<<endl; } 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; } qGiả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 x y z head m index=0 SetPosition(2) index=1 index=2 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 new_node a y following_node phần tử tại vị trí position x previous_node phần tử tại vị trí position-1 bây giờ, phần tử này có vị trí position bây giờ, phần tử này có vị trí position+1 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++; } } } Phương thức Insert template void List::Insert(const T& item){ InsertAt(0,item); } Xóa bỏ từ một DSLK đơn bây giờ, phần tử này có vị trí position phần tử tại vị trí position phần tử tại vị trí position+1 x z previous_node phần tử tại vị trí position-1 y following_node Phương thức RemoveAt template void List::RemoveAt(int pos){ if(count ==0){ throw exception("List is empty"); return; } if(poscount-1){ throw exception("Index is out of range"); }else{ Node* previous, *following; if(pos>0){ 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 void List::Clear(){ while(count>0)RemoveAt(0); } template List::~List(void) { Clear(); } Phương thức Traverse template void List::Traverse(void (*visit)(T& item)) const{ Node* q = head; while(q !=nullptr){ (*visit)(q->item); q = q -> next; } } template void Print(T& item){ cout << item << " "; } void main(){ List list; list.Insert(1); list.Insert(3); list.Insert(4); list.InsertAt(1,2); list.Traverse(Print); cout<< endl; } Thử nghiệm DSLK kép (Doubly linked list) template class List { public: // 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 *current; // The auxiliary function to locate list positions follows: void SetPosition(int position) const; }; Định nghĩa DSLK kép Các hàm hằng (const) có thể thay đổi giá trị của các biến mutable này Định nghĩa Node cho DSLK kép template struct Node { // data members T item; Node *next; Node *back; // constructors Node( ); Node(T, Node *link_back = NULL, Node *link_next = NULL); }; z Tìm vị trí trong DSLK kép set_position(6)8 x y z m current current_position position = 5 position = 6 position = 7 position = 8 Thêm vào trong DSLK kép x y z current previous following new_node phần tử tại vị trí position-1 phần tử tại vị trí position phần tử này bây giờ có vị trí là position phần tử này bây giờ có vị trí là position+1 CÁM ƠN VÌ ĐÃ LẮNG NGHE!