数据结构(C语言版)严蔚敏---＞一些操作相关数据结构的题目

1.将一个带头节点的单链表A分解成两个带头节点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B中含有原表中序号为偶数的元素，且保持相对顺序不变

思路：原本是想定义一个变量用来记单链表A的序号的，但是后面代码写出来，发现，根本没有必要定义这个变量。用一个指针pa1直接指向带头节点的单链表A的后一个节点(也就是序号为1(奇数)的节点)，它的后一个节点(如果不为NULL)，那么肯定是一个序号为偶数的节点，对单链表A的操作是用指针pa2指向pa1的后一个节点，然后pa1的后一个节点直接指向pa2后一个节点，然后将pa2后一个节点为NULL，之后将pa2接在单链表B后面。【描述的不是很清楚哈！】

参考代码：

void function1(LinkList &A,LinkList &B){
    LNode *pa1 = A->next,*pa2;
    // 建立单链表B
    B = (LNode *)malloc(sizeof(LNode));
    B->next = NULL;
    LNode *pb = B;
    while(pa1){
        if(pa1->next){
            pa2 = pa1->next;
            pa1->next = pa2->next;
            pa2->next = NULL;
            pb->next = pa2;
            pb = pa2;
        }
        pa1 = pa1->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果：

2. 在带头节点的单链表L中，删除所有值为x的节点，并释放其空间，假设值为x的节点不唯一。

思路：直接用指针p指向L，进行循环遍历单链表L，循环的条件为p->next，如果L不为空，用指针q指向p的下一个节点，如果q所指的节点值为x，那么q前一个数据元素(即p)的next值为q的后一个节点(即q->next),并释放q所指向的节点所占的空间；如果q所指的节点值不为x，那么p=p->next(或者p=q)。按照上述步骤循环下去，直到p指向L的末尾，退出循环即可。

参考代码如下：

void function2(LinkList &L,ElemType x){
    LNode *p = L;
    while(p->next){
        LNode *q = p->next;
        if(q->data == x){
            p->next = q->next;
            free(q);
        }else{
            p = p->next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

【注】：运行结果是删除L中值为4的节点。

3.设L为带头节点的单链表，编写算法实现从尾到头反向输出每个节点的值。

• 方法1
  思路：直接去leetcode上看相似的题吧！链接为：反转链表
  参考代码：

void function3(LinkList L){
    LNode *curr = L->next,*next;
    L->next = NULL;
    while(curr){
        next = curr->next;
        curr->next = L->next;
        // 使用头插法
        L->next = curr;
        curr = next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

【注】：上述代码只是将原单链表逆序，然后再输出，如果题目要求不改变原单链表，可以参考如下。

• 方法2
  思路：使用一个栈记录单链表中各个节点，然后依次输出栈中节点元素的值即可。
• 方法3
  思路：方法2使用栈，那么可以考虑使用递归。

参考代码：

void function4(LinkList L){
    if(L->next)
        function4(L->next);
    if(L)
        printf("%d ",L->data);
}
1
2
3
4
5
6

4. 编写在带头节点的单链表L中删除一个最小值节点的高效算法（假设最小值节点是唯一的）

思路：最小值节点可能在单链表L的末尾，因此，必须用一个节点来记住最小节点的前驱节点。

参考代码：

void function5(LinkList &L){
    LNode *p = L,*pre;
    int min_v = 999999; // 一个最大的数
    while(p->next){
        if(p->next->data<min_v){
            min_v = p->next->data;
            pre = p;
        }
        p = p->next;
    }
    pre->next = pre->next->next;
}
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

5. 在一个递增有序的线性表，有数值相同的元素存在，若采用单链表形式存储，设计算法去掉数值相同的元素

思路：因为递增有序，所以数值相同的元素如果存在肯定是挨在一起的，找到这些数值相同的节点起点节点和终止节点，然后进行处理即可。不过需要注意在单链表末尾时的情况（当然两个两个节点单独处理也行）。

void function6(LinkList &L){
    LNode *p = L->next,*pre;
    int temp = p->data;
    pre = p;
    while(p){
        if(temp != p->data){
            pre->next = p;
            pre = p;
            temp = p->data;
        }

        if(!p->next)
            pre->next = NULL;
        p = p->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果：

6. 假设两个按元素递增次序排列的单链表。请编写算法将这两个单链表归并为一个按元素递减次序排列的单链表，并要求利用原来两个单链表的节点存放归并后的单链表

思路：和将两个按元素递增次序排列的单链表合并成一个递增的单链表一样，但是需要注意使用头插法来链接单链表的节点。

参考代码：

void function7(LinkList &L1,LinkList &L2){
    LNode *p1 = L1->next,*p2 = L2->next,*tail;
    L1->next = NULL;
    while(p1&&p2){
        if(p1->data > p2->data){
            tail = p2->next;
            // 头插法
            p2->next = L1->next;
            L1->next = p2;

            p2 = tail;
        }else{
            tail = p1->next;
            // 头插法
            p1->next = L1->next;
            L1->next = p1;

            p1 = tail;
        }
    }
    // 两个单链表进行上述循环后，有可能还有一个单链表还没有到达末尾
    if(p2){
        p1 = p2;
    }

    while(p1){
        tail = p1->next;
        p1->next = L1->next;
        L1->next = p1;
        p1 = tail;
    }
}

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
30
31
32
33

运行结果：