线性表【数据结构】

顺序表由长度定义成Maxsize的数组来实现

1.【查找】

时间复杂度： O ( n ) O(n) O(n)

证：

顺序表的平均查找次数为：
1 + 2 + 3 + ⋅ ⋅ ⋅ + n n = n + 1 2 frac{1+2+3+···+n}{n} = frac{n+1}{2} n1+2+3+⋅⋅⋅+n​=2n+1​
∴时间复杂度： O ( n ) O(n) O(n) 略去常数项以及常数系数(下同)

P.S【ASL:平均查找长度】:
A S L = ∑ i = 1 n p i c i ASL = sum_{i=1}^{n}p_ic_i ASL=i=1∑n​pi​ci​
其中 n n n为要查找的元素集的个数， p i p_i pi​为查找到元素 a i a_i ai​的概率， c i c_i ci​为查找到元素时需要比较的次数。

顺序表查找操作的ASL(显而易见 p i = 1 n p_i = frac{1}{n} pi​=n1​ )：
A S L = ∑ i = 1 n p i c i = p i ∑ i = 1 n c i = 1 n ∑ i = 1 n c i = 1 n × ( 1 + 2 + ⋅ ⋅ ⋅ + n ) = n + 1 2 ASL = sum_{i=1}^{n}p_ic_i = p_isum_{i=1}^{n}c_i = frac{1}{n}sum_{i=1}^{n}c_i = frac{1}{n}times(1+2+···+n) = frac{n+1}{2} ASL=i=1∑n​pi​ci​=pi​i=1∑n​ci​=n1​i=1∑n​ci​=n1​×(1+2+⋅⋅⋅+n)=2n+1​
即平均查找次数 = 平均查找长度

2.【插入】

时间复杂度： O ( n ) O(n) O(n)

证：

顺序表插入时平均移动次数为：
n + ( n − 1 ) + ( n − 2 ) + ⋅ ⋅ ⋅ + 1 + 0 n + 1 = n 2 frac{n+(n-1)+(n-2)+···+1+0}{n+1} = frac{n}{2} n+1n+(n−1)+(n−2)+⋅⋅⋅+1+0​=2n​
∴时间复杂度： O ( n ) O(n) O(n)

3.【删除】

时间复杂度： O ( n ) O(n) O(n)

证：

顺序表插入时平均删除次数为：
( n − 1 ) + ( n − 2 ) + ⋅ ⋅ ⋅ + 1 + 0 n = n − 1 2 frac{(n-1)+(n-2)+···+1+0}{n} = frac{n-1}{2} n(n−1)+(n−2)+⋅⋅⋅+1+0​=2n−1​
∴时间复杂度： O ( n ) O(n) O(n)

一、单链表

【实现代码】：

import java.util.*;

class Link {
    int data;
    Link next;
}
public class Main {
    public static void InitList(Link List_Head) {
        List_Head.next = null;
    }

    public static void InsertList(Link List_Head, int data) {
        Link ptr = List_Head;
        while (ptr.next != null) {
            ptr = ptr.next;
        }
        //Insert after ptr;
        Link List_new = new Link();
        List_new.data = data;
        List_new.next = null;
        ptr.next = List_new;
    }

    public static void TraverseList(Link List_Head) {
        Link ptr = List_Head;
        while (ptr.next != null) {
            System.out.println(ptr.next.data);
            ptr = ptr.next;
        }
    }

    public static void main(String[] argv) {
        Scanner cin = new Scanner(System.in);
        Link List_Head = new Link();
        InitList(List_Head);
        int n = cin.nextInt();
        for (int i = 0; i < n; i++) {
            int x = cin.nextInt();
            InsertList(List_Head, x);
        }
        TraverseList(List_Head);
    }
}

import java.util.*;

class Link {
    int data;
    Link next;
    static Link List_Head;
}
public class Main {

    public static void InitList() {
        Link.List_Head = null;
    }
    public static void InsertList(int data) {
        if (Link.List_Head == null) {
            Link.List_Head = new Link();
            Link.List_Head.data = data;
            Link.List_Head.next = null;
        }
        else {
            Link ptr = Link.List_Head;
            while (ptr.next != null) {
                ptr = ptr.next;
            }
            //Insert after ptr;
            Link List_new = new Link();
            List_new.data = data;
            List_new.next = null;

            ptr.next = List_new;
        }
    }

    public static void TraverseList() {
        Link ptr = Link.List_Head;
        while (ptr != null) {
            System.out.println(ptr.data);
            ptr = ptr.next;
        }
    }

    public static void main(String[] argv) {
        Scanner cin = new Scanner(System.in);
        InitList();
        int n = cin.nextInt();
        for (int i = 0; i < n; i++) {
            int x = cin.nextInt();
            InsertList(x);
        }
        TraverseList();
    }
}

