Danh sách liên kết với ngôn ngữ C – Linked list in C programming language

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

// khai bao cau truc cho mot nut cua danh sach
typedef struct Node
{
// truong du lieu
int data;
struct Node * next;
} NodeType;

// khai bao kieu danh sach
typedef struct
{
NodeType * head;
NodeType * tail;
// so phan tu cua danh sach
int spt;
}LList;

// ham khoi tao danh sach
void init(LList * list);
// ham them 1 phan tu vao dau danh sach
void addFirst(LList *list, int d);
// ham them mot phan tu vao cuoi danh sach
void addLast(LList *list, int d);
// ham xoa phan tu o cuoi danh sach
int delLast(LList * list);
// ham xoa phan tu o dau danh sach
int delFirst(LList * list);
void insertAfter(LList * list, NodeType * p);
void insertBefore(LList * list, NodeType * p);
void removeAfter(LList * list, NodeType * p);
void removeBefore(LList * list, NodeType * p);
// ham in danh sach
void printList(LList list);
// ham sap xep danh sach
void sort(LList *list);
// ham tim kiem trong danh sach
NodeType * search(LList *, int d);
// giai phong toan bo danh sach
void freeAll(LList * list);

int main()
{
LList myList;
init(&myList);
addFirst(&myList, 10);
addFirst(&myList, 1);
addFirst(&myList, 12);
addLast(&myList, 20);
addLast(&myList, 23);
addLast(&myList, 25);
sort(&myList);
printList(myList);
freeAll(&myList);
printList(myList);
return 0;
}
void init(LList * list)
{
list->head = list->tail = NULL;
list->spt = 0;
}

void printList(LList list)
{
NodeType * tmp;
tmp = list.head;
while(tmp!=NULL)
{
printf(“%d “, tmp->data);
tmp = tmp->next;
}
printf(“\n”);
}

void addFirst(LList * list, int d)
{
NodeType * tmp = (NodeType *)malloc(sizeof(NodeType));
tmp->data = d;
if(list->spt==0)
{
tmp->next = NULL;
list->head = list->tail = tmp;
}
else
{
tmp->next = list->head;
list->head = tmp;
}
list->spt = list->spt+1;
}

void addLast(LList * list, int d)
{
NodeType * tmp = (NodeType *)malloc(sizeof(NodeType));
tmp->data = d;
tmp->next = NULL;
if(list->spt==0)
list->head = list->tail = tmp;
else
{
list->tail->next = tmp;
list->tail = tmp;
}
list->spt = list->spt+1;
}

NodeType * search(LList * list, int d)
{
NodeType * tmp = list->head;
while(tmp!=NULL)
{
if (tmp->data==d)
break;
tmp = tmp->next;
}
return tmp;
}

int delLast(LList * list)
{
NodeType * p, * q;
int ret = -1;

if(list->spt>0)
{
p = list->head;
q = NULL;
while(p->next!=NULL)
{
q = p;
p = p->next;
}
if(q!=NULL)
{
// danh sach chi co 1 phan tu
q->next = NULL;
list->tail = q;
}
else
list->head = list->tail = NULL;
ret = p->data;
free(p);
list->spt = list->spt-1;
}
return ret;
}

int delFirst(LList * list)
{
int ret=-1;
NodeType * tmp;
if(list->spt>0)
{
tmp = list->head;
if(list->spt==1)
{
// danh sach chi co 1 phan tu
ret = list->head->data;
list->head = list->tail = NULL;
}else
list->head = list->head->next;
free(tmp);
list->spt = list->spt – 1;
}
return ret;
}

// sap xep dung thuat toan doi cho truc tiep (interchange sort)
void sort(LList * list)
{
NodeType * p, * q;
int tmp;

p = list->head;
while(p!=NULL)
{
q = p->next;
while(q!=NULL)
{
if(q->data < p->data)
{
tmp = q->data;
q->data = p->data;
p->data = tmp;
}
q = q->next;
}
p = p->next;
}
}

void freeAll(LList * list)
{
NodeType * p, * q;
if(list->spt>0)
{
p = list->head;
list->head = list->tail = NULL;
list->spt = 0;
while(p)
{
q = p->next;
free(p);
p = q;
}
}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: