从查找、插入、删除三个算法的时间复杂性比较链表和顺序表

1. 查找算法

对于顺序表，查找算法的时间复杂度为O(n)，因为需要遍历整个数组来进行查找。

对于链表，如果是单向链表，则查找算法的时间复杂度为O(n)，因为需要从头结点开始遍历整个链表。如果是双向链表，则可以优化查找算法，时间复杂度为O(n/2)，因为可以从头结点或尾结点开始遍历。

2. 插入算法

对于顺序表，插入算法的时间复杂度为O(n)，因为需要将插入位置后面的元素都往后移动一位。

对于链表，插入算法的时间复杂度为O(1)，因为只需要修改指针指向即可。

3. 删除算法

对于顺序表，删除算法的时间复杂度为O(n)，因为需要将删除位置后面的元素都往前移动一位。

对于链表，删除算法的时间复杂度为O(1)，因为只需要修改指针指向即可。

综上所述，链表在插入和删除操作上具有优势，而在查找操作上与顺序表相比较劣。因此，在选择数据结构时，应根据实际情况选择适合的数据结构来进行操作。

相关问题

设计算法并编程实现用三元组顺序表解决稀疏矩阵的转置问题，解决稀疏矩阵的转置问题的两种方法实现并分析比较3种算法的时间和空间复杂性。

稀疏矩阵转置问题可以通过两种方法进行解决：基于三元组顺序表的方法和基于十字链表的方法。本文将着重介绍基于三元组顺序表的方法。

一、基于三元组顺序表的转置方法
1. 三元组顺序表的定义
三元组顺序表是指将一个三元组按一定的顺序存储在一维数组中，具体定义如下：

typedef struct {
    int i, j; // 行下标和列下标
    ElemType e; // 元素值
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1]; // 存储三元组的一维数组，data[0]未使用
    int mu, nu, tu; // 稀疏矩阵的行数、列数和非零元素个数
} TSMatrix;

2. 稀疏矩阵转置的算法思路
稀疏矩阵转置的算法思路是：将原矩阵中的每个非零元素，按其列下标为主关键字，行下标为次关键字，插入到转置矩阵中。具体实现步骤如下：

（1）创建一个新的三元组顺序表，用于存储转置后的矩阵。

（2）遍历原矩阵中的每个非零元素，将其插入到新的三元组顺序表中，同时行下标和列下标交换。

（3）将新的三元组顺序表中的元素按行下标为主关键字，列下标为次关键字进行排序。

3. 稀疏矩阵转置的算法实现

void transpose(TSMatrix M, TSMatrix *T) {
    int col, p, q;
    T->mu = M.nu; // 转置后矩阵的行数等于原矩阵的列数
    T->nu = M.mu; // 转置后矩阵的列数等于原矩阵的行数
    T->tu = M.tu; // 转置后矩阵的非零元素个数等于原矩阵的非零元素个数
    if (T->tu) { // 非零矩阵
        q = 1;
        for (col = 1; col <= M.nu; col++) { // 遍历每一列
            for (p = 1; p <= M.tu; p++) { // 遍历每一行
                if (M.data[p].j == col) { // 如果该元素在当前列
                    T->data[q].i = M.data[p].j; // 行下标和列下标交换
                    T->data[q].j = M.data[p].i;
                    T->data[q].e = M.data[p].e;
                    q++; // 移动到下一个位置
                }
            }
        }
    }
}

二、时间和空间复杂性分析
1. 时间复杂性
稀疏矩阵转置的时间复杂性取决于原矩阵中的非零元素个数 tu，转置后的矩阵中的非零元素个数也为 tu。因此，稀疏矩阵转置的时间复杂性为 O(tu)。

2. 空间复杂性
稀疏矩阵转置的空间复杂性取决于原矩阵中的非零元素个数 tu 和转置后的矩阵中的非零元素个数 tu。因此，稀疏矩阵转置的空间复杂性为 O(tu)。

基于十字链表的稀疏矩阵转置方法，其时间复杂性和空间复杂性均为 O(tu)。因此，两种方法在时间和空间上都是等价的。

