- Khởi tạo Danh sách liên kết: Init()/ Contructor()
Init(){
LinkedList = null;
}
Hoặc đặt trong hàm khởi tạo của Class < C++ >
Class SingleLinkedList{
SingleLinkedList(){
LinkList=null;
}
}
- Cấp phát bộ nhớ cho 1 node
node* CreateNode(int value){
struct node *temp; //Khai bao con tro node *temp
temp = new(struct node); //Capp phatt mien nho cho temp
if (temp == NULL){ // neu khong cap phat duoc
cout<<"Khong du bo nho de cap phat" << endl;
}
else {
temp->data = value;//Thiet lap thong tin cho node temp
temp->next = NULL; //Thiet lap lien ket cho node temp
return temp;
}
}
- Thêm node vào đầu bên trái danh sách liên kết đơn
void InsertBegin(int value){
struct node *temp, *p;
temp =CreateNode(value);//Tao mot node voi gia tri value
if (LinkedList == NULL){ //Neu danh sach rong
LinkedList = temp; //node dau tien chinh la node temp
LinkedList->next = NULL; //Khong co lien ket voi node khac
}
else { //Neu danh sach khong rong
p = LinkedList; //p tro den node dau cua LinkedList
LinkedList = temp; //LinkedList duuc tro den temp
LinkedList->next = p;//LinkedList tro tiep den node tiep theo
}
}
- Thêm node vào đầu bên phải theo chiều con trỏ next
void InsertLast(int value){//Them node vao cuoi DSLKÐ
struct node *temp, *s;
temp = CreateNode(value);
s = LinkedList; //s tro den node dau danh sach
while (s->next != NULL){ //Di chuyen s den node cuoi cung
s = s->next;
}
temp->next = NULL;
s->next = temp;
}
- Thêm vào vị trí bất kì
void InsertPos(int value,int pos){
int counter=0;
struct node *temp, *s, *ptr;
temp = CreateNode(value);
int i; s = LinkedList;
while (s != NULL){
s = s->next; counter++;
}
if (pos == 1){ //Neu pos là vi tri dau tien
if (LinkedList == NULL){
LinkedList = temp;
LinkedList->next = NULL;
}
else{
ptr = LinkedList;
LinkedList = temp;
LinkedList->next = ptr;
}
}
else if (pos > 1 && pos <= counter){
s = LinkedList;
for (i = 1; i < pos; i++){
ptr = s;
s = s->next;
}
ptr->next = temp; temp->next = s;
}
else {
cout << "Vuot qua gioi han DSLKÐ" << endl;
}
}
- Loại node ở giữa danh sách liên kết đơn
void free(node* p){
struct node *temp;temp=p;
temp->next=NULL;
}
void DeletePos(int pos){//Loai phan tu o vi tri cho truoc
int i, counter = 0;
if (LinkedList == NULL){
cout<<"DSLK rong, khong thuc hiun duoc" << endl;
return;
}
struct node *s, *ptr; s = LinkedList;
if (pos == 1){
LinkedList = s->next;
s->next=NULL;
free(s);
}
else {
while (s != NULL) { // dem so node
s = s->next;
counter++;
}
if (pos > 0 && pos <= counter){
s = LinkedList;
for (i = 1;i < pos;i++){
ptr = s;
s = s->next;
}
ptr->next = s->next;
}
else {
cout<<"Vi tri ngoai danh sach"<< endl;
}
free(s);
}
}
- Sửa thông tin của 1 node
void Update(int value,int pos){//Sua thông tin cua node
int i;
if (LinkedList == NULL){
cout<<"DSLK rong, khong thuc hien duoc"<< endl;
return;
}
struct node *s, *ptr;
s = LinkedList;
if (pos == 1) {
LinkedList->data = value;
}
else {
for (i = 0;i < pos - 1;i++){
if (s == NULL){//Neu s là node cuoi cung
cout<< "Vi tri "<< pos <<" khong hop le";
return;
}
}
s= s->next;
s->data = value;
}
}
- Lấy giá trị của 1 node
int Get(int pos){ //lay gia tri tai 1 node
if (LinkedList == NULL){
cout << "DSLK rong thi tim cai gi?" << endl;
}
else{
struct node *s; s = LinkedList;
int k = 1;
while(s->next != NULL && k != pos){
++k;
s = s->next;
}
return s->data;
}
}
- Tìm kiếm vị trí của 1 node theo giá trị
void Search(int value){//Tim kiem node
int pos = 0;
bool flag = false; // fasle : khong tim thay , true: tim thay
if (LinkedList == NULL){
cout<<"DSLK rong thi tim cai gi?"<< endl;
return;
}
struct node *s; s = LinkedList;
while (s != NULL){
pos++;
if (s->data == value){//Neu s->datar là value
flag = true;
cout<<"Tim thay "<< value<<" tai vi tri "<< pos << endl;
}
s= s->next;
}
if (!flag) {
cout<< "Gia tri" << value << "khong tim thay"<< endl;
}
}
- Duyệt thông tin của danh sách liên kết đơn
void Display(){//Hien thi noi dung DSLKÐ
struct node *temp;
if (LinkedList == NULL){
cout << "Co gi dau ma hien thi"<< endl;
return;
}
temp = LinkedList;
cout<<"DSLK: "<< endl;
while (temp != NULL) {
cout<data<<"->";
temp = temp->next;
}
cout<<"NULL"<< endl;
}
- Sắp xếp các giá trị theo thứ tăng dần < int >
void Sort(){//Sap xep noi dung cac node
struct node *ptr, *s;
int value; //gia tri trung gian
if (LinkedList == NULL){
cout<<"Co gi dau ma sap xep"<< endl;
return;
}
ptr = LinkedList;
while (ptr != NULL){
for (s = ptr->next;s !=NULL;s = s->next){
if (ptr->data > s->data){ // hoan doi vi tri
value = ptr->data;
ptr->data = s->data;
s->data = value;
}
}
ptr = ptr->next;
}
}
- Đảo ngược các giá trị trong DSLK
void Reverse(){//Dao nguoc danh sach
struct node *ptr1, *ptr2, *ptr3;
if (LinkedList == NULL) {
cout<<"Can gi phai dao"<< endl;
return;
}
if (LinkedList->next == NULL){
cout << "Dao nguoc la chinh no" << endl;
return;
}
ptr1 = LinkedList; //ptr1 tro den node dau tien
ptr2 = ptr1->next;//ptr2 tro den node ke tiep cua ptr1
ptr3 = ptr2->next;//ptr3 tri den node ke tiep cua ptr2
ptr1->next = NULL;//Ngat liên ket ptr1
ptr2->next = ptr1;//node ptr2 bay gio dung truoc node ptr1
while (ptr3 != NULL){//Lap neu ptr3 khac rong
ptr1 = ptr2;
ptr2 = ptr3;
ptr3 = ptr3->next;
ptr2->next = ptr1;
}
LinkedList = ptr2; // nut dau tien la ptr2
}
0 Nhận xét