具有n个元素的线性表采用顺序存储结构，在其第i个位置插入一个

[单选题]

具有n个元素的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）（1≤i≤n+1）

```
O(1)
```
```
O(i)
```
```
O(n)
```
```
O(n^2)
```

JingXu

C,最坏情况是在1位置处插入新元素，即将所有元素往后移，此时需要移动n次，故算法的时间复杂度为O（n）

编辑于 2017-05-03 14:24:47 回复(0)

牛客882122502号

O(n)，最坏的情况是从第一个元素开始插入（对应物理位置0），所有元素后移

typedef struct 
{
    int data[MaxSize];
    int length;
} SqList;

bool ListInsert(SqList *&L, int i, int e)
{
    int j;
    if (i < 1 || i > L->length+1)
    {
        return false;
    }
    //这里将从1开始的序号（逻辑序号）转为从0开始（物理序号）
    i--;
    //将data[i]及后面的元素后移一个位置倒着后移
    for (j = L->length;j > i;j--)
    {
        L->data[j] = L->data[j-1];
    }
    //插入元素
    L->data[i] = e;
    //链表长度增长1
    L->length++;
    return true;
}

扩展：链式存储方式，时间复杂度也是o(n)，最坏的情况是查找到元素的末尾。

typedef struct LNode 
{
    int data;
    struct LNode *next;
} LinkNode;

bool ListInsert(LinkNode *&L, int i, int e)
{
    int j = 0;
    //p指向头结点
    LinkNode *p = L, *s;
    if (i <= 0)
    {
        return false;
    }
    //查找第i-1个结点p
    while (j < i-1 && p!=NULL)
    {
        j++;
        p = p->next;
    }
    //没有找到第i个元素返回false
    if (p == NULL)
    {
        return false;
    }
    else
    {
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = e;
        //将新结点s插入到第i个结点后
        s->next = p->next;
        p->next = s;
        return true;
    }
}

发表于 2021-04-04 09:00:12 回复(0)