Chatbox
Các bạn vui lòng dùng từ ngữ lịch sự và có văn hóa,sử dụng Tiếng Việt có dấu chuẩn. Chúc các bạn vui vẻ!
08/11/2012 21:11 # 1
anh2bmw
Cấp độ: 48 - Kỹ năng: 44

Kinh nghiệm: 255/480 (53%)
Kĩ năng: 408/440 (93%)
Ngày gia nhập: 27/11/2009
Bài gởi: 11535
Được cảm ơn: 9868
Đồ án Quản lý điểm sinh viên trên danh sách liên kết đơn link mediafire.com

Khác với stack, queue danh sách liên kết đơn cũng là một kiểu danh sách tuyến tính gồm các phần tử vào lần lượt theo thứ tự tuy nhiên nó khác stack và queue ở chỗ là nó được cấp phát trong bộ nhớ bởi các phần tử rời rạc nhau, không nằm kề nhau, tuy nhiên giữa phần tử trước thì có 1 liên kết đến phần tử sau 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



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

2. Con trỏ tới 1 node



PHP Code:
struct  node { 
        int infor; 
        struct node *next; 
    }; 
    typedef struct node *NODEPTR;  

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



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

4. Giải phóng 1 node



PHP Code:
NODEPTR Freenode( NODEPTR p){ 
        free(p); 
    }  

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



PHP Code:
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



PHP Code:
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



PHP Code:
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



PHP Code:
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



PHP Code:
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; 
        } 
        // xoa node cuoi danh sach; 
        q->next =NULL; 
        Freenode(p); 
    } 
}  

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



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

 



Thông tin liên hệ anh2bmw khi có bất kỳ thắc mắc:
skype: trantien281
mail:  anh2bmw@gmail.com


 
 
08/11/2012 22:11 # 2
anh2bmw
Cấp độ: 48 - Kỹ năng: 44

Kinh nghiệm: 255/480 (53%)
Kĩ năng: 408/440 (93%)
Ngày gia nhập: 27/11/2009
Bài gởi: 11535
Được cảm ơn: 9868
Phản hồi: Đồ án Quản lý điểm sinh viên trên danh sách liên kết đơn link mediafire.com

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



PHP Code:
#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(); 
} 

 



Thông tin liên hệ anh2bmw khi có bất kỳ thắc mắc:
skype: trantien281
mail:  anh2bmw@gmail.com


 
 
Copyright© Đại học Duy Tân 2010 - 2024