数据结构与算法分析学习笔记(2)

表、栈、和队列

对于Node点的定义

 1 #ifdef _List_H
 2 struct Node;
 3 typedef struct Node *PtrToNode;
 4 typedef PtrToNode List;
 5 typedef PtrToNode Position;
 6 List MakeEmpty(List L);
 7 int IsEmpty(List L);
 8 int IsLast(Position P ,List L);
 9 Position Find (ElementType X,List L);
10 void Delete(ElementType X,List L);
11 Position FindPrevious(ElementType X,List L);
12 void Insert(ElementType X,List L,Position p);
13 void DeleteList(List L);
14 Position Header(List L);
15 Position First(List L);
16 Position Advance(Position P);
17 ElementType Retrieve(Position P);
18 #endif
19 
20 struct Node
21 {
22       ElementType Element；
23      Positon         next；
24 }；

单链表函数实现：

测试链表是否为空

1 int IsEmpty（List L）
2 {
3      return L->ext==NULL;
4 }

测试链表是不是末尾

1 int IsLast（Position P，list L）
2 {
3       return P->next==NULL;
4 }

查找元素

1 Position Find( ElementType X,List L)
2 {
3         Position p;
4         p=L->next;
5         while (p!=NULL&&p->Element!=X)
6                  p=p->next;
7          return p;
8  
9 }

链表的删除

void Delete (ElementeType X,List L)
{
      Position p,Temp;
      p=FindPrevious(X,L);
      if(!IsLast(p,L))
        {
            Temp=p->next;
            p->next=Temp->next;
            free(Temp);
        }  
}

1 Position FindPrevious(ElementType X,List L)
2 {
3    Position p;
4    p=L;
5    while(p->next!=NULL&&p->next->Element!=X)
6           p=p->next;
7 }

链表的插入

 1 void Insert(ElementType X, List L,Position p)
 2 {
 3      Positon pTemp;
 4      pTemp=malloc(siziof(struct Node));
 5      if(pTemp==NULL)
 6        printf("erro");
 7      pTemp->element=X;
 8      pTemp->next=p->next;
 9      p->next=pTemp;
10 }

完全删除一个表

void DeleteList(List L)
{
    Position p, pTmp;
    p=L->next;
    L->next=NULL;
    while(p!=NULL)
       {
           pTmp=p->next;
           free(p);
          p=pTmp;
        }
}

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

典型例子

利用数组实现多项式

 1 typedef struct
 2 {
 3           int CoeffArray[MaxDegree+1];
 4           int HighPower;
 5 } * Ploynomial;
 6 
 7 void ZeroPolynomial(Polynomial poly)//初始化为0
 8 {
 9      int i;
10      for(i=0;i<=Maxdegree;i++)
11          poly->CoeffArray[i];
12          poly->highPower=0;
13 }
14 //多项式相加
15 void AddPolynomial(const Polynomial poly1,const Polynomial poly2,Polynomial polySum)
16 {
17       int i；
18      ZeroPolynomial（PolySum）;
19       polySum->HighPower=Max( poly1,poly2);
20       for(i=poly->HighPower;i>=0;i--)
21           ploySUm->CoeffArray[i]=poly1->CoeffArray[i]+poly2->CoeffArray[i];
22 }
23 //多项式相乘
24 void MultPolynomial(const Polynomial poly1,const Polynomial poly2,Polynomial polyProd)
25 {
26         int i，j;
27         ZeroPolynomial(polyProd);
28         polyProd->HighPower=poly1->HighPower+poly2->HighPower;
29          if (polyProd->HighPower>Maxdegree)
30              Error("Exceeded array size");
31          for(i=0;i<=poly1->HighPower;i++)
32              for(j=0;j<=poly2->HighPower;j++)
33                  polyProd->CoeffArray[i+j]=poly1->CoeffArray[i]*poly2->CoeffArray[j];
34 }

可以将其改为通过单链表予以实现；链表节点结构

1 typedef struct Node *PtrToNode
2 struct Node
3 {
4        int CoeffArray;
5        int Exponent;
6        PtrToNode Next;
7 };
8 typedef      PtrToNode   Polynomial;

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

栈为一种后进先出表，实现表的方式都可以用来实现栈。

栈的链表实现：

 1 //栈链表实现的声明
 2 #ifndef  _Stack_h
 3  struct Node;
 4  typedef struct Node *PtrToNode;
 5  typedef ptrToNode Stack;
 6  
 7 int IsEmpty(Stack S);
 8 Stack CreateStack(void);
 9 void DisposeStack(Stack S);
10 void MakeEmpty(Stack S);
11 void Push(ElementType X,Stack S);
12 ElementType Top( Stack S);
13 void Pop(Stack S);
14 
15 #endif 
16 
17 struct Node
18 {
19    ElementType Element;
20    ptrToNode Next;
21 }

测试栈是不是空栈；

1 int IsEmpty(Stack S)
2 {
3     return NULL==S->Next;
4 }

创建一个空栈

 1 Stack CreateStack(void)
 2 {
 3     Stack S;
 4     S=malloc(sizeof(Strcut Node));
 5     if(Null==S)
 6         FataError("out of space!!")；
 7    S->next=Null;
 8     MakeEmpty(S);
 9     return S;
10 }
11 void MakeEmpty(Stack S)
12 {
13   if (NULL==S)
14       Erro("Must create Stack first!")；
15   else
16    whlie(!IsEmpty(S))
17       Pop(S);
18 }

链表栈的PUSH操作

 1 void Push(Stack S,ElementType Element)
 2 {
 3     prtToNode tmp;
 4     tmp=malloc(sizeof (struct Node));
 5     if(tmp==NULL)
 6     FataErro("Out of space !")；
 7    else
 8     {    
 9          tmp->Element=X;
10           tmp->next=S->next;
11           S->next=tmp->next;          
12     }
13 }

返回栈顶元素和Pop操作的实现

 1 ElementType Top(Stack S)
 2 {
 3    if (!IsEmpty(S))
 4       return S->next->Element;
 5    else
 6       Erro("Empty Stack");
 7   }
 8 //栈的Pop操作
 9 void Pop(Stack S)
10 {
11    PtrToNode tmp;
12    if (isEmpty(S))
13       Erro("Empty Stack");
14    else
15         {
16             Tmp=S->next;
17              s->next=s->next->next;
18              free(tmp);
19         }
20 }

由数组实现的栈更为流行：

 1 //栈的数组实现
 2 #ifndef _Stack_h
 3 struct StackRecord;
 4 typedef struct StackRecord *Stack;
 5 
 6 int IsEmpty( Stack S);
 7 int IsFull(Stack S);
 8 Stack CreateStack(int MaxElements);
 9 void DisposeStack(Stack S);
10 void MakeEmpty(Stack S);
11 void Push (Stack S,ElememtType X);
12 ElementType Top(Stack S);
13 void Pop(Stack S);
14 ElementType TopAndPop();
15 
16 #endif
17 
18 #define EmptyTOS (-1)
19 #define MinStackSize (5)
20 
21 struct StackRecord
22 {
23     int Capacity;
24     int TopOfStack;
25     ElementType *Array;
26 }
27 
28 
29 //栈的创建 数组实现
30 stack createStack（int MaxElements）
31 {
32     stack S;
33     if(MaxElements<MinStackSize)
34         Error("Stack size is too small");
35     S= malloc(sizeof(struct StackRecord));
36     if(NULL==S)
37         FataError("out of space")；
38     S->Array=malloc(sizeof(ElementType)*MaxElements);
39     if(S->Array==NULL)
40             FataErro("out of space !")；
41     S->Capacity=MaxElements;
42     MakeEmpty（S）;
43     return S;
44 }
45 //释放一个栈
46 void DisposeStack(Stack S)
47 {
48     if(S!=NULL)
49     {
50         free(S->Array);
51         free(S);
52     }
53 }
54 //检测是否是空栈
55 int IsEmpty(Stack S)
56 {
57     return S->TopOfStack==EmptyTOS;
58 }
59 //创建一个空栈
60 void MakeEmpty(Stack S)
61 {
62     S->TopOfStack=EmptyTOS;
63 }
64 //进栈
65 void Push(ElementType X,Stack S)
66 {
67     if(IsFull(S))
68         Erro("Full stack");
69     else
70         S->Array[++TopOfStack]=X;
71 }
72 //返回栈顶元素
73 ElmentType Top(Stack s)
74 {
75     if(!IsEmpty(S))
76         return S->Array[S->TopOfStack];
77     Erro("Empty stack");
78     return 0;
79 }
80 //Pop
81 void Pop(Stack S)
82 {
83     if(IsEmpty(S))
84         Erro("Empty Stack");
85     else
86         S->TopOfStack--;
87 }
88 //TopAndPop
89 ElementType TopAndPop( Stack S)
90 {
91     if(!IsEmpty(S))
92         return S->Array[S->TopOfStack--];
93     Erro("Empty Stack");
94     
95 }

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

栈的典型应用：括号匹配，后缀表达式的应用，中缀到后缀的转换；函数调用

=============================================================================================================================

队列

#ifndef _Queue_h
struct QueueRecord;
typedef struct QueueRecord *Queue;
int IsEmpty(Queue Q    );
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void EnQueue(ElementType X,Queue Q);
Element Front(Queue Q);
void DeQueue(Queue Q);
ElementType FrontAndDequeue(Queue Q);
#endif


#define MinQueueSize (5)

struct QueueRecord
{
    int Capacity;
    int Front;
    int Rear;
    ElementType *Array;
};

//判空
int IsEmpty(Queue Q)
{
    return Q->size==0;
}
//构造空队列
void MakeEmpty(Queue Q)
{
    Q->size=0;
    Q->Front=1;
    Q->Rear=0;
}
//入队
static int succ(int Value ,Queue Q)//循环队列
{
    if(++Value==Q->Capacity)
        Value=0;
    return Value;
}
void EnQueue(ElmentType X,Queue Q)
{
    if(IsFull(Q))
        Erro("Full Queue");
    else
        {
            Q->Size++;
            Q->Rear=Succ(Q->Rear,Q);
            Q->Array[Q->Rear]=X;
        }
}

------------------------------------------------------------------------------------------------------------------------------------------------------------------

数据结构与算法分析 学习笔记(2)

数据结构与算法分析学习笔记(2)