Bài giải cấu trúc dữ liệu và giải thuật [LIST ]

#pragma once

class Node//lớp này là biểu diễn cho 1 nút trên danh sách liên kết
{

public :
int gia_tri;
Node *next;
Node(int giatri)
{
gia_tri=giatri;
this->next=NULL;
}
};


class LIST//1 danh sách gồm phần tử đầu,pt cuối và pt giữa (theo anh Lê Mậu Long)
{
Node *pt_dau,*pt_duoi,*pt_giua;

public://những phần theo sau là những khai báo còn định nghĩa của nó thì ở file .cpp
int chiso;
LIST(void);//phương thức khởi tạo
Node *Huy_Phan_tu(Node *pt);//hỗ trợ phương thức hủy
~LIST(void);//phương thức hủy
void Chen_Vao_List(int giatri,Node *pt_vi_tri_chen);//chèn ở 1 vị trí bất kì
void Chen_Vao_Dau(int giatri);
void Chen_Vao_Cuoi(int giatri);
void In_Danh_Sach();
bool Tim_Phan_tu(int giatri);
Node *Truy_Xuat_Tai_Vi_Tri_Index(int index);
void Xoa_Phan_Tu_Dau();
void Xoa_Phan_Tu_Cuoi();
void Xoa_Phan_Tu_Giua(Node *pt);
int Dem_Phan_Tu_List();
Node *DaoNguoc1(Node *pt);//hổ trợ hàm đảo ngược
void DaoNguoc();

};
//////////////////// file trên đuợc lưu lại dạng LIST.h /////////////
// List.cpp : Defines the entry point for the console application.
//
#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
#include "stdafx.h"//nếu chạy = visual studio thì cần còn chạy với cFree thì hình như khỏi thêm cái này(lúc tạo với VS nó có sẵn)
#include <stdio.h>
#include <tchar.h>
#include "LIST.h"
#include <iostream>



using namespace std;




LIST::LIST()
{
chiso=0;

this->pt_dau=this->pt_duoi=this->pt_giua=NULL;

}



Node *LIST::Huy_Phan_tu(Node *pt)//hỗ trợ phương thức hủy
{

if(pt->next!=NULL)
{
delete Huy_Phan_tu(pt->next);
}

return pt;


}



LIST::~LIST(void)//phương thức hủy dùng đệ qui
{
delete Huy_Phan_tu(this->pt_dau);


}




void LIST::Chen_Vao_List(int giatri, Node *pt_vi_tri_chen)
{
Node *p=new Node(giatri);

if(pt_vi_tri_chen==NULL)
{
pt_vi_tri_chen=p;
}
else
{
p->next=pt_vi_tri_chen->next;
pt_vi_tri_chen->next=p;
}
}
void LIST::Chen_Vao_Dau(int giatri)
{
Node *p=new Node(giatri);
if(this->pt_dau==NULL)
{
this->pt_dau=pt_duoi=pt_giua=p;
this->pt_duoi->next=NULL;
}
else if(pt_dau==pt_duoi)
{
pt_duoi=p;
pt_dau->next=pt_duoi;

}
else
{
p->next=pt_dau->next;
pt_dau->next=p;
}

}
void LIST::Chen_Vao_Cuoi(int giatri)
{
Node *p=new Node(giatri);
if(this->pt_duoi==NULL)
{
this->pt_duoi=pt_dau=pt_giua=p;
}
else
{
this->pt_duoi->next=p;
}
this->pt_duoi=p;
}

void LIST::In_Danh_Sach()
{
this->pt_giua=this->pt_dau;
while(this->pt_giua)
{
cout<<this->pt_giua->gia_tri<<"->";
this->pt_giua=this->pt_giua->next;
}
cout<<"NULL\n";
}



