Diễn đàn cntt ĐH-TÔN ĐỨC THẮNG.Thân mời các anh em tham gia để diễn đàn phong phú hơn
Chào mừng bạn ghé thăm diễn đàn, hãy tham gia đăng kí thành viên cùng chúng tôi để có thêm động lực post bài

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

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

Bài gửi by Admin on Fri Dec 16, 2011 11:46 pm

#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
avatar
Admin
Thiếu Tá
Thiếu Tá

Tổng số bài gửi : 107
Age : 27

Xem lý lịch thành viên http://itam.forumvi.com

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết