Kinh Nghiệm về Bài tập list link đôi có lời giải 2022
You đang tìm kiếm từ khóa Bài tập list link đôi có lời giải được Cập Nhật vào lúc : 2022-12-03 06:32:05 . Với phương châm chia sẻ Bí kíp về trong nội dung bài viết một cách Chi Tiết Mới Nhất. Nếu sau khi Read Post vẫn ko hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Ad lý giải và hướng dẫn lại nha.
Danh sách link là một khái niệm rất cơ bản trong Lập trình. Việc tìm hiểu về list link trong C/C++ có nhiều điểm thú vị là vì:
Nội dung chính
- Cơ bản về list link
- 3. DeleteList()
- 5. InsertNth()
- 6. SortedInsert()
- 7. InsertSort()
- 8. Append()
- 9. FronBackSplit()
- 10. RemoveDuplicates()
- 11. MoveNode()
- 12. ShuffleMerge()
- Lời giải
- 3. DeleteList()
- 5. InsertNth()
- 6. SortedInsert()
- 7. InsertSort()
- 8. Append()
- 9. FronBackSplit()
- Cấu trúc của list link rất đơn thuần và giản dị, việc mô tả nó rất thuận tiện và đơn thuần và giản dị
- Tuy vậy những giải thuật xử lý list link lại hoàn toàn có thể rất phức tạp và thú vị
- Làm việc với list link yên cầu việc sử dụng con trỏ một cách thành thạo
- Các list link đặc biệt quan trọng thích hợp cho việc mô tả dùng hình vẽ. Làm việc với chúng giúp bạn tăng trưởng kỹ năng hình tượng hóa yếu tố khi lập trình
Bài viết này sẽ điểm qua một số trong những khái niệm cơ bản về list link và đưa ra 18 bài toán về list link theo thứ tự từ dễ đến khó.
Cơ bản về list link
Cấu trúc của một list link đơn như sau:
struct node
int data;
struct node* next;
;
Chúng ta sẽ điểm qua một vài hàm cơ bản dùng để thao tác với list. Hàm tính độ dài của list như sau:
int Length(struct node *head)
int count =0;
struct node *elem = head;
while (elem)
count ++;
elem = elem->next;
return count;
Hàm thêm một thành phần vào đầu list:
void Push(struct node** headRef, int data)
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = *headRef; // The ‘*’ to dereferences back to the real head
*headRef = newNode; // ditto
Chúng ta hoàn toàn có thể dùng hàm sau để xây dựng một list link đơn thuần và giản dị, dùng làm nguồn vào cho những bài toán ở phần sau:
struct node *BuildOneTwoThree() !second
1. Count()
Viết hàm Count() thực thi việc đếm mỗi lần xuất hiện của một số trong những nguyên trong một list.
void CountTest()
List myList = BuildOneTwoThree(); // build 1, 2, 3
int count = Count(myList, 2); // returns 1 since there’s 1 ‘2’ in the list
Mẫu hàm:
/* Given a list and an int, return the number of times that int occurs in the list. */
int Count(struct node* head, int searchFor)
// Your code
2. Nth()
Viết hàm Nth() trả về đối tượng người dùng thứ n trong list (bắt nguồn từ 0)
void GetNthTest()
struct node* myList = BuildOneTwoThree(); // build 1, 2, 3
int lastNode = GetNth(myList, 2); // returns the value 3
Mẫu hàm:
// Given a list and 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 link và thiết lập con trỏ head thành NULL
void DeleteListTest()
struct node* myList = BuildOneTwoThree(); // build 1, 2, 3
DeleteList(&myList); // deletes the three nodes and sets myList to NULL
Mẫu hàm:
void DeleteList(struct node** head)
// Your code
4. Pop()
Viết hàm Pop() để lấy ra thành phần thứ nhất của list, phần từ này đồng thời được xóa khỏi list.
void PopTest()
struct node* head = BuildOneTwoThree(); // build 1, 2, 3
int a = Pop(&head); // deletes “1” node and returns 1
int b = Pop(&head); // deletes “2” node and returns 2
int c = Pop(&head); // deletes “3” node and returns 3
int len = Length(head); // the list is now empty, so len == 0
Mẫu hàm:
/*
The opposite of Push(). Takes a non-empty list
and removes the front node, and returns the data
which was in that node.
*/
int Pop(struct node** headRef)
// your code…
5. InsertNth()
Viết hàm để thêm vào list một đối tượng người dùng tại vị trí thứ n
void InsertNthTest() {
struct node* head = NULL; // start with the empty list
InsertNth(&head, 0, 13); // build 13)
InsertNth(&head, 1, 42); // build 13, 42
InsertNth(&head, 1, 5); // build 13, 5, 42
DeleteList(&head); // clean up after ourselves
Mẫu hàm:
/*
A more general version of Push().
Given a list, an index ‘n’ in the range 0..length,
and a data element, add a new node to the list so
that it has the given index.
*/
void InsertNth(struct node** headRef, int index, int data)
// your code…
6. SortedInsert()
Có một list đã được sắp xếp. Viết hàm để thêm vào list một đối tượng người dùng vào list và giữ được thứ tự sắp xếp.
Mẫu hàm:
void SortedInsertNth(struct node** headRef,struct node *newNode)
// your code
7. InsertSort()
Nhận một list nguồn vào, sắp xếp list này theo thứ tự tăng dần, bài toán yêu cầu sử dụng hàm SortedInsert() ở câu 6.
Mẫu hàm:
// Given a list, change it to be in sorted order (using SortedInsert()).
void InsertSort(struct node** headRef) // Your code
8. Append()
Viết hàm nhận hai tham số là list A và B, trả về list A với B được gắn vào đuôi của A và B được thiết lập là NULL.
Mẫu hàm:
// Append ‘b’ onto the end of ‘a’, and then set ‘b’ to NULL.
void Append(struct node** aRef, struct node** bRef)
// Your code…
9. FronBackSplit()
Viết hàm tách một list link ra làm hai, ngắt ở giữa. Nếu chiều dài của list là lẻ thì list thứ nhất sẽ dài hơn thế nữa list thứ hai một thành phần.
Mẫu hàm:
/*
Split the nodes of the given list into front and back halves,
and 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 sắp xếp theo thứ tự tăng dần, hãy xóa những thành phần bị lặp với Đk list chỉ được duyệt một lần.
Mẫu hàm:
/*
Remove duplicates from a sorted list.
*/
void RemoveDuplicates(struct node* head)
// Your code…
11. MoveNode()
Mẫu hàm:
/*
Take the node from the front of the source, and move it to
the front of the dest.
It is an error to call this with the source list empty.
*/
void MoveNode(struct node** destRef, struct node** sourceRef)
// Your code
12. ShuffleMerge()
Mẫu hàm:
/*
Merge the nodes of the two lists into a single list taking a node
alternately from each list, and return the new list.
*/
struct node* ShuffleMerge(struct node* a, struct node* b)
// Your code
Lời giải
1. Count()
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;
2. Nth()
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);
3. DeleteList()
void DeleteList(struct node **head)
struct node *elem = *head;
struct node *another;
while (elem)
another = elem->next;
không lấy phí(elem);
elem = another;
*head = NULL;
4. Pop()
int Pop(struct node **head)
struct node *elem = *head;
int a;
assert( elem );
a = elem->data;
*head = elem->next;
không lấy phí(elem);
return a;
5. InsertNth()
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;
6. SortedInsert()
void InsertNth(struct node** head, truct node *newNode)
struct node *elem = *head;
while (elem)
if (newNode->data < elem->data)
newNode->next = elem->next;
elem->next = newNode;
break;
elem = elem->next;
7. InsertSort()
void InsertNth(struct node** head, truct node *newNode)
8. Append()
void Append(struct node** aRef, struct node** bRef)
struct node *elem = *aRef;
if (*aRef == NULL)
*aRef = *bRef;
else
while (elem->next)
elem = elem->next;
elem->next = *bRef;
*bRef = NULL;
9. FronBackSplit()
void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef)
Reply
7
0
Chia sẻ
Share Link Cập nhật Bài tập list link đôi có lời giải miễn phí
Bạn vừa tìm hiểu thêm tài liệu Với Một số hướng dẫn một cách rõ ràng hơn về Video Bài tập list link đôi có lời giải tiên tiến và phát triển nhất và Share Link Cập nhật Bài tập list link đôi có lời giải miễn phí.
Hỏi đáp vướng mắc về Bài tập list link đôi có lời giải
Nếu sau khi đọc nội dung bài viết Bài tập list link đôi có lời giải vẫn chưa hiểu thì hoàn toàn có thể lại Comment ở cuối bài để Ad lý giải và hướng dẫn lại nha
#Bài #tập #danh #sách #liên #kết #đôi #có #lời #giải