#include
using namespace std;
int n;
struct node
{
int data;
struct node* next;
};
typedef struct node node;
struct list//đầu đuôi
{
node* head;
node* tail;
};
void init(list& l)//khởi tạo danh sách rỗng
{
l.head = l.tail = NULL;
}
node* creatnode(int x)//tạo một node mới
{
node* p = new node;
if (p == NULL) exit(1);//nếu ko tạo mới đc thì thoát
p->data = x;
p->next = NULL;
return p;
}
void newhead(list& l, int x)//chèn đầu
{
node* p = creatnode(x);//tạo một node mới
if (l.head == NULL)//nếu danh sách đang rỗng, cho head = p luôn!
l.head = l.tail = p;
else
{
p->next = l.head;//cho p trỏ đến l.head lúc này đang là đứng đầu
l.head = p;//đổi l.head cũ thành p
}
}
void newtail(list& l, int x)//chèn đuôi
{
node* p = creatnode(x);//tạo một node mới
if (l.head == NULL)
l.head = l.tail = p;
else
{
(l.tail)->next = p;//next của tail sẽ là p
l.tail = p;//chuyển p thành tail
}
}
node* search(list l, int k)//tìm kiếm
{
node* p = l.head;//tạo con chạy p
while (p != NULL)
{
if (p->data == k)
return p;
else
p = p->next;
}
return NULL;
}
void newnode(list& l, int x, int k)//tạo node tại vị trí bất kì
{
node* p = search(l, k);
if (p != NULL)
{
node* q = creatnode(x);//tạo node cần chèn
node* r = p->next;//node trung gian
p->next = q;
q->next = r;
}
else
cout << "Khong tim thay node co gia tri k nhap vao! ";
}
void newn(list& l, int x, int k)//tạo node tại vị trí n
{
if (l.head == NULL || k <= 1)//nếu ko có danh sách thì chèn đầu
newhead(l, x);
else if (k >= n)//nếu n lớn quá thì chèn đuôi
newtail(l, x);
else
{
node* p = creatnode(x);//tạo node đã
node* q = new node;
node* w = new node;
node* r = l.head;//r là con chạy
int i = 0;//đếm số node
while (r != NULL)
{
i++;
q = r;//lưu vị trí r vào q
if (i == k)
break;//nếu đã tới vị trí cần tìm thì thôi
else
r = r->next;//đi tiếp
}
w = l.head;//lại vị trí đầu à ?
while (w->next != q)
{
w = w->next;
}
w->next = p;
p->next = r;
delete q;//xoá bộ nhớ đi
delete w;
}
}
void nhap(list& l)//nhập thông tin cho list
{
cout << "NHap so phan tu du kien: ";
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cout << "Nhap phan tu " << i << ": ";
cin >> x;
newtail(l, x);
}
}
void xuat(list l)//xuất thông tin list
{
node* p = l.head;
while (p != NULL)
{
cout << "-->" << p->data;
p = p->next;
}
}
void dehead(list& l)//xoá node ở đầu
{
if (l.head != NULL)
{
node* p = l.head;//lưu vị trí l.head
l.head = l.head->next;//vị trí sau sẽ là l.head
delete p;//p lúc này cũng như l.head
}
}
void detail(list& l)//xoá đuôi
{
if (l.head != NULL)
{
node* p = l.head;//tạo con chạy p
node *q = new node;//tạo một bản sao
while (p->next != l.tail)
{
p = p->next;
}
q = p;//gán node
p = p->next;//trong while đã chạy đến trước tail, nên giờ p là tail
l.tail = q;//tail mới
l.tail->next = NULL;//và hoàn thiện tail
delete p;
delete q;//ừm ??? thực ra ta đã gán q = p nên thôi ko cần
}
}
void den(list& l, int k)//xoá tại một vị trí nào đó
{
if (k <= 1)
dehead(l);
else if (k >= n)
detail(l);
else
{
int i = 0;
if (l.tail != NULL)
{
node* p = l.head;//con chạy p
node* q = new node;//bản sao
while (p != NULL)
{
i++;
q = p;//sao chép
if (i == k)
break;
else
p = p->next;//tiếp tục tìm
}
node* r = l.head;//lại con chạy ?
while (r->next != q)
{
r = r->next;//đến node k-1
}
r->next = q->next;//đến k +1 luôn
delete q;//xoá cả p luôn rồi
}
}
}
void dele(list& l)//xoá hết
{
node* p = l.head;//con chạy
if (l.head == NULL)
exit(1);
else
{
while (l.head!=NULL)
{
p = p->next;//p lúc này chạy tới sau l.head
delete l.head;//xoá l.head
l.head = p;//lại gán tiếp
}
l.head = l.tail = NULL;//xoá nốt
}
}
void menu()
{
list l;//danh sách l
init(l);//khởi tạo
nhap(l);
xuat(l);
int k, x, lc;
do {
cout << "\n______MENU______\n1_Chen dau.\n2_chen cuoi."
<< "\n3_Chen sau vi tri node data = k.\n4_Chen vao vi tri bat ki."
<< "\n5_Xuat Thong tin List.\n6_Xoa phan tu dau List."
<< "\n7_Xoa phan tu o cuoi List.\n8_Xoa node o vi tri k."
<<"\n9_Xoa ca danh sach."
<< "\n0_Thoat.\n_Ban chon ? ";
cin >> lc;
switch (lc) {
case 0: break;
case 1: cout << "\nNhap x: "; cin >> x; newhead(l, x); n++; break;
case 2: cout << "\nNhap x: "; cin >> x; newtail(l, x); n++; break;
case 3: cout << "\nNhap x, k: "; cin >> x >> k; newnode(l, x, k); n++; break;
case 4: cout << "\nNhap x, vi tri k: "; cin >> x >> k; newn(l, x, k); n++; break;
case 5: xuat(l); break;
case 6: dehead(l); n--; break;
case 7: detail(l); n--; break;
case 8: cout << "\nNhap vi tri k: "; cin >> k; den(l, k); n--; break;
case 9: dele(l); break;
}
} while (lc != 0);
}
int main()
{
menu();
return 0;
}
hmmm !!!
Trả lờiXóaĐăng nhận xét