目录
1.顺序表的定义
用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系又存储的邻接关系体现。
注：之所以要提出动态顺序表，是因为如果使用静态顺序表的话，空间上很容易就处于满的状态，但是如果一下子申请很大的空间的话，那么会造成空间上的浪费，所以根据需要申请空间的大小是必要的。
2.申请空间
（1）申请空间的方式一
ElemType *p=L.data;
L.data=(ElemType*)malloc((L.MaxSize+len)*sizeof(ElemType));
for(int i=0;i<L.length;i++){
L.data[i]=p[i];
}
L.MaxSize=L.MaxSize+len;
free(p);（2）申请空间的方式二
ElemType *newBase=(ElemType*)realloc(L.data,(L.MaxSize+len)*sizeof(ElemType));
L.data=newBase;
L.MaxSize+=len; 3.动态顺序表的定义
#include<stdlib.h>
#include<stdio.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct {
ElemType*data;
int length;
int MaxSize;
}SqList;4.动态顺序表的相关操作
（1）初始化
//顺序表的初始化
void InitSqList(SqList&L){
L.data=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));
L.MaxSize=MAXSIZE;
L.length=0;
}（2）申请空间
//增加顺序表的容量
void IncreaseSize(SqList&L,int len){
//定义方式一
// ElemType *p=L.data;
// L.data=(ElemType*)malloc((L.MaxSize+len)*sizeof(ElemType));
// for(int i=0;i<L.length;i++){
// L.data[i]=p[i];
// }
// L.MaxSize=L.MaxSize+len;
// free(p);
//方式二
ElemType *newBase=(ElemType*)realloc(L.data,(L.MaxSize+len)*sizeof(ElemType));
L.data=newBase;
L.MaxSize+=len;
} （3）顺序表的判空和判满
//操作清单
void MenuSqList(){
printf("-------------1.插入操作-------------\n");
printf("-------------2.定位插入操作---------\n");
printf("-------------3.查找操作-------------\n");
printf("-------------4.定位删除操作---------\n");
printf("-------------5.按值删除元素---------\n");
printf("-------------6.删除整个顺序表-------\n");
printf("-------------7.打印操作-------------\n");
printf("-------------8.结束操作-------------\n");
}
//判断顺序表是否空
bool IsEmpty (SqList L){
if(L.length<=0){
return true;
}else {
return false;
}
}
//判断顺序表是否为满
bool IsFull(SqList L){
if(L.length>=L.MaxSize){
return true;
}else{
return false;
}
}（4）顺序表的插入和定位插入元素
//顺序表的插入操作
void ListInsert(SqList&L,ElemType e) {
if(IsFull(L)){
printf("顺序表已满!\n");
return ;
}
L.data[L.length]=e;
L.length++;
}
//定位向顺序表中插入数据
void ListInsertLocate(SqList&L,int i,ElemType e){
if(i<0||i>L.length+1){
printf("输入的插入元素位置不合法\n");
return ;
}
if(L.length>=L.MaxSize){
printf("存储空间已满!\n");
printf("请输入申请的空间大小: ");
int len=0;
scanf("%d",&len);
IncreaseSize(L,len);
printf("申请空间成功,目前空间大小: %d\n",L.MaxSize);
return ;
}
for(int j=L.length;j>=i;j--){
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
}（5）定位删除元素和按值删除元素
//定位删除操作
void DeleteElemType(SqList&L,int i,ElemType&e){
if(i<0||i>L.length+1){
printf("输入的插入元素位置不合法\n");
return ;
}
e=L.data[i-1];
for(int j=i-1;j<L.length;j++){
L.data[j]=L.data[j+1];
}
L.length--;
}
//顺序表按值删除（删除第一个元素为e的值）
void DeleteElem(SqList&L,ElemType&e) {
int index=0;
for(int i=0;i<L.length;i++){
if(L.data[i]==e){
index=i;
break;
}
}
for(int j=index;j<L.length;j++){
L.data[j]=L.data[j+1];
}
L.length--;
}（6）删除表和打印
//删除顺序表
void DeleteSqList(SqList&L){
for(int i=0;i<L.length;i++){
L.data[i]=0;
}
L.length=0;
}
//顺序表的打印操作
void PrintSqList(SqList L){
for(int i=0;i<L.length;i++){
printf("%d\t",L.data[i]);
}
printf("\n");
} （7）主函数
int main() {
SqList L;
//对顺序表进行初始化
InitSqList(L);
//对顺序表进行插入操作
ElemType x;
int flag=-1;
//各种操作
while(1) {
int i=0;
ElemType e=0;
MenuSqList();
printf("请输入操作: ");
scanf("%d",&flag);
switch(flag){
case 1:
printf("请输入元素(-1_end): ");
scanf("%d",&x);
i=1;
while(x!=-1) {
ListInsert(L,x);
printf("请输入元素(-1_end): ");
scanf("%d",&x);
i++;
if(i>=L.MaxSize+1){
printf("存储空间已满!\n");
break;
}
}
break;
case 2:
printf("请输入元素插入位置: \n");
scanf("%d",&i);
printf("请输入元素: ");
scanf("%d",&x);
ListInsertLocate(L,i,x);
break;
case 3:
printf("请输入查找元素位置: ");
scanf("%d",&i);
if(i<0||i>=L.length+1){
printf("输入的查找元素位置不合法!\n");
break;
}
printf("Elem = %d\n",L.data[i-1]);
printf("删除元素成功!\n");
break;
case 4:
printf("请输入删除的定位位置: ");
scanf("%d",&i);
DeleteElemType(L,i,e);
printf("删除成功元素=%d\n",e);
break;
case 5:
printf("请输入要删除的元素: ");
scanf("%d",&e);
DeleteElem(L,e);
break;
case 6:
DeleteSqList(L);
printf("删除成功!\n");
break;
case 7:
PrintSqList(L);
break;
default:
printf("结束操作\n");
}
if(flag==8){
break;
}
}
return 0;
}（8）测试
本文含有隐藏内容，请 开通VIP 后查看