错题本之＜数据结构＞

1. 已知指针 p 指向单向不循环链表中的某一个节点，且不知道头结点。
   问：如何删除 p 指向的节点？
   答：

如果 p 指向的不是最后一个节点
定义一个指针 q 保存 p->next; 然后将 q 的数据域和指针域都覆盖到 p 指向的节点中
最后释放 q 指向的节点即可。

q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
q = NULL;
1
2
3
4
5

如果 p 指向的是最后一个节点了，就只能free(p)了，且没法修改倒数第二节点的指针域了

2. 已知p指针指向的是某单向不循环链表的某一节点，该节点数据域存放了数据B，且不知头节点，如何在下面链表中数据B的前面再插入一个数据X？

答：

思路：将新节点插入到p节点的后面，然后交换两个节点的数据域
方法：定义一个指针q指向新节点，将q指向的节点插入到p指向的节点后面，即q->next=p->next，p->next=q，之后交换两个节点的数据域，即定义一个变量temp记录p->data的数据域，然后利用三杯水思想交换两个节点的数据域即可。

int temp=p->data;
p->data=q->data;
q->data=temp;
q->next=p->next;
p->next=q;
1
2
3
4
5

3. 问：如何通过一趟遍历找到单向不循环链表的中点？

答：

可以通过 快慢指针 实现
定义两个指针 p q 都指向链表开头
然后开始循环， q每次走2步，p每次走1步
当 q 走到结尾时，p 指向的就是链表的中点

int *p=phead;
int *q=phead;
//如果是代码实现 要注意 得保证 p->next 不是NULL  才能取 p->next->next 
while(NULL != q  ||  NULL != q->next){
q = q->next->next;
p = p->next;
}
1
2
3
4
5
6
7

3. 顺序表(数组)和链表有什么区别？

答：
首先，从时间复杂度来看，
链表增删的时间复杂度是O(1)，但是查找的时间复杂度是O(n);
顺序表增删的时间复杂度是O(n)，但是查找的时间复杂度是O(1)；
其次，从内存角度来看，
顺序表地址连续，无需额外的空间记录节点之间的逻辑关系，但是内存分配属于静态分配，程序执行之前必须明确规定存储规模，预先分配足够大的存储空间。
链表内存存储位置不连续，需要分配额外的内存空间记录与其他节点的逻辑关系，但是内存分配属于动态分配，需要多大空间就分配多大空间

4. 如何使用两个栈实现一个队列？

答：栈是先入后出的数据结构，队列是先入先出的数据结构
首先定义两个栈A、B
入队列时：
直接入到A栈中
出队列时：
先判断B栈是否为空，如果不为空，则直接在B栈出队列
如果B栈为空，判断A是否空，如果A不空，则A栈中数据依次出栈并入栈到B栈中，然后再从B栈中出队列；如果A栈也为空，说明队列空。

伪代码：

int my_push_queue(stack_t *A,int data){
    if(NULL==A) return -1;
    if(push_stack(A,data))
        return -1;
    return 0;
}

int my_pop_queue(stack_t *A,stack_t *B,int *num){
    if(NULL==A||NULL==B||NULL==num) return -1;
    int n=0;
    if(is_empty(B)){
        if(is_empty(A)){
            printf("队列空\n");
            return -1;
        }else{
            while(!is_empty(A)){
                pop_stack(A,&n);
                push_stack(B,n);
            }
        }
    }
    pop_stack(B,num);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5. 如何使用两个队列实现一个栈的功能

答：定义两个队列A、B
入栈：
先判断A是否为空，
如果为空，则将元素入到A队列中，然后依次将B队列的元素入到A队列里；
如果不为空，则将元素入到B队列中，然后依次将A队列的元素入到B队列中。
出栈：
先判断A队列是否为空，如果不为空，则将A直接出队列；
如果A为空，判断B是否为空，如果B不为空，则B出队列；
如果B为空，则队列空。

int mystack_push(queue_t *A,queue_t *B,int data){
    if(NULL==A) return -1;
    int temp=0;
    if(is_empty(A)){
        push_queue(A,data);
        while (!pop_queue(B,&temp)){
            push_queue(A,temp);
        }
    }else{
        push_queue(B,data);
        while(!pop_queue(A,&temp)){
            push_queue(B,temp);
        }
    }
    return 0;
}

int mystack_pop(queue_t *A,queue_t *B,int *num){
    if(NULL==A||NULL==B||NULL==num) return -1;
    if(!is_empty(A)){
        pop_queue(A,num);
    }else if(!is_empty(B)){
        pop_queue(B,num);
    }else{
        printf("栈空\n");
        return -1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29