二、循环链表

			tail.next = null -----------> tail.next = head

三、双向链表

class Link {
    Link prior;
    int data;
    Link next;
}

【C语言实现常用模板（带头结点的单链表）】：

#include
#include

typedef struct Link {
	int data;
	struct Link* next;
}List;

void InitList(List* List_Head) {
	List_Head->next = NULL;
}

void InsertList(List* List_Head, int data) {
	List* ptr = List_Head;
	while (ptr->next != NULL) {
		ptr = ptr->next;
	}
	//Insert after ptr;
	List* List_new = (List*)malloc(sizeof(List));
	List_new->data = data;
	List_new->next = NULL;
	ptr->next = List_new;
}

void TraverseList(List* List_Head) {
	List* ptr = List_Head;
	while (ptr->next != NULL) {
		printf("%dn", (ptr->next)->data);
		ptr = ptr->next;
	}
}

int main() {
	
	List List_Head;
	InitList(&List_Head);

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		InsertList(&List_Head, x);
	}
	TraverseList(&List_Head);
	return 0;
}

应用：一元多项式的运算、约瑟夫环问题

A n ( x ) = a 0 + a 1 x + a 2 x 2 + ⋅ ⋅ ⋅ + a n x n A_n(x)=a_0+a_1x+a_2x^2+···+a_nx^n An​(x)=a0​+a1​x+a2​x2+⋅⋅⋅+an​xn

B m ( x ) = b 0 + b 1 x + b 2 x 2 + ⋅ ⋅ ⋅ + b m x m B_m(x)=b_0+b_1x+b_2x^2+···+b_mx^m Bm​(x)=b0​+b1​x+b2​x2+⋅⋅⋅+bm​xm

求：
C n ( x ) = A n ( x ) + B m ( x ) = ( a 0 + b 0 ) + ( a 1 + b 1 ) x + ⋅ ⋅ ⋅ + ( a n + b n ) x n C_n(x)=A_n(x)+B_m(x)=(a_0+b_0)+(a_1+b_1)x+···+(a_n+b_n)x^n Cn​(x)=An​(x)+Bm​(x)=(a0​+b0​)+(a1​+b1​)x+⋅⋅⋅+(an​+bn​)xn
【实现代码】：

class Link {
    double coef;	//系数
    int exp;	    //指数
    Link next;
}

完整代码（带头结点单链表实现）

public static void ListSum(Link List_1, Link List_2){
        Link ptr_1 = List_1, ptr_2 = List_2;    //ptr_1为主链表，合并到ptr_1链表
        while (ptr_1.next != null && ptr_2.next != null) {
            //0指数结点删去
            if ((ptr_1.next).coef == 0) ptr_1.next = (ptr_1.next).next;
            if ((ptr_2.next).coef == 0) ptr_2 = ptr_2.next;
            if (ptr_1.next == null || ptr_2.next == null) break;

            //按指数从小到大排列
            if ((ptr_1.next).exp < (ptr_2.next).exp) {
                // |ptr_1|->|ptr_1.next|->|(ptr_1.next).next|
                //               |------> ptr_1.next < ptr_2.next ?     ptr_1 = ptr_1.next;
                // |ptr_2|->|ptr_2.next|
                ptr_1 = ptr_1.next;
            }
            else if ((ptr_1.next).exp > (ptr_2.next).exp) {
                // |ptr_1|->|ptr_1.next|                              |ptr_1|->|ptr_2.next|(ptr)->|ptr_1.next|
                //        ↑-insert-↓                              =>
                // |ptr_2|->|ptr_2.next|(ptr)->|(ptr_2.next).next|    |ptr_2|->|(ptr_2.next).next|
                Link ptr = ptr_2.next;
                ptr_2.next = ptr.next;  //Delete ptr_2.next in List_2

                //Insert ptr(ptr_2.next) between ptr_1 and ptr_1.next
                ptr.next = ptr_1.next;
                ptr_1.next = ptr;
            }
            else {
                // |ptr_1|->|ptr_1.next|->|(ptr_1.next).next|
                //              |||
                // |ptr_2|->|ptr_2.next|->|(ptr_1.next).next|
                (ptr_1.next).coef += (ptr_2.next).coef;
                if ((ptr_1.next).coef == 0) ptr_1.next = (ptr_1.next).next;
                else ptr_1 = ptr_1.next;
                ptr_2 = ptr_2.next;
            }
        }
        if (ptr_1.next == null) ptr_1.next = ptr_2.next;
    }

无注释版本（建议画草稿图写）

