Danh sách liên kết đơn | Đại học Kinh tế Kỹ thuật Công nghiệp

1 Người soạn
Đặng Đình Thế Hiếu
Danh sách liên kết đơn Cài đặt danh sách typedef struct node { int info; node* next; }NODE; typedef NODE* NodePtr; NodePtr pHead; pHead = NULL; 1 lOMoAR cPSD| 46884348 2 Hàm tạo node mới NodePtr MakeNode(int x) { NodePtr node = new NODE;
node->info = x; node->next = NULL; return node; } Thêm node vào đầu
void InsertFirst(NodePtr& pHead, int x) {
NodePtr node = new NODE; node->info = x; node->next = NULL; if (pHead == NULL) { pHead = node; } else { node->next = pHead; pHead = node; } } Thêm node vào giữa
void Insert_Mid(NodePtr& pHead, int x, int pos) { NodePtr node = MakeNode(x); int cnt = 0; //đếm số node của dslk NodePtr p = pHead; //để duyệt dslk while (p != NULL) { cnt++; p = p->next; } if (pos == 1) { //chèn đầu if (pHead == NULL) { //rỗng pHead = node; } else { //không rỗng node->next = pHead; 2 lOMoAR cPSD| 46884348 3 pHead = node; } }
else if (pos > 1 && pos <= cnt+1) { NodePtr truoc, sau = pHead;
for (int i = 1; i < pos; i++) { truoc = sau; sau = sau->next; } node->next = sau; truoc->next = node; } else {
cout << "Vượt quá giới hạn danh sách"; } }
Thêm node vào danh sách đã sắp xếp
void InsertMid_Sort(NodePtr& pHead, int x) {
NodePtr node = new NODE; node->info = x; node->next = NULL; if (pHead == NULL) { pHead = node; } else { if (x < pHead->info) { //chèn đầu node->next = pHead; pHead = node; } else {
NodePtr q = pHead; //duyệt trước NodePtr p
= pHead->next; //duyệt sau while (p->info < x && p != NULL) { p = p->next; q = q->next; } node->next = p; q->next = node; } } } 3 lOMoAR cPSD| 46884348 4 Thêm node vào cuối
void InsertLast(NodePtr& pHead, int x) {
NodePtr node = new NODE; node->info = x; node->next = NULL; if (pHead == NULL) { pHead = node; } else { NodePtr p = pHead; while (p->next != NULL) { p = p->next; } p->next = node; } } Xóa node đầu
void DeleteFirst(NodePtr& pHead) { if (pHead == NULL) {
cout << "List is empty"; } else { NodePtr p = pHead; pHead = pHead->next; delete p; } }
Xóa node giữa p bất kỳ
// p trỏ đến node bất kỳ trong danh sách
// nếu ko cho p thì duyệt tìm p bằng hàm tìm kiếm giá trị hoặc vị trí
void DeleteNode_p(NodePtr& pHead, NodePtr p) { if (pHead == NULL) {
cout << "Cannot delete"; } else { if (p == pHead) { // p trỏ node đầu pHead = pHead->next; delete p; } else { 4 lOMoAR cPSD| 46884348 5 NodePtr q = pHead; while (q->next != p) { q = q->next; } q->next = p->next; delete p; } } } Xóa toàn bộ node
void DeleteAll(NodePtr& pHead) { while (pHead != NULL) { NodePtr p = pHead; pHead = pHead->next; delete p; } } Xóa node cuối
void DeleteLast(NodePtr& pHead) { if (pHead == NULL) {
cout << "List is empty"; } else {
if (pHead->next == NULL) { //1 node NodePtr p = pHead; pHead = pHead -> next; delete p; }
NodePtr q = pHead, p = pHead->next;
while (p -> next != NULL) { q = q->next; p = p->next; } delete p; q->next = NULL; } } 5 lOMoAR cPSD| 46884348 6 Tìm kiếm
NodePtr Search(NodePtr pHead, int x) { NodePtr p = pHead;
while (p != NULL && p->info != x) { p = p- >next; } return p; } Sắp xếp
void Sort(NodePtr& pHead) { NodePtr p = pHead,q,min; while (p != NULL) { min = p; q = p->next; while (q != NULL) {
if (min->info > q->info) { min = q; } q = q->next; } if (min != p) { int tmp = p->info; p->info = min->info; min->info = tmp; } p = p->next; } } 6 lOMoAR cPSD| 46884348 7
Danh sách liên kết vòng Cài đặt danh sách typedef struct node { int info; node* next; }NODE; typedef NODE* NodePtr;
NodePtr pList = NULL; //trỏ nút cuối ds 7 8 Hàm tạo node mới NodePtr MakeNode(int x) { NodePtr node = new NODE; node->info = x; return node; } Thêm node vào đầu
void InsertFirst(NodePtr& pList, int x) {
NodePtr node = new NODE; node->info = x; if (pList == NULL) { pList = node; pList->next = pList; } else {
node->next = pList->next; pList->next = node; } } Thêm node vào sau p
void InsertAfter_p(NodePtr& pList, int x, NodePtr p) { NodePtr node = new NODE; node->info = x; if (p == NULL) { return; } else { node->next = p->next; p->next = node; } 8 lOMoAR cPSD| 46884348 9 } Thêm node vào cuối
void InsertLast(NodePtr& pList, int x) { NodePtr node = new NODE; node->info = x; if (pList == NULL) { pList = node; pList->next = pList; } else {
node->next = pList->next; pList->next = node; pList = node; } } Xóa trước node p
void InsertLast(NodePtr& pList, int x) { NodePtr node = new NODE; node->info = x; if (pList == NULL) { pList = node; pList->next = pList; } else {
node->next = pList->next; pList->next = node; pList = node; } } Xóa node đầu
void DeleteFirst(NodePtr& pList) { if (pList == NULL) {
cout << "List is empty"; } else {
if (pList == pList->next) { NodePtr p = pList; pList = NULL; delete p; } else { NodePtr p = pList->next; pList->next = p->next; 9 lOMoAR cPSD| 46884348 10 delete p; } } } Xóa sau node p
void DeleteAfter_p(NodePtr& pList, NodePtr p) { if (p == NULL) {
cout << "List is empty"; } else { if (p == p->next) { pList = NULL; delete p; } else { NodePtr q = p->next; p->next = q->next; delete q; } } } Xóa node cuối
void DeleteLast(NodePtr& pList) { if (pList == NULL) {
cout << "List is empty"; } else {
if (pList == pList->next) { NodePtr p = pList; pList = NULL; delete p; } else { NodePtr p = pList->next; while (p->next != pList) { p = p->next; } p->next = pList->next; NodePtr q = pList; delete q; } } } 10 11 Tìm kiếm
NodePtr Search(NodePtr pList, int x) { if (pList == NULL) { return NULL; } else { NodePtr p = pList->next;
while (p != pList->next && p->info!=x) { p = p->next; }
if (p->info == x) return p; return NULL; } } Sắp xếp
void Sort(NodePtr &pList) { if (pList == NULL) { return; } else {
NodePtr p = pList->next, q, min; while (p != pList) { min = p; q = p->next; while (q != pList->next) {
if (q->info < min->info) { min = q; } q = q->next; } if (min != p) {
swap(min->info, q->info); } q = q->next; } } } 11 lOMoAR cPSD| 46884348 12
Danh sách liên kết kép Cài đặt danh sách typedef struct node { int info; node* next; node* prev; }NODE; typedef NODE* NodePtr; NodePtr pHead; pHead = NULL; 12 13 In đảo ngược
void ShowReverse(NodePtr pHead) { if (pHead == NULL) { return; } NodePtr p = pHead; while (p->next != NULL) { p = p->next; } while (p != NULL) { cout << p->info; p = p->prev; } } Hàm tạo node mới NodePtr MakeNode(int x) { NodePtr node = new NODE; node->info = x; node->next = NULL; node->prev = NULL; return node; } Thêm node vào đầu
void InsertFirst(NodePtr &pHead, int x) {
NodePtr node = new NODE; node->info = x; node->next = NULL; node->prev = NULL; if (pHead == NULL) { pHead = node; } else { node->next = pHead; pHead->prev = node; pHead = node; } } 13 14
Thêm node vào trước p
void InsertAfter_p(NodePtr& pHead, NodePtr& p, int x) { NodePtr node = new NODE; node->info = x; node->next = NULL; node->prev = NULL; if (pHead == NULL) { return; } else { NodePtr right = p->next; node->next = right; node->prev = p; p->next = node; if (right != NULL) { right->prev = node; } } }
Thêm node vào sau node p
void InsertBefore_p(NodePtr& pHead, NodePtr &p, int x) { if (pHead == NULL) { return; } NodePtr node = new NODE; node->info = x; node->next = NULL; node->prev = NULL; if (p == pHead) { node->next = pHead; pHead->prev = node; pHead = node; } else { NodePtr left = p->prev; node->next = p; left->next = node; node->prev = left; p->prev = node; } } 14 lOMoAR cPSD| 46884348 15 Thêm node vào cuối
void InsertLast(NodePtr& pHead, int x) { NodePtr node = new NODE; node->info = x; node->next = NULL; node->prev = NULL; if (pHead == NULL) { pHead = node; } else { NodePtr p = pHead;
while (pHead->next != NULL) { p = p->next; } p->next = node; node->prev = p; } } Xóa node đầu
void DeleteFirst(NodePtr& pHead, NodePtr& p) { if (pHead == NULL) { return; }
else if (pHead->next = pHead->prev) { NodePtr p = pHead; pHead = NULL; delete p; } else { NodePtr p = pHead; pHead = pHead->next; pHead->prev = NULL; delete p; } } Xóa sau node p
void DeleteAfter_p(NodePtr& pList, NodePtr p) { if (p == NULL) {
cout << "List is empty"; } else { if (p == p->next) { pList = NULL; delete p; } else { NodePtr q = p->next; p->next = q->next; delete q; 15 lOMoAR cPSD| 46884348 16 } } } Xóa node cuối
void DeleteLast(NodePtr& pHead, NodePtr& p) { if (pHead == NULL) { return; }
else if (pHead->next == pHead->prev) { NodePtr p = pHead; pHead = NULL; delete p; } else { NodePtr p = pHead; while (p->next != NULL) { p = p->next; } NodePtr q = p->prev; q->next = NULL; delete p; } } } Tìm kiếm
NodePtr Search(NodePtr pHead, int x){ NodePtr p;
if (pHead == NULL) return NULL; p = pHead;
while (p->info != x && p != NULL) p = p->next;
if (p->info == x) return p; else return NULL; }