2017-09-21

无所事事刷anyview的日子（chapter 01~02）

好久没更博了，实在是很懒了。开学后都没怎么看前端的知识，把主要精力都放在课程上了。主要是大二觉得课程变难变多，也想好好学。还有的想法是，先把学习弄好，然后之后才能留出更多精力来忙其他的事情。事情总会一件一件一件一件一件一件一件一件一件一件慢慢做完的……

最近都在抓紧时间看数据结构，感觉大二老师讲的都很快很乱，都要自学了= =。数据结构感觉是培养一种编程思维，对思维的锻炼很有帮助。一边看书一边刷anyview，还是学得比较快的。

DC01

/**********
【题目】已知k阶裴波那契序列的定义为
    f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;
    f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
**********/
Status Fibonacci(int k, int m, int &f) 
/* 求k阶斐波那契序列的第m项的值f */
{  
    int a[60],sum,i,j;
    if(k<2||m<0) return ERROR;  /*k<2为负*/
    if(m<k-1) f=0; /*前k-1项均为0*/
    else if(m==k) f=1;
    else {
      for(i=0;i<=k-2;i++){
        a[i]=0;
        a[k-1]=1;
        for(i=k;i<=m;i++){
            sum=0;  /*置0*/
            for(j=i-k;j<i;j++) sum+=a[j];
            a[i]=sum;
        }
      }
      f=a[m];
    }
    return OK;
}

/**********
【题目】试写一算法，由长度为n的一维数组a构建一个序列S。
序列的类型定义为：
typedef struct {
  ElemType  *elem;
  int  length;
} Sequence;
***********/
Status CreateSequence(Sequence &S, int n, ElemType *a) 
/* 由长度为n的一维数组a构建一个序列S，并返回OK。 */
/* 若构建失败，则返回ERROR                       */
{
    int i;
    S.elem=(ElemType*)malloc(n*sizeof(ElemType)); /*分配n个元素空间*/
    if(S.elem==NULL||n<=0) return ERROR;  /*空间分配不成功或参数错误*/
    else {
        S.length=n;
        for(i=0;i<n;i++) {
            S.elem[i]=*(a+i);
        }
        return OK;
    }
}

DC02

1、顺序栈

/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status InitStack_Sq2(SqStack2 &S, int size, int inc)
/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/ 
/* 若成功，则返回OK；否则返回ERROR。                 */
{
    S.elem=(ElemType*)malloc(sizeof(ElemType));
    if(S.elem==NULL||size<=0||inc<=0) return ERROR;
    else {
        S.top=S.elem;
        S.size=size;
        S.increment=inc;
        return OK;
    }    
}

2、循环队列：注意，规定当 Q.rear==maxSize-1/Q.front==maxSize-1时，Q.rear/Q.front置0。
合并两种情况，即：Q.rear=(Q.rear+1)%maxSize/Q.front=(Q.front+1)%maxSize，循环加一。
所以 Q.front==Q.rear 不能判断队列状态是”空”还是”满”。
可以用三种方法：
1）设一标志域标识队列的空与满。
2）设一个长度域记录队列中元素的个数。
3）少用一个元素空间，即 Q.front==(Q.rear+1)%maxSize 为队满。

