• free(p)只释放该空间, 标记该空间为可复用，空间中数据暂时不会被清除，指针值未变，需要使用p=NULL，防止野指针。
  • 顺序表函数clearlist(Sqlist &L)仅使length变为0，所存储值仍也存在，待覆盖。
  • 头插法可用于建立逆向链表
  • 就地逆转单链表方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

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

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

栈的应用

  • 数制转换
    • eg.10->8
1
2
3
4
5
6
7
8
9
10
void conversion(unsigned int n){
    Sqstack* s = InitStack(6);
    while(n){
        Push(s,n%8);
        n/=8;
    }
    while(!StackEmpty(s)){
        printf("%d",Pop(s));
    }
}
    • 汉诺塔(和栈类似，只允许从顶出)
1
2
3
4
5
6
7
8
9
10
11
12
13
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);
    }
}