数据结构之线性表（顺序表与单链表的比较）

迈不过友情╰ 2023-07-17 06:07 56阅读 0赞

**结构**

> **顺序表：** 逻辑相邻物理上也相邻，通过相邻表示逻辑关系。  
> **单链表：** 逻辑相邻物理上不一定相邻，通过指针表示逻辑关系。

**基本操作：**

> 删除&插入  
> 单链表为O(1)(节点指针已知)；O(n)(节点指针未知)，但操作时只需修改指针  
> 顺序表为O(n)且需要大量移动元素。

> 查找  
> 按值查找中单链表和顺序表（无序）都为O(n)。  
> 按序号查找中单链表为O(n),顺序表为O(1)。

> 内存空间  
> **顺序存储：** 无论静态分配还是非静态分配都需要预先分配合适的内存空间  
> 静态分配时预先分配空间太大会造成浪费，太小会造成溢出  
> 动态分配时虽然不会溢出但是扩充需要大量移动元素，操作效率低  
> **连式存储：** 在需要时分配结点空间即可，高效方便，但是指针要使用额外空间

单链表找最值

p指向头结点
    int min=p->next->data；
    int max=p->next->data；
    for(;p!=NULL;p=p->next){ 
    if(min>p->data)
    min=p->data;
    if(max<p->data)
    max=p->data;
    }

逆置

顺序表
    int i=0;
    int j=n-1;
    while(i<j)
    { 
    temp=L[i];
    L[i]=L[j];
    L[j]=temp;
    }
    时间复杂度为O(n)

单链表
    r是开始指向表尾的指针，不断在它后面加入新节点，当它成为第一个结点时逆置完成
    while(p->next!=r)
    { 
    temp=p->next;
    p->next=temp->next;
    temp->next=r->next
    r->next=temp;
    }
    时间复杂度为O(n)

两个表的合并

顺序表
    int i=0,j=0;
    int k=0;
    for(;i<L1_Size&&j<L2_Size;k++)
    { 
    if(L1[i]<L2[j])
    L[k]=L[i++];
    else
    L[k]=L[j++];
    }
    while(i<L1_Size)
    L[k++]=L1[i++];
    while(i<L2_Size)
    L[k++]=L1[j++];
    时间复杂度为O(n)

单链表
    while(p->next!=NULL&&q->next!=NULL)
    { 
    if(p->next->data<q->next->data){ 
    r->next=p->next;
    p->next=p->next->next;
    r=r->next;}
    else{ 
    r->next=q->next;
    q->next=q->next->next;
    r=r->next;
    }
    }
    if(p->next!=NULL)   r->next=p->next;
    if(q->next!=NULL)   r->next=q->next;
    free(p);
    free(q);
    时间复杂度为O(n)