[Tổng hợp ]Giải bài tập về Danh Sách Liên kết

jony_vu

Bạn bè
Thao tác trên danh sách liên kết đơn.




bài 1 : với các yêu cầu sau.


1: Nhập dạnh sách.( Thêm đầu - Thêm cuối)
2: Xuất danh sách.
3: Liệt kê các phần tử mang phần tử chẵn.
4: Tìm phần tử có phần tử nhỏ nhất.
5: Đếm số lượng số nguyên tố trong danh sách.
6: Thêm phần tử X vào trước phần tử chẳn đầu tiên.
7: Thêm phần tử X vào sau phần tử lẽ cuối cũng.
8: Xoá phần tử nhỏ nhất trong danh sách.
9: Xoá phần tử đứng trước và sau X trong danh sách.
10: Tách danh sách hiện tại thành 2 danh sách sao cho danh sách 1 chứa các phần tử nguyên tố, danh sách 2 chứa các phần tử còn lại






file dslk.h
Code:
#ifndef __DSLK__
#define __DSLK__


#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;


typedef struct node
{
    int data;
    node* pNext;
}NODE;
typedef struct list
{
    NODE* pHead;
    NODE* pTail;
}LIST;


void Init(LIST &l);
NODE* GetNode(int x);
void AddHead(LIST &l,NODE* new_ele);
void AddTail(LIST &l,NODE* new_ele);
void InPut(LIST &l);
void OutPut(LIST l);
void XuatChan(LIST l);
NODE* TimMax(LIST l);
int DemSNT(LIST l);
void ThemXTruocChanDau(LIST &l,int x);
void ThemXSauLeCuoi(LIST &l,int x);
void XoaMin(LIST &l);
void XoaPhanTuTruoc_SauX(LIST &l,int x);
void TachDS(LIST &l,LIST &l1,LIST &l2);
#endif
file main.cpp


Code:
#include "dslk.h"
int MeNu()
{
    
    int c;
    cout<<endl<<endl<<endl<<"                            DANH SACH LIEN KET"<<endl;
    cout<<"      ----------------------------------------------------------------"<<endl;
    cout<<"      |     0 : Thoat.                                               |"<<endl;
    cout<<"      |     1 : Nhap danh sach.                                      |"<<endl;
    cout<<"      |     2 : Xuat danh sach.                                      |"<<endl;
    cout<<"      |     3 : Xuat Chan.                                           |"<<endl;
    cout<<"      |     4 : Tim max.                                             |"<<endl;
    cout<<"      |     5 : Dem so Nguyen To.                                    |"<<endl;
    cout<<"      |     6 : Them x truoc chan dau.                               |"<<endl;
    cout<<"      |     7 : Them x sau le cuoi.                                  |"<<endl;
    cout<<"      |     8 : Xoa phan tu nho nhat trong danh sach.                |"<<endl;
    cout<<"      |     9 : Xoa phan tu truoc va sau x.                          |"<<endl;
    cout<<"      |     10: Tach thanh 2 danh sach(nguyen to va k nguyen to).    |"<<endl;
    cout<<"      ----------------------------------------------------------------"<<endl;
    cout<<endl<<endl<<"ban chon:";
    cin>>c;
    return c;
}
int main()
{
    system("color 2C");
    LIST l;
    int chon;
    Init(l);
    do
    {
        chon=MeNu();
        switch(chon)
        {
        case 0: return 0;


        case 1:
            {
                InPut(l); 
            }break;


        case 2: 
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                    OutPut(l); 
            }break;


        case 3:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                XuatChan(l);
            }break;


        case 4:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                cout<<"\n\nMax la:"<<TimMax(l)->data<<endl<<endl;
            }break;


        case 5:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                cout<<"so luong cac so nguyen to la"<<DemSNT(l);
            }break;


        case 6:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                {
                    int x;
                    cout<<"nhap x =";
                    cin>>x;
                    ThemXTruocChanDau(l,x);
                }
            }break;


        case 7:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                {
                    int x;
                    cout<<"nhap x =";
                    cin>>x;
                    ThemXSauLeCuoi(l,x);
                }
            }break;


        case 8:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                XoaMin(l);
            }break;


        case 9:
            {
                if(l.pHead==NULL)
                    cout<<"danh sach rong - khong the thuc hien thao tac";
                else
                {
                    int x;
                    cout<<"nhap x=";
                    cin>>x;
                    XoaPhanTuTruoc_SauX(l,x);
                }
            }break;
        case 10:
            {
                LIST l1,l2;
                if(l.pHead==NULL)
                    cout<<"danh sach rong ko the tach dc";
                else
                {
                    TachDS(l,l1,l2);
                    if(l1.pHead==NULL)
                    {
                        cout<<"khong co so nguyen to trong list 1"<<endl<<endl;
                        cout<<"danh sach so k nguyen to trong list 2 la"<<endl;
                        OutPut(l2);
                    }
                    else if(l2.pHead==NULL)
                    {
                        cout<<"danh sach so nguyen to trong list 1"<<endl;
                        OutPut(l1);
                        cout<<endl<<endl<<"danh sach list 2 khong co"<<endl;
                    }
                    else
                    {
                        cout<<"danh sach so nguyen to trong list 1"<<endl;
                        OutPut(l1);
                        cout<<endl<<endl<<"danh sach so k nguyen to trong list 2 la"<<endl;
                        OutPut(l2);
                    }
                }
            }break;
        default : cout<<"\n\nban chon ko co trong danh sach, xin nhap lai"<<endl<<endl;break;
        }
        
    }while(1);
    system("pause");
}
file caidat.cpp


