Bài 12-Cài đặt danh sách kề bằng mảng

Cho cau truc du lieu cua mot danh sach ke nhu sau:

struct danh_sach {

                          int a[MAX +1];

                          int last;     // So phan tu cua danh sach

                          };

typedef struct danh_sach DS;

 

Viet chuong trinh  thuc hien cac nhiem vu sau:

 

1.Tao danh sach rong

2. Nhap cac phan tu cho danh sach     

3. In toan bo cac phan tu cho danh sach     

4. Chen mot phan tu moi vao vi tri thu p cua danh sach

5. Xoa mot phan tu o vi tri thu p cua danh sach 6. Xoa cac phan tu co gia tri bang x ra hoi danh sach

7. Ket thuc chuong trinh

#include<stdio.h>

#include<conio.h>

#define MAX 100

struct danh_sach {

                          int a[MAX +1];

                          int last;     // So phan tu cua danh sach

                          };

typedef struct danh_sach DS;

/* PHAN KHAI BAO NGUYEN MAU CAC HAM */

void tao_rong(DS *d);       // Lam rong danh sach

void nhap_ds(DS *d);       // Nhap danh sach

void in_ds(DS ds);

void chen(DS *d,int x,int p);  // ham nay se chen 1 so x vao danh sach ds1

                                           // sau khi ket thuc ham thi so phan tu ( last)

                                           //se duoc tang len 1

void xoa(DS *d,int p);       // ham nay se xoa phan tu cua danh sach ds1

                                           // sau khi ket thuc ham thi so phan tu ( last)

                                           // se bi giam di 1

void   xoa_x(DS *d,int x); // Xoa tat ca cac phan tu co gia tri la x

/* HAM MAIN() */

void main()

{ clrscr();          DS  ds1;  // day la 1 bien kieu ban ghi, bien nay la 1 danh sach cac so nguyen

  char tl; // bien nhan 1 ky tu la cau tra loi

  int stop =0;  clrscr();  int giatri, p,x;  // gia tri can chen, vi tri chen la p

       do{  clrscr();

      printf("\n1. Tao danh sach rong ");

      printf("\n2. Nhap cac phan tu cho danh sach");

      printf("\n3. In toan bo cac phan tu cho danh sach");

      printf("\n4. Chen mot phan tu moi vao vi tri thu p cua danh sach");

      printf("\n5. Xoa mot phan tu o vi tri thu p cua danh sach");

      printf("\n6. Xoa cac phan tu co gia tri bang x ra khoi danh sach");

      printf("\n7. Ket thuc chuong trinh");

 tl = getch();  // doi nhan 1 cau tra loi la chon 1 muc tu 1-6

  switch(tl)

             {

              case '1': tao_rong(&ds1);break;

              case '2': nhap_ds(&ds1); getch(); break;

              case '3': in_ds(ds1);    getch(); break;

              case '4': in_ds(ds1);    // hien thi danh sach de xem truoc khi chen

                            printf("\n\nBan nhap 1 gia tri de chen vao danh sach giatri:");

                            scanf("%d",&giatri);

                            printf("\nHien tai danh sach co %d phan tu\n",ds1.last);

                            printf("Ban nhap vi tri chen p:",ds1.last);

                            scanf("%d",&p);

                            chen(&ds1,giatri,p);

                            in_ds(ds1);              // sau khi chen ta hien thi xem ket qua

                            getch(); break;

              case '5':in_ds(ds1);  // hien thi de xem xoa phan tu nao

                           printf("\n\nBan muon xoa phan tu thu may p:");

                           scanf("%d",&p);

                           xoa(&ds1, p);

                           in_ds(ds1);  // hien thi danh sach sau khi 1 phan tu bi xoa

                           getch(); break;

              case '6':in_ds(ds1);

                           printf("\n\nBan muon xoa phan tu co gia tri la x =");

                           scanf("%d",&x);

                           xoa_x(&ds1,x);

                           in_ds(ds1); getch();             break;

              case '7': stop = 1;                  // dau hieu ket thuc chuong trinh khi stop =1

             }

          }while( !stop);  // Neu stop =1 thi ket thuc chuong trinh

}

/* Phan noi dung cac ham, o day ta se viet cac ham ma da khai bao o tren  */

/*------------------------------------------------------------------------------------------------------------*/

void tao_rong(DS *d){ 

d->last=0;  printf("\n\n\nMot danh sach rong da duoc tao.....");  getch();

}

/*------------------------------------------------------------------------------------------------------------*/

void nhap_ds(DS *d)

{ int n,giatri;

  printf("\n\n\n Ban muon nhap bao nhieu phan tu:");

  scanf("%d",&n);

  d->last = n;

  for( int i=1; i <= d->last ; i++)

     {     printf("A[%d]:",i);    scanf ("%d",&giatri);

d->a[i] =giatri;                       // dua gia tri vua nhapvao phan tu thu i cua mang a

   }

  // hien thi cac phan tu vua nhap cho danh sach ma duoc tro boi con tro p

  if( d->last > 0 ){

                printf("\n\n\n\t\tCac phan tu vua nhap la: ");

                for(i=1; i <= d->last ; i++)

                printf("%4d",d->a[i]);

                }

  else  printf ("\n\nDanh sach rong");

}

/*------------------------------------------------------------------------------------------------------------*/

void in_ds(DS ds)

{

  if (ds.last > 0)  // danh sach khac rong

   { printf("\n\n\nCac phan tu cua danh sach:");

     for( int i=1; i <= ds.last ; i++)

             printf("%4d",ds.a[i]);

   }

   else  printf ("\n\nDanh sach rong");

}

/*------------------------------------------------------------------------------------------------------------*/

void chen(DS *d,int x,int p)

{

 /* dich chuyen cac phan tu tu phan tu cuoi den phan tu thu p cua mang

    a ve cuoi, roi chen s1 so x vao mang */

    for ( int i= d->last; i >= p; i--)   d->a[i+1] = d->a[i];

    d->last = d -> last+1;

     // tang so phan tu cua danh sach ma duoc troi bo con tro d len 1

     // chen so x vao vi tri p;

    d->a[p] =x;

}

/*------------------------------------------------------------------------------------------------------------*/

void   xoa(DS *d,int p)

{  int i;

  if( d->last >=1)

  {

for (i=p; i<=d->last; i++)   

d->a[i] =  d->a[i+1];   // phan tu truoc duoc gan bang phan tu sau

           

            // so phan tu giam di 1

            d->last= d->last -1;

   }

   else

            printf("\nKhong xoa duoc");

}

 

/*------------------------------------------------------------------------------------------------------------*/

void xoa_x(DS *d,int x)

{

  int dem=0;     // neu co x trong danh sach thi dem se tang len

  int j, i=1;       // j la bien luu vi tri cua I khi ma tim thay 1 phan tu co gia tri la x

  while ( i<=d->last)

   {

     if(  d->a[i]==x ) {j=i;                                // luu lai vi tri cua i

                                    xoa(d,i);                      // xoa phan tu thu i vi a[i] = x, goi ham xoa o tren

dem= dem +1;            // Them 1 phan tu bi xoa

                                    i=j;                              // lay lai vi tri i tra ve i

                               }

     else   i++;

   }

  if( dem > 0) printf ("\n\nDa xoa %d phan tu co gia tri la %d",dem,x);

  else        printf ("\n\nKhong tim thay phan tu %d trong danh sach.",x);

}

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI