Bài Tập Danh Sách Liên Kết Đơn Có Lời Giải

*
*

Danh sách liên kết là một trong những có mang khôn cùng cơ bản vào Lập trình. Việc tò mò về list liên kết trong C/C++ có không ít điểm thú vui là vì:

Cấu trúc của list link siêu đơn giản dễ dàng, vấn đề diễn đạt nó rất dễ dàng dàngTuy vậy những lời giải cách xử lý list link lại có thể vô cùng phức hợp với thú vịLàm việc cùng với list link đòi hỏi việc sử dụng nhỏ trỏ một cách thành thạoCác list liên kết đặc biệt cân xứng đến Việc trình bày sử dụng hình vẽ. Làm việc với bọn chúng giúp đỡ bạn cải cách và phát triển khả năng biểu tượng hóa sự việc lúc lập trình

Bài viết này đang điểm qua một vài định nghĩa cơ bạn dạng về list links và chỉ dẫn 18 bài tân oán về list liên kết theo vật dụng trường đoản cú tự dễ mang đến khó khăn.

Bạn đang xem: Bài tập danh sách liên kết đơn có lời giải

Cơ phiên bản về danh sách liên kết

Cấu trúc của một danh sách link 1-1 như sau:


Chúng ta đã điểm qua một vài ba hàm cơ bản cần sử dụng để triển khai việc với list. Hàm tính độ dài của danh sách như sau:


int Length(struct node *head) int count =0; struct node *elem = head; while (elem) count ++; elem = elem->next; return count;
void Push(struct node** headRef, int data) struct node* newNode = malloc(sizeof(struct node));newNode->data = data;newNode->next = *headRef; // The "*" lớn dereferences baông xã to lớn the real head*headRef = newNode; // ditto
Chúng ta rất có thể dùng hàm sau nhằm phát hành một danh sách kết nối đơn giản và dễ dàng, sử dụng làm cho nguồn vào cho những bài xích toán ở vị trí sau:


struct node *BuildOneTwoThree()

18 bài xích tân oán về list liên kết

1. Count()

Viết hàm Count() triển khai vấn đề đếm những lần mở ra của một số trong những ngulặng vào một danh sách.


void CountTest() List myList = BuildOneTwoThree(); // build 1, 2, 3int count = Count(myList, 2); // returns 1 since there"s 1 "2" in the list
/* Given a list and an int, return the number of times that int occurs in the danh sách. */int Count(struct node* head, int searchFor) // Your code
void GetNthTest() struct node* myList = BuildOneTwoThree(); // build 1, 2, 3int lastNode = GetNth(myList, 2); // returns the value 3
// Given a list & an index, return the data// in the nth node of the list. The nodes are numbered from 0.// Assert fails if the index is invalid (outside 0..lengh-1).int GetNth(struct node* head, int index) // Your code

3. DeleteList()

Viết hàm DeleteList() để xóa một list links với thiết lập cấu hình con trỏ head thành NULL


void DeleteListTest() struct node* myList = BuildOneTwoThree(); // build 1, 2, 3DeleteList(&myList); // deletes the three nodes và sets myList khổng lồ NULL

4. Pop()

Viết hàm Pop() để mang ra thành phần trước tiên của list, phần trường đoản cú này bên cạnh đó được xóa bỏ danh sách.


void PopTest() struct node* head = BuildOneTwoThree(); // build 1, 2, 3int a = Pop(&head); // deletes "1" node & returns 1int b = Pop(&head); // deletes "2" node & returns 2int c = Pop(&head); // deletes "3" node and returns 3int len = Length(head); // the các mục is now empty, so len == 0
/*The opposite of Push(). Takes a non-empty listand removes the front node, and returns the datawhich was in that node.*/int Pop(struct node** headRef) // your code...
void InsertNthTest() {struct node* head = NULL; // start with the empty listInsertNth(&head, 0, 13); // build 13)InsertNth(&head, 1, 42); // build 13, 42InsertNth(&head, 1, 5); // build 13, 5, 42DeleteList(&head); // clean up after ourselves
/*A more general version of Push().Given a các mục, an index "n" in the range 0..length,và a data element, add a new node khổng lồ the menu sothat it has the given index.*/void InsertNth(struct node** headRef, int index, int data) // your code...

6. SortedInsert()

Có một list đã có được thu xếp. Viết hàm để sản xuất list một đối tượng người sử dụng vào list và giữ được trang bị trường đoản cú bố trí.

Xem thêm: Cách Fix Lỗi Kết Nối Máy In Qua Mạng Lan 2020, Cài Đặt Máy In Qua Mạng Lan

Mẫu hàm:


7. InsertSort()

Nhận một danh sách đầu vào, thu xếp list này theo sản phẩm công nghệ tự tăng ngày một nhiều, bài toán đòi hỏi sử dụng hàm SortedInsert() làm việc câu 6.

Mẫu hàm:


// Given a danh mục, change it khổng lồ be in sorted order (using SortedInsert()).void InsertSort(struct node** headRef) // Your code

8. Append()

Viết hàm dấn nhị tđắm đuối số là danh sách A với B, trả về danh sách A với B được đã tích hợp đuôi của A và B được tùy chỉnh là NULL.

Mẫu hàm:


// Appover "b" onto the over of "a", & then phối "b" khổng lồ NULL.void Append(struct node** aRef, struct node** bRef) // Your code...

9. FronBackSplit()

Viết hàm bóc tách một list liên kết ra có tác dụng hai, ngắt trọng tâm. Nếu chiều nhiều năm của list là lẻ thì list trước tiên vẫn dài thêm hơn list đồ vật nhị một phần tử.

Mẫu hàm:


/*Split the nodes of the given menu into lớn front và bachồng halves,& return the two lists using the reference parameters.If the length is odd, the extra node should go in the front list.*/void FrontBackSplit(struct node* source,struct node** frontRef, struct node** backRef) // Your code...

10. RemoveDuplicates()

Cho một list đã có bố trí theo máy tự tăng cao, hãy xóa những bộ phận bị lặp cùng với điều kiện danh sách chỉ được thông qua một lần.

Mẫu hàm:


/*Take the node from the front of the source, & move it tothe front of the dest.It is an error to lớn Hotline this with the source các mục empty.*/void MoveNode(struct node** destRef, struct node** sourceRef) // Your code
/*Merge the nodes of the two lists into lớn a single các mục taking a nodealternately from each menu, & return the new danh mục.*/struct node* ShuffleMerge(struct node* a, struct node* b) // Your code
int Count(struct node* head, int searchFor) int count =0;struct node *element = head;while (element) if ( element->data == searchFor) count++;element = element-> next;return count;
int GetNth(struct node* head, int index) struct node *elem = head; int i = 0; while (elem) if (i==index) return elem->data; elem = elem->next; i++; assert(0);
void DeleteList(struct node **head) struct node *elem = *head; struct node *another; while (elem) another = elem->next; free(elem); elem = another; *head = NULL;
int Pop(struct node **head) struct node *elem = *head; int a; assert( elem ); a = elem->data; *head = elem->next; free(elem); return a;
void InsertNth(struct node** head, int index, int data) struct node *newElem; newElem = (struct node*) malloc(sizeof(struct node)); newElem->data = data; int i = 0; struct node *elem = *head; while (elem) if (i== (index-1)) newElem->next = elem->next; elem->next = newElem; break; i++; elem = elem->next;
void InsertNth(struct node** head, truct node *newNode) struct node *elem = *head; while (elem) if (newNode->data data) newNode->next = elem->next; elem->next = newNode; break; elem = elem->next;