データ構造:第3章学習まとめ

1.内容のまとめ:
スタック(FILO)とキュー(FIFO)は、「エンドポイント」に限定された線形テーブルを挿入して削除し、順序記憶構造とチェーン記憶構造があります.
1.1スタック:
スタックの実現と基本操作:

 1    ： 
 2 #define MAXSIZE 100//            
 3 typedef struct{
 4     SElemType *base;//    
 5     SElemType *top; //    
 6     int stacksize;  //         
 7 }SqStack;
 8 
 9 Status InitStack(SqStack &s){
10     s.base = new SElemType[MAXSIZE];//            
11     if(!s.base)        exit(OVERFLOW);     //         
12     s.top = s.base;                  //top    base,   
13     s.stacksize = MAXSIZE;             //stacksize         
14     return OK; 
15 } 16 17 Status Push(SqStack &s, SElemType e){ 18 if(s.top - s.base == s.stacksize){//   19 return ERROR; 20  } 21 *s.top++ = e; //e（ ）  ，（ ）     1 22 return OK; 23 } 24 25 Status Pop(SqStack &s, SElemType &e){ 26 if(s.top == s.base){ //   27 return ERROR; 28  } 29 e = *--s.top; //    （ ） 1，( )       e 30 } 31 32 33   ： 34 typedef struct StackNode{ 35  ElemType data; 36 StackNode *next; 37 }StackNode, *LinkStack; 38 39 Status InitStack(LinkStack &s){//      40 s = NULL; 41 return OK; 42 } 43 44 Status Push(LinkStack &s, SElemType e){//    FILO   ，            ,         45 StackNode *p = new StackNode; 46 p -> data = e; 47 p ->next = s; 48 s = p; 49 return OK; 50 } 51 52 Status Pop(LinkStack &s, SElemType &e){ 53 if(s == NULL) return ERROR;//   54 e = s -> data; 55 StackNode *temp = s; 56 s = s -> next; 57 delete temp; //          58 return OK; 59 } 

スタックの適用:
スタックの応用はたくさんあります.ここで言うのは再帰です.
スタックと再帰を利用して、以下の3つの問題を解決できます.

定義は再帰的であり、例えば、Fibonacci数列を印刷し、nの階乗を印刷する.

データ構造は再帰的であり、本章で学んだようなスタック及び後に学ぶ広義表である.

問題の解法は再帰的なもので、例えばハノイタワー問題です.

再帰的な利点は十分に、ロジックが明確で、コードが簡潔です.しかし、再帰的には多くの時間と空間が消費され、時には計算を繰り返す問題がある.
1.2キュー
 
キューの実現と基本操作:

 1     ： 
 2 #define MAXSIZE 100                //          
 3 typedef struct{
 4     QElemType *base;            //         
 5     int front;                    //    
 6     int rear;                    //    
 7 }SqQueue; 
 8 
 9 Status IninQueue(SqQueue &q){    //       
10     q.base = new QElemType[MAXSIZE];
11     if(!q.base)        exit(OVERFLOW);        //         
12     q.front = q.rear = 0;                
13     return OK; 14 } 15 16 Status Enter(SqQueue &q, QElemtype e){ 17 if( (q.rear + 1) % MAXSIZE == q.front){//          1       18 return ERROR;//     19  } 20 q.base[q.rear] = e; //        21 q.rear = (q.rear + 1) % MAXSIZE; //     1 22 return OK; 23 } 24 25 Status Exit(SqQueue &q, QElemtype &e){ 26 if(q.front == q.rear) return ERROR;//   27 e = q.base[q.front]; 28 q.front = (q.front + 1) % MAXSIZE;//     1 29 return OK; 30 } 31 32     ： 33 typedef struct QNode{ 34  QElemType data; 35 struct QNode *next; 36 }QNode; 37 typedef struct{ 38 QNode *front; //     39 QNode *rear; //     40 }LinkQueue; 41 42 Status InitQueue(LinkQueue &q){ 43 q.front = q.rear = new QNode; //            44 q.front -> next = NULL; 45 return OK; 46 } 47 48 Status Enter(LinkQueue &q, QElemType e){ 49 QNode *p = new QNode; 50 p -> data = e; 51 p -> next = NULL; 52 q.rear -> next = p; //           53 q.rear = p;//      54 return OK; 55 } 56 57 Status Exit(LinkQueue &q, QElemType &e){ 58 if(q.front == q.rear) return ERROR;//   59 QNode *p = q.front -> next; //p       60 e = p -> data; 61 q.front -> next = p -> next; //          62 if(q.rear == p) q.rear = q.front; //           ，      63 delete p; 64 return OK; 65 } 

2.心得:
問題を完成したら、時間と空間に対する考えを重視しなければなりません.時には問題が提示されなくても、ちょっとした工夫で時間と空間を節約することができます.
3.資料の紹介:
基礎的な知識は教科書を見てもいいし、コミュニティやウェブサイトを見てもいいです.
4.前段階の完成状況とその後の目標:
前の段階の目標はこの章をマスターするので、基本的に完成して、足りないのは再帰に対してまだ熟知していません.
後続の目標はもちろん第四章をマスターすることです.