Code:
#include "dslk.h"


int n;
void Init(LIST &l)
{
    l.pHead=l.pTail=NULL;
}
NODE* GetNode(int x)
{
    NODE* p;
    p=new NODE;
    if(p==NULL)
        cout<<"cap phat bo nho khong du.";
    p->data=x;
    p->pNext=NULL;
    return p;
}


void AddHead(LIST &l,NODE* new_ele)
{
    if(l.pHead==NULL)
        l.pHead=l.pTail=new_ele;
    else
    {
        new_ele->pNext=l.pHead;
        l.pHead=new_ele;
    }
}
void AddTail(LIST &l,NODE* new_ele)
{
    if(l.pTail==NULL)
        l.pHead=l.pTail=new_ele;
    else
    {
        l.pTail->pNext=new_ele;
        l.pTail=new_ele;
    }
}
void InPut(LIST &l)
{
    int x;
    cout<<"nhap so luong Node:";
    cin>>n;
    Init(l);
    for(int i=1;i<=n;i++)
    {
        cout<<"nhap node x=";
        cin>>x;
        NODE* p=GetNode(x);
        AddHead(l,p);
    }
}


void OutPut(LIST l)
{
    for(NODE* p=l.pHead;p;p=p->pNext)
        cout<<p->data<<" --> ";
    cout<<"NULL";
}


void XuatChan(LIST l)
{
    for(NODE* p=l.pHead;p;p=p->pNext)
        if(p->data%2==0)
            cout<<p->data<<"\t";
}
NODE* TimMax(LIST l)
{
    NODE* max=l.pHead;
    for(NODE* p=l.pHead->pNext;p;p=p->pNext)
        if(p->data>max->data)
            max=p;
    return max;
}
int LaSNT(int x)
{
    if(x<2) return 0;
    for(int i=2;i<=sqrtf(x);i++)
        if(x%2==0)
            return 0;
    return 1;
}
int DemSNT(LIST l)
{
    int d=0;
    for(NODE* p=l.pHead;p;p=p->pNext)
        if(LaSNT(p->data)==1)
            d++;
    return d;
}
NODE* TimChanDau(LIST l)
{
    for(NODE* p = l.pHead;p;p=p->pNext)
        if(p->data%2==0)
            return p;
    return NULL;
}
void ThempTruocq(LIST &l,NODE* p,NODE* q)
{
    NODE*k=l.pHead;
    while(k->pNext!=q)
        k=k->pNext;
    p->pNext=q;
    k->pNext=p;
}
void ThemXTruocChanDau(LIST &l,int x)
{
    NODE* p=GetNode(x);
    NODE* q=TimChanDau(l);
    if(q==l.pHead || q==NULL)
        AddHead(l,p);
    else
        ThempTruocq(l,p,q);
}
NODE* TimLeCuoi(LIST l)
{
    NODE* p;
    NODE* k=NULL;
    for(p=l.pHead;p;p=p->pNext)
        if(p->data%2!=0)
            k=p;
    return k;
}
void ThempSauq(LIST &l,NODE* p,NODE* q)
{
    p->pNext=q->pNext;
    q->pNext=p;
}
void ThemXSauLeCuoi(LIST &l,int x)
{
    NODE* p=GetNode(x);
    NODE* q=TimLeCuoi(l);
    if(q==NULL || q==l.pTail)
        AddTail(l,p);
    else
        ThempSauq(l,p,q);
}
NODE* TimMin(LIST l)
{
    NODE* min=l.pHead;
    for(NODE*p=l.pHead->pNext;p;p=p->pNext)
        if(p->data<min->data)
            min=p;
    return min;
}
void XoaDau(LIST &l)
{
    NODE* h=l.pHead;
    l.pHead=l.pHead->pNext;
    delete(h);
}
void XoaCuoi(LIST &l)
{
    NODE*p=l.pHead;
    while(p->pNext!=l.pTail)
        p=p->pNext;
    NODE* k=l.pTail;
    l.pTail=p;
    l.pTail->pNext=NULL;
    delete(k);
}
void Xoap(LIST &l,NODE* p)
{
    NODE* k=l.pHead;
    while(k->pNext!=p)
        k=k->pNext;
    k->pNext=p->pNext;
    delete(p);
}
void XoaMin(LIST &l)
{
    NODE* p=TimMin(l);
    if(p==l.pHead)
        XoaDau(l);
    else
        if(p==l.pTail)
            XoaCuoi(l);
        else
            Xoap(l,p);
}


NODE* TimX(LIST &l, int x)
{
    NODE* p=l.pHead;
    for( ; p; p=p->pNext)
        if(p->data==x)
            return p;
    return NULL;
}
void XoapTruocq(LIST &l,NODE* p,NODE*q)
{
        NODE*k=l.pHead;
        while(k->pNext!=p)
            k=k->pNext;
        k->pNext=q;
        delete(p);
}
void XoapSauq(LIST &l,NODE* p,NODE*q)
{
    NODE* h=l.pHead;
    while(h->pNext!=l.pTail && h!=NULL)
        h=h->pNext;
    if(q==h)
        XoaCuoi(l);
    else
    {
        NODE*k=p;
        q->pNext=k->pNext;
        delete(p);
    }
}
void XoaPhanTuTruoc_SauX(LIST &l,int x)
{
    NODE* q=TimX(l,x);


        if(q==NULL)
            cout<<"ko co gia tri x can tim";
        else
        {
            if(q==l.pHead)
            cout<<"";
    
            else if(q==l.pHead->pNext)
            XoaDau(l);
            else
            {
                NODE*p=l.pHead;
                while(p->pNext!=q && p!=NULL)
                    p=p->pNext;
                XoapTruocq(l,p,q);
            }
            if(q==l.pTail)
                cout<<"";
            else
                XoapSauq(l,q->pNext,q);
        }
}


void TachDS(LIST &l,LIST &l1,LIST &l2)
{
    Init(l1);
    Init(l2);
    NODE* p=l.pHead,*pAdd;
    while(p)
    {
        int k=p->data;
        pAdd=GetNode(k);
        if(LaSNT(k)==1)
            AddHead(l1,pAdd);
        else
            AddHead(l2,pAdd);
        p=p->pNext;
    }
    Init(l);
}


Bài 2: cho 2 danh sách liên kết l1 và l2, gồm các phần tử là số nguyên, thực hiện các yêu cầu sau:


1: sắp xếp l1 và l2 tắng dần.
2: nối l1 và l2 thành l3 sao cho l3 tăng dần.




file noidanhsachtang.h


Code:
#ifndef __NOIDS__
#define __NOIDS__


#include <iostream>
#include <iomanip>
#include <math.h>
#include <conio.h>
#include <windows.h>
using namespace std;


typedef struct node
{
    int data;
    node* pNext;
}NODE;
typedef struct list
{
    NODE* pHead;
    NODE* pTail;
}LIST;


void Init(LIST &l);
NODE* GetNode(int x);
void AddHead(LIST &l,NODE* new_ele);
void AddTail(LIST &l,NODE* new_ele);
void InPut(LIST &l);
void OutPut(LIST l);
void SapXep(LIST l);
void NoiDS(LIST l1,LIST l2,LIST &l3);
#endif
file main.cpp


Code:
#include "noidanhsachtang.h"
int MeNu()
{
    
    int c;
    cout<<endl<<endl<<endl<<"                            DANH SACH LIEN KET"<<endl;
    cout<<"      ----------------------------------------------------------------"<<endl;
    cout<<"      |     0 : Thoat.                                               |"<<endl;
    cout<<"      |     1 : Nhap 2 danh sach.                                    |"<<endl;
    cout<<"      |     2 : Sap xep list 1 va list 2.                            |"<<endl;
    cout<<"      |     3 : Xuat danh sach da nhap.                              |"<<endl;
    cout<<"      ----------------------------------------------------------------"<<endl;
    cout<<endl<<endl<<"ban chon:";
    cin>>c;
    return c;
}
int main()
{
    system("color 2C");
    LIST l1,l2,l3;
    int chon;
    Init(l1);
    Init(l2);
    do
    {
        chon=MeNu();
        switch(chon)
        {
        case 0: return 0;


        case 1:
            {
                cout<<"nhap List 1"<<endl;
                InPut(l1);
                cout<<"nhap List 2"<<endl;
                InPut(l2);
            }break;
        case 2:
            {
                SapXep(l1);
                SapXep(l2);
                cout<<"da sap xep xong";
            }break;
        case 3: 
            {
                cout<<endl<<endl<<"List 3 da noi thang cong"<<endl;
                NoiDS(l1,l2,l3);
                OutPut(l3);
            }break;


        default : cout<<"\n\nban chon ko co trong danh sach, xin nhap lai"<<endl<<endl;break;
        }
    }while(1);
    system("pause");
}
file caidat.cpp


Code:
#include "noidanhsachtang.h"


int n;
void Init(LIST &l)
{
    l.pHead=l.pTail=NULL;
}
NODE* GetNode(int x)
{
    NODE* p;
    p=new NODE;
    if(p==NULL)
        cout<<"cap phat bo nho khong du.";
    p->data=x;
    p->pNext=NULL;
    return p;
}


void AddHead(LIST &l,NODE* new_ele)
{
    if(l.pHead==NULL)
        l.pHead=l.pTail=new_ele;
    else
    {
        new_ele->pNext=l.pHead;
        l.pHead=new_ele;
    }
}
void AddTail(LIST &l,NODE* new_ele)
{
    if(l.pTail==NULL)
        l.pHead=l.pTail=new_ele;
    else
    {
        l.pTail->pNext=new_ele;
        l.pTail=new_ele;
    }
}
void InPut(LIST &l)
{
    int x;
    cout<<"nhap so luong Node:";
    cin>>n;
    Init(l);
    for(int i=1;i<=n;i++)
    {
        cout<<"nhap node x=";
        cin>>x;
        NODE* p=GetNode(x);
        AddHead(l,p);
    }
}


void OutPut(LIST l)
{
    for(NODE* p=l.pHead;p;p=p->pNext)
        cout<<p->data<<" --> ";
    cout<<"NULL";
}
void HoanVi(int &a,int &b)
{
    int t=a;a=b;b=t;
}
void SapXep(LIST l)
{
    
    for(NODE* p=l.pHead;p;p=p->pNext)
        for(NODE*q=p->pNext;q;q=q->pNext)
            if(p->data>q->data)
                HoanVi(p->data,q->data);
}
void NoiDS(LIST l1,LIST l2,LIST &l3)
{
    Init(l3);
    NODE* p1=l1.pHead;
    NODE* p2=l2.pHead;
    NODE* Add;
    while(1)
    {
        if(p1==NULL && p2==NULL) break;
        else if(p1==NULL && p2!=NULL)
        {
            Add=GetNode(p2->data);
            AddTail(l3,Add);
            p2=p2->pNext;
        }
        else if(  p2==NULL && p1!=NULL )
        {
            Add=GetNode(p1->data);
            AddTail(l3,Add);
            p1=p1->pNext;
        }
        else
        {
            if(p1->data < p2->data )
            {
                Add=GetNode(p1->data);
                AddTail(l3,Add);
                p1=p1->pNext;
            }
            else
            {
                Add=GetNode(p2->data);
                AddTail(l3,Add);
                p2=p2->pNext;
            }
        }
        
    }
}
Bài 3: cho danh sách sinh viên. mỗi sinh viên gồm các thông tin: MSSV, họ tên, địa chỉ, giới tính và điểm trung bình... thực hiện các yêu cầu sau:


1: Nhập danh sách sinh viên.
2: Xuất danh sách sinh viên.
3: Xoá 1 sinh viên với MSSV khỏi danh sách.
4: Sắp xếp danh sách tăng dần theo điểm trung bình.
5: Liệt kê các sinh viên có điểm trung bình >= 5.
6: Đếm số lượng sinh viên nam.
7: Cập nhật điểm trung bình của 1 SV thông qua MSSV.


file sinhvien.h


Code:
#ifndef __DSSV__
#define __DSSV__


#include <iostream>
#include <string.h>
#include <conio.h>
#include <iomanip>
using namespace std;


typedef struct sinhvien
{
    char mssv[11]; 
    char hoten[50];
    int gt;
    float dtb; 
}SINHVIEN;


typedef struct node
{
    SINHVIEN info;
    struct node* pNext;
}NODE;


typedef struct list
{
    NODE* pHead;
    NODE* pTail;
}LIST;


void init(LIST &l);
NODE* TaoNode(SINHVIEN sv);
void NhapSV(SINHVIEN &x);
void Input(LIST &l,SINHVIEN &sv);
void ChenDau(LIST &l, NODE* ele);
void ChenCuoi(LIST &l,NODE* ele);
void XuatSV(LIST l);
void XuatDSSV(LIST l,SINHVIEN sv);
void XoaSV(LIST &l,char mssv[]);
void SapXepDTBTang(LIST l);
void LietKeTBLonHon5(LIST l);
int DemSVNam(LIST l);
void CapNhatDem(LIST l,char mssv[]);
#endif
file main.cpp


Code:
#include "sinhvien.h"


int Menu()
{
    int c;
    cout<<endl<<endl<<"                      CHUONG TRINH QUAN LY SINH VIEN"<<endl;
    cout<<"          ------------------------------------------------------"<<endl;
    cout<<"          |      1 : nhap danh sach.                           |"<<endl;
    cout<<"          |      2 : Xuat Danh Sach.                           |"<<endl;
    cout<<"          |      3 : Xoa 1 sinh vien voi MSSV.                 |"<<endl;
    cout<<"          |      4 : Sap xep SV tang dan theo DTB.             |"<<endl;
    cout<<"          |      5 : Liet ke SV co DTB >= 5.0.                 |"<<endl;
    cout<<"          |      6 : Dem so luong SV nam.                      |"<<endl;
    cout<<"          |      7 : Cap nhat DTB cua VS thong qua MSSV.       |"<<endl;
    cout<<"          |      0 : Thoat.                                    |"<<endl;
    cout<<"          ------------------------------------------------------"<<endl<<endl;
    cout<<"xin moi ban chon:";cin>>c;
    return c;
}
int main()
{
    system("color 2C");
    int chon;
    SINHVIEN sv;
    LIST l;
    do{
        chon=Menu();
        switch(chon)
        {
        case 0: return 0;
        case 1:
            {
                init(l);
                Input(l,sv);
                cout<<endl<<endl<<endl;
            }break;
        case 2:
            XuatDSSV(l,sv);break;
        case 3:
            {
                char mssv[11];
                cin.ignore(1);
                cout<<"nhap ma so sinh vien can xoa:";
                cin.get(mssv,11);
                XoaSV(l,mssv);
            }break;
        case 4:
            {
                SapXepDTBTang(l);
                cout<<endl<<"da sap xep xong"<<endl;
            }break;
        case 5:
            {
                    LietKeTBLonHon5(l);
            }break;
        case 6:
            {
                cout<<"so luong sinh vien nam la:"<<DemSVNam(l);
            }break;
        case 7:
            {
                char mssv[11];
                cin.ignore(1);
                cout<<"nhap MSSV can cap nhat:";
                cin.get(mssv,11);
                CapNhatDem(l,mssv);
            }break;
        
        default:cout<<endl<<endl<<"nhap sai sinh moi nhap lai"<<endl<<endl;break;
        }
    }while(true);
    system("pause");
}
file caidat.cpp


Code:
#include "sinhvien.h"


void init(LIST &l)
{
    l.pHead=NULL;
    l.pTail=NULL;
}


NODE* TaoNode(SINHVIEN sv)
{
    NODE* p;
    p=new NODE;
    if(p== NULL)
        return NULL;
    p->info=sv;
    p->pNext=NULL;
    return p;
}
void NhapSV(SINHVIEN &x)
{
   cin.ignore(1); 
    cout<<"nhap ma so sinh vien:"; 
    cin.get(x.mssv,11); 
    cin.ignore(1); 
    cout<<"nhap ho va ten:"; 
    cin.get(x.hoten,50); 
    cout<<"nhap gioi tinh (1: nam - 0: nu):"; 
    cin>>x.gt;
    cout<<"nhap diem trung binh:"; 
    cin>>x.dtb; 
}
void ChenDau(LIST &l, NODE* ele)
{
    if(l.pHead==NULL)
    {
        l.pHead=ele;
        l.pTail=l.pHead;
    }
    else
    {
        ele->pNext=l.pHead;
        l.pHead=ele;
    }
}
void ChenCuoi(LIST &l,NODE* ele)
{
    if(l.pTail==NULL)
        ChenDau(l,ele);
    else
    {
        ele->pNext=l.pTail->pNext;
        l.pTail->pNext=ele;
        l.pTail=ele;
    }
}
void Input(LIST &l,SINHVIEN &sv)
{
    int n;
    NODE* p;
    cout<<endl<<endl<<"nhap so luong sinh vien:";
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cout<<endl<<endl<<"nhap thong tin sinh vien thu"<<i<<endl;
        cout<<"---------------------------------"<<endl;
        NhapSV(sv);
        p=TaoNode(sv);
        ChenCuoi(l,p);
        cout<<endl<<endl;
    }
}
void XuatSV(SINHVIEN sv)
{


    cout<<"          *          ma so sinh vien: "<<sv.mssv<<"."<<endl; 
    cout<<"          *          ho va ten: "<<sv.hoten<<"."<<endl; 
    cout<<"          *          gioi tinh:";
    if(sv.gt==1)
        cout<<" nam."<<endl;
    else cout<<" nu."<<endl;
    cout<<"          *          diem trung binh: "<<sv.dtb<<"."<<endl; 
}
void XuatDSSV(LIST l,SINHVIEN sv)
{
    int i=1;
    cout<<"                      DANH SACH SINH VIEN"<<endl;
    cout<<"          ********************************************"<<endl;
    for(NODE* p=l.pHead;p!=NULL;p=p->pNext)
        {
            cout<<"          *          sinh vien thu "<<i<<":"<<endl;
            XuatSV(p->info);
            if(p!=l.pTail)
            cout<<"          *___________________________________________"<<endl;
            i++;
        }
    cout<<"          ********************************************";
} 
void XoaDau(LIST &l)
{
    NODE* h=l.pHead;
    l.pHead=l.pHead->pNext;
    delete(h);
}
void XoaCuoi(LIST &l)
{
    NODE*p=l.pHead;
    while(p->pNext!=l.pTail)
        p=p->pNext;
    NODE* k=l.pTail;
    l.pTail=p;
    l.pTail->pNext=NULL;
    delete(k);
}
void Xoap(LIST &l,NODE* p)
{
    NODE* k=l.pHead;
    while(k->pNext!=p)
        k=k->pNext;
    k->pNext=p->pNext;
    delete(p);
}
void XoaSV(LIST &l,char mssv[])
{
    NODE* p;
    for(p=l.pHead;p;p=p->pNext)
    {
        if(strcmp(p->info.mssv,mssv)==0)
        {
            if(p==l.pHead)
                XoaDau(l);
            else
                if (p==l.pTail)
                    XoaCuoi(l);
                else
                    Xoap(l,p);
            break;
        }
    }
    if(p==NULL)
        cout<<endl<<endl<<"khong tim thay sinh vien co ma so nay"<<endl;
    else
        cout<<endl<<endl<<"xoa thanh cong"<<endl;
}
void HoanVi(SINHVIEN &a,SINHVIEN &b)
{
    SINHVIEN t=a;a=b;b=t;
}
void SapXepDTBTang(LIST l)
{
    for(NODE*p=l.pHead;p;p=p->pNext)
        for(NODE* p1=p->pNext;p1;p1=p1->pNext)
            if(p->info.dtb>p1->info.dtb)
                HoanVi(p->info,p1->info);
}
void LietKeTBLonHon5(LIST l)
{
    NODE* p;
    int flag=0;
    cout<<"          DANH SACH SINH VIEN CO DIEM TRUNG BINH  >=  5"<<endl;
    cout<<"          ********************************************"<<endl;
    for(p=l.pHead;p;p=p->pNext)
        if(p->info.dtb>=5)
        {
            XuatSV(p->info);
            flag=1;
            if(p!=l.pTail)
            cout<<"          *___________________________________________"<<endl;
        }
    if(flag==0)
        cout<<"khong co sinh vien nao co diem trung binh >=5"<<endl;
    cout<<"          ********************************************"<<endl;
}
int DemSVNam(LIST l)
{
    NODE*p;
    int d=0;
    for(p=l.pHead;p;p=p->pNext)
        if(p->info.gt==1)
            d++;
    return d;
}
void CapNhatDem(LIST l,char mssv[])
{
    NODE*p;
    for(p=l.pHead;p;p=p->pNext)
        if(strcmp(p->info.mssv,mssv)==0)
        {
            cout<<"nhap dem can sua:";
            cin>>p->info.dtb;
            break;
        }
    if(p==NULL)
        cout<<endl<<"khong tim thay mssv vua nhap"<<endl;
}
Bài 4
1 : Nhập danh sách số nguyên.
2 : Xuất danh sách số nguyên.
3 : Tính tổng.
4 : Sắp Xếp.


Code:
#include <iostream.h>
typedef struct node//khai bao node
{
      struct node*pNext;//con tro ke tiep
       int info;//kieu so nguyen cho danh sach
} NODE;
typedef struct list//danh sach chua pTail va pHead
{
       NODE* pTail;
       NODE* pHead;
}LIST;


void init(LIST &l);//ham gan cho danh sach la NULL
NODE* getnode(int x);//ham tao ra 1 node moi chua so nguyen
void addHead(LIST &l,NODE* new_ele)//ham them 1 node moi vao dau danh sach
void addTail(LIST &l, NODE* new_ele);//ham them node moi vao cuoi danh sach
void input(LIST &l); // ham nhap danh sach
void output(LIST l);// ham xuat danh sach
long sum(LIST l);//ham tinh tong danh sach
void HoanVi(int &a,int &b);// ham hoan vi
void SapXepTang(LIST l);//ham sap xep
int main()
{
    LIST lst;
    int x;
     init(lst);
    input(lst);
    output(lst);
    cout<<"tong cac node la:"<<sum(lst);
    SapXepTang(lst);
    cout<<endl<<"da sap xep tang dan"<<endl;
    output(lst);
    system("pause");
}
void init(LIST &l)//gan cho danh sach la NULL ngay tu dau
{
     l.pHead=NULL;
     l.pTail=NULL;
}
NODE* getnode(int x)
{
      NODE *p;
      p=new NODE;//tao ra 1 node moi co con tro bat ki
      if(p==NULL)
                 return NULL;
      p->info=x; // gan so nguyen x vao node moi
      p->pNext=NULL;//cho node moi do tro den NULL
      return p;
}
void addHead(LIST &l,NODE* new_ele)
{
     if(l.pHead==NULL)//neu danh sach la NULL thi 
     {
                      l.pHead=new_ele;//pHead luc nay la NULL se dc gan= node moi tao
                      l.pTail=l.pHead;//pTail se bang pHead vi chi co 1 node H va T se nam chung
     }
     else//neu da co tren 1 node trong danh sach thi
     {
         new_ele->pNext=l.pHead;//node moi tro den pHead
         l.pHead=new_ele;//pHead = node moi
     }
}
void addTail(LIST &l,NODE* new_ele)
{
     if(l.pTail==NULL)//chua co node nao thi them vao dau
                    addHead(l,new_ele);
     else
     {
        new_ele->pNext=l.pTail->pNext;
        l.pTail->pNext=new_ele;
        l.pTail=new_ele;
     }
}
void input(LIST &l)
{
     int n,x;
     cout<<"nhap so luong node = ";
     cin>>n;
     for(int i=1;i<=n;i++)// o day i chi the hien so luong phan tu trong danh sach
     {
             cout<<"nhap node thu "<<i<<" = ";
             cin>>x;
             
             NODE* p=getnode(x);//cho gia tri x vao 1 node va gan no vao node p
             addTail(l,p);//them node p nay vao sau danh sach
     }
}
void output(LIST l)
{
     for(NODE* p=l.pHead;p!=NULL;p=p->pNext)
               cout<<p->info<<"\t";//p->info co nghia la dua ra so nguyen x
}
long sum(LIST l)
{
     long s=0;
     for(NODE* p=l.pHead;p!=NULL;p=p->pNext)
               s=s+p->info;
               return s;
}


