Thứ Ba, 22 tháng 5, 2012

Cai Dat Danh Sach Lien Ket Kep

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |


// CaiDat_DSLK_Kep.cpp : Defines the entry point for the console application.
// DSLKK : o day la vi du ve doan tau, cac toa tau : hang khac va so ghe trong 1 toa

#include "stdafx.h"
#include <iostream>
#include <conio.h>

//Dinh nghia kieu toa tau
typedef struct {
    int number_of_seats;// Tong so ghe ngoi
    int number_of_passenger;// So hanh khach tren toa
} railroad_car;
typedef struct node{
    railroad_car infor;
    node *left;
    node *right;
} *dlist;

//KHoi tao DSLK
void init(dlist *l){
    *l= NULL;
}

//Nhap vao 1 toa tau
void inputRC(railroad_car &rc){
    printf("\n\n Nhap vao so ghe ngoi: ");
    scanf("%d",&rc.number_of_seats);
    printf("\n Nhap vao so hanh khach: ");
    scanf("%d",&rc.number_of_passenger);
    fflush(stdin);
}

//Hien thi 1 toa tau
void show(railroad_car rc, int i){
    printf("\n\n Toa thu %d: ",i);
    printf("\n So ghe ngoi:   %d",rc.number_of_seats);
    printf("\n So hanh khach: %d",rc.number_of_passenger);
}

//Duyet sang trai
void travel_left(dlist *l){
    dlist p= *l;
    int i= 1;
    while(p!= NULL){
        show(p->infor,i);
        i++;
        p= p->left;
    }
}
//Duyet sang phai
void travel_right(dlist *l){
    dlist p= *l;
    int i=1;
    //Chuyen p toi cuoi danh sach
    while(p->left!= NULL){
        p= p->left;
        i++;
    }
    while(p!= NULL){
        show(p->infor,i);
        i--;
        p= p->right;
    }
}
//=============== Them =================
//Them vao 1 node tren cung
void add_top(dlist *l){
    railroad_car rc;
    inputRC(rc);
    dlist p= *l;//p o dau danh sach
    dlist add = new node;//add la node can them vao
    add->infor= rc;
    add->left= p;
    if(p!= NULL)
        p->right= add;
    add->right= NULL;
    *l= add;//gan *l len dau danh sach
}
//Them 1 node vao cuoi
void add_bottom(dlist *l){
    railroad_car rc;
    inputRC(rc);//Nhap thong tin
    dlist p= *l;//p o dau danh sach
    dlist add = new node;//add la node can them vao
    add->infor = rc;
    //Neu danh sach rong
    if(p== NULL){
        add->left= NULL;
        add->right= NULL;
        *l= add;
    }
    else{
        //Duyet toi cuoi danh sach
        while(p->left!=NULL)
            p= p->left;
        //p dang o cuoi danh sach
        add->left= NULL;
        p->left= add;
        add->right= p;
    }
}
//Them 1 node vao giua
void add_before(dlist *l){
    int n,i=1;
    dlist p= *l;
    printf("\n Nhap vi tri ban muon them vao truoc: ");
    scanf("%d",&n);
    while(p!= NULL && i<n ){
        p= p->left;
        i++;
    }
    if(p== NULL || n<1){//Neu ko ton tai vi tri
        printf("\n Vi tri khong hop le ");
        getch();
        return;
    }
    //Neu ton tai vi tri do
    railroad_car rc;
    inputRC(rc);
    dlist add = new node;//add la node can them vao
    add->infor= rc;
        //neu vi tri do la cuoi cung
        if(p->left== NULL){
            add->left= NULL;
            add->right= p;
            p->left= add;
        }
        else{
            dlist q;
            q= p->left;
            //Can them vao giua p va q . p dang o truoc q
                //Noi p voi add
                p->left= add;
                add->right= p;
                //Noi add voi q
                add->left= q;
                q->right= add;
        }
}

//=================Xoa===========================
//Xoa o dau danh sach
void del_top(dlist *l){
    dlist p= *l;
    if(p== NULL){
        printf("\n Danh sach rong !");
        return;
    }
    else{
        if(p->left== NULL){
            delete(p);
            *l= NULL;
        }
        else{
            dlist q= p->left;//q o ben phai p
            delete(p);
            q->right= NULL;
            *l= q;
        }
    }
}

