21 December 2019

Danh sách liên kết đơn dùng con trỏ

by NGUYEN DINH QUANG

Con trỏ cơ bản

#include<stdio.h>
 
int main() {
    int qndev = 50;
    int *p1;
    int **p2;
    p1 = &qndev;
    p2 = &p1;
    printf("Gia tri cua bien qndev: %d \n", qndev);
    printf("Dia chi cua bien qndev la: %x \n", &qndev);
    printf("Dia chi cua bien con tro p1 la: %x \n", &p1);
    printf("Gia tri cua bien con tro p1 la: %x \n", p1);
    printf("Gia tri cua bien ma con tro p1 tro toi la: %d \n", *p1);
    printf("Dia chi cua bien con tro p2 la: %x \n", &p2);
    printf("Gia tri cua bien con tro p2 la: %x \n", p2);
    printf("Gia tri cua bien ma con tro p2 tro toi la (Gia tri cua bien con tro p1/ Dia chi cua bien qndev): %x \n", *p2);
    printf("Gia tri cua bien **p2 la: %d \n", *(*p2));
    return 0;
}

Output:

Gia tri cua bien qndev: 50 
Dia chi cua bien qndev la: 33a8ea4c 
Dia chi cua bien con tro p1 la: 33a8ea40 
Gia tri cua bien con tro p1 la: 33a8ea4c 
Gia tri cua bien ma con tro p1 tro toi la: 50 
Dia chi cua bien con tro p2 la: 33a8ea38 
Gia tri cua bien con tro p2 la: 33a8ea40 
Gia tri cua bien ma con tro p2 tro toi la (Gia tri cua bien con tro p1/ Dia chi cua bien qndev): 33a8ea4c 
Gia tri cua bien **p2 la: 50 

Danh sách sách liên kết đơn

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
struct _PointerType{
  ElementType Inf;
  struct _PointerType *Next;
};
typedef struct _PointerType PointerType;

PointerType *BuildList() {
    PointerType *head = NULL;
    PointerType *second = NULL;
    PointerType *third = NULL;

    head = malloc(sizeof(PointerType));
    second = malloc(sizeof(PointerType));
    third = malloc(sizeof(PointerType));

    head->Inf = 2;
    head->Next = second;

    second->Inf = 3;
    second->Next = third;
    third->Inf = 4;
    third->Next = NULL;

    return head;
}

PointerType *InsertMiddle(PointerType *Prev, ElementType X)
{
  PointerType *TempNode;
  
  TempNode = (PointerType *)malloc(sizeof(PointerType));
  TempNode->Inf = X;
  TempNode->Next = Prev->Next;
  Prev->Next = TempNode;
  
  return TempNode;
}

ElementType Delete(PointerType *Prev){
  ElementType X;
  PointerType *TempNode;
  
  TempNode = Prev->Next; Prev->Next = Prev->Next->Next;
  X = TempNode->Inf;
  free(TempNode);
  
  return X;
}

PointerType *InsertToHead(PointerType *First, ElementType X){
  PointerType *TempNode;
  
  TempNode = (PointerType *) malloc(sizeof(PointerType));
  TempNode->Inf = X;
  TempNode->Next = First;
  First = TempNode;
  // printf("Gia tri cua First %p \n", First);
  return First;
}

PointerType *InsertToLast(PointerType *First, ElementType X){
  PointerType *NewNode; PointerType *TempNode;

  NewNode = (PointerType *)malloc(sizeof(PointerType));
  NewNode->Inf = X;NewNode->Next = NULL; 
  TempNode = First;
  
  while(TempNode->Next!=NULL)
    TempNode = TempNode->Next;
  
  TempNode->Next = NewNode;
  return First;
}

PointerType *DeleteHead(PointerType *First){
  PointerType *TempNode;
  
  TempNode = First->Next;
  free(First);
  
  return TempNode;
}

