Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Một số chú ý về xâu liên kết

    Một số nội dung cần thuộc như nước chảy. Không được nhầm lẫn. Nếu nhầm là 0 điểm luôn.
    Về các đề bài về một xâu liên kết sẽ có dạng:

    Cho một danh sách được tổ chức bởi cấu trúc sau:
    Danh_sách: ^ Phần_tử
    Phần_tử
    = Record;
    Dữ_liệu_1: Data;
    Dữ_liệu_2: Data;
    ...
    Dữ_liệu_n: Data;
    Next: List;
    End


    Trong đó:
    Những phần chữ màu đỏ sẽ được thay bằng nội dung của đề bài, các bạn nhớ phải viết và lập luận theo nó. Phần chữ màu đen là từ khoá.

    Danh sách liên kết thường được cho luôn là nó được trỏ bởi Head.

    Một số phần cần thuộc luôn, để khi ứng dụng chỉ việc bê nguyên xi:

    1. Ví dụ đề bài:
    Cho một danh sách S được tổ chức bởi cấu trúc sau:

    List: ^ Element;

    Element
    = Record;

    D: Data;

    Next: List;

    End



    Tìm một phần tử có nội dung X.

    Giả sử phần tử cần tìm là Y.
    Bước 1. Cho Y bằng luôn Head, ở đây Head được gọi tên là S (Tên danh sách).
    Y:=S;
    Bước 2. Viết vòng lặp cho Y chạy dần qua từng phần tử, nếu dữ liệu của phần tử hiện tại (Y) mà không bằng giá trị cần tìm (X), thì chuyển sang phần tử kế tiếp.
    While (Y^.D <>X) Do
    Y:=Y^.Next

    Kết quả, Y sẽ dừng đúng vị trí của phần tử cần tìm.

    Hay nhầm dễ bị trừ điểm, hoặc bị đưa về mo là: Lẽ ra phải viết Y.D <> X thì lại viết Y.Data <>X
    Bởi tên trường theo đầu bài là D.



    Được sửa bởi Admin ngày Sun Jun 19, 2011 6:04 am; sửa lần 1.

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Thêm phần tử vào danh sách liên kết

    Cần học thuộc luôn. Bao giờ cũng phải làm như vầy mới đủ. Giả sử có danh sách liên kết như phần trên trình bày. Bây giờ cần thêm một phần tử có giá trị B vào sau phần tử có giá trị A trong danh sách.

    Thủ tục cần thực hiện:
    Tìm lần lượt từng phần tử. Bằng cách sử dụng một biến con trỏ luôn chỉ vào 1 nút có trong danh sách. Nó là phần tử hiện tại. Nếu phần tử hiện tại có giá trị là A, thì phải thực hiện tạo một nút mới M. Sau đó đặt lại các giá trị trường Next giúp cho việc nối thành chuỗi được liên tục:
    1. Trường Next của M sẽ chỉ theo trường Next của ô hiện tại.
    2. Phần tử tìm thấy (Tức phần tử hiện tại) có trường Next chỉ vào M.
    3. Chuyển ô hiện tại thành M.

    Thế là xong.
    Trong trường hợp thêm vào tất cả các ô có giá trị A, thì cứ lần lượt mà thực hiện:
    4. Kiểm tra tiếp từ M xem giá trị có bằng B không, khi không bằng thì chuyển sang phần tử kế tiếp.

    Bây giờ là bài thầy giáo giảng:
    Gọi Y là con trỏ đang trỏ vào đầu danh sách.

    Proc Insert (A: Data; VAR Y: List)
    While (Y <> Null)
    Begin
              IF (^Y.D = A) THEN
                        New (M)
                        M.D = B
                        M^.Next = Y^.Next
                        Y^.Next = M
    IF Y<> Null THEN Y=Y^.Next
    End

    Ở đây đang tranh cãi là có cần thiết phải có IF Y<> Null THEN không? vì vòng While đã kiểm tra điều kiện Y<> Null rồi.



    Được sửa bởi Admin ngày Sun Jun 19, 2011 5:00 am; sửa lần 1.

    https://khmt.123.st

    3[Ý kiến]Cần thống nhất cách hiểu và làm việc với xâu liên kết Empty Xoá một phần tử trong danh sách Wed May 18, 2011 1:14 pm

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Xoá một phần tử trong danh sách

    Bài này thầy làm theo cách đệ quy. Nghĩa là khi gặp phần tử cần xoá thì thầy cho nó luôn là phần tử kế tiếp.
    Bài của thầy:

    Proc Delete (VAR Y: List);
    IF (Y <> Null) Then
              IF (Y^.D = C) Then
                        Y:= Y^.Next
    IF (Y <> Null) Then Delete (Y^.Next);

    Ở đây, biến được truyền là một phần tử của chuỗi tên là Y. Nên thủ tục này sẽ làm việc với 1 phần tử hiện tại. Nếu thoả mãn cần xoá thì thay phần tử đang xét bằng phần tử kế tiếp mà nó trỏ đến.



    Được sửa bởi Admin ngày Sun Jun 19, 2011 4:57 am; sửa lần 1.

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Hợp 2 danh sách và trừ hai danh sách liên kết
    Cho 2 danh sách liên kết A, B có cấu trúc như trên viết thủ tục để có được danh sách C có thể là

    [You must be registered and logged in to see this image.] Cộng 2 danh sách, ở đây những phần tử trùng nhau về giá trị, cả ở trong A và B sẽ chỉ được đưa vào danh sách C 1 lần. Có lời giải của thầy.

    [You must be registered and logged in to see this image.] Trừ 2 danh sách, những phần tử có trong A mà cũng có trong B sẽ bị loại đi. Chỉ còn một phần của A. Có lời giải của thầy.

    [You must be registered and logged in to see this image.] Tạo danh sách là những phần tử giống nhau của cả A và B. Tự viết.

    [You must be registered and logged in to see this image.] Tạo danh sách là những phần tử không giống nhau của cả A và B. Tự viết.

    (Sở dĩ phải gõ lên đây để sẽ có lúc chúng ta cần đến, hoặc những đồng chí nghỉ học có cái mà tham khảo)

    Ở đây thầy đưa ra một hàm phải thiết kế đó là hàm thuộc. Nếu xét một danh sách liên kết, có một phần tử có giá trị x thì trả về giá trị đúng, ngược lại là sai.

    Cách 1: Giả sử A là con trỏ đang chỉ ra phần tử hiện tại.
    Func Thuoc (X: Data, A: List);
    While (^A.D <> x ) A:= A^.Next
    return A!= Null;

    Cách 2:
    While A <>Null Do
    IF A^.D = x return True
    else A:= A^.Next
    Return False


    Đây là nội dung hàm CONG
    C:=A;
    While B <> Null do
    IF B !thuộc (B^.D, C)
    New (M); M^.D = B^.D;
    M^.Next :=C;
    C:=M
    B:= B^.Next


    Đây là nội dung hàm TRU

    C:=Null;
    While (A<> Null)
    IF !Thuộc (A^D, B)
    New (M); M^.D = A^.D;
    A:=A^.Next


    Các bạn căn cứ để viết hàm lại cho hoàn chỉnh nha. Bạn nào làm xong chia sẻ chút nha.

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Sử dụng đệ quy để thêm một phần tử vào danh sách
    Đây là bài thầy ra về nhà làm.

    Proc THEM (A, B: Data, Y: List)
    IF (Y^.D = A) then
    New (M);
    M.D = B;
    M^.Next = Y^.Next
    Y^.Next = M
    IF (Y<> Null) THEN
    THEM (A, B, Y^.Next)
    End.

    https://khmt.123.st

    mrP

    mrP
    Thành viên cao cấp
    Thành viên cao cấp
    Tìm một phần tử có nội dung X.

    Giả sử phần tử cần tìm là Y.
    Bước 1. Cho Y bằng luôn Head, ở đây Head được gọi tên là S (Tên danh sách).
    Y:=S;
    Bước 2. Viết vòng lặp cho Y chạy dần qua từng phần tử, nếu dữ liệu của phần tử hiện tại (Y) mà không bằng giá trị cần tìm (X), thì chuyển sang phần tử kế tiếp.
    While (Y^.D <>X) Do
    Y:=Y^.Next

    Kết quả, Y sẽ dừng đúng vị trí của phần tử cần tìm.


    Nếu không tìm thấy X thì Y sẽ đi về đâu?
    :\

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Sở dĩ tôi đưa lại vấn đề này vì danh sách liên kết là bài đáng được tranh luận để rút ra cái đúng nhất. Nhiều người trong lớp chúng ta không phải là học sinh cũ của HV nên có cách lưu trữ và tiếp cận với vấn đề này khác nhau. Về đây học kiến thức của HV là học những gì tiên tiến nhất, hiện tại chúng ta đang tự mâu thuẫn là không biết tiếp cận kiểu gì, khi mà sách và lời giảng trên lớp của thầy có nhiều chỗ được trình bày và triển khai theo 2 hướng khác nhau. Vấn đề này, lớp mình cũng đã tranh luận nhiều chưa đến hồi phân giải. Bởi theo nguyên tắc, nếu phần này chưa thống nhất, thì tất cả những bài tập về sau nếu dữ liệu ra kiểu này thì mỗi người sẽ hiểu một phách. Mà cách đánh giá của các thầy chỉ có một loại đáp án. Học theo đáp án của thầy thì cần làm rõ như thế nào?
    Tham gia làm rõ phần này, đề nghị các đ/c chuyên viên có bình luận để tìm ra xem những gì ta đang quan niệm và những gì là bài giảng để tìm ra và làm theo nội dung chuẩn theo đáp án của đáp án chấm thi hơn.

    Để chỉ ra những điểm không thống nhất giữa sách của thầy viết và bài giảng của thầy, tôi chịu khó gõ lại nội dung sách lên đây, vì tôi biết chúng ta tranh luận ở lớp bao phen rồi vẫn bất phân thắng bại, và cuối cùng nếu vẫn không biết theo cái nào, thì sẽ viết biên bản gửi lên khoa, đề nghị xem cách nào là đúng để chúng ta học cho chuẩn với đáp án chấm thi.

    Tôi gõ chính xác từng chữ, kể cả những chữ mà các đồng chí bảo là sai chính tả. Những chữ này sẽ được tô màu. Việc gõ này phục vụ khi tranh luận, các đồng chí chỉ việc copy, đỡ phải gõ lại.
    Phần nền màu hồng, để che đi chống dàn trải bài viết, khi nào cần đọc các đ/c nháy chuột vào đó.

    Nội dung sách "Cấu trúc dữ liệu và giải thuật" của Học viện KTQS, tài liệu ôn thi Cao học ngành CNTT, sản xuất năm 2005, Chương 3, trang 19.
    Danh sách liên kết

    I. Danh sách liên kết đơn

    1. Định nghĩa:

    Mỗi nút của danh sách được lưu trữ trong một phần tử nhớ - gọi là nút (nude) của danh sách. Mỗi nút chiếm một số ô nhớ nhất định. Trong mỗi nút, ngoài các ô nhớ dành để lưu trữ thông tin của phần tử tương ứng, còn một số ô nhớ chứa địa chỉ của phần tử đứng ngay sau nó trong danh sách. Cách tổ chức dữ liệu theo kiểu móc nối các phần tử trong danh sách như vậy giải thích cho cách đặt tên kiểu cấu trúc dữ liệu. Có thể hình dung một cách đại khái một nút như sau:
    Data
    Next
    Trường Data chứa thông tin phần tử, trường Next chứa địa chỉ của nút tiếp theo. Trường Next của nút cuối cùng chứa địa chỉ đặc biệt, dùng để đánh dấu kết thúc danh sách, ký hiệu Nil.
    Ví dụ, định nghĩa danh sách dữ liệu về một nhân sự:
    Ví dụ, định nghĩa danh sách dữ liệu về một nhân sự:
    Một phần tử trong danh sách đơn là một biến động sẽ được yêu cầu cấp phát khi cần. Và danh sách đơn chính là sự liên kết các biến động này với nhau. Từ cách tổ chức như vậy, dễ thấy được, nếu có địa chỉ của phần tử đầu tiên trong danh sách đơn thì có thể dựa vào thông tin Next của nó để truy xuất đến phần tử thứ 2 trong xâu, và lại dựa vào thông tin Next của phần tử thứ 2 để truy xuất đến phần tử thứ 3... Nghĩa là để quản lý một xâu đơn, chỉ cần biết địa chỉ phần tử đầu xâu. Thường một con trỏ Head sẽ được dùng để lưu trữ phần tử đầu xâu, ta gọi Head là đầu xâu. Ta có thể khai báo:
    Head: LINK;
    Nếu dùng mũi tên để chỉ mối liên kết thông thường qua trường Next, ta có thể hình dung một danh sách móc nối đơn như sau:
    [You must be registered and logged in to see this image.]
    Ký hiệu Ø chỉ mối nối không. Nếu danh sách rỗng thì đặt Head = Nil.

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    2. Các phép toán:
    1. Tìm một phần tử có nội dung X

    • Danh sách được trỏ bởi Head
    • X là dữ liệu cần tìm
    • R là nút cần tìm
                        1) R: = Head;
                        2) While (R^.Data ≠ X) Do R:=R^.Next;
    2. Bổ sung một nút mới vào danh sách móc nối đơn để chứa phần tử X.

    • Danh sách được trỏ bởi Head;
    • R là con trỏ, trỏ tới một nút đang có trong danh sách
    • X chứa dữ liệu cần bổ sung vào
    • Tạo một nút mới ngay sau R để lưu giá trị X
                        1) New (P); Khởi tạo một nút mới
                        2) P^.Data := X;
                        3) P^.Next := R^.Next;
                        4) R^.Next := P;
    Nháy vào phần hồng hồng này để ẩn hiện hình vẽ minh hoạ:
    3. Loại bỏ một nút ra khỏi danh sách đơn

    • Danh sách được trỏ tới bởi Head
    • R là con trỏ trỏ tới một nút đang có trong danh sách
    • Loại bỏ nút R
              IF R:= Head Then Head:= Head^.Next;
                        ELSE
                        Begin
                                  1) P := Head;
                                  2) While (P^.Next ≠ R) Do P := P^.Next;
                                  3) P^.Next := R^.Next;
                        End;
    Nháy vào phần hồng hồng này để ẩn hiện hình vẽ minh hoạ:
    4. Ghép hai danh sách đơn

    • Cho hai danh sách được trỏ bởi Head và P
    • Ghép P vào cuối Head
                        1) New (R);
                        2) R := Head;
                        3) While (R^.Next ≠ Nil) Do R := R^.Next;
                        4) R^. Next := P;

    https://khmt.123.st

    sangminh2009

    sangminh2009
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    anh ơi . cho em hỏi trường hợp cần loại phần tử cuối cùng trong danh sách P thì làm thế nào?
    Đây chỉ nói chung chung là loại một phần tử bất kỳ nên em chưa rõ lằm nhờ anh chị hướng dẫn?
    em cảm ơn nhiều.

    BQT:
    Câu này đã được trả lời ít nhất 2 lần ở 2 topic gần đây:

    [You must be registered and logged in to see this image.] [You must be registered and logged in to see this link.] [You must be registered and logged in to see this link.]

    Đề nghị search trước khi hỏi cho đỡ mất công

    trangmeomeo

    trangmeomeo
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    xin lỗi em hỏi mọi người một câu hơi ngớ ngấn một chút: kí hiệu" ^ "trong các bước gán có nghĩa là gì vậy ? Hix! Quả thật khi vào ôn trường mình em mới biết tới kí hiệu này.

    Ban QT:
    Bạn đã lập trình với biến con trỏ chưa? Nếu bạn chưa học đến biến con trỏ sẽ không hiểu ký hiệu biến con trỏ để làm gì. Nó là ký hiệu để bạn lập trình chỉ ra vị trí của giá trị trong ô nhớ thôi.

    Ví dụ cho bạn dễ hiểu. Lẽ ra bạn phải gán giá trị cho biến x bằng 5000 chẳng hạn. Cách lập trình thông thường là ngửa cái biến x ra, rồi phụt vào đấy giá trị = 5000 đúng không. Sau đó cập nhật lại giá trị vào cái danh sách địa chỉ ghi x = 5000.
    Còn cách lập trình với biến con trỏ là lập trình trong bộ nhớ địa chỉ. Giống như bạn lãnh đạo vậy đó. Ghi x^ = b. Nghĩa là đổ vào biến x giá trị mà giá trị đó lưu ở vị trí b. Lúc này trong b là 1 tỷ hay 1 triệu thì x sẽ có giá trị 1 triệu hay 1 tỷ. Thay vì cộng trừ các giá trị 1 tỷ hay 1 triệu (chạy qua bộ nhớ, tốn thời gian và công sức) thì ta chỉ báo nó là đổi giá trị trong địa chỉ thôi. Sau này cộng trừ triệt tiêu địa chỉ thì ta chỉ lấy giá trị cuối cùng ở một địa chỉ khác, thay vì phụt giá trị trực tiếp vào.
    Như bạn đó, lẽ ra bạn giải quyết xong việc phải đếm tiền ăn ngay, thì thay vào việc đó ta dùng biến chon trỏ để trả tiền trong tài khoản vậy thôi.
    Thế nhé! Nếu bạn lập trình tốt thông qua biến con trỏ thì bạn thấy tốc độ máy chạy nhanh hơn nhiều. Các cấu trúc bây giờ người ta đưa ra một dạng dữ liệu có con trỏ thì có dấu mũ đó bạn!

    Anh Đức

    Anh Đức
    Thành viên cao cấp
    Thành viên cao cấp
    trangmeomeo đã viết:xin lỗi em hỏi mọi người một câu hơi ngớ ngấn một chút: kí hiệu" ^ "trong các bước gán có nghĩa là gì vậy ? Hix! Quả thật khi vào ôn trường mình em mới biết tới kí hiệu này.

    Bó tay chấm com... [You must be registered and logged in to see this image.]

    trangmeomeo

    trangmeomeo
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    trời. Bó tay thì bác cũng phải giả thích cho em hiểu chứ :(

    Ban QT:
    Nếu em có gì không hiểu thì điện thoại cho anh
    [You must be registered and logged in to see this link.], hoặc [You must be registered and logged in to see this link.] Quản trị và Chuyên viên diễn đàn nhé. 0976.096.086, 0982.601.369 bọn anh cũng chưa có vợ đâu!

    Anh Đức

    Anh Đức
    Thành viên cao cấp
    Thành viên cao cấp
    Đó là ký hiệu con trỏ... Em nhé!

    thinhdh1588

    thinhdh1588
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    theo như mình biết thì node trong danh sách gồm có 2 phần: một là giá trị(key) và hai là chứa link ( NEXT )đến node kế tiếp.vậy thì muốn thao tác trên phần nào(key, link) thì phải trỏ tới nó đúng ko?
    vậy thì ký hiệu ^: mang ý nghĩa là trỏ tới 1 phần tử nào đó.
    vd: M^.Next tức là nude M trỏ tới phần NEXT (link đến node tiếp theo trong danh sách liên kết)

    mình có quyển cẩm nang thuật toán(ko dùng nữa) nếu bạn cần thì mình có thể cho bạn để ôn tập
    PS: anh phạm thái hưng chưa có gia đình( nhưng đã có người iu) (CuoiBo)

    trangmeomeo

    trangmeomeo
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    thinhdh1588 đã viết:theo như mình biết thì node trong danh sách gồm có 2 phần: một là giá trị(key) và hai là chứa link ( NEXT )đến node kế tiếp.vậy thì muốn thao tác trên phần nào(key, link) thì phải trỏ tới nó đúng ko?
    vậy thì ký hiệu ^: mang ý nghĩa là trỏ tới 1 phần tử nào đó.
    vd: M^.Next tức là nude M trỏ tới phần NEXT (link đến node tiếp theo trong danh sách liên kết)

    mình có quyển cẩm nang thuật toán(ko dùng nữa) nếu bạn cần thì mình có thể cho bạn để ôn tập
    PS: anh phạm thái hưng chưa có gia đình( nhưng đã có người iu) (CuoiBo)
    Thanks các anh đã giải thích cho em hiểu. Nhưng có thể giúp em giải thích thêm về Điều kiện trong if của cấu trúc dưới đây được không ạ:

    Proc Insert (A: Data; VAR Y: List)
    WHILE (Y <> Null)
    Begin
    IF (^Y.D = A) THEN
    New (M)
    M.D = B
    M^.Next = Y^.Next
    Y^.Next = M
    IF Y<> Null THEN Y=Y^.Next
    End


    à quên mất bạn thinhdh1588 bảo cho mình quyển cẩm nang thuật toán à. vậy thì còn gì bằng, nhưng làm sao để mình lấy được đây???????? (ChamChi)

    thinhdh1588

    thinhdh1588
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    ah mình xin giải thích giùm bạn như sau:
    trước hết đây là thủ tục chèn một nude mới vào danh sách :D(chèn có điều kiện). Bài toán là chèn một nude mới vào sau nude có giá trị =A

    WHILE (Y <> Null) // đây là câu lệnh dùng để duyệt danh sách, vòng lặp sẽ dừng khi ta ở cuối
    danh sách (tức là Y=Null)
    Begin
    IF (Y^.D = A) THEN // câu lệnh này dùng để kiểm tra xem nếu nude hiện thời có giá trị =A thì
    chèn thêm 1 nude mới vào

    New (M) // thủ tục tạo mới nude M

    M.D = B // gán giá trị B cho nude M

    M^.Next = Y^.Next // nude link (NEXT) của M sẽ trỏ vào nude đứng sau nude hien thời( nút đứng
    sau nút chứa giá trị A)

    Y^.Next = M // nude chứa giá trị A sẽ trỏ tới( link tới) nude M

    IF Y<> Null THEN Y=Y^.Next // câu lệnh này mình nghĩ không cần thiết.
    End



    PS: sáng thứ 4: 27-6 bọn mình thi môn của thầy lâm. nếu rảnh thì bạn có thể lên tầng 10( phòng 1013 tòa nhà S1 bên xuân phương) mình sẽ mang cho. hoặc không thì liên hệ với mình theo số: 097.909.1368

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất