Trang ChínhCalendarGalleryTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng NhậpTin tức
Latest topics
» chuyên cung cấp máy ép thủy lực 1m x 1m6 giá rẻ
by vominhtien Sat Jan 09, 2016 9:29 am

» chuyên cung cấp máy ép chân không giá rẻ
by vominhtien Sat Jan 09, 2016 9:25 am

» chuyên cung cấp máy in epson 9600 giá rẻ
by vominhtien Sat Jan 09, 2016 9:11 am

» chuyên cung cấp máy in epson 9800 giá rẻ
by vominhtien Sat Jan 09, 2016 9:09 am

» chuyên cung cấp máy in epson 9900 giá rẻ
by vominhtien Sat Jan 09, 2016 9:07 am

» Nhận in gia công bảng tên nhân viên, thẻ sinh viên giá siêu rẻ
by huyenrio Mon Apr 20, 2015 10:24 am

» Cung cấp máy in hình theo yêu cầu lên dĩa sứ, dĩa nhựa
by huyenrio Mon Apr 20, 2015 10:22 am

» bán máy ép hình ảnh lên ly
by huyenrio Sat Mar 28, 2015 4:14 pm

» cung cấp máy ép hình ảnh lên áo vải
by huyenrio Sat Mar 28, 2015 4:13 pm

» máy ép nhiệt hình ảnh lên mặt phẳng kích thước 40 x 60cm
by vominhtien Sat Sep 13, 2014 3:11 pm

» máy ép nhiệt hình ảnh lên vải kích thước 60x80cm
by vominhtien Sat Sep 13, 2014 3:10 pm

» giấy in nhiệt transfer cuộn giá siêu rẻ
by vominhtien Tue Sep 09, 2014 1:01 pm

» máy ép đĩa giá khuyến mãi
by vominhtien Tue Sep 09, 2014 1:00 pm

» máy ép hơi 40x60cm giá cực hót
by vominhtien Tue Sep 09, 2014 12:59 pm

» máy ép phẳng thủy lực 1mx1,6m
by vominhtien Wed Jun 04, 2014 2:56 pm

» máy ép thủy lực hơi 60x80 cm giá cực "Hot"
by vominhtien Wed Jun 04, 2014 2:54 pm

» máy in nhiệt epson pro 10000 giá khuyến mãi
by vominhtien Wed Jun 04, 2014 2:53 pm

» máy in chuyên dụng 4 màu ,6 màu khổ A4,A3,A0… giá hấp dẫn
by vominhtien Mon Dec 30, 2013 2:41 pm

» nhận in gia công lên mọi chất liệu làm quà tặng tết
by vominhtien Mon Dec 30, 2013 2:40 pm

» máy in nhiệt giá rẻ cuối năm
by vominhtien Mon Dec 30, 2013 2:37 pm

Đăng Nhập
Tên truy cập:
Mật khẩu:
Đăng nhập tự động mỗi khi truy cập: 
:: Quên mật khẩu
Top posters
final fantasy (1098)
 
vominhtien (347)
 
doicoluu (222)
 
Monitor (219)
 
Chuối Chúa (112)
 
Dao_Kid (88)
 
Ve Sầu (76)
 
trunglenhu (61)
 
genius.no3 (55)
 
Admin[MP] (38)
 
THOI TIET
Du bao thoi tiet - Thanh pho Da Nang
Poll
Statistics
Diễn Đàn hiện có 113 thành viên
Chúng ta cùng chào mừng thành viên mới đăng ký: huyenrio

Tổng số bài viết đã gửi vào diễn đàn là 2736 in 1143 subjects
Tìm kiếm
 
 

Display results as :
 
Rechercher Advanced Search
Thống Kê
Hiện có 3 người đang truy cập Diễn Đàn, gồm: 0 Thành viên, 0 Thành viên ẩn danh và 3 Khách viếng thăm

Không

Số người truy cập cùng lúc nhiều nhất là 14 người, vào ngày Fri Jan 08, 2010 12:14 am
April 2018
MonTueWedThuFriSatSun
      1
2345678
9101112131415
16171819202122
23242526272829
30      
CalendarCalendar
Keywords
Lượt truy cập

Share | 
 

 18 bài toán về danh sách liên kết

Go down 
Tác giảThông điệp
final fantasy
Admin
Admin
avatar

Nam Tổng số bài gửi : 1098
Age : 29
Đến từ : Đà Nẵng
Registration date : 04/06/2008

Bài gửiTiêu đề: 18 bài toán về danh sách liên kết   Thu Dec 11, 2008 11:39 pm

Bài viết về danh sách liên kết trong ngôn ngữ C từ trang web http://cslibrary.stanford.edu/. "This is document #105, Linked List Problems, in the Stanford CS Education Library. This and other free educational materials are available at http://cslibrary.stanford.edu/. This document is free to be used, reproduced, or sold so long as this notice is clearly reproduced at its beginning."