public static void ListSum(Link List_1, Link List_2){
        Link ptr_1 = List_1, ptr_2 = List_2;
       
   		while (ptr_1.next != null && ptr_2.next != null) {
            
            if ((ptr_1.next).coef == 0) ptr_1.next = (ptr_1.next).next;
            if ((ptr_2.next).coef == 0) ptr_2 = ptr_2.next;
            if (ptr_1.next == null || ptr_2.next == null) break;

            if ((ptr_1.next).exp < (ptr_2.next).exp) ptr_1 = ptr_1.next;
            else if ((ptr_1.next).exp > (ptr_2.next).exp) {
                Link ptr = ptr_2.next;
                ptr_2.next = ptr.next;
                ptr.next = ptr_1.next;
                ptr_1.next = ptr;
            }
            else {
                (ptr_1.next).coef += (ptr_2.next).coef;
                if ((ptr_1.next).coef == 0) ptr_1.next = (ptr_1.next).next;
                else ptr_1 = ptr_1.next;
                ptr_2 = ptr_2.next;
            }
        }
    
        if (ptr_1.next == null) ptr_1.next = ptr_2.next;
    }

​ 有 n n n个人，编号分别为 1 , 2 , 3 , . . . , n 1,2,3,...,n 1,2,3,...,n,从编号为 1 1 1号的人开始报数，报到数字 m m m的人离开，下一个人重新开始从 1 1 1开始报数，依次类推，直至最终剩余 1 1 1人，求剩余的那个人的编号。

【实现代码】：

import java.util.*;

class Link {
    int num;
    Link next;
}

public class Main {

    public static void InitList(Link List_Head) {
        List_Head.next = List_Head;
    }

    public static void InsertList(Link List_Head, int num) {
        Link ptr = List_Head;
        while (ptr.next != List_Head) {
            ptr = ptr.next;
        }
        //Insert between ptr and List_Head
        Link List_new = new Link();
        List_new.num = num;
        List_new.next = List_Head;
        ptr.next = List_new;
    }

    public static void JosephusList(Link List_Head, int m) {
        Link ptr = List_Head;
        int count = 1;
        while ((List_Head.next).next != List_Head) {
            if (ptr.next == List_Head) ptr = ptr.next;
            if (count == m) {
                //Delete ptr.next
                System.out.println((ptr.next).num + " OUT");
                ptr.next = (ptr.next).next;

                count = 1;

            }
            else {
                count++;
                ptr = ptr.next;
            }
        }

        System.out.println("*" + (List_Head.next).num + "*");
    }

    public static void TraverseList(Link List_Head) {
        Link ptr = List_Head;
        while (ptr.next != List_Head) {
            System.out.println((ptr.next).num + " ");
            ptr = ptr.next;
        }
    }

    public static void main(String[] argv) {
        Scanner cin = new Scanner(System.in);
        Link List_Head = new Link();
        InitList(List_Head);
        System.out.println("请输入n:");
        int n = cin.nextInt();
        System.out.println("请输入m:");
        int m = cin.nextInt();
        for (int i = 1; i <= n; i++) {
            InsertList(List_Head, i);
        }
        JosephusList(List_Head, m);
    }
}

时间复杂度分析：

​ 每删去一个人需要将链表查找 m m m次，所以删去 n − 1 n-1 n−1个人需要的次数为：
m × ( n − 1 ) {m}times{(n-1)} m×(n−1)
∴时间复杂度为： O ( m × n ) O({m}times{n}) O(m×n)

附：约瑟夫环公式

1）.右移

推理：

设ptr、ptr’ 分别为移动前与移动后的位置,移动 t t t位

①、先求出ptr相对于起始位置（图中为 a 1 a_1 a1​）的相对位置：
p t r − h e a d ptr - head ptr−head
②、求出移动后超出 n n n的部分（即为相对起始位置（下个循环）的相对位置长度）：
( p t r − h e a d + t ) m o d n (ptr - head + t)quad mod quad n (ptr−head+t)modn
③、易得：
p t r ′ = ( p t r − h e a d + t ) m o d n + h e a d ptr'=(ptr-head+t)quad modquad n + head ptr′=(ptr−head+t)modn+head
结论：ptr’ = (ptr - 起始位置 + t) mod n + 起始位置

2）.左移

推理：

设ptr、ptr’ 分别为移动前与移动后的位置,移动 t t t位

①、先求出ptr相对于起始位置（图中为 a 1 a_1 a1​）的相对位置：
p t r − h e a d ptr - head ptr−head
②、求出移动后超出 n n n的部分（为负值）：
( p t r − h e a d − t ) m o d n (ptr - head - t)quad mod quad n (ptr−head−t)modn
③、根据②式以及图像易得到ptr’相对于上个循环起始位置的相对位置长度：
p t r − h e a d − t + n ptr - head - t + n ptr−head−t+n
接下来，易得：
p t r ′ = ( p t r − h e a d − t + n ) m o d n + h e a d ptr'=(ptr-head-t+n)quad modquad n + head ptr′=(ptr−head−t+n)modn+head
结论：ptr’ = (ptr - 起始位置 - t + n) mod n + 起始位置