Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: STACK & QUEUE Dùng Mảng 1 Chiều !

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định STACK & QUEUE Dùng Mảng 1 Chiều !

    Bài viết này của kidkid không biết có được gọi là tut không nữa ? Lần đầu tiên viết tut về C/C++ , do đó có chi mọi người cứ góp ý .
    Hiện nay đối với phần lớn SV năm I như kidkid thì phần lớn anh em chưa được học Danh Sách Liên Kết (DSLK) do đó mặc dù vẫn hay nghe đến những tên gọi rất quen thuộc như Stack (Ngăn Xếp ) và Queue (Hàm đợi ) vẫn chưa thể cài đặt được nó .
    Tất nhiên trong các mục ebook thì vẫn nói rất nhiều về vấn đề này , nhưng phần lớn vẫn dành sự ưu ái cho những ai đã biết qua CTDL , hôm nay kidkid viết 1 bài hoàn toàn mới về cách cài đặt Stack và Queue sử dụng những kiến thức đúng với tên gọi của “Box C/C++ cơ bản “ .

    1. Cài đặt Stack sử dụng C và mảng một chiều :

    Đầu tiên kidkid xin được nói sơ qua về Stack mặc dù các bạn ít nhiều đã biết về nó . Stack là một cấu trúc có nhiều nút như một list vậy , tuy nhiên chúng ta chỉ có thể thêm vào hoặc lấy ra 1 nút tại đỉnh của nó ! Kidkid lấy ví dụ thế này , khi chúng ta nạp đạn ,viên nạp đạn cuối cùng sẽ là viên được bắn trước tiên còn viên nạp đầu tiên sẽ được bắn cuối cùng như vậy chúng ta sẽ tóm là 1 câu là Vào Trước Ra Sau hay Last In First Out . ( Xem Hình )



    Bây giờ chúng ta xem buồng đạn này như 1 stack . mỗi viên đạn nạp vào là 1 nút .
    Như vậy để biết tổng số viên đạn có thể nạp vào chúng ta sẽ có một biến tên là MAX (ở đây MAX=6) , tốt rồi bây giờ để biết số đạn hiện có chúng ta sẽ dùng một biến TOP . Mỗi lần nạp đạn ta phải nạp từng viên một do đó để nạp một viên chúng ta phải biết được là buồng đạn này đầy chưa ! Có nghĩa là nếu TOP =MAX thì buồng đạn đầy và TOP = 0 thì buồng đạn rỗng (nhưng vì đặc điểm riêng của mảng 1 chiều với chỉ số từ 0 đến n-1 nên stack đầy khi TOP +1 = MAX , và rỗng khi TOP = -1 ) . Bây giờ để nạp đạn thì chúng ta phải kiểm tra thử là buồng đạn đã đầy chưa nếu chưa thì nhận vào một viên và tăng TOP lên 1 giá trị . Để loại bỏ 1 viên đạn ra ngoài thì chúng ta phải kiểm tra xem thử là có còn đạn không ( hay là buồng đạn không rỗng ) nếu thỏa thì ta loại ra 1 viên và hạ TOP xuống .

    Như vậy để cài đặt 1 stack thường thì chúng ta có các hàm cơ bản để thực hiện yêu cầu như sau :
    1. Hàm dùng để khởi động cho 1 stack , với giá trị TOP = -1 . Cái này ta có thể để trong main()
    2. Hàm dùng để kiểm tra stack có bị rỗng không ? (TOP = -1 )
    3. Hàm dùng để kiểm tra stack có bị đầy không ? ( TOP +1 = MAX)
    4. Hàm dùng để đặt vào 1 nút cho stack nếu stack chưa bị đầy !
    5. Hàm dùng để loại bỏ 1 nút nếu stack không rỗng !
    6. Hàm dùng để truy xuất thông tin của một nút nếu stack không rỗng .

    Trong các ebook mà kidkid đọc được thì phần lớn người ta viết các hàm kiểm tra stack có bị rỗng hay đầy riêng rồi truyền đối vào ? Tuy nhiên theo kidkid nghĩ thì với cách viết sử dụng mảng một chiều như chúng ta thì nên kiểm tra trực tiếp trong hàm đặt vào và loại ra luôn !

    Dưới đây là code kidkid đã viết cho các bạn ! Phân tích cho kĩ nha !

    C++ Code:
    1. // stack setup by C that use struct and one way array !
    2. #include "stdafx.h"
    3. #include "stdio.h"
    4. #define MAX 10
    5.  
    6. typedef struct
    7. {            
    8.              char Name[30];
    9.              int age;
    10. }IMFORMATION;
    11. typedef struct
    12. {   int top;               
    13.     IMFORMATION node[MAX];
    14. }STACK;
    15.  
    16. //---------------------------------- declae these funtion that were used in program.
    17.  
    18. void InputData(IMFORMATION &data)
    19. {
    20.     puts("Hi ! What student's name");
    21.     gets(data.Name);
    22.     puts("How old is student");
    23.     scanf("%d",&data.age);
    24.     fflush(stdin);
    25. }
    26.  // this funtion use for receive a node
    27. //  if stacks don't full
    28. void push(STACK &s)
    29. {
    30.     if(s.top == MAX)        // check stack is full or not
    31.     { printf("Stack over flow !");
    32.       return ;
    33.     }
    34.     printf("Student nume %d",s.top+2);
    35.     InputData(s.node[++s.top]); // set up data student to next node
    36. }
    37.  
    38. void pop(STACK &s)          // Deletion a node
    39. {
    40.     if(s.top == -1 )        // check stack is empty or not
    41.     {
    42.         puts("Stack under flow !");
    43.         return ;
    44.     }
    45.     --s.top;
    46. }
    47.  
    48. void stacktop(STACK  &s)
    49. {
    50.     if(s.top == -1 )        // check stack is empty or not
    51.     {
    52.         puts("Stack under flow !");
    53.         return ;
    54.     }
    55.    
    56.     printf("Student number %d\n",s.top);
    57.     puts(s.node[s.top].Name);
    58.     printf("%d\n",s.node[s.top].age);
    59. }
    60. int main(int argc, char* argv[])
    61. {
    62.  
    63.     //  to start for stack
    64.     STACK s;        //  make a statement a s variable of STACK struct ;
    65.     s.top = -1 ;    //  top=1 same as stack is empty .
    66.    
    67.     push(s);
    68.     stacktop(s);
    69.     pop(s);
    70.     pop(s);
    71.  
    72.     return 0;
    73. }
    Tất nhiên code trên về một khía cạnh nào đó thì không được hay lắm . Ví dụ như nếu tui muốn nhập vào nut thứ 11 thì sao ? Cũng như mọi người kidkid cũng suy nghĩ đắn đo lắm để trả lời câu hỏi này và cuối cùng cũng đã tìm ra bằng cách cấp phát thêm cho mảng như chính những gì DSLK đã làm . Tất nhiên là khi chạy vẫn tuyệt như DSLK vậy , mặc dù nó không được phổ biến vì không phải là cách chính qui nhưng kidkid tin rằng dù sao đó vẫn là 1 điều quí báu . Do đó kidkid để dành điều quí báu ấy lại cho chính các bạn đó . Hãy khám phá nào !

    Trong bài tiếp theo kidkid sẽ giới thiệu với các bạn về queue còn bi giờ thì ngủ đã . Chúc các bạn của kidkid học tốt !
    Đã được chỉnh sửa lần cuối bởi iamvtn : 16-11-2007 lúc 12:56 AM.

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    list, stack, queue viết bằng array là 1 kỹ thuật cao cấp chứ không phải thông thường đâu nha, gọi là contiguous list, stack, queue

    kiểu hiện thực này có khá nhiều ưu điểm hơn linked list hay linked stack, queue

    Nếu bạn làm được contiguous list thì rất tốt đấy, vì nó khá phức tạp.
    Khuyết điểm tệ nhất của linked list là vấn đề sort (sắp xếp) - bạn chỉ có thể làm tuần tự, các giải thuật sort khác cũng không hiệu quả trên linked list (trên linked list thì quicksort cũng xêm xêm với sort tuần tự - đây là đánh giá của riêng mình)

    contiguous list không bị khuyết điểm đó, vì là mảng cho nên có thể sử dụng quicksort nhanh nhất, mà bạn biết đấy quicksort thì đã có sẵn trong thư viện chuẩn. Và hàm quicksort có sẵn này làm việc được trên contiguous list mà không chịu làm việc trên linkedlist

    Và nhiều ưu điểm khác.

    Stack, queue cũng vậy
    Khuyết điểm của dạng contiguous này là hiện thực phức tạp, không tự động allocate memory (cái này thì có thể khắc phuc, và cũng dễ xử lý)
    Đã được chỉnh sửa lần cuối bởi nguyentuan2 : 02-05-2007 lúc 05:08 PM.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Thưa bác Nguyễn Tuân ( Bác bay vào vũ trụ nên kiến thức có khác thông tuệ quá ) . Dạ kidkid em không biết cái contiguous list nó ra làm sao ? Cái stack for array đó là do bác Neverland thách em nên em tự viết ra chứ không thuộc một cái cơ sở nào để gọi là bài bản cả ? kidkid đã thử chạy và thấy hiệu quả vẫn tốt như thường ? Có thể sắp xếp trên stack kiểu này ? Có thể chèn và tìm kiếm rất tốt ! Cũng có thể mở rộng theo kiểu không giới hạn như trong DSLK ? Tất nhiên là điều này nếu anh em thích thì có thể giới thiệu sau nhưng trong vấn đề căn bản thì như thế là được rồi ? Còn về cái contigous list gì đó thì kidkid mới nghe lần đầu ? Dịch theo từ điển cùi bắp là danh sách kề không biết nó ra sao ? sẽ nghiên cứu và post lên để anh em ta cùng tham khảo thế nào ?

  4. #4
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Bạn tham khảo contiguous list ở:
    Chapter 6 of
    "Data Structures and Program Design in C++"
    by Robert L. Kruse and Alexander J. Ryba
    Copyright (C) 1999 by Prentice-Hall
    Sample code:
    contiguous list sample implementation code

    Stack, queue cũng tương tự như thế
    Đã được chỉnh sửa lần cuối bởi nguyentuan2 : 02-05-2007 lúc 06:43 PM.

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Hix cảm ơn tấm lòng của bác NT nhưng em mở ra là choáng rồi ? Tiếng anh ? Trời ơi ! Đó là nỗi đau đớn nhất của đời em ? < spam thôi rồi em xóa > đừng trách .

  6. #6
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Mặc định Ứng dụng của stack

    stack ứng dụng be bé

    C++ Code:
    1. #include<iostream.h>
    2. #include<conio.h>
    3. #include<STDLIB.H>
    4. //////////////////////////////////////////
    5. typedef int Datatype;
    6. //////////////////////////////////////////
    7. typedef struct TagNode
    8. {
    9.     Datatype data;
    10.     struct TagNode *pNext;
    11. }StackNode;
    12. //////////////////////////////////////////
    13. typedef StackNode *StackPtr;
    14. //////////////////////////////////////////
    15. void initStack(StackPtr &sp)
    16. {
    17.     sp=NULL;
    18. }
    19. //////////////////////////////////////////
    20. bool isEmpty(StackPtr sp)
    21. {
    22.     return sp==NULL;
    23. }
    24. //////////////////////////////////////////
    25. void push(StackPtr &sp,Datatype data)
    26. {
    27.     StackPtr p= new StackNode;
    28.     if(p==NULL)
    29.     {
    30.         cout<<"Stack is Full !!"<<endl;
    31.         getch();
    32.         exit(1);
    33.     }
    34.     p->data=data;
    35.     p->pNext=NULL;
    36.     if(sp==NULL)
    37.         sp=p;
    38.     else
    39.     {
    40.         p->pNext=sp;
    41.         sp=p;
    42.     }
    43. }
    44. //////////////////////////////////////////
    45. Datatype pop(StackPtr &sp)
    46. {
    47.     Datatype data;
    48.     if(isEmpty(sp))
    49.     {
    50.         cout<<"Stack is Empty"<<endl;
    51.         getch();
    52.         exit(1);
    53.     }
    54.     StackPtr p;
    55.     p=sp;
    56.     data=sp->data;
    57.     sp=p->pNext;
    58.     delete p;
    59.     return data;
    60. }
    61. ///////////////////////////////////////////
    62. void convert(int n,int b)
    63. {
    64.     Datatype temp;
    65.     StackPtr sp;
    66.     initStack(sp);
    67.     while(n)
    68.     {
    69.         push(sp,n%b);
    70.         n/=b;
    71.     }
    72.     while(!isEmpty(sp))
    73.     {
    74.         temp=pop(sp);
    75.         if(temp==10) cout<<"A";
    76.             else if(temp==11) cout<<"B";
    77.                 else if(temp==12) cout<<"C";
    78.                     else if(temp==13) cout<<"D";
    79.                         else if(temp==14) cout<<"E";
    80.                             else if(temp==15) cout<<"F";
    81.         else cout<<temp;
    82.     }
    83.     cout<<endl;
    84. }
    85. ///////////////////////////////////////////
    86. int giaiThua(int n)
    87. {
    88.     int  gt=1;
    89.     int temp=1;
    90.     StackPtr sp;
    91.     initStack(sp);
    92.     while(n)
    93.     {
    94.         push(sp,n);
    95.         n=n-1;
    96.     }
    97.     while(isEmpty(sp))
    98.     {
    99.         gt=gt*pop(sp);
    100.     }
    101.     return gt;
    102. }
    103. //////////////////////////////////////////
    104. int main()
    105. {
    106.     cout<<"doi tu he 10 sang he 2."<<endl;
    107.     cout<<"nhap so can doi n:=";
    108.     int n;
    109.     cin>>n;
    110.     cout<<"ket Qua      :";
    111.     convert(n,2);
    112.     cout<<"doi tu he 10 sang 16"<<endl;
    113.     cout<<"nhap so can doi n:=";
    114.     cin>>n;
    115.     cout<<"ket Qua     ";
    116.     convert(n,16);
    117.     cout<<"Tinh giai thua"<<endl;
    118.     cout<<"nhap n:=";
    119.     cin>>n;
    120.     cout<<"ket qua: = "<<giaiThua(n)<<endl;
    121.     return 0;
    122. }
    Cái danh sách kề dùng để lưu đồ thị thì phải? bảng băm nữa nhỉ? ai hiện thực cái đó chưa? em xin cái code!!

  7. #7
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Danh sách kề thường dùng để lưu đồ thị dạng Forward Start, có 2 kiểu cài đặt, một kiểu dùng Linked List, một kiểu dùng mảng thông thường, bạn muốn sử dụng kiểu nào, mình viết code cho.

  8. #8
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Viết đi roài post lên đây luôn nhá!! Nhưng mình ko hiểu đồ thị dạng Forward Start là j`. Dùng linked list đi!thanks!!

  9. #9
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Thực ra cách lưu trữ này dùng Linked List rất đơn giản, đơn thuần chỉ là danh sách các đỉnh kề của một đỉnh thôi
    C++ Code:
    1. #include <cstdio>
    2.  
    3. using namespace std;
    4.  
    5. /* Khai bao kieu Linked List */
    6. struct LIST {
    7.     long val;
    8.     LIST *next;
    9. };
    10. typedef LIST* LINKEDLIST;
    11.  
    12. /* Khai bao cac ham lam viec voi Linked List */
    13. /* Khoi tao danh sach */
    14. void initList(LINKEDLIST &list) {
    15.     list = NULL;
    16. }
    17. /* Them mot phan tu vao danh sach */
    18. void insertToList(long node, LINKEDLIST &list) {
    19.     LINKEDLIST p;
    20.     p = new LIST;
    21.     p->val = node;
    22.     p->next = list;
    23.     list = p;
    24. }
    25. /* Cac thu tuc con lai khong can thiet */
    26.  
    27. LINKEDLIST *a;
    28. long n;
    29.  
    30.     void makeFS(long n) {
    31.         a = new LINKEDLIST[n];
    32.         for (long i = 1; i <= n; i++) a[i] = NULL;
    33.     }
    34.  
    35.     void readInput() {
    36.         long x1, x2;
    37.        
    38.         /* Su dung tep input va output sau dau lam standard in/out */
    39.         freopen("GRAPH.INP", "r", stdin);
    40.         freopen("GRAPH.OUT", "w", stdout);
    41.        
    42.         /* Su dung doc du lieu theo chuan C
    43.            Vi se lam tang toc do chuong trinh  */
    44.         scanf("%ld", &n); /* Doc so dinh */
    45.         makeFS(n); /* Tao danh sach ke */
    46.         while (scanf("%ld%ld", &x1, &x2) != EOF) {
    47.             insertToList(x1, a[x2]);
    48.             insertToList(x2, a[x1]);
    49.         }
    50.     }
    51.    
    52.     void printList() {
    53.         long i, j;
    54.         LINKEDLIST p;
    55.         for (i = 1; i <= n; i++) {
    56.             printf("Cac dinh ke voi dinh %ld: ", i);
    57.             p = a[i];
    58.             if (!p) printf("Khong co dinh nao ca\n");
    59.             else {
    60.                 while (p) {
    61.                     printf("%ld ", p->val);
    62.                     p = p->next;
    63.                 }
    64.                 printf("\n");
    65.             }
    66.         }
    67.     }
    68.  
    69. int main()
    70. {
    71.     readInput();
    72.     printList();
    73.     return 0;
    74. }
    Cách cài đặt với mảng khéo léo hơn một chút, dùng mảng adj[] là mảng danh sách các đỉnh kề cộng thêm mảng head[] là mảng giới hạn xem phần đỉnh kề với đỉnh i thuộc đoạn nào của mang adj[]. Thông thường, các đỉnh kề với đỉnh i thuộc đoạn từ head[i-1] + 1 đến head[i].

  10. #10
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Mặc định Stack sử dụng Linklist

    Stack dùng DSLKD

    C++ Code:
    1. #include <time.h>
    2. #include <stdlib.h>
    3. typedef long KieuDL;
    4. typedef struct NUT
    5. {
    6.     struct NUT(long dl)
    7.     {
    8.         this->duLieu=dl;
    9.         this->tiep=NULL;
    10.     }
    11.     KieuDL duLieu;
    12.     struct NUT* tiep;
    13. }NUT;
    14.  
    15. class Stack
    16. {
    17.     private:
    18.         NUT *sp;
    19.     public:
    20.         Stack();
    21.         ~Stack();
    22.         void push(long);
    23.         //void push(NUT *);
    24.            long pop ();
    25.         //NUT* pop ();
    26.         void huyStack();
    27.         bool stackRong();
    28. };

    Hiện thực phương thức
    C++ Code:
    1. #include<iostream.h>
    2. #include<conio.h>
    3. #include <time.h>
    4. #include <stdlib.h>
    5. #include "ST.H"
    6. Stack::Stack()
    7. {
    8.     sp=NULL;
    9. }
    10. Stack::~Stack()
    11. {
    12.     huyStack();
    13. }
    14. bool Stack::stackRong()
    15. {
    16.     return (sp==NULL)?true:false;
    17. }
    18. void Stack::push(long dulieu)
    19. {
    20.     NUT *p=new NUT (dulieu);
    21.     if(sp==NULL)
    22.         sp=p;
    23.     else
    24.     {
    25.         p->tiep=sp;
    26.         sp=p;
    27.     }
    28. }
    29. /*
    30. ///push cho 1 nut
    31. void Stack::push(NUT *p)
    32. {
    33.     if(sp==NULL)
    34.         sp=p;
    35.     else
    36.     {
    37.         p->tiep=sp;
    38.         sp=p;
    39.     }
    40. }*/
    41. long Stack::pop ()
    42. {
    43.     long dulieu;
    44.     if(stackRong())
    45.         cout<<"Stack rong!"<<endl;
    46.     else
    47.     {
    48.         NUT *p=sp;
    49.         dulieu=sp->duLieu;
    50.         sp=sp->tiep;
    51.         delete p;
    52.         return dulieu;
    53.     }
    54. }
    55. /*
    56. NUT *Stack::pop()
    57. {
    58.     if(stackRong())
    59.     {
    60.         cout<<"Stack rong!"<<endl;
    61.     }
    62.     else
    63.     {
    64.         NUT *p=sp;
    65.         p->tiep=NULL;
    66.         sp=sp->tiep;
    67.         return p;
    68.     }
    69. }*/
    70. void Stack::huyStack()
    71. {
    72.     if(stackRong())
    73.         return;
    74.     while(sp!=NULL)
    75.     {
    76.         NUT *p;
    77.         p=sp;
    78.         sp=sp->tiep;
    79.         delete p;
    80.     }
    81. }
    Đã được chỉnh sửa lần cuối bởi soda_chanhmuoi : 28-05-2007 lúc 10:54 PM.

Các đề tài tương tự

  1. Giáo trình Stack và Queue, có code minh họa
    Gửi bởi vitbau1412 trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 8
    Bài viết cuối: 21-08-2013, 04:00 PM
  2. Xây dựng chương trình mô phỏng: Danh sách liên kết, stack, queue?
    Gửi bởi cherry0103 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 28-06-2012, 11:49 PM
  3. Bài tập stack & queue ai giúp với
    Gửi bởi conglam92 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 17-03-2012, 10:37 PM
  4. Danh sách bài tập C++ cơ bản về con trỏ, stack and queue
    Gửi bởi K9K trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 12-09-2011, 03:35 PM
  5. Duyệt đồ thị theo chiều sâu dùng stack (help me!!!)
    Gửi bởi rong3sao trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 03-02-2010, 10:09 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn