T1

顺序表删除指定范围
设计一个高效的算法，从顺序表L中删除所有值介于x和y之间(包括x和y)的所有元素（假设y>=x），要求时间复杂度为O(n)，空间复杂度为O(1)。
函数原型如下：
void del_x2y(SeqList *L, ElemType x, ElemType y);
相关定义如下：
struct _seqlist{
```
ElemType elem[MAXSIZE];
int last;
```
};

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-02, Mon, 11:46:50
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

void del_x2y(SeqList* L, ElemType x, ElemType y)
{
    int last = -1;
    for (int i = 0; i <= L->last; i++)
        if (L->elem[i] < x || L->elem[i] > y)
            L->elem[++last] = L->elem[i];
    L->last = last;
}

T2

顺序表删除重复
编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。
函数原型如下：
void del_dupnum(SeqList *L)
相关定义如下：
struct _seqlist{
```
ElemType elem[MAXSIZE];
int last;
```
};
typedef struct _seqlist SeqList;

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-02, Mon, 11:49:49
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

void del_dupnum(SeqList* L)
{
    int flag = 0, val = L->elem[0];
    for (int i = 1; i <= L->last; i++) {
        if (val != L->elem[i]) {
            val = L->elem[i];
            flag += 1;
            L->elem[flag] = val;
        }
    }
    L->last = flag;
}

T3

顺序表数据调整
已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，并要求算法的时间复杂度为O(n),空间复杂度为O（1）。
链表结点定义如下：
void odd_even(SeqList *L);
相关定义如下：
struct _seqlist{
```
ElemType elem[MAXSIZE];
int last;
```
};
typedef struct _seqlist SeqList;

2.解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-03, Tue, 18:32:04
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

void odd_even(SeqList* L)
{
    int i = 0;
    int j = L->last;
    while (i < j) {
        while (L->elem[i] % 2 != 0)
            i++;
        while (L->elem[j] % 2 == 0)
            j--;
        if (i < j) {
            int t = L->elem[i];
            L->elem[i] = L->elem[j];
            L->elem[j] = t;
        }
    }
}

T4

链表删除范围内结点
已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。
链表结点定义如下：
struct _lnklist{
```
ElemType data;
struct _lnklist *next;
```
};
typedef struct _lnklist Node;
typedef struct _lnklist *LinkList;
函数原型如下：
void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)
其中L指向链表的头结点。

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-13, Fri, 18:35:51
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)
{
    LinkList p, q, prev = NULL;
    if (mink > maxk)
        return;
    p = L;
    prev = p;
    p = p->next;
    while (p && p->data < maxk) {
        if (p->data <= mink) {
            prev = p;
            p = p->next;
        } else {
            prev->next = p->next;
            q = p;
            p = p->next;
            free(q);
        }
    }
}

T5

链表倒数查找
已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。
函数原型为：
int lnk_search(LinkList L, int k, ElemType* p_ele)
若查找成功，函数通过指针参数 p_ele 返回该结点 data 域的值，此时函数返回 1；否则，函数返回 0。相关定义如下：
struct _lnklist{
```
ElemType data;
struct _lnklist *next;
```
};
typedef struct _lnklist Node;
typedef struct _lnklist *LinkList;

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-13, Fri, 18:40:21
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

int lnk_search(LinkList L, int k, ElemType* p_ele)
{
    LinkList p = L->next, q = L->next;
    int count = 0;
    while (p != NULL) {
        if (count < k)
            count++;
        else
            q = q->next;
        p = p->next;
    }
    if (count < k)
        return 0;
    else {
        p_ele = q->data;
        return 1;
    }
}

T6

链表合并
设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时；
或者
C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
函数的原型如下：
void lnk_merge(LinkList A, LinkList B, LinkList C)
即将A和B合并为C，其中 C 已经被初始化为空单链表
相关定义如下：
struct _lnklist{
```
ElemType data;
struct _lnklist *next;
```
};
typedef struct _lnklist Node;
typedef struct _lnklist *LinkList;

解析

Code

/*
 * 完成人　：岳昕峰(201909******4)
 * 完成时间：2020-03-21, Sat, 12:38:40
 * 最高分数：100
 */


#include "list.h" // 请不要删除，否则检查不通过
#include <stdio.h>
#include <stdlib.h>

void lnk_merge(LinkList A, LinkList B, LinkList C)
{
    Node *p, *q, *m, *temp;
    p = A->next;
    q = B->next;
    m = C;
    while (p != NULL && q != NULL) {
        m->next = p;
        temp = p->next;
        p->next = q;
        m = q;
        p = temp;
        q = q->next;
    }
    if (p != NULL) {
        m->next = p;
    }
    if (q != NULL) {
        m->next = q;
    }
}