2012-02-19 ~ VinhVu

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;
}
}
}

Thứ Ba, 21 tháng 2, 2012

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

Popular Posts

Blog Archive

Nhãn

Tìm kiếm Blog này

About