1.4 编写程序，输入若干正整数，按从小到大次序建立1个带头结点单链表，设计一个实现单链表分离算法的split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求split算法时间复杂性达到o（n）,程序不可存在内存泄漏。

### 回答1：
题目要求我们编写一个程序，输入若干正整数，按从小到大顺序建立1个带头结点单链表，设计一个实现单链表分离算法的split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，请在程序退出前销毁单链表。要求split算法时间复杂度达到O(n)，程序不可存在内存泄漏。

### 回答2：
思路：

- 输入若干正整数，按从小到大次序建立一个带头结点单链表
- 分离原单链表的偶数节点，生成新的带头结点单链表
- 输出两个单链表，销毁原单链表和新单链表

第一步，建立如下单链表：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def createListNode(head: ListNode, nums: List[int]):
    for num in nums:
        node = ListNode(num)
        if head.next == None:
            head.next = node
        else:
            cur = head.next
            pre = head
            while cur and cur.val < num:
                pre = cur
                cur = cur.next
            pre.next = node
            node.next = cur

第二步，分离偶数节点，生成新单链表：

先遍历原单链表，将偶数节点放进新单链表。这里注意记录分离的偶数节点链的头结点，函数返回它；用prev指针记录当前节点的上一个节点，便于拼接列表。

时间复杂度: O(n) (n是总节点数)。

def split(head: ListNode) -> ListNode:
    node_even = ListNode(-1)
    even = node_even
    prev = head
    curr = head.next
    while curr:
        if curr.val % 2 == 0:
            prev.next = curr.next
            even.next = curr
            even = even.next
            curr = prev.next
        else:
            prev = prev.next
            curr = curr.next
    even.next = None
    return node_even

第三步，输出两个单链表，销毁原单链表和新单链表。

def printListNode(node):
    cur = node.next
    res = []
    while cur:
        res.append(cur.val)
        cur = cur.next
    print(res)

def destroyListNode(head: ListNode):
    cur = head.next
    while cur:
        tmp = cur.next
        del cur
        cur = tmp
    head.next = None

if __name__ == "__main__":
    nums = [2, 7, 1, 5, 6, 3, 4, 8, 9, 10]
    head = ListNode(-1)
    createListNode(head, nums)
    node_even = split(head)
    printListNode(head)
    printListNode(node_even)
    destroyListNode(head)
    destroyListNode(node_even)

完整代码如下：

### 回答3：
算法步骤：

（1）定义一个指向链表头结点的指针head和一个当前结点指针p。

（2）定义一个指向分离后新链表头结点的指针newHead和一个当前结点指针q。

（3）遍历链表，当当前结点的值为偶数时，将该结点从原链表上摘除，接入新链表中。同时更新head、p节点，newHead、q节点。

（4）事件复杂度是O(n)，插入新链表操作仅执行n/2次，与n无关，空间复杂度为O(1)。

下面是完整程序实现：

#include<iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

void createlist(ListNode*& L)
{
    L = new ListNode(0);
    int x;
    cin >> x;
    while (x > 0)
    {
        ListNode* p = new ListNode(x);
        p->next = L->next;
        L->next = p;
        cin >> x;
    }
}

void printlist(ListNode* L)
{
    while (L->next != NULL)
    {
        cout << L->next->val << " ";
        L = L->next;
    }
    cout << endl;
}

void split(ListNode*& head, ListNode*& newHead)
{
    ListNode *p, *q;
    newHead = new ListNode(0);
    p = head; q = newHead;
    while (p->next != NULL)
    {
        if (p->next->val % 2 == 0)
        {
            q->next = p->next;
            p->next = p->next->next;
            q = q->next;
            q->next = NULL;
        }
        else
        {
            p = p->next;
        }
    }
}

void destroylist(ListNode*& L)
{
    ListNode* p;
    while (L != NULL)
    {
        p = L;
        L = L->next;
        delete p;
    }
}

int main()
{
    ListNode* head, * newHead;
    createlist(head);

    split(head, newHead);
    cout << "Original List: ";
    printlist(head);
    cout << "New List: ";
    printlist(newHead);

    destroylist(head);
    destroylist(newHead);
    return 0;
}