顺序存储:
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
顺序表的特点:
- 能在O(1)的时间内找到第i个元素
- 存储密度高
- 拓展容量不方便
- 插入,删除操作不方便
C语言中可使用:sizeof(ElemType) 来查询数据元素的大小
顺序表的实现:
静态分配:
#include <stdio.h>
#define MaxSize 10 //宏定义最大长度为10
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++)L.data[i] = 0;L.length = 0;
}int main() {SqList L;InitList(L);for(int i=0; i<MaxSize; i++)printf("data[%d]=%d\n",i,L.data[i]);
}
动态分配:
#include <stdlib.h>
#define InitSize 10 //默认最大长度为10
typedef struct{ //定义一个顺序表int *date; //指示动态分配的指针int MaxSize; //顺序表的最大容量int length; //顺序表当前长度
}SeqList;void InitList(SeqList &L){ //初始化一个顺序表L.date = (int *)malloc( InitSize*sizeof(int) ); //用malloc申请一片连续的存储空间L.length = 0;L.MaxSize = InitSize;
}void IncreaseSize(SeqList &L, int len){ //动态增加顺序表的长度int *p = L.date; //将旧数据保存L.date = (int *)malloc((L.MaxSize + len) * sizeof(int)); //开辟更大的存储空间for(int i = 0; i < L.length; i++){ //循环将旧数据复制到新区域L.date[i] = p[i];}L.MaxSize = L.MaxSize + len; //最大长度增加lenfree(p); //释放原来的存贮空间
}int main(){SeqList L; //声明一个顺序表InitList(L); //初始化顺序表//...此处省略部分代码,在顺序表中随便插入几个元素...IncreaseSize(L, 5); //增加长度为5return 0;
}
顺序表的插入和删除:
插入:
将元素e插入到第i个位置
平均时间复杂度为O(n)
#include <stdio.h>
#define MaxSize 10 //宏定义最大长度为10
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++)L.data[i] = 0;L.length = 0;
}bool ListInsert(SqList &L, int i, int e){if(i<1 || i>L.length)return false;if(L.length >= MaxSize)return false;for(int j=L.length; j>=i; j--)L.data[j] = L.data[j-1];L.data[i-1] = e;L.length++;return true;
}int main() {SqList L;InitList(L);//此处省略一些代码,随便向顺序表中插入几个元素ListInsert(L, 3, 3);for(int i=0; i<MaxSize; i++)printf("data[%d]=%d\n",i,L.data[i]);
}
删除:
将第i个元素删除,并用e返回
平均时间复杂度为O(n)
#include <stdio.h>
#define MaxSize 10 //宏定义最大长度为10
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++)L.data[i] = 0;L.length = 0;
}bool ListDelete(SqList &L, int i, int &e){if(i<1||i>L.length)return false;e = L.data[i-1];for(int j=i; j<L.length; j++)L.data[j-1] = L.data[j];L.length--;return true;
}int main() {SqList L; InitList(L);//此处省略一些代码,随便向顺序表中插入几个元素int e = -1;if (ListDelete(L, 1, e))printf("已删除第3个元素,删除的元素值=%d", e);elseprintf("删除失败");return 0;
}
查找元素:
按位查找:
平均时间复杂度O(1)
int GetElen(SqList L, int i){return L.data[i-1];
}
按值查找:
平均时间复杂度O(n)
int LocateElem(SqList L, int e){for(int i=0; i<L.length; i++)if(L.data[i] == e)return i+1;return 0
}