考研中线性表相关代码题

public static void change(int[] array){
    int left = 0;
    int right = array.length-1;
    while(left<right){
        int n1 = array[left];
        int n2 = array[right];
        if(n1 > 0 && n2 > 0 ){
            left++;
            right--;
        }else if(n1>0 && n2 <0){
            array[left] = n2;
            array[right] = n1;
        }else if(n1<0 && n2<0){
            left++;
        }else if(n1<0&&n2>0){
            right--;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public static void insertElem(int[] array,int m,int n){
    //遍历后n个元素，以方便将后n个元素插入到前面
    for (int i = m; i < m+n; i++) {
        //将当前位置元素存入临时变量
        int temp = array[i];
        int j;
        //从当前位置元素的前一个元素开始向前遍历，查找插入位置，也就是当找到比当前元素小的元素时，就插入到这个找到的元素后面
        for (j = i-1; j >=0 && temp

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

4、考察链表相关的插入、删除算法

public static void lickNode(Link l1,Link l2){
    Link p = l1.next;
    Link q = l2.next;
    //设置前一个结点，默认指向l1的头节点，这个节点的作用：因为我们遍历链表时只能遍历到当前节点，所以需要设置指向前一个节点的节点
    Link pre = l1;
    //p和q在遍历过程中都不能为null
    while(p != null && q != null){
        if (p.value < q.value){
            //如果p节点的值小于q节点的值，那么将p赋值给前置节点，然后p节点向后移动
            pre = p;
            p = p.next;
        } else if (p.value > q.value) {
            //如果p节点的值大于q节点的值，那么直接将q节点后移
            q = q.next;
        } else{
            //如果相等，则需要将p中当前的节点删除掉
            pre.next = p.next;
            p = p.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法一 建立一个新链表，通过头插法将原链表中的元素插入新链表中，那么倒数第k个也就成了在新链表中查找正数第k个

public static int findNode(Link link,int k){
    Link newLink = new Link();
    Link head = link.next;
    while(head != null){
        Link temp = newLink.next;
        newLink.next = new Link();
        newLink.next.value = head.value;
        newLink.next.next = temp;
        head = head.next;
    }
    for (int i = 0; i < k && newLink != null; i++) {
        head = newLink.next;
        newLink = newLink.next;
    }
    if (head != null){
        System.out.println(head.value);
        return 1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二 我们发现，如果要找倒数第k个，那么我们需要从头节点向后移动n-k+1次（n为除头节点外的节点总数），那么我们可以先遍历一遍链表得到节点总数，然后我们可以根据公式在正向遍历链表查找想要的结果。

public static int findNode(Link link,int k){
    Link head = link.next;
    int sum = 0;
    while(head != null){
        sum++;
        head = head.next;
    }
    head = link;
    for (int i = 0;i<sum-k+1 && head != null;i++){
        head = head.next;
    }
    if (head != null){
        System.out.println(head.value);
        return 1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法三 我们可以设置两个指针，初始化时两个指针first、last都指向头节点，随后设置一个变量step，我们判断步长是否为k，如果不为k，那么就不断向后移动last，如果为k，那么我们向后移动first，如果last已经为空，则遍历结束。

public static int findNode(Link link,int k){
    Link first = link;
    Link last = link;
    int step = 0;
    while(last!= null){
        //一开始step为0，所以在step==k之前一直是last向后移动，随后last和first同时向后并保持step距离
        if (step == k){
            first = first.next;
            step = step-1;
        }else{
            last = last.next;
            step++;
        }
    }
    if (first != null){
        System.out.println(first.value);
        return 1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5、408真题中的顺序表考题

方法一 双层暴力循环

public static void findMainElem(int[] arrays){
    int n = arrays.length;
    for (int i = 0;i<n;i++){
        int m = 1;
        for (int j = i+1; j < n; j++) {
            if (arrays[i] == arrays[j])m++;
        }
        if (m > n/2){
            System.out.println(arrays[i]);
            return;
        }
    }
    System.out.println(-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二

public static void findMainElem02(int[] arrays){
    int c = 0;
    int sum = 0;
    int n = arrays.length;
    for (int i = 0; i < n; i++) {
        if (sum == 0){
            c = arrays[i];
            sum++;
        }else{
            if (c == arrays[i])sum++;
            else sum--;
        }
    }
    sum = 0;
    for (int i = 0; i < n; i++) {
        if (arrays[i] == c)sum++;
    }
    if (sum > n/2){
        System.out.println(c);
    }else{
        System.out.println(-1);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24