Danh sách liên kết là một khái niệm rất cơ bản trong Lập trình. Việc tìm hiểu về danh sách liên kết trong C/C++ có nhiều điểm thú vị là vì:

* Cấu trúc của danh sách liên kết rất đơn giản, việc mô tả nó rất dễ dàng
* Tuy vậy các giải thuật xử lý danh sách liên kết lại có thể rất phức tạp và thú vị
* Làm việc với danh sách liên kết đòi hỏi việc sử dụng con trỏ một cách thành thạo
* Các danh sách liên kết đặc biệt phù hợp cho việc mô tả dùng hình vẽ. Làm việc với chúng giúp bạn phát triển kỹ năng hình tượng hóa vấn đề khi lập trình

Bài viết này sẽ điểm qua một số khái niệm cơ bản về danh sách liên kết và đưa ra 18 bài toán về danh sách liên kết theo thứ tự từ dễ đến khó.

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

Cấu trúc của một danh sách liên kết đơ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 để làm việc với danh sách. 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;
}

Hàm thêm một phần tử vào đầu danh sách:

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 có thể dùng hàm sau để xây dựng một danh sách kết nối đơn giản, dùng làm đầu vào cho các bài toán ở phần sau:

struct node *BuildOneTwoThree() {
struct node *head = NULL;
struct node *second = NULL ;
struct node *third = NULL;

head = (struct node*) malloc(sizeof (struct node));
second = (struct node*) malloc(sizeof (struct node));
third = (struct node*) malloc(sizeof (struct node));

if (!head || !second || !third) {
printf("cannot allocate memory\n");
exit(1);
}
head->data=1;
head->next=second;

second->data=2;
second->next=third;

third->data=3;
third->next=NULL;

return head;
}

_________________
"·´`·.(*·.¸(`·.¸ ¸.·´)¸.·*).·´`·"
"* † * My "LoVe" FoReVeR * † *"
"·´¨*·.¸¸.*..^_^ Chi Yêu Mình Em ^_^..*.¸¸.·*¨."
"·´`·.(¸.·´(¸.·* *·.¸)`·.¸).·´`·"
Về Đầu Trang Go down
Xem lý lịch thành viên http://07t2.forum777.com
final fantasy
Admin
Admin
avatar

Nam Tổng số bài gửi : 1098
Age : 29
Đến từ : Đà Nẵng
Registration date : 04/06/2008

Bài gửiTiêu đề: Re: 18 bài toán về danh sách liên kết   Thu Dec 11, 2008 11:39 pm

18 bài toán về danh sách liên kết

1. Count()

Viết hàm Count() thực hiện việc đếm các lần xuất hiện của một số nguyên trong một danh sách.
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 thứ n trong danh sách (bắt đầu 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 danh sách liên kết và thiết lập con trỏ head thành NULLvoid 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 phần tử đầu tiên của danh sách, phần từ này đồng thời được xóa khỏi danh sách.
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 danh sách một đối tượng tại vị trí thứ nvoid 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 danh sách đã được sắp xếp. Viết hàm để thêm vào danh sách một đối tượng vào danh sách 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 danh sách đầu vào, sắp xếp danh sách 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à danh sách A và B, trả về danh sách 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 danh sách liên kết ra làm hai, ngắt ở giữa. Nếu
chiều dài của danh sách là lẻ thì danh sách thứ nhất sẽ dài hơn danh
sách thứ hai một phần tử.

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 danh sách đã được sắp xếp theo thứ tự tăng dần, hãy xóa các
phần tử bị lặp với điều kiện danh sách 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;
free(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;
free(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) {
if (source == NULL || source->next == NULL) {
*frontRef = source;
*backRef = NULL;
} else {
struct node *fast = source;
struct node *slow = source->next;
while (fast) {
fast = fast->next;
if (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}

_________________
"·´`·.(*·.¸(`·.¸ ¸.·´)¸.·*).·´`·"
"* † * My "LoVe" FoReVeR * † *"
"·´¨*·.¸¸.*..^_^ Chi Yêu Mình Em ^_^..*.¸¸.·*¨."
"·´`·.(¸.·´(¸.·* *·.¸)`·.¸).·´`·"
Về Đầu Trang Go down
Xem lý lịch thành viên http://07t2.forum777.com
 
18 bài toán về danh sách liên kết
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Cần bán gấp đất gần KDC Đồng Danh đường nhựa tận cửa 6m giá chỉ 240tr/62m
» LikeWatch - Sự khác biệt từ các nhãn hiệu danh tiếng
» Những món quà sinh nhật cho bạn gái cung Kim ngưu
» Thơ Hàn Mặc Tử
» Chức danh xưa đi vào địa danh Việt Nam

Permissions in this forum:Bạn không có quyền trả lời bài viết
 :: Học tập :: Thảo luận về chuyện học (HK III) :: CTDL>-
Chuyển đến