Phần 1: Cài đặt danh sách liên kết, viết các hàm thực hiện:
- Tính số lượng các nút của danh sách.
- Cho thêm con trỏ M trỏ tới một nút có trong danh sách nói trên và một danh sách đơn khác có nút đầu tiên trỏ bởi P.
- Hãy chèn danh sách P này vào sau nút trỏ bởi M.
- Tách thành hai danh sách mà danh sách sau trỏ bởi M (cho ở câu trên).
- Đảo ngược danh sách đã cho (tạo một danh sách L’ mà các nút móc nối theo thứ tự ngược lại so với L).
Phần 2: Code
using System;
namespace Danhsachlienket
{
//Cấu trúc 1 node thông qua class node này
class Node
{
public int info; //Lưu giá trị node
public Node next; //Lưu con trỏ next để trỏ về phần tử kế tiếp
public Node()
{
this.info = -1; //Giá trị mặc định khi khởi tạo node
this.next = null; //Giá trị mặc định khi khởi tạo node
}
}
class Program
{
//Hàm thêm nút vào danh sách
static void insert(ref Node l, int x)
{
if (l == null) //Nếu danh sách hiện tại rỗng
{
l = new Node();
l.info = x;
l.next = null;
}
else //Danh sách có phần tử thì thêm vào cuối danh sách
{
Node p = l; //Gán p bằng node đầu danh sách là node l
while(p.next!=null) //Thực hiện next tới để tìm về cuối danh sách
{
p = p.next;
}
//Tạo node mới, gán giá trị và trỏ next của node cuối về node mới.
Node newnode = new Node();
newnode.info = x;
newnode.next = null;
p.next = newnode;
}
}
//Hàm Tính số lượng các nút của danh sách
static int countList(ref Node l)
{
int len = 0;
Node p = l; // Gán p bằng node đầu danh sách là node l
//Rồi thực hiện di chuyển lần về các node cho đến khi gặp node cuối thì dừng.
//Mỗi lần đi qua 1 node thì đếm node đó vô để tính chiều dài
while (p!=null)
{
len = len + 1;
p = p.next;
}
return len;
}
//Hàm thực hiện chèn list p vào list l ở vị trí sau nút m
static void addorderlistintoposition(ref Node l, ref Node m, ref Node p)
{
Node ptam = p; //Lưu Vị trí cuối danh sách p
while(ptam.next!=null)
{
ptam = ptam.next;
}
//Thực hiện gắn con trỏ next của phần tử cuối danh sách p vào con trỏ next của phần tử m trong danh sách l
ptam.next = m.next;
//Thực hiện trỏ con trỏ next của m về p
m.next = p;
}
//Hàm này trả về 1 Node có vị trí là position trong danh sách
static Node getNodebyPosition(Node l, int position)
{
int i = 1;
Node p = l;
while(1==1)
{
if (i == position)
{
break;
}
else
{
p = p.next;
i = i + 1;
}
}
return p;
}
//Hàm Tách thành hai danh sách mà danh sách sau trỏ bởi M
static void splitbympositon(ref Node l, ref Node m, ref Node newlist)
{
newlist = m.next; //Chuyển phần tử sau m cho danh sách mới newlist;
m.next = null; //Cắt đuối danh sách l bằng cách gán con trỏ next của m là null
}
//Đảo ngược danh sách đã cho (tạo một danh sách L’ mà các nút móc nối theo thứ tự ngược lại so với L).
static void makereverselistfromoldlist(Node l, ref Node newlist)
{
if(l.next!=null)
{
Node current=null;//= new Node();
Node previous=null; //=new Node();
// [l] ---> [...]---> [...]
//Thực hiện quán đổi vị trí 2 nút current và previous
while (l!=null)
{
current = l;
l = l.next;
current.next = previous;
previous = current;
}
l = current;
}
newlist = l;
}
static void printlist(Node l)
{
Node p = l;
while (p != null)
{
Console.Write(p.info + "; ");
p = p.next;
}
}
static void Main(string[] args)
{
Node L1 = null; //Danh sách L1
Node M = new Node(); //Vị tri node M trong danh sach L1
Node P = null; //Danh sach thu 2
Node SplitList = new Node(); //Danh sách tách từ L1
Node L3 = new Node(); //Danh sach dao cua L1
while (1 == 1)
{
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("==========MENU==========");
Console.WriteLine("1. Nhap danh sach L");
Console.WriteLine("2. In danh sach L");
Console.WriteLine("3. Dem so luong nut danh sach L");
Console.WriteLine("4. Nhap danh sach P");
Console.WriteLine("5. In danh sach P");
Console.WriteLine("6. Dem so luong nut danh sach P");
Console.WriteLine("7. Chen danh sách P vao L (o vi tri M)");
Console.WriteLine("8. Tach danh sach tu vi tri M");
Console.WriteLine("9. Danh sach dao cua L");
Console.WriteLine("0. Thoat");
Console.WriteLine("========================");
Console.Write("Ban chon menu so: ");
string chon = Console.ReadLine();
if (chon == "1")
{
Console.WriteLine("1. Nhap danh sach L");
int x = 0;
while (1 == 1)
{
Console.Write("Hay nhap so roi bam enter (nhap -1 de ket thuc viec nhap): ");
x = int.Parse(Console.ReadLine());
if (x != -1)
{
insert(ref L1, x);
}
else
{
break;
}
}
}
else if (chon == "2")
{
Console.WriteLine();
Console.Write("Danh sach L: ");
printlist(L1);
}
else if (chon == "3")
{
int sonut = countList(ref L1);
Console.WriteLine();
Console.WriteLine("So nut cua danh sach L: " + sonut.ToString());
}
else if (chon == "4")
{
Console.WriteLine("4. Nhap danh sach P");
int x = 0;
while (1 == 1)
{
Console.Write("Hay nhap so roi bam enter (nhap -1 de ket thuc viec nhap): ");
x = int.Parse(Console.ReadLine());
if (x != -1)
{
insert(ref P, x);
}
else
{
break;
}
}
}
else if (chon == "5")
{
Console.WriteLine();
Console.Write("Danh sach P: ");
printlist(P);
}
else if (chon == "6")
{
int sonut = countList(ref P);
Console.WriteLine();
Console.WriteLine("So nut cua danh sach P: " + sonut.ToString());
}
else if (chon == "7")
{
int vitriM = 0;
Console.Write("Hay nhap vi tri M de chen P vao L (tai vi tri M): ");
vitriM = int.Parse(Console.ReadLine());
M = getNodebyPosition(L1, vitriM);
addorderlistintoposition(ref L1, ref M, ref P);
Console.WriteLine();
Console.Write("Danh sach L sau khi chen danh sach P: ");
printlist(L1);
}
else if (chon == "8")
{
int vitriM = 0;
Console.Write("Hay nhap vi tri M de tach danh sach L: ");
vitriM = int.Parse(Console.ReadLine());
M = getNodebyPosition(L1, vitriM);
splitbympositon(ref L1, ref M, ref SplitList);
Console.WriteLine();
Console.Write("Danh sach moi duoc tach: ");
printlist(SplitList);
}
else if (chon == "9")
{
makereverselistfromoldlist(L1, ref L3);
Console.WriteLine();
Console.Write("Danh sach dao cua L (L3): ");
printlist(L3);
}
else
{
break;
}
}
}
}
}
Phần 3: Code C++
/*Cài đặt danh sách liên kết, viết các hàm thực hiện:
*- Tính số lượng các nút của danh sách.
*- Cho thêm con trỏ M trỏ tới một nút có trong danh sách nói trên và một danh sách đơn khác có nút đầu tiên trỏ bởi P.
* Hãy chèn danh sách P này vào sau nút trỏ bởi M.
*- Tách thành hai danh sách mà danh sách sau trỏ bởi M (cho ở câu trên).
*- Đảo ngược danh sách đã cho (tạo một danh sách L’ mà các nút móc nối theo thứ tự ngược lại so với L).
* */
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
//Khai báo kiểu dữ liệu Node
struct Node {
int info;
struct Node * next;
};
//Hàm thêm nút vào danh sách
void insert(Node* &l, int x)
{
if (l == NULL) //Nếu danh sách hiện tại rỗng
{
l = (Node *) malloc (sizeof(Node));
l->info = x;
l->next = NULL;
}
else //Danh sách có phần tử thì thêm vào cuối danh sách
{
Node* p = l; //Gán p bằng node đầu danh sách là node l
while(p->next!=NULL) //Thực hiện next tới để tìm về cuối danh sách
{
p = p->next;
}
//Tạo node mới, gán giá trị và trỏ next của node cuối về node mới.
Node* newnode = (Node *) malloc (sizeof(Node));
newnode->info = x;
newnode->next = NULL;
p->next = newnode;
}
}
//Hàm Tính số lượng các nút của danh sách
int countList(Node* l)
{
int len = 0;
Node* p = l; // Gán p bằng node đầu danh sách là node l
//Rồi thực hiện di chuyển lần về các node cho đến khi gặp node cuối thì dừng.
//Mỗi lần đi qua 1 node thì đếm node đó vô để tính chiều dài
while (p!=NULL)
{
len = len + 1;
p = p->next;
}
return len;
}
//Hàm thực hiện chèn list p vào list l ở vị trí sau nút m
void addorderlistintoposition(Node* &m, Node* &p)
{
Node* ptam = p; //Lưu Vị trí cuối danh sách p
while(ptam->next!=NULL)
{
ptam = ptam->next;
}
//Thực hiện gắn con trỏ next của phần tử cuối danh sách p vào con trỏ next của phần tử m trong danh sách l
ptam->next = m->next;
//Thực hiện trỏ con trỏ next của m về p
m->next = p;
}
//Hàm này trả về 1 Node có vị trí là position trong danh sách
Node* getNodebyPosition(Node* l, int position)
{
int i = 1;
Node* p = l;
while(1==1)
{
if (i == position)
{
break;
}
else
{
p = p->next;
i = i + 1;
}
}
return p;
}
//Hàm Tách thành hai danh sách mà danh sách sau trỏ bởi M
void splitbympositon(Node* &m, Node* &newlist)
{
newlist = m->next; //Chuyển phần tử sau m cho danh sách mới newlist;
m->next = NULL; //Cắt đuối danh sách l bằng cách gán con trỏ next của m là null
}
//Đảo ngược danh sách đã cho (tạo một danh sách L’ mà các nút móc nối theo thứ tự ngược lại so với L).
void makereverselistfromoldlist(Node* &l, Node* &newlist)
{
if(l->next!=NULL)
{
Node* current=NULL; //= new Node();
Node* previous=NULL; //=new Node();
// [l] ---> [...]---> [...]
//Thực hiện quán đổi vị trí 2 nút current và previous
while (l!=NULL)
{
current = l;
l = l->next;
current->next = previous;
previous = current;
}
l = current;
}
newlist = l;
}
void printlist(Node* l)
{
Node* p = l;
while (p != NULL)
{
cout<<p->info<<"; ";
p = p->next;
}
}
int main()
{
Node* L1 = NULL; //Danh sách L1
Node* M = (Node *) malloc (sizeof(Node)); //Vị tri node M trong danh sach L1
Node* P = NULL; //Danh sach thu 2
Node* SplitList = (Node *) malloc (sizeof(Node)); //Danh sách tách từ L1
Node* L3 = (Node *) malloc (sizeof(Node)); //Danh sach dao cua L1
while (1 == 1)
{
cout << "\n\n==========MENU==========\n";
cout<<"1. Nhap danh sach L\n";
cout<<"2. In danh sach L\n";
cout<<"3. Dem so luong nut danh sach L\n";
cout<<"4. Nhap danh sach P\n";
cout<<"5. In danh sach P\n";
cout<<"6. Dem so luong nut danh sach P\n";
cout<<"7. Chen danh sach P vao L (o vi tri M)\n";
cout<<"8. Tach danh sach tu vi tri M\n";
cout<<"9. Danh sach dao cua L\n";
cout<<"0. Thoat\n";
cout<<"========================\n";
cout<<"Ban chon menu so: ";
int chon=0;
scanf("%d", &chon);
if (chon == 1)
{
cout<<"1. Nhap danh sach L\n";
int x = 0;
while (1 == 1)
{
cout<<"Hay nhap so roi bam enter (nhap -1 de ket thuc viec nhap): ";
int x = -1;
scanf("%d", &x);
if (x != -1)
{
insert(L1, x);
}
else
{
break;
}
}
}
else if (chon == 2)
{
cout<<"\nDanh sach L: ";
printlist(L1);
}
else if (chon == 3)
{
int sonut = countList(L1);
cout<<"\nSo nut cua danh sach L: "<<sonut<<"\n";
}
else if (chon == 4)
{
cout<<"4. Nhap danh sach P\n";
int x = 0;
while (1 == 1)
{
cout<<"Hay nhap so roi bam enter (nhap -1 de ket thuc viec nhap): ";
int x = -1;
scanf("%d", &x);
if (x != -1)
{
insert(P, x);
}
else
{
break;
}
}
}
else if (chon == 5)
{
cout<<"\nDanh sach P: ";
printlist(P);
}
else if (chon == 6)
{
int sonut = countList(P);
cout<<"\nSo nut cua danh sach P: " << sonut<<"\n";
}
else if (chon == 7)
{
int vitriM = 0;
cout<<"Hay nhap vi tri M de chen P vao L (tai vi tri M): ";
scanf("%d", &vitriM);
M = getNodebyPosition(L1, vitriM);
addorderlistintoposition(M, P);
cout<<"\nDanh sach L sau khi chen danh sach P: ";
printlist(L1);
}
else if (chon == 8)
{
int vitriM = 0;
cout<<"Hay nhap vi tri M de tach danh sach L: ";
scanf("%d", &vitriM);
M = getNodebyPosition(L1, vitriM);
splitbympositon(M, SplitList);
cout<<"\nDanh sach moi duoc tach: ";
printlist(SplitList);
}
else if (chon == 9)
{
makereverselistfromoldlist(L1, L3);
cout<<"\nDanh sach dao cua L (L3): ";
printlist(L3);
}
else
{
break;
}
}
return 0;
}
Hy vọng hữu ích với bạn!
Nosomovo
