Nội dung text HDTH-Tuan08 (LL cont.).pdf
Thực hành Kỹ thuật lập trình Khoa CNTT - KHTN Page 1 Mục tiêu Nắm vững các thao tác với danh sách liên kết. Nội dung Giải bài tập cũ (Bài 3 tuần 7) //khai báo Node struct Node { int info; Node *pNext; }; //khai báo dslk struct List { Node *pHead, *pTail; }; //hàm khởi tạo dslk void initList(List &l) { l.pHead = l.pTail = NULL; } //hàm tạo Node Node* CreateNode(const int &x) { Node *p = new Node; if (p != NULL) { p->info = x; p->pNext = NULL; } return p; } //hàm thêm node vào cuối dslk void AddNode(List &l, Node *p) { if (p == NULL) { return; } //kiểm tra dslk có rỗng không if (l.pHead == NULL) { l.pHead = l.pTail = p; } else { //dslk đã có phần tử thì thêm vào cuối
Thực hành Kỹ thuật lập trình Khoa CNTT - KHTN Page 2 l.pTail->pNext = p; l.pTail = p; } } void Bai3w7(List l, List &l1, List &l2, const int &x) { //duyệt từ đầu ds đến cuối ds for (Node *p = l.pHead; p != NULL; p = p->pNext) { //tạo Node có giá trị để thêm vào ds Node *pTemp = CreateNode(p->info); //phân chia phần tử if (p->info > x) { //thêm vào dslk 1 AddNode(l1, pTemp); } else { //thêm vào dslk 2 AddNode(l2, pTemp); } } } void main() { //phát sinh dslk List l; initList(l); //khởi tạo hàm random srand((unsigned)time(NULL)); //phát sinh số lượng phần tử trong khoảng [10, 100] int n = 10 + rand() % 91; for (int i=0; iThực hành Kỹ thuật lập trình Khoa CNTT - KHTN Page 3 { Node *p = l.pHead; if(p == NULL) return p; while(p != NULL && CompareData(p->info, info) != 0) { p = p->pNext; } return p; } // Hàm tìm node có chỉ số (bắt đầu từ 0) cho trước // Đầu vào: DSLK (l), chỉ số của node cần lấy (index) // Đầu ra: Con trỏ đến node tìm được (trả về NULL nếu không tìm được) Node* GetNodePointer(List l, int index) { Node *p = l.pHead; int i = 0; while(p!=NULL && ipNext; ++i; } return p; } // Hàm xác định vị trí của một node cho trước trong DSLK cho trước // Đầu vào: DSLK (l), con trỏ đến node cần xác định vị trí (pNode) // Đầu ra: Thứ tự của node cho trước (trả về -1 nếu node này không có trong DSLK) int GetNodeIndex(List l, Node *pNode) { if(l.pHead == NULL) return -1; Node *p = l.pHead; int i = 0; while(p!=NULL) { if(p==pNode) return i; p=p->pNext; ++i; } return -1; } // Hàm xác định con trỏ đến node đứng trước của một node cho trước trong DSLK // Đầu vào: DSLK (l), con trỏ đến node cho trước (pNode) // Đầu ra: Con trỏ đến node tìm được (trả về NULL nếu không tìm được) Node* GetPreviousNodePointer(List l, Node *pNode) { Node *p = l.pHead; Node *pOld = NULL; while(p!=NULL) { if(p == pNode) return pOld;
Thực hành Kỹ thuật lập trình Khoa CNTT - KHTN Page 4 pOld = p; p=p->pNext; } return NULL; } // Hàm chèn một node cho trước vào đầu DSLK // Đầu vào: Tham chiếu đến DSLK (l), con trỏ đến node cần chèn (pNewNode) // Đầu ra: Không có void AddHead(List &l, Node *pNewNode) { pNewNode->pNext = l.pHead; l.pHead = pNewNode; if(l.pTail == NULL) l.pTail = l.pHead; } // Hàm chèn một node có dữ liệu cho trước vào đầu DSLK // Đầu vào: Tham chiếu đến DSLK (l), dữ liệu của node cần chèn (info) // Đầu ra: Con trỏ đến node được chèn (trả về NULL nếu không chèn được) Node* AddHead(List &l, Data info) { Node *p = CreateNode(info); if(p!=NULL) AddHead(l, p); return p; } // Hàm chèn một node cho trước vào cuối DSLK // Đầu vào: Tham chiếu đến DSLK (l), con trỏ đến node cần chèn (pNewNode) // Đầu ra: Không có void AddTail(List &l, Node *pNewNode) { if(l.pTail==NULL) { l.pHead = pNewNode; l.pTail = pNewNode; } else { l.pTail->pNext = pNewNode; l.pTail = pNewNode; } l.pTail->pNext = NULL; } // Hàm chèn một node có dữ liệu cho trước vào cuối DSLK // Đầu vào: Tham chiếu đến DSLK (l), dữ liệu của node cần chèn (info) // Đầu ra: Con trỏ đến node được chèn (trả về NULL nếu không chèn được) Node* AddTail(List &l, Data info) { Node *p = CreateNode(info); if(p!=NULL) AddTail(l, p); return p; }