void HoanVi(int &a,int &b)
{
     int t=a;a=b;b=t;
}


void SapXepTang(LIST l)
{
     for(NODE* p=l.pHead;p;p=p->pNext)
     {
               for(NODE*q=p->pNext;q;q=q->pNext)
                   if((p->info)>(q->info))
                       HoanVi(p->info,q->info);
     }
còn nữa.......
 

thaihungdaklak

Thành viên
Góp ý cái nhé ! một cái diễn đàn code mà copy code về nằm 1 hàng thì quá tệ, admin xem lại nhé !, thông tin hay mà ko thể chia sẻ thì diễn đàn này chẳng có tác dụng gì !
 

crviet92

Thành viên
A ơi em muốn hỏi về tạo 1 template lớp danh sách đơn có các phương thức tạo danh sách,thêm 1 nút,xóa 1 nút,sửa 1 nút,duyệt danh sách
như trong danh sách đơn thì nó có phần thêm 1 nút vào đầu,vào cuối mà phần này ta tạo 1 nút thêm là như nào e k hiểu lắm a giúp em nhé?
 

hungxc

Thành viên
Thêm bài tập dạng này :)

Sử dụng danh sách liên kết đơn cho bài tập Danh Sách Sinh Viên


Dùng mảng một chiều để lưu trữ một lớp học có N sinh viên. Biết rằng mỗi sinh viên bao gồm các thông tin sau: Tên (chuỗi ký tự), Mã số sinh viên (chuỗi ký tự), Điểm trung bình. Hãy viết hàm thực hiện các yêu cầu sau:
a.In danh sách sinh viên ra màn hình
b.Liệt kê những sinh viên có điểm trung bình cao nhất trong lớp học.
c.Cho biết số sinh viên có điểm trung bình >=5. Nếu không có thì thông báo không có.
d.Tìm một sinh viên có tên X trong lớp học (X nhập từ bàn phím)
e.Xoá một sinh viên có mã số cho trước trong lớp học. Nếu không có thì thông báo không có.
f.Sắp xếp danh sách sinh viên tăng theo điểm trung bình bằng thuật toán sắp xếp mà các bạn đã học (Selection Sort, Interchange Sort, Binary Sort)
g.Chèn một sinh viên vào lớp học, biết ràng sau khi chèn danh sách sinh viên vẫn tăng dần theo điểm trung bình.

