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

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

25
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu: Danh sách liên kết cung cấp cho người học những kiến thức như: Danh sách sử dụng mảng; Xóa từ một danh sách liên tục; Duyệt qua các phần tử; Danh sách sử dụng con trỏ; Giải thuật tìm vị trí trên danh sách liên kết đơn; Phương thức InsertAt;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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++; } } }