bool LIST::Tim_Phan_tu(int giatri)
{
pt_giua=pt_dau;
while(pt_giua)
{
if(pt_giua->gia_tri==giatri)
return true;//nếu tìm ra thì trả về là có
pt_giua=pt_giua->next;
}

return false;//nếu không tìm ra thì trả về là false
}
Node *LIST::Truy_Xuat_Tai_Vi_Tri_Index(int index)
{
pt_giua=pt_dau;
int bien_dem=0;
if(index==0)
{
return pt_dau;
}
//ngược lại
while(pt_giua)
{
bien_dem++;
if(bien_dem==index)
{
Node *p;
p=pt_giua->next;
return p;
}
pt_giua=pt_giua->next;
}
cout<<"\nindex vượt quá số lượng danh sách\n";
return NULL;

}

void LIST::Xoa_Phan_Tu_Dau()
{
if(pt_dau!=NULL)//nếu danh sách có phần tử thì mới làm
{
Node *p=pt_dau;
pt_dau=pt_dau->next;//chuyển phần tử đầu xịch tới 1 đơn vị
delete p;

if(pt_dau==NULL)//nếu danh sách chỉ có 1 phần tử
pt_duoi=pt_giua=NULL;
}
}

void LIST::Xoa_Phan_Tu_Cuoi()
{
pt_giua=pt_dau;
if(pt_giua!=NULL)
{
if(pt_giua->next==NULL)//trường hợp 1 phần tử
{
delete pt_giua;
pt_giua=pt_duoi=pt_dau=NULL;
}
else
{
while(pt_giua->next->next)//nếu phần tử giữa khác NULL
{
pt_giua=pt_giua->next;
}
pt_duoi=pt_giua;
delete pt_giua->next;
pt_duoi->next=NULL;
}
}
}


void LIST::Xoa_Phan_Tu_Giua(Node *pt)
{
pt_giua=pt_dau;
if(pt_giua==pt)
{
this->Xoa_Phan_Tu_Dau();
}
else
{
while(pt_giua->next)//nếu phần tử tiếp theo là khác NULL thì mới so sánh dc ở dòng tiếp theo
{
if(pt_giua->next==pt)
{

pt_giua->next=pt_giua->next->next;
delete pt;
}
pt_giua=pt_giua->next;
}
}

}

int LIST::Dem_Phan_Tu_List()
{
int bien_dem=0;
pt_giua=pt_dau;
while(pt_giua)
{
bien_dem++;
pt_giua=pt_giua->next;

}
return bien_dem;
}


//================hàm đảo ngược danh sách có đệ qui==========================
Node *LIST::DaoNguoc1(Node *pt)
{
if(pt->next==NULL)
{
return pt;
}
else
{
LIST::DaoNguoc1(pt->next)->next=pt;
return pt;
}
}
void LIST::DaoNguoc()
{
pt_giua=pt_dau;
LIST::DaoNguoc1(pt_giua);
pt_giua=pt_duoi;
pt_duoi=pt_dau;
pt_dau=pt_giua;
pt_duoi->next=NULL;
}
//=================hàm main====================

int _tmain(int argc, _TCHAR* argv[])
{
LIST l=LIST();//tạo danh sách mới
//chèn 10 phần tử vào cuối
for(int i=0;i<10;i++)
{
l.Chen_Vao_Cuoi(i);
}
l.In_Danh_Sach();//in ra danh sách

//chèn 10 phần tử vào đầu
for(int i=0;i<10;i++)
{
l.Chen_Vao_Dau(i);
}
l.In_Danh_Sach();//in ra danh sách
//xóa 10 phần tử đầu
for(int i=0;i<10;i++)
{
l.Xoa_Phan_Tu_Dau();


}
l.In_Danh_Sach();


cout<<"so phan tu con lai trong danh sach la: "<<l.Dem_Phan_Tu_List()<<"\n";

cout<<"\ndanh sach sau khi dao nguoc\n";
l.DaoNguoc();
l.In_Danh_Sach();

//thử stack

return 0;
}

Tác giả của bài viết này là bạn Lê Văn Vuơng_08TH1D