数据结构-线性表·栈·队列

• free(p)只释放该空间, 标记该空间为可复用，空间中数据暂时不会被清除，指针值未变，需要使用p=NULL，防止野指针。
• 顺序表函数clearlist(Sqlist &L)仅使length变为0，所存储值仍也存在，待覆盖。
• 头插法可用于建立逆向链表
• 就地逆转单链表方法

  typedef struct LNode{
    elemtype data;
    struct LNode *next;
  }LNode,*LinkList;
  LinkList Reverse(Linklist &L){
    if(L->next==NULL||L->next->next) return L;
    LNode *pre = NULL;
    LNode *cur = L->next;
    LNode *next = NULL;
    while (cur != NULL){
        next=cur->next;  //保留直接后继
        cur->next=pre;  //调转方向
        pre=cur;       //后移
        cur=next;
    }
    L->next=pre;  //执行完循环操作后cur为原尾节的next，为NULL，pre为新的首元，令原头指针指向它
  }
  

  }LNode,*LinkList;相当于给struct LNode起了两个别名，同时使得LinkList直接为指向这种结构的指针，方便后续简便书写。

• 在涉及到某个函数调用比较方法时，可以考虑使用函数指针，方便运用不同的比较规则

栈分为顺序栈和链栈

SqStack

typedef struct{
    elemtype *base;   //基址，站地指针
    elemtype *top; //栈顶
    int size;
}*SqStack

top指向下一个可以入栈的空位置（约定）

栈的应用

• 数制转换
• • eg.10->8

    void conversion(unsigned int n){
    Sqstack* s = InitStack(6);
    while(n){
        Push(s,n%8);
        n/=8;
    }
    while(!StackEmpty(s)){
        printf("%d",Pop(s));
    }
    }
    

• • 汉诺塔(和栈类似，只允许从顶出)

    void move(char from,int n, char to){
    printf("Move disk %d from %c to %c\n", n, from, to);
    }
    void hanoi(int n, char from, char to, char temp) {
    if(n == 1){
        move(from, 1, to);
    }
    else{
        hanoi(n-1, from, temp, to);
        move(from, n, to);
        hanoi(n-1, temp, to, from);
    }
    }