PDA

View Full Version : Danh sách liên kết.



daoson_hai
29-12-2007, 21:27
Nghe nói học đại học là sẽ học về "danh sách liên kết" bác nào biết chỉ cho em biết đôi chút về nó với?

mr_invincible
29-12-2007, 21:50
Khi dùng mảng, do có một số nhược điểm: số phần tử được định trước, khó khăn trong việc thêm và xóa phần tử nên người ta đã nghĩ ra việc dùng danh sách liên kết:
- Danh sách liên kết sử dụng bộ nhớ động (heap)
- Mỗi phần tử của danh sách liên kết gồm có một phần chứa địa chỉ dữ liệu và một phần để lưu trữ địa chỉ của phần tử tiếp theo. Phần tử cuối chỉ vào rỗng
Có gì thiếu sót mong các bạn góp ý

meotrang7x
30-12-2007, 08:43
Nhiều lắm bác: danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết vòng v.v... Mời bác xem thêm:
http://en.wikipedia.org/wiki/Linked_list

Trinh Van Hoan
31-12-2007, 16:56
Khi dùng mảng, do có một số nhược điểm: số phần tử được định trước, khó khăn trong việc thêm và xóa phần tử nên người ta đã nghĩ ra việc dùng danh sách liên kết:
- Danh sách liên kết sử dụng bộ nhớ động (heap)
- Mỗi phần tử của danh sách liên kết gồm có một phần chứa địa chỉ dữ liệu và một phần để lưu trữ địa chỉ của phần tử tiếp theo. Phần tử cuối chỉ vào rỗng
Có gì thiếu sót mong các bạn góp ý
Nói mảng & danh sách liên kết đều có những ưu điểm và nhược điểm, tùy từng trường hợp cụ thể và ta sử dụng loại cấu trúc dữ liệu nào cho chính xác.
Mảng: Dùng để lưu trữ danh sách các phần tử (lưu liền kề nhau) cùng kiểu.
-Ưu điểm:
+ Dễ cài đặt và truy nhập các phần tử dữ liệu
+ Tốc độ truy nhập đến một vị trí bất kỳ trên mảng nhanh, hiệu quả
-Nhược điểm:
+ Cần phải xác định trước số phần tử mảng trước khi sử dụng(kể cả mảng động)==>không phù hợp với các bài toán chưa biết trước số lượng các phần tử.
+ Khó khăn trong các thao tác chèn và xóa một phần tử bất kỳ trong mảng. Nếu bài toán mà việc chèn phần tử và xóa phần tử diễn ra liên tục==>tốc độ xử lý sẽ rất chậm.
Danh sách liên kết:Cũng như mảng, danh sách liên kết(DSLK) dùng để lưu trữ danh sách các phần tử. Tuy nhiên cách lưu trữ của DSLK khác hẳn với mảng.Với danh sách liên kết, các phần tử ngoài phần dữ liệu, nó còn lưu trữ các địa chỉ mà các phần tử có quan hệ với nó (nhờ các địa chỉ này mà ta có thể tìm được các phần tử khác nhau trong DS).
DSLK có rất nhiều loại, tuy nhiê chung quy lại nó chỉ có 2 loại cơ bản: Danh sách đơn liên kết và danh sách đa liêu kết.
Ưu điểm:
+ Do DSLK dùng tới đâu thì cấp phát tới đó==> phù hợp với các bài toán mà các phần tử chưa xác định trước.
+ Dễ dàng trong việc xóa, chèn các phần tử trong DS(chỉ cần thay đổi lại các địa chỉ của các phần tử có quan hệ với nó cho phù hợp là được).
Nhược điểm:
+ Khó cài đặt và truy nhập đến các phần tử trong DS.
+ Tốc độ truy nhập của danh sách chậm ==> do đó người ta thường dùng các cây quyết định để phục vụ cho việc tìm kiếm trong DS(cây nhị phân tìm kiếm...)

stonyboy8x
01-12-2008, 12:34
Mình mới nhận đề tài là dùng đồ họa C minh họa giải thuật danh sách liên kếtđơn vòng!các bạn júp mình nhá! mính mới học nên chưa bít đc n` cần tham khảovới lại time ko còn n`cho việc nghiên cúu! júp nhá~!0_+! thanks

the_blind
11-01-2009, 19:44
đây là 1 ví dụ về DSLK đơn [C++] :
#include <iostream.h>

typedef struct Cell* List;
struct Cell
{
int key;
List head,next;
};

void Constructor(Cell &c)
{
c.head = &c;
c.key = NULL;
c.next = NULL;
}

void Constructor(List x)
{
x->head = x;
x->key = NULL;
x->next = NULL;
}

void Insert(Cell &c, int n)
{
c.head->key=n;
List x = new Cell;
Constructor(c);
x->next = c.head;
c.head = x;
}
void Print (Cell c)
{
for (List x = c.head->next; x != NULL; x = x->next)
cout << x->key << " " ;
cout << endl;
}
int main()
{
Cell c;
Constructor(c);
cout << " Nhap so phan tu : ";
int n;
cin >> n;
cout << " Nhap gia tu tung phan tu : ";
for (int i = 1; i <= n; i++)
{
int k;
cin >> k;
Insert(c,k);
}
cout << " Out put : ";
Print(c);
cout << endl;

return 0;
}
////////////////////////////////
mở Visual C++ lên chạy thử coi sao bạn nhé !

stonyboy8x
26-02-2009, 23:43
cám ơn n` n` lắm! 0_+! hì!

ancntt
12-03-2009, 14:33
bạn ơi! bạn có thể hướng dẫn mình cài một đa thức bằng danh sách liên kết theo kiểu lập trình hướnmg đối tượng không.

thehaicitd
09-07-2009, 07:37
tớ thử test bài cua cậu rồi mặc dù không có lỗi xong phần output chưa đáp ứng.chưa đưa ra được danh sách,cậu kiểm tra lại xem nhé!

[=========> Bổ sung bài viết <=========]

có bạn nào biết về cài đặt suy diễn tiến không chỉ dùm mình với gần đây cô mình có cho bài tập lớn về nhà nhưng mình chưa có phương thức xử lý vẫn còn loay hoay phần khai báo.tớ còn phải vận dụng từ thuật toán vào để cài đặt ứng dụng cho bài này.bạn nào biết chỉ giùm mình với,thanks!

khtndtvt
13-09-2009, 21:06
Bạn hỏi về DSLK trong lập trình hướng đối tượng theo mình biết có một cách là bạn đọc trong cuốn Lập trình Hướng đối tượng của GS.Phạm văn Ất ấy.Dễ hiểu,dễ học và có nhiều ví dụ hay...

cuophang
14-09-2009, 20:18
bác nào pro giúp em bài tập này cái..

cài đặt lớp đối tượng liên kết đơn sao cho có thể:

+ chứa được các kiểu dữ liệu khác nhau

+ tính số nút của danh sách

+ tìm tới nút thứ k trong danh sách ,nếu có nút thứ k thì đưa ra

địa chỉ bộ nhớ của nó nếu ko thì đưa ra NULL

+ bổ xung 1 nút vào sau nút k

+ loại bỏ nút đứng trước nút k

+ đảo ngược danh sách

+ hiển thị toàn bộ danh sách

bác nào biết thì giúp em nha

live_a_lie
14-09-2009, 21:11
bác nào pro giúp em bài tập này cái..

cài đặt lớp đối tượng liên kết đơn sao cho có thể:

+ chứa được các kiểu dữ liệu khác nhau

+ tính số nút của danh sách

+ tìm tới nút thứ k trong danh sách ,nếu có nút thứ k thì đưa ra

địa chỉ bộ nhớ của nó nếu ko thì đưa ra NULL

+ bổ xung 1 nút vào sau nút k

+ loại bỏ nút đứng trước nút k

+ đảo ngược danh sách

+ hiển thị toàn bộ danh sách

bác nào biết thì giúp em nha

Bài này dễ mà, bạn nên ngồi đọc các tài liệu về linked list rồi code thử. Nếu còn vướng mắc chỗ nào thì có thể hỏi mọi người chứ làm gì có ai rỗi hơi code hết cho bạn được

cuophang
15-09-2009, 07:42
các pác xem và sửa dùm em nha:

tinh so nut cua danh sach:

int dem_tong_phan_tu_mang(node *pFirst)
{
node *pWalk;
int count;

count = 0;

pWalk = pFirst;

while (pWalk != NULL)
{
count++;
pWalk = pWalk->pNext;
}

return count;
}

\\\\\\\\\\\\\\\\\\\\\

tìm tới nút thứ k :

SkipListNode* Search(SkipList *list, int searchKey)
{
k = list->head;
// điều kiện dừng: (k->forward[i]->key >= searchKey) và (level=1)
for (i=list->level;i>1;i--)
while (k->forward[i]->key < searchKey)
k = k->forward[i];
k = k->forward[1];
if (k->key == searchKey)
return k;
else
return 0;
}
/////////////
đảo ngược danh sach;

List DaoList_TaoList(List &L)
{
NodePointer tam = L.Head;

List L_new;
CreateListEmpty(L_new);

while(L.Head != NULL)
{
//1.Tach L.Head cua L_old;
tam = L.Head; L.Head = L.Head->Next; tam->Next = NULL;
//2.Chen dau List_new;
AddNodeHeadList(L_new,tam->Data);
}
return L_new;
}

ngọa hổ
15-09-2009, 08:25
ơ C++ không thêm bớt phần tử trong mảng được à.

meocon_it
30-11-2009, 01:04
trong C++ cug them, xoa, sua phan tu binh thuong ma., chi la hoi roi xiu thoi.,

trungfptabc
08-03-2010, 08:13
minh co bai tap nhu the nay co pro nao giup minh voi :
nhap vao 1 so nguyen (theo de bai thi fai nhap gia tri cuc ki lon VD : 324214143421254342425545312424) roi add moi chu so cua so do vao 1 danh sach lien ket. minh bi roi cac pro a