PointerType *DeleteLast(PointerType *First){
  PointerType *Temp1,*Temp2;
  Temp1 = First; Temp2 = First;
  
  while(Temp1->Next != NULL){
   Temp2 = Temp1;
   Temp1 = Temp1->Next;}
  
  Temp2->Next = NULL;
  free(Temp1);
  return First;
}

PointerType* Reverse(PointerType* head) { 
    
    if (head == NULL) 
        return NULL; 
    if (head->Next == NULL) { 
        return head;
    }

    PointerType* newHead = Reverse(head->Next);
    head->Next->Next = head;
    head->Next = NULL;

    return newHead;
}

int IsEmpty(PointerType *First)
{
  return !First;
}

PointerType *MakeNull(PointerType *First)
{
  while(!IsEmpty(First))
   First=DeleteHead(First);
  return First;
}

void Print(PointerType *First){
  PointerType *TempNode;
  
  printf("%p ",First);
  TempNode = First;
  while(TempNode!=NULL){
   printf("-> [ %d : %p ]",TempNode->Inf,TempNode->Next);
   TempNode = TempNode->Next;
  }
  printf("\n");
}

// Than chuong trinh chinh
int main(){
    PointerType *ds=NULL,*pv=NULL;
    int i,p;

    // Chen 5 gia tri vao vi tri dau
    ds = InsertToHead(ds,1);
    ds = InsertToHead(ds,2);
    ds = InsertToHead(ds,3);
    ds = InsertToHead(ds,4);
    ds = InsertToHead(ds,5);

    //PointerType *ds = BuildList();
    // In ra danh sach sau khi chen
    printf("In ra danh sach sau khi chen vao dau \n");
    Print(ds);
    
    printf("Danh sach sau khi chen 6 vao dau \n");
    ds = InsertToHead(ds,6);
    Print(ds);

    ds = Reverse(ds);
    printf("Danh sach sau khi dao nguoc \n");
    Print(ds);

    // Chen so 7 vao vi tri cuoi cua danh sach
    printf("Danh sach sau khi chen 7 vao cuoi \n");
    ds = InsertToLast(ds,7);
    Print(ds);
    
    // In ra danh sach sau khi xoa phan tu dau
    printf("In ra danh sach sau khi xoa dau \n");
    ds = DeleteHead(ds);
    Print(ds);
    
    // In ra danh sach sau khi xoa phan tu cuoi
    printf("In ra danh sach sau khi xoa cuoi \n");
    ds = DeleteLast(ds);
    Print(ds);
    
    // In ra danh sach sau khi xoa phan tu dau
    printf("Cho vi tri ban muon chen 7 vao sau p = ");scanf("%d",&p);
    pv = ds;i=1;
    while(i<p){pv = pv->Next;i++;}
    InsertMiddle(pv,7);
    Print(ds);
    getchar();
    return 0;
}

Output:

In ra danh sach sau khi chen vao dau 
0x55e09e4d92e0 -> [ 5 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d9260 ]-> [ 1 : (nil) ]
Danh sach sau khi chen 6 vao dau 
0x55e09e4d9710 -> [ 6 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d9260 ]-> [ 1 : (nil) ]
Danh sach sau khi dao nguoc 
0x55e09e4d9260 -> [ 1 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : (nil) ]
Danh sach sau khi chen 7 vao cuoi 
0x55e09e4d9260 -> [ 1 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : 0x55e09e4d9730 ]-> [ 7 : (nil) ]
In ra danh sach sau khi xoa dau 
0x55e09e4d9280 -> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : 0x55e09e4d9730 ]-> [ 7 : (nil) ]
In ra danh sach sau khi xoa cuoi 
0x55e09e4d9280 -> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : (nil) ]
Cho vi tri ban muon chen 7 vao sau p = 5
0x55e09e4d9280 -> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : 0x55e09e4d9730 ]-> [ 7 : (nil) ]

Latest Posts

tags: notes - data structures and algorithms - c