Từ 1 tới 8 trên tổng số 8 kết quả

Đề tài: Đảo ngược LinkList

  1. #1
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Mặc định Đảo ngược LinkList

    Mình muonó hỏi các bạn là có thể đaỉo ngược 1 LinkList được khong nhỉ
    Nếu có thì có thể làm như thế nào
    thanks
    Time

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Bạn dùng DSLK nào, và muốn đảo ngược để làm gì vậy?
    ht không hiểu ý bạn lắm.
    Nếu là danh dách liên kết kép thì không cần phải đảo ngược. Vì bạn có thể đi ngược từ cuối danh sách về lại đầu danh sách.
    Không biết ghi gì luôn ...

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    153

    Đây là cách đảo ngược linked list đơn hay nói đúng hơn là tan duyệt ngược linked list:
    C Code:
    1. #include "stdio.h"
    2. #include "alloc.h"
    3. #include "conio.h"
    4. #include "string.h"
    5. typedef struct pp
    6.     {
    7.         char ht[25];
    8.         char qq[20];
    9.         int tuoi;
    10.         struct pp *tiep;
    11.     } nhansu;
    12. main()
    13.     {
    14.         char tt;
    15.         nhansu *pdau,*pcuoi,*p;
    16.                  char tam[10];
    17.         clrscr();
    18.         pdau=NULL;
    19.         do
    20.             {
    21.                     p=(nhansu*)malloc(sizeof(nhansu));
    22.                     printf("\n Ho ten : ");
    23.                   gets(p->ht);
    24.                     printf(" Que quan : ");
    25.                   gets(p->qq);
    26.         printf(" Tuoi: ");
    27.                   gets(tam);
    28.                   p->tuoi=atoi(tam);
    29.                     if (pdau==NULL)
    30.                        {
    31.                          pdau=p;
    32.                          pcuoi=p;
    33.                        p->tiep=NULL;
    34.                     }
    35.                  else
    36.                    {
    37.                      p->tiep=pcuoi;
    38.                          pcuoi=p;
    39.                    }
    40.               printf("\nBam phim bat ky de tiep tuc, ESC de dung");
    41.               tt=getch();
    42.                } while(tt!=27) ;
    43.         /* §­a danh s¸ch liªn kÕt ra mµn h×nh, trá pdau tro */
    44.         printf("\n Danh sach nhu sau :\n");
    45.         p=pcuoi;
    46.         while (p!=NULL)
    47.             {
    48.                 printf("\n Ho ten: %25s  Que : %20s Tuoi :  %d",(*p).ht,(*p).qq,(*p).tuoi);
    49.                 p=p->tiep;
    50.             }
    51.         getch();
    52.         }
    ttecak ?

  4. #4
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi Forlorn_hope Xem bài viết
    Bạn dùng DSLK nào, và muốn đảo ngược để làm gì vậy?
    ht không hiểu ý bạn lắm.
    Nếu là danh dách liên kết kép thì không cần phải đảo ngược. Vì bạn có thể đi ngược từ cuối danh sách về lại đầu danh sách.
    uhm
    Danh sách liên kết đơn bạn ạ.
    Time

  5. #5
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi comeonbaby Xem bài viết
    Đây là cách đảo ngược linked list đơn hay nói đúng hơn là tan duyệt ngược linked list:
    C Code:
    1. #include "stdio.h"
    2. #include "alloc.h"
    3. #include "conio.h"
    4. #include "string.h"
    5. typedef struct pp
    6.     {
    7.         char ht[25];
    8.         char qq[20];
    9.         int tuoi;
    10.         struct pp *tiep;
    11.     } nhansu;
    12. main()
    13.     {
    14.         char tt;
    15.         nhansu *pdau,*pcuoi,*p;
    16.                  char tam[10];
    17.         clrscr();
    18.         pdau=NULL;
    19.         do
    20.             {
    21.                     p=(nhansu*)malloc(sizeof(nhansu));
    22.                     printf("\n Ho ten : ");
    23.                   gets(p->ht);
    24.                     printf(" Que quan : ");
    25.                   gets(p->qq);
    26.         printf(" Tuoi: ");
    27.                   gets(tam);
    28.                   p->tuoi=atoi(tam);
    29.                     if (pdau==NULL)
    30.                        {
    31.                          pdau=p;
    32.                          pcuoi=p;
    33.                        p->tiep=NULL;
    34.                     }
    35.                  else
    36.                    {
    37.                      p->tiep=pcuoi;
    38.                          pcuoi=p;
    39.                    }
    40.               printf("\nBam phim bat ky de tiep tuc, ESC de dung");
    41.               tt=getch();
    42.                } while(tt!=27) ;
    43.         /* §­a danh s¸ch liªn kÕt ra mµn h×nh, trá pdau tro */
    44.         printf("\n Danh sach nhu sau :\n");
    45.         p=pcuoi;
    46.         while (p!=NULL)
    47.             {
    48.                 printf("\n Ho ten: %25s  Que : %20s Tuoi :  %d",(*p).ht,(*p).qq,(*p).tuoi);
    49.                 p=p->tiep;
    50.             }
    51.         getch();
    52.         }
    bạn ơi mình cần đảo ngược thực sự chứ không phải là duyệt ngược
    Time

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Mặc định Đảo ngược LinkList

    -Giả sử head và tail lần lượt là đầu và cuối dslk.
    Sử dụng 1 nút khác (_tail) giả tạo là cuối của dslk:
    C++ Code:
    1. _tail=head;
    2. _tail->tiep=NULL;
    Sử dụng thêm một nút khác (giả sử ban đầu là _tail)
    C++ Code:
    1. _Temp=_tail;
    - Sử dụng vòng lặp for(đi từ đầu đến cuối danh sách liên kết). Cứ mỗi khi duyệt đến nút nào (_Nut), ta chuyển vị trí tiếp theo của nút đó đến _Temp. Cứ thế, đến hết dslk thì ok.
    - Ta chỉ cần gán lại head=_Temp; và tail=_tail. Thế là xong

    C++ Code:
    1.  
    2. _Nut->tiep=_Temp;
    3. _Temp=_Nut;
    4. _Nut=_Temp->tiep;
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 14-04-2008 lúc 07:24 AM. Lý do: hoàn thiện
    Không biết ghi gì luôn ...

  7. #7
    Ngày gia nhập
    04 2011
    Nơi ở
    TPHCM
    Bài viết
    5

    Mặc định Có ! Bạn xem code demo bên dưới

    Trích dẫn Nguyên bản được gửi bởi nthung Xem bài viết
    Mình muonó hỏi các bạn là có thể đaỉo ngược 1 LinkList được khong nhỉ
    Nếu có thì có thể làm như thế nào
    thanks
    Dưới đây tôi viết code đảo cả cấu trúc linkedlist . Còn đảo key của nó thì đơn giản . Bạn có thể làm được
    Code:
    #include<iostream>
    #include<conio.h>
    #include<stdlib.h>
    using namespace std;
    typedef struct node NODE;
    struct node
    {
    	int key;
    	node* next;
    };
    
    NODE* find_endnode(NODE* head)
    {
    	NODE* t =head;
    	while(t->next !=NULL)
    	{
    		t=t->next;
    	}
    	return t;
    }
    void display(NODE* head)
    {
    	NODE* t =head;
    	while(t!=NULL)
    	{
    		cout<<t->key<<"\t";
    		t=t->next;
    	}
    }
    NODE* new_node(int key)
    {
    	NODE* n = (NODE*)malloc(sizeof(NODE));
    	n->key = key;
    	n->next = NULL;
    	return n;
    
    }
    NODE* find_afternode(NODE* head,NODE* p)
    {
    	NODE* t = head;
    	while(t != NULL)
    	{
    		if(t->next == p)
    			return t;
    		t=t->next;
    	}
    	return NULL;
    }
    void add_node(NODE* &head,NODE* n)
    {
    	if(head == NULL)
    		head = n;
    	else
    	{
    		NODE* q = find_endnode(head);
    		q->next=n;
    	}
    
    }
    void rev_node(NODE* &head)
    {
    	NODE* p,*t,*q,*k;
    	t=find_endnode(head);
    	q =t;
    	k =t;
    	while(q != head)
    	{
    		q = find_afternode(head,q);
    		t->next =q;
    		t=t->next;
    	}
    	head= k;
    	q->next =NULL;
    }
    void main()
    {
    	NODE* head = NULL;
    	NODE* n;
    	n = new_node(-4);
    	add_node(head,n);
    	n=new_node(5);
    	add_node(head,n);
    	n=new_node(6);
    	add_node(head,n);
    	n=new_node(7);
    	add_node(head,n);
    	n=new_node(8);
    	add_node(head,n);
    	n=new_node(9);
    	add_node(head,n);
    	n=new_node(10);
    	add_node(head,n);
    	display(head);
    	rev_node(head);
    	cout<<"\n";
    	display(head);
    	getch();
    }

  8. #8
    Ngày gia nhập
    11 2013
    Nơi ở
    paradise
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi nthung Xem bài viết
    Mình muonó hỏi các bạn là có thể đaỉo ngược 1 LinkList được khong nhỉ
    Nếu có thì có thể làm như thế nào
    thanks
    Thân, mình có 1 cách để đảo ngược 1 linked list (singly linked list).
    Ý tưởng như sau, bạn khai báo 3 struct Node gồm *prev,*current,*next.
    Đầu tiên cho prev=NULL( trường next của Node đầu tiên sẽ trỏ về NULL để đánh dấu sự kết thúc list), current=head;
    Dùng vòng lặp while, duyệt từ đầu list (head).
    - next=current->next (lưu địa chỉ của node kế current, nếu ko làm như vậy sau bước 1, ta sẽ mất toàn bộ các node còn lại)
    - current->next=prev (cho trường next của current trỏ về node trước nó)
    - prev=current ( trỏ prev tới vị trí kế tiếp)
    - current=next (trỏ current tới node kế)
    - nếu current==NULL thì dừng vòng lặp, ngựoc lại tiếp tục.
    cho head=prev (sau lần lặp cuối cùng, prev sẽ trỏ vào node đầu tiên (node cuối cùng trước khi đảo), không làm như vậy thì khi in list, ta chỉ thấy được 1 node)
    Bạn chỉ cần làm mọi thứ trong 1 hàm duy nhất, nhanh gọn, mình rất vui nếu bạn tìm đựoc 1 cách nào nhanh hơn cách này.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node{
    	int Data;
    	struct Node *next;
    };
    
    struct Node *head;
    
    //Khoi gan gia tri NULL cho struct header cua danh sach
    void Initialize();
    //Nhap du lieu, dung nhap lieu khi gap so 0
    void Input_Data();
    //In danh sach bang de quy
    void Print(struct Node *p);
    //In nguoc danh sach bang de quy
    void Print_Reverse(struct Node *p);
    //Dao nguoc danh sach bang Iterative Method (Tam dich la phuong phap lap di lap lai)
    struct Node* Reverse_By_Iterative_Method();
    
    int main(){
    	Initialize();
    	Input_Data();
    	printf("\nPrint forward: \n");
    	Print(head);
    	printf("\nPrint backward: \n");
    	Print_Reverse(head);
    	Reverse_By_Iterative_Method();
    	printf("\n");
    	Print(head);
    	return 0;
    }
    
    //Khoi gan gia tri NULL
    void Initialize(){
    	head=NULL;
    }
    //Nhap danh sach, dung nhap lieu khi gap so 0
    void Input_Data(){
    	int Temp;
    	struct Node *pnode;
    	do{
    		scanf("%d",&Temp);
    		if(Temp!=0){
    			pnode=(struct Node*)malloc(sizeof(struct Node));
    			if(pnode==NULL){
    				printf("Out of space!\n");
    				return;
    			}
    			pnode->Data=Temp;
    			pnode->next=NULL;
    			if(head==NULL) head=pnode;
    			else{
    				struct Node *temp=head;
    				while(temp->next!=NULL)
    					temp=temp->next;
    				temp->next=pnode;
    			}
    		}
    	}while(Temp!=0);
    }
    //In danh sach bang de quy
    void Print(struct Node *p){
    	if(p==NULL)	return;
    	printf("%d ",p->Data);
    	Print(p->next);
    }
    //In danh sach dao nguoc bang de quy
    void Print_Reverse(struct Node *p){
    	if(p==NULL)	return;
    	Print_Reverse(p->next);
    	printf("%d ",p->Data);
    }
    //Dao nguoc danh sach bang cach dao nguoc truong dia chi
    struct Node* Reverse_By_Iterative_Method(){
    	struct Node *prev,*current,*next;
    	//Dau tien cho current tro den head
    	current=head;
    	//prev = NULL vi phan tu dau tien sau khi dao nguoc la phan tu cuoi cung cua danh sach
    	//nen no phai mang gia tri NULL de danh dau su ket thuc danh sach
    	prev=NULL;
    	while(current!=NULL){
    		//cho con tro next luu dia chi cua node ke current
    		next=current->next;
    		//cho con tro next cua current tro toi prev (luc dau prev mang gia tri NULL)
    		current->next=prev;
    		//cho prev tro vao current (lan thu 2 tro di prev khong con gia tri NULL)
    		prev=current;
    		//current tro toi next khi nay ta luu dia chi node ke current.
    		current=next;
    	}
    	//cho head = prev 
    	// vi la cuoi, prev va current tro vao node cuoi, ma sau khi dao xong node cuoi lai chinh la node dau tien cua danh sach
    	//nen ta cho head = prev, neu ko lam nhu vay thi chi in ra duoc 1 node duy nhat
    	head=prev;
    	return head;
    }
    Personal Forum: www.mrnoctv.eazy.vn

Các đề tài tương tự

  1. Tạo danh sách linklist trong lập trình hướng đối tượng với C++
    Gửi bởi MATXCOVA trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 6
    Bài viết cuối: 02-10-2011, 05:31 PM
  2. biểu diễn đồ thị bằng linklist như thế nào?
    Gửi bởi rocktea trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 01-12-2010, 02:40 PM
  3. con trỏ trong linklist. Làm sao gán cho một giá trị?
    Gửi bởi rocktea trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 25-11-2010, 09:23 PM
  4. Thắc mắc LinkList
    Gửi bởi maldinxnam trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 26-07-2010, 11:40 AM
  5. Linklist bài toán quản lý sách trên C. Giúp đỡ
    Gửi bởi kidqn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 12-04-2010, 10:10 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn