线性表、栈与队列

一、结构定义
  线性表有两种方式表示，这里说的是存储方式，包括连续的数组表示和链表表示两种。仅以链表表示为例。

  首先要定义结点类型，总的来说一个结点应该包括两个部分，指针域和数据域。

  struct _DNode
  {
    LPVOID data;/*数据域*/
    LPVOID link;/*指针域*/
  };

  指针域很简单无非是前趋指针和后继指针，但数据域却是不定的，我们对这个链表的要求是要有高适应性，所以应该做一个开放的数据域，就用一个空指针表示吧。于是修改成：

  struct _DNode
  {
    LPVOID data;/*数据域*/
    LPVOID pre;
    LPVOID next;
  };

  这里我提倡一种习惯，就是善于使用宏。在C语言里宏是个非常好的工具，它帮助我们更好的书写代码。常用的方法就是用#define和typedef。

  严格来说只有#define是宏定义，但typedef我们可以看成是宏（别名），它可以更灵活的使用。

  在上面代码之前，添加

  typedef void far *LPVOID;
  typedef struct _DNode DNode;
  typedef DNode *LPDNode;

  于是结构体也可以再修改为

  struct _DNode
  {
    LPVOID data;/*数据域*/
    LPDNode pre;
    LPDNode next;
  };

  有了结点类型，就可以定义链表类型了。

  struct _DList
  {
    LPDNode head,tail;/*指向链表的头和尾，头表示第一个元素*/
    DWORD length;/*结点的个数*/
  };

  其中DWORD是双字，即32位长的数据类型，可以宏定义为typedef unsigned long DWORD;

  同样的在前面再加上它的宏名

  typedef struct _DList DList;
  typedef DList *LPDList;

  今后我们定义数据的时候都将直接使用这些宏名。用它的好处会在以后体会到的。

  OK，到这里顶点集定义完毕，我们要定义它们的边集，也就是常用操作。

二、常用操作
  线性表的操作想一想需要哪此，查找、插入、删除，另外还包括整个线性表的初始化和最后的销毁。全部操作列在下面

  BOOL InitList(LPDList *pl);/*初始化*/
  BOOL DestroyList(LPDList pl);/*销毁*/
  LPVOID GetElem(LPDList pl,int index,BOOL fromtail);/*查找*/
  BOOL ListInsert(LPVOID data,LPDList pl,int index,BOOL fromtail);/*插入*/
  BOOL ListDelete(LPDList pl,int index,BOOL fromtail);/*删除*/

  除了这些基本操作之外，还有一些很常用的

  BOOL ClearList(LPDList pl);/*清空链表*/
  DWORD ListLength(LPDList pl);/*返回链表长*/
  BOOL ListEmpty(LPDList pl);/*判断是否为空*/

  当然前面有宏名定义
  typedef int BOOL;
  #define TRUE 1
  #define FALSE 0

  以上这些定义和申明全部放在一个MyList.h文件中，然后在对应的MyList.c中写这些操作的实现代码。

  #include "MyList.h"
  #include "malloc.h"
  #include "assert.h"
  BOOL InitList(LPDList *pl)
  {
    (*pl)=(LPDList)malloc(sizeof(DList));
    if((*pl)==NULL)return FALSE;
    (*pl)->head=(*pl)->tail=NULL;
    (*pl)->length=0;
    return TRUE;
  }
  BOOL DestroyList(LPDList pl)
  {
    LPDNode p=pl->head,q;
    while(p!=NULL)
    {
       q=p;
       p=p->next;
       free(q);
    }
    free(pl);
  }
  LPVOID GetElem(LPDList pl,int index,BOOL fromtail)/*fromtail表示是否从尾部开始*/
  {
    LPDNode p;
    if(index<0||index>=pl->length)return NULL;
    if(fromtail)
    {
      p=pl->tail;
      while(index--)p=p->pre;
    }
    else
    {
      p=pl->head;
      while(index--)p=p->next;
    }
    return p->data;
  }
  BOOL ListInsert(LPVOID data,LPDList pl,DWORD index,BOOL fromtail)
  {
    LPDNode p,q;
    if(pl->length==0)
    {
      q=pl->head=pl->tail=(LPDNode)malloc(sizeof(DNode));
      q->next=q->pre=NULL;
      q->data=data;
      pl->length++;
      return TRUE;
    }
    if(index>=pl->length)return FALSE;
    q=(LPDNode)malloc(sizeof(DNode));
    q->data=data;
    if(fromtail)
    {
      p=pl->tail;
      while(index--)p=p->pre;
      q->pre=p;
      q->next=p->next;
      if(p->next)
        p->next->pre=q;
      else
        pl->tail=q;
      p->next=q;
    }
    else
    {
      p=pl->head;
      while(index--)p=p->next;
      q->next=p;
      q->pre=p->pre;
      if(p->pre!=NULL)
        p->pre->next=q;
      else
        pl->head=q;
      p->pre=q;
    }
    pl->length++;
    return TRUE;
  }
  BOOL ListDelete(LPDList pl,DWORD index,BOOL fromtail)
  {
    LPDNode p;
    if(index>=pl->length)return FALSE;
    if(fromtail)
    {
      p=pl->tail;
      while(index--)p=p->pre;
    }
    else
    {
      p=pl->head;
      while(index--)p=p->next;
    }
    if(p->pre)
      p->pre->next=p->next;
    else
      pl->head=p->next;
    if(p->next)
      p->next->pre=p->pre;
    else
      pl->tail=p->pre;
    free(p);
    pl->length--;
    return TRUE;
  }

  有了这些定义，就可以方便的操作链表了。

  其它操作
  BOOL ClearList(LPDList pl)
  {
    while(ListDelete(pl,0,FALSE));
    return pl->length==0;
  }
  最后两个完全用宏定义了：
  #define ListLength(pl) (pl->length)
  #define ListEmpty(pl) (pl->length==0)

  到这里就全部完成了。

三、栈与队列
  从本质上看，栈与队列都是线性表，所以没有必要再定义栈和队列，老规矩用宏。

  typedef DList DStack;
  typedef DList *LPDStack;
  typedef DList DQueue;
  typedef DList *LPDQueue;

  所谓栈，就是LIFO，后进先出，它的操作类似的有：
  #define InitStack(ps) InitList(ps)
  #define DestroyStack(ps) DestroyList(ps)
  #define GetTop(ps) GetItem(ps,0,FALSE)
  #define Push(ps) ListInsert(ps,0,FALSE)
  #define Pop(ps,e) ((e=GetItem(ps,0,FALSE)),ListDelete(ps,0,FALSE))

  此外还有
  #define StackLength(ps) ListLength(ps)
  #define StackEmpty(ps) ListEmpty(ps)
  #define ClearStack(ps) ClearList(ps)

  其中用得多的是Push(ps)，压栈，和Pop(ps,e)弹栈。

  所谓队列，就是FIFO，先进先出，它的操作类似的有：
  #define InitQueue(pq) InitList(pq)
  #define DestroyQueue(pq) DestroyList(pq)
  #define GetHead(pq) GetItem(pq,0,FALSE)
  #define EnQueue(pq,e) ListInsert(e,pq,0,TRUE)
  #define DeQueue(pq,e) ((e=GetItem(pq,0,FALSE)),ListDelete(pq,0,FALSE))

  类似的还有
  #define QueueLength(pq) ListLength(pq)
  #define QueueEmpty(pq) ListEmpty(pq)
  #define ClearQueue(pq) ClearList(pq)

  其中用得多的是EnQueue(pq,e)，入队，和DeQueue(pq,e)出队。