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

Các thao tác trên danh sách liên kết đơn(single-link list)
1.Định nghĩa tổng quát

Code:

struct tq {
thtin_t phantu;
struc tq*tiep;
};
typedef struct tq tq_t;

2.Con trỏ tới 1 node

Code:

struct  node {
		int infor;
		struct node *next;
	};
	typedef struct node *NODEPTR;

3.Cấp phát bộ nhớ cho 1 node

Code:

NODEPTR Getnode(void) {
	NODEPTR p;
	P = (NODEPTR) malloc(sizeof( struct node));
	Return(p);
}

4.Giải phóng 1 node

NODEPTR Freenode( NODEPTR p){
		free(p);
	}

5.Thêm phần tử vào đỉnh danh sách

void Push_Top( NODEPTR *plist, int x) {
	NODEPTR p;
	p= Getnode();
	p -> infor = x;
	p ->next = *plist;
	*plist = p;
}
6.Thêm node mới vào cuối danh sách


void Push_Bottom( NODEPTR *plist, int x) {
	NODEPTR p, q;
	p= Getnode(); //
	p->infor = x;
	q = *plist;
	while (q-> next != NULL)
		q = q -> next;

	q -> next = p;
	p ->next = NULL;
}

7.Thêm node mới vào giữa danh sách

void Push_Before( NODEPTR p, int x ){
	NODEPTR q;
	if (p->next==NULL)
		Push_Bottom(p, x);
	else {
		q= Getnode();
		q -> infor = x;
		q-> next = p-> next;
		p->next = q;
	}
}

8. Xóa 1 node đầu danh sách

void Del_Top( NODEPTR *plist) {
	NODEPTR p;
	p = *plist;
	if (p==NULL) return;
	(*plist) = (*plist) -> next;
	p-> next = NULL;
	Freenode(p);
}
9.Xóa node cuối danh sách

void Del_Bottom(NODEPTR *plist) {
	NODEPTR p, q;
	if (*plist==NULL) return;
	else if ( (*plist)->next==NULL))
		Del_Top(plist);
	else {
		p = *plist;
		while (p->next!=NULL){
			q = p;
			p = p->next;
		}
		// p lµ node cuèi danh s¸ch;
		q->next =NULL;
		Freenode(p);
	}
}

10.Xóa node giữa danh sách

void Del_before(NODEPTR p){
	NODEPTR q;
	if (p->next==NULL) return;
	q = p ->next;
	p->next = q->next;
	Freenode(q);
}

Ngoài ra các thao tác duyệt danh sách, tìm kiếm trên danh sách…

Chúng ta xét 1 ứng dụng đơn giản của danh sách liên kết đơn sau;
Chương trình quản lí sinh viên với dạng đơn giản chỉ gồm mã SV và họ tên

#include    <stdio.h>
#include    <stdlib.h>
#include    <conio.h>
#include    <dos.h>
#include    <string.h>
#include     <math.h>
#include <alloc.h>
#define TRUE 1
#define FALSE 0

typedef struct {
    int masv;
    char hoten[20];
} sinhvien;
typedef struct node{
    sinhvien infor;
    struct node *next;
} *NODEPTR;
void Initialize(NODEPTR *plist){
    *plist=NULL;
}
NODEPTR Getnode(void){
    NODEPTR p;
    p=(NODEPTR) malloc(sizeof(struct node));
    return(p);
}
void Freenode(NODEPTR p){
    free(p);
}
int Emptynode(NODEPTR *plist){
    if(*plist==NULL)
        return(TRUE);
    return(FALSE);
}
NODEPTR Inserttop(NODEPTR *plist, sinhvien x){
    NODEPTR p;
    p=Getnode();
    p->infor=x;
    if(Emptynode(plist)){
        p->next=NULL;
        *plist=p;
        return(p);
    }
    p->next=*plist;
    *plist=p;
    return(p);
}
int Bottomnode(NODEPTR *plist){
    int i; NODEPTR p;
    if(Emptynode(plist))
        return(-1);
    p=*plist;i=0;
    while(p!=NULL){
        i=i+1;
        p=p->next;
    }
    return(i);
}
NODEPTR Insertbottom(NODEPTR *plist, sinhvien x){
    NODEPTR p, q;int n,i;
    n=Bottomnode(plist);
    if(n==-1){
        Inserttop(plist,x);
        return(*plist);
    }
    p=*plist;i=0;q=Getnode();q->infor=x;
    while(i<n-1){
        p=p->next;
        i=i+1;
    }
    p->next=q;q->next=NULL;
    delay(2000);return(q);
}
NODEPTR Insertafter(NODEPTR *plist, sinhvien x, int n){
    NODEPTR p,q; int i;
    if(n<0){
        printf("\n Vi tri khong hop le");
        delay(2000);return(NULL);
    }
       p=*plist;i=0;
    while(p!=NULL && i<n){
        i=i+1;
        p=p->next;
    }
    if(p==NULL){
        printf("\n Vi tri khong hop le");
        delay(2000); return(NULL);
    }
    q=Getnode();q->infor=x;
    q->next= p->next;
    p->next=q;
    return(q);
}
void Deltop(NODEPTR *plist){
    NODEPTR p, q;
    p=*plist;
    if(Emptynode(plist)){
        printf("\n Danh sach rong");
        delay(2000); return;
    }
    q=p;p=p->next;*plist=p;
    printf("\n Node bi loai bo");
    printf("\n%-5d%-20s",q->infor.masv, q->infor.hoten);
    delay(2000);Freenode(q);
}
void Delbottom(NODEPTR *plist){
    NODEPTR p,q; int i,n;
    n=Bottomnode(plist);
    if(n==-1){
        printf("\n Danh sach rong");
        delay(2000); return;
    }
    if(n==1){
        Deltop(plist);return;
    }
    p=*plist;i=0;
    while(i<n-2){
        p=p->next;
        i=i+1;
    }
    q=p->next;p->next=NULL;
    printf("\n Node duoc loai bo");
    printf("\n %-5d%-20s",q->infor.masv,q->infor.hoten);
    delay(2000); Freenode(q);
}
void Delcurrent(NODEPTR *plist, int n){
    NODEPTR p,q; int i;
    if(Emptynode(plist)){
        printf("\n Danh sach rong");
        delay(2000);return;
    }
    if(n==0){
        Deltop(plist); return;
    }
    p=*plist; i=0;
    while(p!=NULL && i<n-1){
        i=i+1;
        p=p->next;
    }
    if(p->next==NULL){
        printf("\n Node khong hop le");
        delay(2000); return;
    }
    q=p->next;p->next=q->next;
    printf("\n Node duoc loai bo");
    printf("\n %-5d%-20s",q->infor.masv, q->infor.hoten);
    delay(2000); Freenode(q);
}
void Travenode(NODEPTR *plist){
    NODEPTR p;
    if(Emptynode(plist)){
        printf("\n Danh sach rong");
        delay(2000);return;
    }
    p=*plist;
    while(p!=NULL){
        printf("\n %-5d%-20s",p->infor.masv, p->infor.hoten);
        p=p->next;
    }
    delay(2000);
}
void Sortnode(NODEPTR *plist){
    NODEPTR p,q;sinhvien temp;
    for(p=*plist; p!=NULL; p=p->next){
        for(q=p->next; q!=NULL; q=q->next){
            if(p->infor.masv>q->infor.masv){
                temp=p->infor; p->infor=q->infor;
                q->infor=temp;
            }
        }
    }
    printf("\n Danh sach duoc sap xep");
    for(p=*plist; p!=NULL; p=p->next){
        printf("\n %-5d%-20s",p->infor.masv,p->infor.hoten);
    }
    delay(2000);
}
void Searchnode(NODEPTR *plist, int masv){
    NODEPTR p;
    p=*plist;
    while(p!=NULL && p->infor.masv!=masv)
        p=p->next;
    if(p==NULL)
        printf("\n Node khong ton tai");
    else {
        printf("\n Node can tim");
        printf("\n %-5d%-20s",p->infor.masv,p->infor.hoten);
    }
    delay(2000);
}

void Thuchien(void){
    NODEPTR plist; sinhvien x,y;int vitri; char c;
    Initialize(&plist);
    do {
        clrscr();
        printf("\n THAO TAC VOI SINGLE LINK LIST");
        printf("\n 1- Them node dau danh sach");
        printf("\n 2- Them node cuoi danh sach");
        printf("\n 3- Them node giua danh sach");
        printf("\n 4- Loai bo node dau danh sach");
        printf("\n 5- Loai bo node cuoi danh sach");
        printf("\n 6- Loai node giua danh sach");
        printf("\n 7- Duyet danh sach");
        printf("\n 8- Sap xep danh sach");
        printf("\n 9- Tim kiem danh sach");
        printf("\n 0- Tro ve");
        c=getch();
        switch(c){
            case '1':
                printf("\n Ma sinh vien:");scanf("%d", &x.masv);
                fflush(stdin); printf("\n Ho va ten:");gets(x.hoten);
                Inserttop(&plist,x); break;
            case '2':
                printf("\n Ma sinh vien:");scanf("%d", &x.masv);
                fflush(stdin); printf("\n Ho va ten:");gets(x.hoten);
                Insertbottom(&plist,x); break;
            case '3':
                printf("\n Vi tri tren:"); scanf("%d",&vitri);
                printf("\n Ma sinh vien:");scanf("%d", &x.masv);
                fflush(stdin); printf("\n Ho va ten:");gets(x.hoten);
                Insertafter(&plist,x,vitri-1); break;
            case '4': Deltop(&plist);break;
            case '5': Delbottom(&plist);break;
            case '6':
                fflush(stdin);printf("\n Vi tri loai bo:");
                scanf("%d",&vitri);
                Delcurrent(&plist,vitri-1);break;
            case '7': Travenode(&plist); break;
            case '8': Sortnode(&plist);break;
            case '9':
                fflush(stdin);printf("\n Ma sinh vien:");
                scanf("%d",&vitri);
                Searchnode(&plist, vitri);break;
        }
    } while(c!='0');
}
void main(void){
    Thuchien();
}

---

#include    <stdio.h>
#include    <stdlib.h>
#include    <conio.h>
#include    <dos.h>
#include    <string.h>
#include     <math.h>
#include <alloc.h>
#define TRUE 1
#define FALSE 0
typedef struct {
    int masv;
    char hoten[20];
} sinhvien;
typedef struct node{
    sinhvien infor;
    struct node *next;
} *NODEPTR;
void Initialize(NODEPTR *plist){
    *plist=NULL;
}
NODEPTR Getnode(void){
    NODEPTR p;
    p=(NODEPTR) malloc(sizeof(struct node));
    return(p);
}
void Freenode(NODEPTR p){
    free(p);
}
int Emptynode(NODEPTR *plist){
    if(*plist==NULL)
        return(TRUE);
    return(FALSE);
}
NODEPTR Inserttop(NODEPTR *plist, sinhvien x){
    NODEPTR p;
    p=Getnode();
    p->infor=x;
    if(Emptynode(plist)){
        p->next=NULL;
        *plist=p;
        return(p);
    }
    p->next=*plist;
    *plist=p;
    return(p);
}
int Bottomnode(NODEPTR *plist){
    int i; NODEPTR p;
    if(Emptynode(plist))
        return(-1);
    p=*plist;i=0;
    while(p!=NULL){
        i=i+1;
        p=p->next;
    }
    return(i);
}
NODEPTR Insertbottom(NODEPTR *plist, sinhvien x){
    NODEPTR p, q;int n,i;
    n=Bottomnode(plist);
    if(n==-1){
        Inserttop(plist,x);
        return(*plist);
    }
    p=*plist;i=0;q=Getnode();q->infor=x;
    while(i<n-1){
        p=p->next;
        i=i+1;
    }
    p->next=q;q->next=NULL;
    delay(2000);return(q);
}
NODEPTR Insertafter(NODEPTR *plist, sinhvien x, int n){
    NODEPTR p,q; int i;
    if(n<0){
        printf("\n Vi tri khong hop le");
        delay(2000);return(NULL);
    }
       p=*plist;i=0;
    while(p!=NULL && i<n){
        i=i+1;
        p=p->next;
    }
    if(p==NULL){
        printf("\n Vi tri khong hop le");
        delay(2000); return(NULL);
    }
    q=Getnode();q->infor=x;
    q->next= p->next;
    p->next=q;
    return(q);
}
void Deltop(NODEPTR *plist){
    NODEPTR p, q;
    p=*plist;
    if(Emptynode(plist)){
        printf("\n Danh sach rong");
        delay(2000); return;
    }
    q=p;p=p->next;*plist=p;
    printf("\n Node bi loai bo");
    printf("\n%-5d%-20s",q->infor.masv, q->infor.hoten);
    delay(2000);Freenode(q);
}
void Delbottom(NODEPTR *plist){
    NODEPTR p,q; int i,n;
    n=Bottomnode(plist);
    if(n==-1){
        printf("\n Danh sach rong");
        delay(2000); return;
    }
    if(n==1){
        Deltop(plist);return;
    }
    p=*plist;i=0;
    while(i<n-2){
        p=p->next;
        i=i+1;
    }
    q=p->next;p->next=NULL;
    printf("\n Node duoc loai bo");
    printf("\n %-5d%-20s",q->infor.masv,q->infor.hoten);
    delay(2000); Freenode(q);
}
void Delcurrent(NODEPTR *plist, int n){
    NODEPTR p,q; int i;
    if(Emptynode(plist)){
        printf("\n Danh sach rong");
        delay(2000);return;
    }
    if(n==0){
        Deltop(plist); return;
    }
    p=*plist; i=0;
    while(p!=NULL && i<n-1){
        i=i+1;
        p=p->next;
    }
    if(p->next==NULL){
        printf("\n Node khong hop le");
        delay(2000); return;
    }
    q=p->next;p->next=q->next;
    printf("\n Node duoc loai bo");
    printf("\n %-5d%-20s",q->infor.masv, q->infor.hoten);
    delay(2000); Freenode(q);
}
void Travenode(NODEPTR *plist){
    NODEPTR p;
    if(Emptynode(plist)){
        printf("\n Danh sach rong");
        delay(2000);return;
    }
    p=*plist;
    while(p!=NULL){
        printf("\n %-5d%-20s",p->infor.masv, p->infor.hoten);
        p=p->next;
    }
    delay(2000);
}
void Sortnode(NODEPTR *plist){
    NODEPTR p,q;sinhvien temp;
    for(p=*plist; p!=NULL; p=p->next){
        for(q=p->next; q!=NULL; q=q->next){
            if(p->infor.masv>q->infor.masv){
                temp=p->infor; p->infor=q->infor;
                q->infor=temp;
            }
        }
    }
    printf("\n Danh sach duoc sap xep");
    for(p=*plist; p!=NULL; p=p->next){
        printf("\n %-5d%-20s",p->infor.masv,p->infor.hoten);
    }
    delay(2000);
}
void Searchnode(NODEPTR *plist, int masv){
    NODEPTR p;
    p=*plist;
    while(p!=NULL && p->infor.masv!=masv)
        p=p->next;
    if(p==NULL)
        printf("\n Node khong ton tai");
    else {
        printf("\n Node can tim");
        printf("\n %-5d%-20s",p->infor.masv,p->infor.hoten);
    }
    delay(2000);
}

void Thuchien(void){
    NODEPTR plist; sinhvien x,y;int vitri; char c;
    Initialize(&plist);
    do {
        clrscr();
        printf("\n THAO TAC VOI SINGLE LINK LIST");
        printf("\n 1- Them node dau danh sach");
        printf("\n 2- Them node cuoi danh sach");
        printf("\n 3- Them node giua danh sach");
        printf("\n 4- Loai bo node dau danh sach");
        printf("\n 5- Loai bo node cuoi danh sach");
        printf("\n 6- Loai node giua danh sach");
        printf("\n 7- Duyet danh sach");
        printf("\n 8- Sap xep danh sach");
        printf("\n 9- Tim kiem danh sach");
        printf("\n 0- Tro ve");
        c=getch();
        switch(c){
            case '1':
                printf("\n Ma sinh vien:");scanf("%d", &x.masv);
                fflush(stdin); printf("\n Ho va ten:");gets(x.hoten);
                Inserttop(&plist,x); break;
            case '2':
                printf("\n Ma sinh vien:");scanf("%d", &x.masv);
                fflush(stdin); printf("\n Ho va ten:");gets(x.hoten);
                Insertbottom(&plist,x); break;
            case '3':
                printf("\n Vi tri tren:"); scanf("%d",&vitri);
                printf("\n Ma sinh vien:");scanf("%d", &x.masv);
                fflush(stdin); printf("\n Ho va ten:");gets(x.hoten);
                Insertafter(&plist,x,vitri-1); break;
            case '4': Deltop(&plist);break;
            case '5': Delbottom(&plist);break;
            case '6':
                fflush(stdin);printf("\n Vi tri loai bo:");
                scanf("%d",&vitri);
                Delcurrent(&plist,vitri-1);break;
            case '7': Travenode(&plist); break;
            case '8': Sortnode(&plist);break;
            case '9':
                fflush(stdin);printf("\n Ma sinh vien:");
                scanf("%d",&vitri);
                Searchnode(&plist, vitri);break;
        }
    } while(c!='0');
}
void main(void){
    Thuchien();
}