//Xoa o cuoi
void del_bottom(dlist *l){
    dlist p= *l;
    if(p== NULL){
        printf("\n Danh sach rong !");
        return;
    }
    else{
        if(p->left== NULL){
            delete(p);
            *l= NULL;
        }
        else{
            while((p->left)->left!= NULL)
                p= p->left;
            dlist q= p->left;
            delete(q);
            p->left= NULL;
        }
    }
}
//Xoa 1 node truoc 1 node
void del_before(dlist *l){
    int n,i=1;
    dlist p= *l;
    printf("\n Nhap vi tri node ");
    scanf("%d",&n);
    if(p== NULL){
        printf("\n Danh sach rong !");
        return;
    }
    while((p->left)->left!= NULL && i<n){
        p= p->left;
        i++;
    }
    //Neu chi co 1 node
    if(p->left== NULL || n<1){
        printf("\n Vi tri khong chinh xac ");
        return;
    }

    dlist del= p->left;//del la phan tu bi xoa
    //Neu node phai xoa la cuoi cung
    if(del->left== NULL){
        delete(del);
        p->left= NULL;
        return;
    }
    //Sau khi del bi xoa can noi p voi q
    p->left=del->left;printf("\n f gan ");
    (del->left)->right= p;printf("\n f bat dau xoa");
    delete(del);
}


void menu(){
    printf("\n\n============= Danh sach lien ket kep =================\n");
    printf("\n 1. Them vao dau danh sach");
    printf("\n 2. Them vao cuoi danh sach");
    printf("\n 3. Them vao truoc 1 node");
    printf("\n 4. xoa dau danh sach");
    printf("\n 5. Xoa cuoi danh sach");
    printf("\n 6. Xoa 1 node dang truoc 1 node");
    printf("\n 7. Duyet trai");
    printf("\n 8. Duyet phai");
    printf("\n 0. ----- Thoat -----\n");
}
// Ham thuc hien cac chuc nang
void execute(){
    dlist l;
    init(&l);
    char choice;
    do{
        menu();
printf("\n Chon 1 trong cac chuc nang tren \n");
        scanf("%c",&choice);
        if(choice== '0') exit(0);
        fflush(stdin);
            switch(choice){
                case '1':{
                    printf("\n 1. Them vao dau danh sach");
                    add_top(&l);
                    printf("\n      THEM THANH CONG    ");
                    getch();
                }break;

                case '2':{
                    printf("\n 2. Them vao cuoi danh sach");
                    add_bottom(&l);
                    printf("\n      THEM THANH CONG    ");
                    getch();
                }break;

                case '3':{
                    printf("\n 3. Them vao truoc 1 node");
                    add_before(&l);
                    printf("\n      THEM THANH CONG    ");
                    getch();
                }break;

                case '4':{
                    printf("\n 4. xoa dau danh sach");
                    del_top(&l);
                    printf("\n      XOA THANH CONG    ");
                    getch();
                }break;

                case '5':{
                    printf("\n 5. Xoa cuoi danh sach");
                    del_bottom(&l);
                    printf("\n      XOA THANH CONG    ");
                    getch();
                }break;

                case '6':{
                    printf("\n 6. Xoa 1 node");
                    del_before(&l);
                    printf("\n      XOA THANH CONG    ");
                    getch();
                }break;

                case '7':{
                    printf("\n     DUYET TRAI    ");
                    travel_left(&l);
                    getch();
                }break;

                case '8':{
                    printf("\n     DUYET PHAI    ");
                    travel_right(&l);
                    getch();
                }break;
            }
    }while(true);

}
int main(){
    execute();
    return (0);
}

Danh Sach Lien Ket Kep

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |


Như chúng ta đa biết có hai dạng danh sách liên kết kép bao gồm :
Danh sách liên kết kép bình thường
Đây là dạng danh sách liên kết kép mà nút cuối cùng của danh sách có trường next là NULL và nút đầu có trường prev cũng là NULL. (xem hình).
 

Danh sách liên kết kép vòng (circular doubly linked list)
Đây là dạng danh sách liên kết kép mà nút cuối có trường next chỉ về nút đầu và nút đầu có trường prev chỉ về nút cuối. (xem hình)

Tuy nhiên trong class LinkedList chỉ hỗ trợ cho bạn danh sách liên kết kép dạng bình thường mà thôi. LinkedList (danh sách liên kết kép) generic là một danh sách liên kết kép nơi mà mỗi nút trỏ sang nút kế tiếp và nút trước nó. Các nút của LinkedList có kiểu là LinkedListNode. Mỗi phần tử của LinkedListNode chứa giá trị dữ liệu của một nút và một tham chiếu đến danh sách liên kết LinkedList chứa nút đó. Bên cạnh đó mỗi phần tử LinkedListNode cũng chứa một tham chiếu dẫn đến nút kế tiếp và đến nút trước nó.
Tập hợp LinkedList thực thi các giao diện ICollection, hỗ trợ các bộ liệt kê (Enumerator) và các lớp Collection khác trong .NET Framework.

Cai Dat Danh Sach Lien Ket Vong

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |


// CaiDat_DSLK_Vong.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
typedef struct node
{
    int info;
    node *link;
}node;
node *fist;
void xuat()
{
    node *p;
    p=fist;
    if(p!=NULL)
    {
       do{
       
        cout<<p->info<<endl;
        p=p->link;  

        }while(p!=fist);
    }
    else
        cout<<"\n Khong co phan tu \n";
}

void rong()
{
    fist=NULL;
}

void themdau(int x)
{
    node *p,*q;  
    p=new node;
    p->info=x;
    q=fist;
    if(fist!=NULL)
        p->link=fist;
    else
        p->link=p;
    if(q!=NULL)
    {
        while(q->link!=fist)
        {
            q=q->link;
        }              
        q->link=p;
    }
    fist=p;
   
}
void xoadau(int &x)
{
    node*p,*q;
    p=fist;
    q=fist->link;  
    if(p->link==fist)
    {
        delete p;
        fist=NULL;
    }
    else
    {
        while(q->link!=fist)
        {
            q=q->link;
        }
        x=p->info;
        fist=fist->link;
        delete p;      
           
    }
    q->link=fist;

}
void themcuoi(int x)
{
    node*p,*q;
    p=new node;
    p->info=x;
    q=fist;
    if(fist==NULL)
    {
        p->link=fist;
    }
    else
    {
        while(q->link!=fist)
        {
            q=q->link;
        }
        q->link=p;
       
    }
    p->link=fist;
}

void xoacuoi(int &x)
{
    node*p,*q;
    q=fist;  
    if(fist==NULL)
    {
        cout<<"\n Khong co phan tu de xoa \n";
    }
    else if(q->link==fist)
    {
        delete q;
        fist=NULL;
    }
    else
    {      
        while(q->link!=fist)
        {  
            p=q;
            q=q->link;
        }
        x=q->info;
        delete q;
        p->link=fist;
    }
   
}
void tim(int &x)
{
    node*p,*q;
    q=fist;
    do
        {
            if(q->info!=x)
            {
            p=q;
            q=q->link;
            }
            else
                break;
           
        }while(q->link!=fist);
    if(q==fist)
    {
        xoadau(x);
    }
    else
    {  
        x=q->info;
        p->link=q->link;
        delete q;      
    }
   
}
void main()
{
    rong();
    int chon = -1,x;
printf("\n CHON THAO TAC THUC HIEN : \n");
    while(chon!= 0)
    {
       
        cout << "1.Xuat"<<endl;
        cout << "2.Them phan tu vao dau danh sach" <<endl;
        cout << "3.Xoa phan tu dau danh sach" <<endl;
        cout << "4.Them phan tu cuoi danh sach" <<endl;
        cout << "5.Xoa phan tu cuoi danh sach" <<endl;
        cout << "6.Tim va xoa" <<endl;
        cout<<" Chon : ";
        cin >> chon;
       
        switch(chon)
        {
        case 1:  
            xuat();
            break;      
        case 2:    cout<<" Nhap phan tu can them :   ";
            cin>>x;          
            themdau(x);
            break;  
        case 3:  
            xoadau(x);
            break;  
        case 4:cout<<" Nhap phan tu can them :    ";
            cin>>x;  
            themcuoi(x);
            break;
            case 5:
            xoacuoi(x);
            break;
            case 6:cout<<" Nhap phan tu can tim :   ";
                cin>>x;
                tim(x);
                break;
        }
       
    }
}

DanH Sach Lien Ket Vong

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |


Danh Sách liên kết vòng là danh sách liên kết nhưng trướng next của nút cuối chỉ nút đầu tiên trong danh sách.

Không nói dài dòng chúng ta sẽ nghiên cứu luôn về cách cài đặt danh sách liên kết vòng bằng biến động.
C Code:Lựa chọn code | Ẩn/Hiện code
int listsize(NODEPTR *plist)
{
     NODEPTR p;
   int i;
   if(empty(plist))
       return (0);
   p = (*plist->next);
   i = 1;
   while(p != *plist)
   {
        i++;
      p = p->next;
   }
}

1. Khai báo cấu trúc một nút strong danh sách liên kết vòng.
Khai báo một nút là một mẫu tin (struct) có hai trường là info và next.
Trường info: chứa nội dung của nút.
Trường next: là con trỏ chỉ nút, dùng chỉ nút kế trong danh sách liên kết vòng.

struct node
{
      int info;
            struct node *next;
};
//khai bao kieu con tro chi den nut
typedef struct node *NODEPTR;
Chúng ta quản lý danh sách liên kết vòng qua con trỏ plist chỉ nút cuối của danh sách. Con trỏ plist có thể khai báo toàn cục hay cụ bộ.


2. Các tác vụ trên danh sách liên kết vòng:

Tác vụ getnode:
Cấp phát một biến động làm cho nút một danh sách liên kết vòng:

NODEPTR getnode(void)
{
      NODEPTR p;
   p = (NODEPTR) malloc(sizeof(struct node));
   return (p);
};

Tác vụ freenode:
Giải phóng biến động đã cấp phát trước đó.

void freenode(NODEPTR p)
{
      free(p);
}

Tác vụ initialize:
Khởi động danh sách liên kết vòng:

void initialize(NODEPTR *plist)
{
     *plist = NULL;
}

Tác vụ empty:
Kiểm tra danh sách liên kết vòng có rỗng không.

int empty(NODEPTR *plist)
{
       return(*plist == NULL ? true : false);
}

Tác vụ listsize:
Đếm số nút có trong danh sách liên kết vòng:

int listsize(NODEPTR *plist)
{
     NODEPTR p;
   int i;
   if(empty(plist))
       return (0);
   p = (*plist->next);
   i = 1;
   while(p != *plist)
   {
        i++;
      p = p->next;
   }
   return (i);
}

Tác vụ nodepointer:
Trả về con trỏ nút thứ i (i = 0,1,2,....) trong danh sách liên kết vòng

NODEPTR nodepointer(NODEPTR *plist, int i)
{
      NODEPTR p;
      int vitri;
      if(i < 0 || i >= listsize(plist))
           return(null);
      p = (*plist)->next; //p chi nut dau dslk vong
      for(vitri = 0;vitri < i;vitri++)
          p = p->next;
      return(p);
}

Tác vụ push:
Thêm một nút vào đầu danh sách liên kết vòng.

void push(NODEPTR *plist, int x)
{
      NODEPTR p;
   p = getnode();
   p->info = x;
   if(empty(plist) == true)
       *plist = p;
   else
       p->next = (*plist)->next;
   (*plist)->next = p;
};

Tác vụ insend:
Thêm nút vào cuối danh sách liên kết vòng.

void insend(NODEPTR *plist, int x)
{
    NODEPTR p;
    p = getnode();
    p->info = x;
    if(empty(plist) == true)
        p->next = p;
    else
    {
         p->next = (*plist)->next;
      (*plist)->next = p;
    }
    *plist = p;
};

Tác vụ pop:
Xóa nút ở đầu danh sách liên kết vòng.

int pop(NODEPTR *plist)
{
      NODEPTR p;
   int x;
   if(empty(plist))
       printf("Danh sach bi rong");
   else
   {
        p = (*plist)->next; // p la nut can xoa
      x = p->info;
      if(p == *plist) // truong hop ds chi co mot nut
          *plist = NULL;
      else
          (*plist)->next = p->next;
      freenode(p);
      return (x);
   }
};

Tác vụ dellast:
Xóa nút ở cuối danh sách liên kết vòng.

int dellast(NODEPTR *plist)
{
     NODEPTR p;
   int x;
   if(empty(plist))  // truong hop danh sach bi rong
       printf("Danh sach bi rong");
   else
   {
        if((*plist)->next == plist) // truong hop cho co mot nut
           {
              p = *plist;
               x = p->info;
             *plist = NULL;
              freenode(p);
              return(x);
         }
         p = *plist;    // p la nut can xoa
         x = p->info;
         *plist = nodepointer(plist, listsize(plist) - 2);
         (*plist)->next = p->next;
         freenode(p);
         return (x);
   }
}

Tác vụ traverse:
Duyệt danh sách liên kết vòng từ nút đầu đến nút cuối.

void traverse(NODEPTR *plist)
{
     NODEPTR p;
   if(*plist == NULL)
       printf("Danh sach rong")
   else
   {
        p = (*plist)->next; //p chi nut dau
      printf("%d", p->info);
      p = p->next;        //p chi nut thu hai
      while(p != (*plist)->next)
      {
           printf("%d",p->info);
         p = p->next;
      }
   }
}

Cai Dat Danh Sach Lien Ket Don

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |


// DSLKD.cpp : Defines the entry point for the console application.
//


//File:quanliSV.c
//Chuong trinh quan li sinh vien so cap
//Input: cac thong tin cua sinh vien nhap vao tu ban phim
//Ouput: in ra danh sach sinh vien va thuc hien mot so chuc nang
//------------------------------------------------------------------------------
//Class:                                Instructor:
//Assignment:                           Date assigned:
//Programmer:                           Date completed:
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <iostream>
using namespace std;

/*dinh nghia cac gia tri ma nguoi dung co the chon*/
#define kiHieu (1,2,3,4,5,0)

//Cau truc cua mot sinh vien
typedef struct pp{
    char ht[20];
    char que[20];
    char maSoSV[20];
    struct pp *next;
}sinhVien;

//Ham nhap danh sach sinh vien
void nhapSV(sinhVien **pdau,int *n);

//Ham sua thong tin cua mot sinh vien trong danh sach
void suaSV(sinhVien *pdau,int *n);

//Ham them sinh vien vao trong danh sach
void themSV(sinhVien *pdau,int *n);

//Ham xoa sinh vien trong danh sach
void xoaSV(sinhVien *pdau,int *n);

//Ham tim kiem thong tin ve 1 sinh vien trong danh sach
void timSV(sinhVien *pdau,int *n);

//Ham in ra danh sach cac sinh vien duoc quan li trong danh sach
void inSV(sinhVien *pdau,int *n);

//Ham main
void main()
{
    //Khai bao dia chi cua sinh vien dau tien
    sinhVien *pdau = NULL;
    int n;
    int chon;
    //Nhap danh sach sinh vien ban dau
    nhapSV(&pdau,&n);
    printf("HAY AN 1 PHIM CHUC NANG SAU:\n\
Phim 1 de sua thong tin cua mot sv trong danh sach\n\
Phim 2 de them 1 sv vao trong danh sach\n\
Phim 3 de xoa 1 sv trong danh sach\n\
Phim 4 de tim kiem 1 sv trong danh sach\n\
Phim 5 de in ra thong tin cac sv trong danh sach\n\
Phim 0 de thoat khoi chuong trinh\n");
    printf("Chon: "); scanf("%d",&chon);
    //Kiem tra so ma nguoi dung nhap vao co hop le hay khong
    while(chon > 6|| chon < 0){
        printf("So ban nhap khong hop le!\n Xin ban nhap lai: ");
        scanf("%d",&chon);
    }
    //Xoa luong du lieu vao
    fflush(stdin);
    //Cac chuc nang tuong ung voi cac so
    switch(chon){
        case 0:
            exit(0);
        case 1:
            suaSV(pdau,&n);
        case 2:
            themSV(pdau,&n);
        case 3:
            xoaSV(pdau,&n);
        case 4:
            timSV(pdau,&n);
        case 5:
            inSV(pdau,&n);
    }
    getch();
}

//Ham nhap danh sach sinh vien
void nhapSV(sinhVien **pdau,int *n)
{
    sinhVien *p;
    char ht[20];
    //tao danh sach sinh vien
    while(1){

        //Nhap ten sinh vien roi kiem tra
        printf("\n Hay nhap ten cua sinh vien: ");
        //Kiem tra xem ten sinh vien co the them vao danh sach duoc hay khong
        gets(ht);
        if(ht[0]==0){
            break;
        }
        //Kiem tra xem dau danh sach da co phan tu nao chua
        //Neu chua co thi se tao ra phan tu dau tien
        if(*pdau==NULL){
            //Cap phat bo nho cho phan tu dau tien
            *pdau=(sinhVien*)malloc(sizeof(sinhVien));
            p=*pdau;
            strcpy(p->ht,ht);
            printf("\n Nhap que cua sinh vien: ");
            gets(p->que);
            printf("\n Ma so sinh vien: ");
            gets(p->maSoSV);
            p->next = NULL;
            *n++;
        }else{
            //Thuc hien tao cac phan tu tiep theo cua danh sach
            //Den khi nguoi dung khong nhap nua
            p->next=(sinhVien*)malloc(sizeof(sinhVien));
            p=p->next;
            /*printf("Hay nhap ten cua sinh vien nay: ");
            gets(ht);
            if(ht==0){
                break;
            }*/
            strcpy(p->ht,ht);
            printf("Que quan: ");
            gets(p->que);
            printf("Ma so sinh vien: ");
            gets(p->maSoSV);
            p->next = NULL;
            *n++;
        }
    }
    return;
}

//Ham sua thong tin cua mot sinh vien
void suaSV(sinhVien *pdau,int *n)
{
    //Con tro chua vi tri cua sinh vien dang kiem tra
    sinhVien *p;
    int kiemTra=1;
    char ht[20];
    char c;
    printf("Hay nhap ten cua sinh vien can sua thong tin: ");
    gets(ht);
    while(1){
        if(ht==0){
            return;
        }
        if(strcmp(p->ht,ht)==0){
            break;
        }
        if(p->next!=NULL){
            p=p->next;
            kiemTra=1;
        }else{
            kiemTra=0;
            break;
        }
    }
    if(kiemTra=0){
        printf("Khong so sinh vien nao co ten nhu ban vua nhap!");
    }else{
        printf("Ban muon sau thong tin gi cua sinh vien nay:\n\
       Chon 1 de sua ten\n\
       Chon 2 de sua que quan\n\
       Chon 3 de sua ma so sinh vien.");
        c=getch();
        while(c!=kiHieu){
            printf("So ban nhap khong hop le!\n\
           Xin hay nhap lai hoac an 0 de thoat");
        }
        while(c!='0'){
            switch(c){
                case 0:
                    exit(0);
                case 1:
                    printf("Hay nhap ten moi ban muon sua:");
                    gets(p->ht);
                case 2:
                    printf("Hay nhap que moi ban muon sua:");
                    gets(p->que);
                case 3:
                    printf("Hay nhap ma so sinh vien moi:");
                    gets(p->maSoSV);
            }
            printf("Ban muon thuc hien sua thong tin gi nua khong\n\
           Hay chon so tuong ung muon thuc hien hoac an so 0 de thoat");
            c=getch();
        }
    }
}

//Ham them 1 sinh vien vao danh sach
void themSV(sinhVien *pdau,int *n)
{
    sinhVien *p;
    char ht[20];
    printf("Ban hay nhap ten cua sinh vien muon them vao danh sach:");
    gets(ht);
    if(ht==0){
        exit(0);
    }
    p=pdau;
    while(p!=NULL){
        p=p->next;
    }
    p->next=(sinhVien*)malloc(sizeof(sinhVien));
    p=p->next;
    strcpy(p->ht,ht);
    printf("Nhap que cua sinh vien moi: ");
    gets(p->que);
    printf("Nhap ma so cua sinh vien moi: ");
    gets(p->maSoSV);
}

//Ham xoa mot sinh vien trong danh sach
void xoaSV(sinhVien *pdau,int *n)
{
    sinhVien *p=pdau,*luu;
    char ht[20];
    printf("Ban hay nhap ten cua sinh vien can xoa khoi danh sach: ");
    gets(ht);
    if(ht==0){
        exit(0);
    }
    if(pdau==NULL){
        printf("Danh sach khong co ai nen tim kiem khong thanh cong!");
        exit(0);
    }
    while(p!=NULL){
        if(strcmp(p->ht,ht)==0){
            break;
        }else{
            if(p->next!=NULL){
                luu=p;
                p=p->next;
            }else{
                exit(0);
            }
        }
    }
    if(p->next==NULL){
        luu->next=NULL;
    }else{
        luu->next=p->next;
    }
}

//Ham tim kiem 1 sinh vien trong danh sach theo ten
void timSV(sinhVien *pdau,int *n)
{
    sinhVien *p=pdau;
    char ht[20];
    printf("Nhap ten sinh vien ban muon tim trong danh sach: ");
    gets(ht);
    if(pdau==NULL){
        printf("Danh sach chong nen tim kiem khong thuc hien!");
        exit(0);
    }
    while(p!=NULL){
        if(strcmp(p->ht,ht)==0){
            break;
        }else{
            if(p->next!=NULL){
                p=p->next;
            }else{
                printf("Khong co sinh vien nao ten nhu ban vua nhap!");
                exit(0);
            }
        }
    }
    printf("Thong tin cua sinh vien ban vua nhap vao la: ");
    printf("ten: %s \nQue quan: %s\nMa so sinh vien: %s",p->ht,p->que,p->maSoSV);
}

//Ham in ra danh sach cac sinh sien
void inSV(sinhVien *pdau,int *n)
{
    sinhVien *p=pdau;
    printf("%-30s%-30s%-30s\n","Ten sinh vien","Que quan","Ma so sinh vien");
    while(p!=NULL){
        printf("%-30s%-30s%-30s\n",p->ht,p->que,p->maSoSV);
        p=p->next;
    }
}
//End

Danh Sach Lien Ket Don

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |


Ý tưởng: 
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ó.
Thông thường thì người ta xây dựng stack, queue bằng mảng, nhưng điểm hạn chế là nó sẽ bị giới hạn về số lượng phần tử, bởi thế cách hay nhất là xây dựng stack, queue bẳng danh sách liên kết đơn ==> stack, queue là 1 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):

Định nghĩa tổng quát

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

Con trỏ tới 1 node

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

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

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

Giải phóng 1 node

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

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;
}

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;
}

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;
    }
}

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);
}

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);
    }
}

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);
}

Danh Sach Lien Ket

Posted by Unknown Thứ Ba, tháng 5 22, 2012, under |

Định nghĩa:
  Trong khoa học máy tính , một danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút với nhau đại diện cho một chuỗi. Dưới hình thức đơn giản, mỗi nút bao gồm dữ liệu và  một liên kết đến nút tiếp theo trong chuỗi các biến thể phức tạp thêm các liên kết bổ sung. Cấu trúc này cho phép chèn hoặc loại bỏ có hiệu quả các yếu tố từ bất kỳ vị trí theo thứ tự.
  Danh sách liên kết là một trong những đơn giản và cấu trúc dữ liệu phổ biến nhất. Chúng có thể được sử dụng để thực hiện một số khác phổ biến dữ liệu trừu tượng các loại , bao gồm cả ngăn xếp , hàng đợi , mảng kết hợp , và các biểu thức tượng trưng , mặc dù nó không phải là phổ biến để thực hiện các cấu trúc dữ liệu khác trực tiếp mà không cần sử dụng một danh sách các cơ sở thực hiện.
  Lợi ích chủ yếu của một danh sách liên kết trong một thông thường mảng là danh sách các yếu tố có thể dễ dàng thêm vào hoặc gỡ bỏ mà không tái phân bổ, tổ chức lại toàn bộ cấu trúc bởi vì các mục dữ liệu không cần phải được lưu trữ liên tục kế nhau trong bộ nhớ hoặc trên đĩa. Danh sách liên kết cho phép chèn và loại bỏ các nút tại bất kỳ điểm nào trong danh sách, và có thể làm như vậy với một số liên tục hoạt động nếu liên kết trước đó để liên kết được thêm vào hoặc gỡ bỏ được duy trì trong danh sách traversal.
Mặt khác, danh sách đơn giản liên kết tự không cho phép truy cập ngẫu nhiên các dữ liệu, hoặc bất kỳ hình thức lập chỉ mục hiệu quả. Vì vậy, nhiều hoạt động cơ bản - như có nút cuối cùng của danh sách (giả định rằng các nút cuối cùng không được duy trì như là tài liệu tham khảo nút riêng biệt trong cấu trúc danh sách), hoặc tìm kiếm một nút có chứa những mốc nhất định, hoặc vị trí nơi mà một nút mới cần được đưa vào có thể yêu cầu quét hầu hết hoặc tất cả danh sách các yếu tố.
Danh sách liên kết được xây dựng năm 1955-1956 bởi Allen Newell , Cliff Shaw và Herbert A. Simon tại RAND Corporation cấu trúc dữ liệu chính cho xử lý ngôn ngữ Thông tin . IPL được sử dụng bởi các tác giả để phát triển trí thông minh nhân tạo một số đầu chương trình, bao gồm cả máy Lý thuyết Logic, Giải quyết vấn đề chung , và cờ tướng máy tính một chương trình. Báo cáo về công việc của họ xuất hiện trong giao dịch IRE thông tin Lý thuyết vào năm 1956, và một số biên bản hội nghị từ 1957 đến 1959, bao gồm Kỷ yếu của Hội nghị máy tính phương Tây chung vào năm 1957 và 1958, và xử lý thông tin (Kỷ yếu đầu tiên UNESCO Hội nghị quốc tế về xử lý thông tin ) vào năm 1959. Sơ đồ cổ điển hiện nay bao gồm các khối đại diện cho các nút danh sách với các mũi tên trỏ đến các nút trong danh sách, xuất hiện trong "Lập trình máy Lý thuyết Logic" của Newell và Shaw trong Proc. WJCC, tháng 2 năm 1957. Newell và Simon đã được công nhận với giải thưởng ACM Turing năm 1975 đã có những đóng góp cơ bản vào trí thông minh nhân tạo, tâm lý của sự nhận thức của con người, và xử lý danh sách ". Các vấn đề của máy dịch thuật ngôn ngữ tự nhiên xử lý đã dẫn Victor Yngve tại Viện Công nghệ Massachusetts (MIT) để sử dụng danh sách liên kết cấu trúc dữ liệu trong ngôn ngữ lập trình COMIT của mình cho nghiên cứu máy tính trong lĩnh vực ngôn ngữ học . Một báo cáo về ngôn ngữ này mang tên "Một ngôn ngữ lập trình cho dịch cơ học" xuất hiện trong dịch cơ khí vào năm 1958.
LISP , đứng cho bộ xử lý danh sách, được tạo ra bởi John McCarthy vào năm 1958 trong khi ông tại MIT và vào năm 1960, ông xuất bản thiết kế của nó trong một bài báo trong truyền thông của ACM , mang tên "đệ quy Chức năng của biểu thức tượng trưng và tính toán của họ bằng máy, phần I ". Một trong những cấu trúc dữ liệu lớn của LISP là danh sách liên kết. Đầu những năm 1960, các tiện ích của cả hai danh sách liên kết và ngôn ngữ sử dụng các cấu trúc dữ liệu chính như đại diện của họ cũng được thành lập. Bert xanh của Phòng thí nghiệm Lincoln MIT xuất bản một bài báo mang tên "ngôn ngữ máy tính cho các thao tác biểu tượng" trong giao dịch IRE trên yếu tố con người trong Điện tử tháng 3 năm 1961 trong đó tóm tắt những lợi thế của phương pháp tiếp cận danh sách liên kết. Một bài báo sau đó, "So sánh các ngôn ngữ máy tính xử lý danh sách" Bobrow và Raphael, xuất hiện trong Truyền thông của ACM vào tháng Tư năm 1964.
Một số hệ điều hành được phát triển bởi các hệ thống tư vấn kỹ thuật (ban đầu của West Lafayette Indiana, và sau đó Chapel Hill, Bắc Carolina) đã sử dụng danh sách đơn lẻ liên kết như các cấu trúc tập tin. Một mục nhập thư mục chỉ cho khu vực đầu tiên của một tập tin, và một phần thành công của tập tin được đặt con trỏ đi qua. Hệ thống sử dụng kỹ thuật này bao gồm Flex ( 6800 Motorola CPU), mini-Flex (cùng CPU), và Flex9 (cho Motorola 6809 CPU). Một biến thể được phát triển bởi TSC và tiếp thị bởi khói tín hiệu phát thanh truyền hình tại California, đã sử dụng danh sách liên kết kép trong cùng một cách thức.
  TSS/360 điều hành hệ thống, phát triển bởi IBM cho hệ thống 360/370 máy, sử dụng một danh sách liên kết đôi cho danh mục hệ thống tập tin của họ. Cấu trúc thư mục tương tự như Unix, một thư mục có thể chứa các tập tin và / hoặc thư mục khác và mở rộng đến chiều sâu nào. Một trời tiện ích được tạo ra để sửa chữa vấn đề hệ thống tập tin sau khi một tai nạn, kể từ khi phần sửa đổi của các cửa hàng của tập tin đôi khi trong bộ nhớ khi một vụ tai nạn xảy ra. Vấn đề đã được phát hiện bằng cách so sánh những liên kết về phía trước và lạc hậu nhất quán. Nếu một liên kết chuyển tiếp là tham nhũng, sau đó nếu một liên kết ngược trở lại, các nút bị nhiễm bệnh đã được tìm thấy, liên kết chuyển tiếp được thiết lập để các nút với các liên kết ngược. Một bình luận hài hước trong mã nguồn mà tiện ích này được gọi nói "Mọi người đều biết một cổ áo trời được thoát khỏi lỗi ở mèo".
  Khái niệm về một danh sách liên kết có thể được giải thích bằng một phép loại suy đơn giản để hộp bưu điện thế giới thực . Giả sử Alice là một gián điệp người muốn cung cấp cho một codebook cho Bob bằng cách đặt nó trong một hộp bưu điện và sau đó cho anh ta chìa khóa. Tuy nhiên, cuốn sách là quá dày để phù hợp với một hộp văn phòng bài duy nhất, do đó, thay vì chia cuốn sách thành hai nửa và mua hai hộp văn phòng bài. Trong ô đầu tiên, bà đặt một nửa đầu tiên của cuốn sách và một chìa khóa để vào ô thứ hai, và trong hộp thứ hai, cô đặt một nửa thứ hai của cuốn sách. Bà ta đưa cho Bob một chìa khóa để các hộp đầu tiên. Không có vấn đề lớn của cuốn sách, chương trình này có thể được mở rộng cho bất kỳ số lượng các hộp bằng cách luôn luôn đặt chìa khóa vào hộp tiếp theo trong hộp trước.
Trong tương tự này, các ô tương ứng với các yếu tố hoặc các nút, các phím tương ứng để con trỏ, và chính cuốn sách là các dữ liệu. Chìa khóa cho Bob là con trỏ đầu, trong khi những người được lưu trữ trong các hộp là con trỏ tiếp theo. Đề án như mô tả ở trên là một danh sách đơn lẻ liên kết (xem dưới đây). 




Các lọai DSLK:
 Danh sách vòng tròn :Trong các nút cuối cùng của một danh sách, các lĩnh vực liên kết thường có chứa một tham chiếu null, một giá trị đặc biệt được sử dụng để chỉ ra thiếu các nút tiếp tục. Một quy ước ít phổ biến hơn là để làm cho nó trỏ đến nút đầu tiên của danh sách, trong trường hợp đó, danh sách được cho là tròn hoặc tròn liên kết, nếu không nó được cho là cởi mở hay tuyến tính.

 Danh sách liên kết đơn: Danh sách đơn lẻ liên kết có chứa các nút có một trường dữ liệu cũng như các lĩnh vực tiếp theo, mà chỉ vào nút tiếp theo trong danh sách liên kết.
 Danh sách liên kết kép : trong một danh sách liên kết kép , mỗi nút chứa, bên cạnh các liên kết nút tiếp theo, một  liên kết thứ hai trỏ đến nút trước đó trong chuỗi. Hai liên kết có thể được gọi là phía trước (s) và sau, hoặc tiếp theo và trước (ious).



Xem Nhiều

Bài đăng phổ biến

Lưu trữ blog

Blog Archive