Thứ Ba, 21 tháng 2, 2012

Danh sách liên kết kép - Code ví dụ

Danh sách liên kết kép

Cho danh sách liên kết kép có cấu trúc:
       struct  hs
            {
                char    ht [30];
                float    ns ;
                 hs* next;
                 hs* prev;
             }
  Gọi p là con trỏ trỏ tới nút đầu danh sách
a)Bổ sung một phần tử vào cuối danh sách.
b)Tìm và in ra họ tên các học sinh có năm sinh từ năm 1980 trở về đây.
c)Xóa một phần tử ở đầu danh sách.

1.Định nghĩa
Danh sách liên kết kép là danh sách mà mỗi phần tử trong danh sách có kết nối với một phần tử đứng trước và một phần tử đứng sau nó



2.Cài đặt DSLK kép

#include<iostream.h>
#include<iomanip.h>
//#include<stdio.h>
Struct data
{
Char ht[30];
Float ns;
};

pNext liên kết với phần tử đứng sau
pPrev liên kết với phần tử đứng trước

Struct tagDNode
{
Data  Info;
Node*  pPrev;
Node*  pNext;
};
Typedef  tagDNode Node;

Struct DList
{
Node*  Head;
Node*  Tail;
};

3.Thủ tục nhập thông tin cho 1 phần tử trong danh sách

Node*  InputNode()
{
Node*  q = new node;
Cout<<”Nhập họ tên : “;
Cin.ignore();
//Fflush(stdin);
Cin.getline(q->info.ht,30);
//Gets(q->info.ht);
Cout<<”Nhập ngày sinh : “;
Cin>>q->info.ns;
q->pNext = q->pPrev = NULL;
return q;
}


4. Chèn 1 phần tử vào cuối danh sách
Minh họa :



Mô tả :
+ Nếu danh sách rỗng thì :
Head = new_ele;
Tail = Head;
+ Ngược lại :
Tail->Next = new_ele; (1)
New_ele->Prev = Tail; (2)
Tail = new_ele; (3)
Cài đặt :

void   AddTail   (List & L )
       {
          Node* new_ele = InputNode () ;
           if ( L.head == NULL )    
        {
                  L.head = L.tail = new_ele ;
                     }
           else
                {
           new_ele -> pPrev = L.tail ;
           L.tail -> pNext = new_ele;              
           L.tail = new_ele;
                  }
         }


5. Xóa thông tin phần tử cuối danh sách
Minh họa :

Mô tả :
+ Nếu danh sách khác rỗng
P = Tail; // p là phần tử cần xóa
Tail = Tail->Prev; // tách p ra khỏi xâu
Tail->Next = NULL;
Free(p); // hủy biến động do p trỏ đến
+ Nếu Head = NULL thì Tail = NULL; // Danh sách rỗng


Cài đặt :

Void DelTail(List &L)
{
Node* p;
If (L.tail != NULL)
{
L.tail = p;
L.tail = L.tail->pPrev;
L.tail->pNext = NULL;
Delete p;
If (L.head == NULL)
L.tail = NULL;
Else
L.head->pPrev = NULL;
}
}


6. In ra Danh sách những người có năm sinh > 1980
Mô tả :
+ p = Head; // cho p trỏ đến phần tử đầu danh sách
+ Trong khi (p != NULL) và (p->info.ns > 1980) thực hiện :
- Cout<<p->info; // In ra thông tin của p
- P = p->Next; // Cho p trỏ đến phần tử kế tiếp

Cài đặt :

Void Process(List &L)
{
Node *p = L.head;
If (L.head == NULL)
Cout<<”\nDanh sach rong !!! “; Cout<<”\n\n==============================”;
Cout<<”\nDanh sach những người sinh sau năm 1980 : “;
While (p->pNext != NULL)
{
If (p-> info.ns > 1980)
{
Cout<<”\nHọ tên : “<<p->info.ht;
Cout<<”\nNam sinh : ”<<p->info.ns;
Cout<<”\n”;
}
P = p->pNext;
}
}

7. Chương trình chính

void main ()
       {
          List  L ;
CreatList(L) ;
int tk;
menu:
          cout<<"\n=============MENU===============\n\n";
cout<<"1. Them mot phan tu vao cuoi danh sach \n";
cout<<"2. Hien thi nhung nguoi co nam sinh > 1980 \n";
cout<<"3. Xoa phan tu cuoi danh sach \n";
cout<<"4. Thoat \n ";
cin>>tk;
switch (tk)
{
case 1:
{
int  t = 1 ;
          cout<<"\nThem 1 phan tu vao cuoi danh sach ";
          while  ( t ==1 )
          {
        AddTail  ( L) ;
        cout<< "Tiep tuc nhap ? ( 1 / 0 ) : " ;
          cin>> t ;
}
goto menu;
}
case 2:
{
Process( L ) ;
goto menu;
}
case 3:
{
DelTail(L);
goto menu;
}
case 4:
{
exit(1);
}
default:
{
cout<<"Lua chon khong phu hop ! \n";
cout<<"Xin moi chon lai !!! ";
goto menu;
}
}
       }


Code hoàn chỉnh :


#include<iostream.h>
#include<stdio.h>
#include<process.h>
struct   hs
 {
char   ht [30] ;
int     ns ;
};
 
typedef   struct    node
{
 hs    info ;
                       node    *next ;
 node    *prev;
                  };
struct   List
                 {
 node  *head ;
          node  *tail ;
};
// Kh?i t?o danh sách r?ng
void   CreatList(List & L)
{
L.head = NULL ;
L.tail = NULL ;
 }
   node *  new_ele =  NULL;

// Nh?p thông tin cho 1 ph?n t?
   node*   _input ()
 {
        node * q = new  node ;
 cout<< "\nHo ten : " ;
        fflush  (stdin) ;
 gets ( q -> info.ht ) ;
        cout<< "Nhap nam sinh : " ;
        cin>> q -> info.ns ;
 q -> next = q -> prev = NULL ;
        return q ;
      }
//  B? sung 1 ph?n t? vào cu?i danh sách
    void   AddTail   (List & L )
{
           new_ele = _input () ;  // Nh?p thông tin c?a ph?n t? m?i
           if ( L.head == NULL ) // Ki?m tra danh sách r?ng
{
                    //N?u ds r?ng thì
   //head = new_ele;
   //tail = head;
L.head = L.tail = new_ele ;
               }
            else
             {
//Ngu?c l?i
   //tail = new_ele->prev;
   //tail->next = new_ele;
   //tail = new_ele;
 new_ele -> prev = L.tail ;
                 L.tail -> next = new_ele;              
                 L.tail = new_ele;
              }
}
 // In ra danh sách h?c sinh có nam sinh t? 1980 tr? v? dây
 void   Process  ( List   L )
        {
node * p = L.head  ; // con tr? p tr? t?i ph?n t? d?u tiên c?a danh sách
            if  ( L.head == NULL ) //Ki?m tra danh sách r?ng
               cout<< "\nDanh sach rong !!! " ;
               cout<<"\n\n===========================\n";
               cout<< "\nDanh sach nhung nguoi sinh sau nam 1980 : \n  " ;
while ( p -> next != NULL )
               {
                   if ( p -> info.ns > 1980 )
   //Trong khi (p!=NULL)& ( p -> info.ns > 1980 )
   //Th?c hi?n:
//Xu?t ra thông tin p
   //p = p->next;
                     {
                        cout<<"\nHo ten : "<<p ->info.ht ;
         cout<<"\nNam sinh :"<<p->info.ns;
cout<<"\n";
                       }
    p = p->next;
                  }
             }
//Xóa  thông tin h?c sinh cu?i danh sách
  void   DelTail  ( List  & L )
     {
 node*  p;
        if  ( L.tail != NULL ) // N?u danh sách khác r?ng
          {
L.tail = p ; //p là ph?n t? c?n h?y
//Tách p ra kh?i xâu
                L.tail = L.tail -> prev ;
   L.tail -> next = NULL ;
             delete  p ; //H?y bi?n do p tr? d?n
             if ( L.head == NULL )
//N?u nút d?u là r?ng thì nút cu?i r?ng
                   L.tail = NULL ;
             else
   //ngu?c l?i head->prev = NULL;
                  L.head -> prev = NULL ;
        }
}
void main ()
       {
           List  L ;
 CreatList(L) ;
 int tk;
 menu:
 cout<<"\n================MENU===============\n\n";
 cout<<"1. Them mot phan tu vao cuoi danh sach \n";
 cout<<"2. Hien thi nhung nguoi co nam sinh > 1980 \n";
 cout<<"3. Xoa phan tu cuoi danh sach \n";
 cout<<"4. Thoat \n ";
 cin>>tk;
 switch (tk)
 {
 case 1:
 {
 int  t = 1 ;
           cout<<"\nThem 1 phan tu vao cuoi danh sach ";
           while  ( t ==1 )
              {
                   AddTail  ( L) ;
                   cout<< "Tiep tuc nhap ? ( 1 / 0 ) : " ;
                   cin>> t ;
}
 goto menu;
 }
 case 2:
 {
 Process( L ) ;
goto menu;
 }
 case 3:
 {
 DelTail(L);
 goto menu;
 }
 case 4:
 {
 exit(1);
 }
 default:
 {
 cout<<"Lua chon khong phu hop ! \n";
 cout<<"Xin moi chon lai !!! ";
 goto menu;
 }
 }
 }

3 nhận xét: