线性表的理解以及顺序表和链表的比较

线性表分为顺序存储和链式存储： 顺序存储的就是顺序表，链式存储分为静态链表(借助数组实现)，单链表，双链表，循环多链表(这三个都是通过指针实现) 线性表的基本操作:

InitList(&L):初始化表。构建空的线性表。 Length(L):获取表长，返回线性表L的长度。 LocateElem(L,i):按值查找。 GetElem(L,i):按位查找操作，获取表中第i位的元素值。 ListInsert(&L,i,e):插入，在第i个位置插入元素e. ListDelete(&l,i,&e):删除操作，删除第i位的数据并且通过e返回删除的元素值。 PrintList(L):输出，输出整个线性表中所有的元素。 Empty(L):判断线性表是否为空，是返回true，不是返回false. DestroyList(&L):销毁操作，销毁线性表，释放线性表L所占的空间。

顺序表基本操作实现： 1.插入操作

bool ListInsert(SqList &L,int i,ElementType e){ if(i<1||i>L.Length+1){ //判断i范围是否有效 return false; } if(l.Length>=MaxSize){//判断表空间是否已满 return false; } for(int j=L.length;j>=i;j--){//i位置后的所有元素向后移动一个位置 L.data[j] = L.data[j-1]; } L.data[i-1] = e;//将e放入i位置 L.Length++; //表长度加1 return true; } 最好情况的时间复杂度为:O(1) 最差情况的时间复杂度为:O(n) 平均的时间复杂度为:O(n)

2.删除操作

bool ListDelete(SqList &L,int i,ElementType &e){ if(i<1||i>L.Length+1){ //判断范围是否有效 return false; } e = L.data[i];//删除的值赋给e for(int j=i;j<L.length;j++){//i之后的所有元素向前移动 L.data[j] = L.data[j-1]; } L.Length--; //表长度减1 return true; } 最好情况的时间复杂度为:O(1) 最差情况的时间复杂度为:O(n) 平均的时间复杂度为:O(n)

3,按值查找

int LocateElem(SqList L,ElemType e){ int i; for(i=0;i<l.Length;i++){ if(L.data[i]==e){ return i+1; //查找成功返回其位序i+1 } } return 0;//查找失败返回0 } 最好情况的时间复杂度为:O(1) 最差情况的时间复杂度为:O(n) 平均的时间复杂度为:O(n)

顺序表和链表的比较： 1.存取(读写)方式 顺序表可以顺序存取，也可以随机存取，链表只能从表头开始。 2.逻辑结构和物理结构 顺序表存储时，逻辑上相邻的数据，物理结构上也相邻。而链表逻辑上相邻的数据，物理结构上不一定相邻。 3.查找插入和删除操作 按值查找当顺序表有序时，时间复杂度为O(n)，无序时为O(log2n), 按序号查找时，顺序表的时间复杂度为O(1),而链表所有的时间复杂度为O(n). 顺序表删除和插入时平均需要移动半个表的元素，而链表的删除和插入只需要需改指针域就行。因此，链表的存储密度不够大。 4.空间分配 顺序表需要预先分配一块存储空间，预分配过大将会导致空间浪费，过小就会导致溢出。动态分配虽然可以扩充，但是没有足够大的连续存储空间时会导致分配失败，链式存储空间是只在需要的时候就会申请，只要有内存空间就可以分配，操作灵活，高效。