第二章：线性表、栈和队列

2.1、设计一个算法，求单链表X中，内容为a的结点的地址

注意:内容为a的结点可能有多个

算法实现：

struct listNode{

      T data;

      struct listNOde *next;

}

 

struct dataAddress{

      struct listNode *address;

      struct dataAddress *next;

}

 

void search(T a; struct listNode *head){

      struct listNode *p = head;

      struct listAddress *q = NULL;

     

      while(p != NULL){

           if(a == p->data){

                 q->next->address = p;

                 q = q->next;

                 q->next = NULL;

           }

           p = p->next;

      }

}

2.3、单链表置逆

struct listNode{

      T data;

      struct listNode *next;

}

 

struct listNode

reverse(struct listNode *X){

      struct listNode *p,*q;

      p = X->next;

      q = p->next;

 

      while(p != NULL && q != NULL){

           p->next = q->next;

           q->next = X->next;

           X->next = q;

           q = p->next;

      }

      return X;

}

 

 

2.13、将Fibonacci序列的递归过程改写成非递归过程

 思路:

   if n > 2 入栈。栈里包含以下内容：flags表示f（n-1）和f（n-2）是否完成（1表示完成，0表示没有完成），n表示当前n的值，f表示f（n-1）和f（n-2）的和，f1表示f（n-1），f2表示f（n-2）。

   当n == 2时，一次出栈，并计算f的值，将flags置1；

 

2.17、模拟“迷宫问题”：数组元素1表示死路，0表示通路MAZE(1,1)为入口，MAZE(m,n)为出口

int maze[m+1][n+1];

int cx[m*n+1];//当前路径

int cy[m*n+1];

 

void Maze(int step, int x, int y){

     int i;

     cx[step] = x;cy[step] = y;

     if(m == x && n == y){

          for (i = 1; i <= step; i++)

              打印cx[i]与cy[i];

          return;

     }

     for(i = 0; i < 4; i++){

          int nx = x + dx[i];

          int ny = y + dy[i];

          if(0 == maze[nx][ny]               

                && x >= 1 && x <= m           

                && y >= 1 && y <= n)

          Maze(step +1, nx, ny);

     }

}