Danh Sách Liên Kết Kép Có Cấu Trúc - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.doc) (10 trang)

Trang chủ

Công Nghệ Thông Tin

Cơ sở dữ liệu

danh sách liên kết kép có cấu trúc

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (133.44 KB, 10 trang )

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ácha)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ĩaDanh 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 saupPrev liên kết với phần tử đứng trướcStruct 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áchNode* 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áchMinh 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áchMinh 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 > 1980Mô 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ếpCà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ínhvoid 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; } } }/* Coder:tauit_dnmd */#include<stdio.h>#include<conio.h>typedef struct DNode{ int value; struct DNode *pnext,*prev;}DNODE;DNODE* InitDNode(int x){ DNODE* temp=new DNODE; if(temp==NULL) return NULL; temp->value=x; temp->prev=temp->pnext=NULL; return temp;}typedef struct DList{ DNODE *phead,*ptail;}DLIST;void InitDList(DLIST &L){ L.phead=L.ptail=NULL;}void AddHead(DLIST &L,DNODE *p){ if(p==NULL) return; if(L.phead==NULL) { p->pnext=p->prev=NULL; L.phead=p; L.ptail=L.phead; } else { p->prev=NULL; p->pnext=L.phead; L.phead=p; }}void AddTail(DLIST &L,DNODE *p){ if(p==NULL) return; if(L.phead==NULL) { p->pnext=p->prev=NULL; L.phead=p; L.ptail=L.phead; } else { p->prev=L.ptail; p->pnext=NULL; L.ptail->pnext=p; L.ptail=p; }}int AddAt(DLIST &L,int x,int pos) //them x vao sau Node co gia tri ==pos dau tien{ if(L.phead==NULL) return 0; DNODE *p=L.phead; while(p!=NULL) { if(p->value==pos) break; p=p->pnext; } if(p!=NULL) { DNODE *temp=InitDNode(x); temp->pnext=p->pnext; temp->prev=p; p->pnext=temp; if(p==L.ptail) L.ptail=temp; return 1; } return 0;}void RemoveHead(DLIST &L){ DNODE *x; if(L.phead==NULL) return; x=L.phead; L.phead=L.phead->pnext; if(L.phead!=NULL) L.phead->prev=NULL; delete x;}void RemoveTail(DLIST &L){ DNODE *p,*q; if(L.phead==NULL) return; p=L.ptail; if(p->prev==NULL){ RemoveHead(L);return;} q=p->prev; q->pnext=NULL; L.ptail=q; delete p; }

Tài liệu liên quan

Danh sách liên kết
- 105
- 1
- 8
Code danh sách liên kết
- 1
- 2
- 8
Các thuật toán trên cấu trúc danh sách liên kết (linked list)
- 8
- 1
- 26
Các thuật toán trên cấu trúc, danh sách liên kết
- 8
- 782
- 2
Cấu trúc danh sách liên kết
- 61
- 912
- 5
Các thuật toán trên cấu trúc danh sách liên kết (Linked list)
- 8
- 807
- 5
Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật HCMUS 2010 DANH SÁCH LIÊN KẾT
- 5
- 1
- 21
Chương 9: Danh sách liên kết pdf
- 7
- 523
- 2
Danh sách liên kết đôi doc
- 12
- 966
- 9
CHAPTER 6: DANH SÁCH LIÊN KẾT pdf
- 33
- 571
- 2