/**********
【题目】如果希望循环队列中的元素都能得到利用，
则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是"空"还是"满"。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：
typedef struct {
  ElemType elem[MAXQSIZE];
  int tag;
  int front;
  int rear;
} CTagQueue;
**********/
Status EnCQueue(CTagQueue &Q, ElemType x)
/* 将元素x加入队列Q，并返回OK；*/
/* 若失败，则返回ERROR。       */
{
    if(Q.front==Q.rear&&Q.tag==1) return ERROR;
    else {
        Q.elem[Q.rear++]=x;
        return OK;
    }    
}
Status DeCQueue(CTagQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK；*/
/* 若失败，则返回ERROR。               */
{
    if(Q.front==Q.rear&&Q.tag==0) return ERROR;
    else {
        x=Q.elem[Q.front++];
        Q.tag=0;
        return OK;
    }    
}

/**********
【题目】假设将循环队列定义为：以域变量rear
和length分别指示循环队列中队尾元素的位置和内
含元素的个数。试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法（在出队列的算
法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下：
typedef struct {
  ElemType elem[MAXQSIZE];
  int length;
  int rear;
} CLenQueue;
**********/
Status EnCQueue(CLenQueue &Q, ElemType x)
  /* 将元素x加入队列Q，并返回OK；*/
  /* 若失败，则返回ERROR。       */
{
    if(Q.length==MAXQSIZE) return ERROR;
    else { 
        Q.rear=(Q.rear+1)%MAXQSIZE;
        Q.elem[Q.rear]=x;        
        Q.length++;
        return OK;
    }    
}
Status DeCQueue(CLenQueue &Q, ElemType &x)
  /* 将队列Q的队头元素退队到x，并返回OK；*/
  /* 若失败，则返回ERROR。               */
{
    if(Q.length==0) return ERROR;
    else {
        x=Q.elem[(Q.rear+MAXQSIZE-Q.length+1)%MAXQSIZE];
        Q.length--;
        return OK;
    }    
}

3、顺序表

/**********
【题目】假设有两个集合A和B分别用两个线性表LA和LB
表示(即：线性表中的数据元素即为集合中的成员），
试写一算法，求并集A＝A∪B。
顺序表类型定义如下
typedef struct {
  ElemType *elem;     // 存储空间的基址
  int length;    // 当前长度
  int size;      // 存储容量 
  int increment; // 空间不够增加空间大小
} SqList;  // 顺序表
可调用顺序表的以下接口函数：   
Status InitList_Sq(SqList &L, int size, int inc); // 初始化顺序表L
int ListLength_Sq(SqList L);  // 返回顺序表L中元素个数
Status GetElem_Sq(SqList L, int i, ElemType &e); 
// 用e返回顺序表L中第i个元素的值
int Search_Sq(SqList L, ElemType e); 
// 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1
Status Append_Sq(SqList &L, ElemType e);  // 在顺序表L表尾添加元素e
**********/
void Union(SqList &La, SqList Lb)
{    
    int i;
    ElemType elem='a';
    for(i=0;i<Lb.length;i++) {
       elem=Lb.elem[i];
       if(Search_Sq(La,elem)==-1) {
             if(La.length>=La.size) {
                 ElemType *newbase;
                 newbase=(ElemType*)realloc(La.elem,(La.size+La.increment)*sizeof(ElemType));
                 if(newbase==NULL) return;
                 La.size=La.size+La.increment;
                 La.elem=newbase;
             }
             Append_Sq(La,elem);                
         }
    }
        
}

4、链栈

/**********
【题目】试写一算法，实现链栈的取栈顶元素操作。
链栈的类型定义为：
typedef struct LSNode {
  ElemType data;       // 数据域
  struct LSNode *next; // 指针域
} LSNode, *LStack;    // 结点和链栈类型
***********/
Status GetTop_L(LStack S, ElemType &e) 
/* 取链栈S的栈顶元素到e，并返回OK; */
/* 若S是空栈，则失败，返回ERROR。  */
{
    if(S==NULL) return ERROR;
    else {
        e=S->data;
        return OK;
    }    
}

5、链队列

/**********
【题目】试写一算法，实现链队列的求队列长度操作。
链队列的类型定义为：
typedef struct LQNode {     
  ElemType  data;  
  struct LQNode  *next;  
} LQNode, *QueuePtr; // 结点和结点指针类型
typedef struct {     
  QueuePtr  front;  // 队头指针
  QueuePtr  rear;   // 队尾指针
} LQueue;  // 链队列类型
***********/
int QueueLength_LQ(LQueue Q)
/* 求链队列Q的长度并返回其值 */
{
    int i=1;
    if(Q.front==NULL) return 0;
    else {
        LQNode *p;
        p=Q.front;
        while(p->next!=NULL) {
            i++;
            p=p->next;
        }
        return i;
    }      
}

6、带头结点的单链表

头指针 L 指向单链表的第一个结点，叫头结点。头结点区别于首元结点，头结点是指在首元结点前预设的一个结点，其数据域可以为空，其指针域指向首元结点。
即：首元结点 = L->next

/**********
【题目】试写一算法，实现带头结点单链表的清空操作。
单链表的类型定义为：
typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status ClearList_L(LinkList &L)
/* 将带头结点单链表L置为空表，并返回OK。*/
/* 若L不是带头结点单链表，则返回ERROR。 */
{
    LinkList p;
    p=L->next;
    if(L==NULL) return ERROR;
    else {
        while(p!=NULL) {           
            L->next=p->next;
            free(p);
            p=L->next;
        }
        return OK;
    }            
}

/**********
【题目】试写一算法，在带头结点单链表L插入第i元素e。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/
/* 若参数不合理，则返回ERROR。              */
{
    int k=0;
    LNode *p=L,*q;
    while(p&&k<i-1) {
        p=p->next;
        k++;
     }
    if(!p||k>i-1) return ERROR;
    q=(LinkList)malloc(sizeof(LNode));
    q->data=e;
    q->next=p->next;
    p->next=q;
    return OK;
}

/**********
【题目】试写一算法，在带头结点单链表删除第i元素到e。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Delete_L(LinkList L, int i, ElemType &e)
/* 在带头结点单链表L删除第i元素到e，并返回OK。*/
/* 若参数不合理，则返回ERROR。                */
{
    int j=0;
    LinkList p=L,q;
    while(p->next&&j<i-1) {
        p=p->next;
        j++;
    }
   if(!p->next||j>i-1) return ERROR;
   q=p->next;
   p->next=q->next;
   e=q->data;
   free(q);
   return OK;
}

/**********
【题目】试写一算法，在带头结点单链表的第i元素起的
所有元素从链表移除，并构成一个带头结点的新链表。
带头结点单链表的类型定义为：
typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Split_L(LinkList L, LinkList &Li, int i)
/* 在带头结点单链表L的第i元素起的所有元素 */
/* 移除，并构成带头结点链表Li，返回OK。   */
/* 若参数不合理，则Li为NULL，返回ERROR。  */
{
    int j;
    LinkList p,t=L;
    Li=(LNode*)malloc(sizeof(LNode));
    if(Li==NULL) return ERROR;
    if(i<=0) {
        Li=NULL;
        return ERROR;
    }
    if(L==NULL||L->next==NULL) {
        Li=NULL;
        return ERROR;
    } 
    for(j=1;j<i;j++) {
        t=t->next;
        if(t->next==NULL) {
            Li=NULL;
            return ERROR;
        }
    }
    p=t->next;
    t->next=NULL;
    Li->next=p;
    return OK;
}

yitian's blog

along the road

无所事事刷anyview的日子（chapter 01~02）

DC01

DC02