Code:
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct sv
{
    char ten[20];
    char MSSV[10];
    int dtb;
};
struct NODE
{
    sv info;
    struct NODE* next;
};
struct LIST
{
    NODE *head;
    NODE *tail;
};
NODE* CreateNode (sv x)
{
    NODE *p;
    p=new NODE;
    if(p==NULL)  exit(1);
    p->info=x;
    p->next=NULL;
    return p;
}
void CreateList (LIST &L)
{
    L.head=L.tail=NULL;
}
void input (sv &x)
{
    printf("\nNhap MSSV: ");  fflush(stdin); gets(x.MSSV);
    printf("\nNhap ten: ");  fflush(stdin); gets(x.ten); 
    printf("\nNhap dtb: "); scanf("%d", &x.dtb);
}
void AddLast (LIST &L, NODE *p)
{
    if(L.head==NULL)  L.head=L.tail=p;
    else
    {
        L.tail->next=p;
        L.tail=p;
    }
}
void nhap (LIST &L)
{
    sv x;
    char kt; 
    printf("\nNhan phim bat ki de tiep tuc nhap.");
    printf("\nNhan 0 de dung nhap.");
    do
    {
        kt=getch();
        if(kt=='0')  break;
        input(x);
        NODE *p=CreateNode(x);
        AddLast(L,p);
    } while (1);
}
void output (sv x)
{
    printf("\n%s    %s      %d",x.MSSV,x.ten,x.dtb);
}
void xuat (LIST L)
{
    NODE *p;
    p=L.head;
    while(p!=NULL)
    {
        output(p->info);
        p=p->next;
    }
}
void maxdtb (LIST L)
{
    NODE *p,*max;
    int dem;
    p=L.head;
    max=p;
    while (p!=NULL)
    {
        if(p->info.dtb>max->info.dtb)  { max=p; dem=0; }
        if(p->info.dtb==max->info.dtb) { max=p; dem++; }
        p=p->next;
    }
    printf("\nSV co dtb cao nhat la: \n");
    if(dem==0)  output(max->info);
    else
    {
        NODE *q=L.head;
        while (q!=NULL)
        {
            if(q->info.dtb==max->info.dtb) output(q->info);
            q=q->next;
        }
    }
}
void thongkedtb (LIST L)
{
    NODE *p;
    int dem=0;
    p=L.head;
    while (p!=NULL)
    {     
        if(p->info.dtb>=5)  dem++;
        p=p->next;
    }
    if(dem==0)  printf("\nKo co sv co dtb>=5.");
    else printf("\nCo %d sv co dtb >=5.",dem);
}
void tim (LIST L)
{
    NODE *p;
    int dem=0;
    char k[20];
    printf("\nNhap ten sv can tim: ");
    fflush(stdin);
    gets(k);
    p=L.head;
    while (p!=NULL)
    {
        if(strcmp(k,p->info.ten)==0)      dem++;
        p=p->next;
    }
    if(dem!=0)
    {
            printf("\nTim thay sv: "); output(p->info);
    }
    else printf("\nKo tim thay.");
}
void xoa (LIST &L)
{
    NODE *p, *q;
    char a[10];
    p=L.head;
    q=NULL;
    printf("\nNhap MSSV can xoa: ");
    fflush(stdin);
    gets(a);
    while (p!=NULL)
    {
        if(strcmp(a, p->info.MSSV)==0)    break;
        else printf("\nKo co sv can xoa.");
        q=p;
        p=p->next;
    }
    if(q!=NULL)
    {
        if(p!=NULL)
        {
            q->next=p->next;
            delete (p);
            if(p==L.tail)  L.tail=q;
            delete(p);
        }
    }
    else
    {
        L.head=p->next;
        delete(p);
        if(L.head==NULL)  L.tail=NULL;
    }
}
void selectionsort (LIST &L)
{
    NODE *p,*q,*min;
    p=L.head;
    sv temp;
    while (p!=L.tail)
    {
        min=p;
        q=p->next;
        while (q!=NULL)
        {
            if(q->info.dtb<min->info.dtb)  min=q;
            q=q->next;
        }
        temp=p->info;
        p->info=min->info;
        min->info=temp;
        p=p->next;
    }
}
void menu()
{
    LIST L;
    NODE *p,*q,*moi;
    sv x;
    char chon;
    CreateList(L);
    do
    {
        printf("\n\t\t\tMENU");
        printf("\n\t1. Nhap ds");
        printf("\n\t2. In ds");
        printf("\n\t3. Ds sv co dtb cao nhat");
        printf("\n\t4. Ds sv co dtb >=5");
        printf("\n\t5. Tim sv");
        printf("\n\t6. Xoa sv");
        printf("\n\t7. Sap xep ds");
        printf("\n\t8. Chen sv");
        printf("\n\tNhap 0 de thoat");
        chon=getch();
        switch(chon)
        {
            case '1': { nhap(L); break;}
            case '2': { xuat(L); break;}
            case '3': { maxdtb(L); break;}
            case '4': { thongkedtb(L); break;}
            case '5': { tim(L); break;}
            case '6': { xoa(L); printf("\nDs sau khi xoa: "); xuat(L); break;}
            case '7': { selectionsort(L);printf("\nDs sau khi sap xep: "); xuat(L); break;}
            case '8':
                    {
                        sv them;
                        printf("\nNhap thong tin sv can them: ");
                        input(them);
                        NODE *t= CreateNode(them);
                        AddLast(L,t);
                        selectionsort(L);
                        printf("\nDs sau khi them :");
                        xuat(L);
                        break;
                    }
            case '0': exit(1);
            default: printf("\nNhap lai.");
        }
    } while (chon!='0');
}
int main()
{
    while(1)
    {
        menu();
        getch();
    }
}
 
xây nhà trọn gói tại quảng ngãi xây nhà trọn gói quảng ngãi xây nhà trọn gói tại quảng ngãi nội thất quảng ngãi
Top