数据结构面试复习之链表

数据结构分为逻辑结构和物理结构，逻辑结构分为集合结构、线性结构、树形结构和图形结构四大类。物理结构分为顺序存储结构和链式存储结构。

顺序存储的线性表

1
2
3
4
5
6
7
8

typedef int ElemType;//数据类型为int  
struct 
{  
    ElemType data[MAXSIZE];//数组存储数据元素  
    int length;//线性表长度  
};

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

链式存储的线性表