相关知识
线性表在物理结构上可以分为：顺序存储结构和链表存储结构，前者是随机存取的存储结构，后者是顺序存取的存储结构。
插入数据
- 在哪个顺序表上的哪个位置插入哪个数据值
- bool InsertList (SqList &L, int loca, ElemType dat)
- 因为要修改顺序表，所以用引用
- ret = InsertList (L, 2, 20);
- 顺序表中已经存满了时，不可以插入
- 时间复杂度：最好：O(1); 最坏：O(n); 平均：O(n)
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
bool InsertList(SqList &L,int loca,ElemType dat)
{
if(loca < 1 || loca >L.length+1)
return false;
if(L.length > MaxSize)
return false;
for(int j=L.length;j>=loca;j--)
{
L.data[j]=L.data[j-1];
}
L.data[loca-1]=dat;
L.length++;
return true;
}
void PrintList(SqList L)
{
for(int i=0;i<L.length;i++)
{
printf("L.data[%d]=%d\n",i,L.data[i]);
}
}
int main(){
SqList L;
L.data[0]=1;
L.data[1]=10;
L.data[2]=100;
L.length=3;
bool ret;
ret=InsertList(L,2,20);
if(ret)
{
printf("插入成功\n");
PrintList(L);
}
else
{
printf("插入失败\n");
}
}
删除数据
- 在哪个顺序表的哪个位置删除数据，返回删除的数据值
- bool DeleteList(SqList &L,int loca,ElemType &dele)
- 因为要修改顺序表，所以用引用；因为要修改变量的值，所以用引用
- ret = DeleteList (L, 1, del);
- 顺序表中没有元素时，不可以删除
- 时间复杂度：最好：O(1); 最坏：O(n); 平均：O(n)
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
bool DeleteList(SqList &L,int loca,ElemType &dele)
{
if(loca < 1 || loca >L.length)
return false;
if(L.length == 0)
return false;
dele=L.data[loca-1];
for(int j=loca-1;j<L.length-1;j++)
{
L.data[j]=L.data[j+1];
}
L.length--;
return true;
}
void PrintList(SqList L)
{
for(int i=0;i<L.length;i++)
{
printf("L.data[%d]=%d\n",i,L.data[i]);
}
}
int main(){
SqList L;
L.data[0]=1;
L.data[1]=10;
L.data[2]=100;
L.length=3;
ElemType del;
bool ret;
ret=DeleteList(L,1,del);
if(ret)
{
printf("删除成功\n");
printf("删除的数据为:%d\n",del);
PrintList(L);
}
else
{
printf("删除失败\n");
}
}
修改元素
- 用哪个数据修改哪个顺序表的哪个位置的数据值，返回修改之前的值
- bool AlterList (SqList &L,int loca,ElemType after,ElemType &before)
- 因为要修改顺序表，所以用引用；因为要修改变量的值，所以用引用
- ret = AlterList (L, 1, after, before);
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
bool AlterList(SqList &L,int loca,ElemType after,ElemType &before)
{
if(loca < 1 || loca >L.length)
return false;
before=L.data[loca-1];
L.data[loca-1]=after;
return true;
}
void PrintList(SqList L)
{
for(int i=0;i<L.length;i++)
{
printf("L.data[%d]=%d\n",i,L.data[i]);
}
}
int main(){
SqList L;
L.data[0]=1;
L.data[1]=10;
L.data[2]=100;
L.length=3;
ElemType before;
ElemType after=88;
bool ret;
ret=AlterList(L,1,after,before);
if(ret)
{
printf("修改成功\n");
printf("修改前的数据为:%d\n",before);
PrintList(L);
}
else
{
printf("修改失败\n");
}
}
查找元素
- 在哪个顺序表查找哪个数据值，返回数据值的位置
- bool FindList (SqList &L,ElemType dat,int &loca)
- 因为要修改顺序表，所以用引用；因为要修改变量的值，所以用引用
- ret = FindList (L, 10, loca);
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
bool FindList(SqList &L,ElemType dat,int &loca)
{
int i;
for(i=0;i<L.length;i++)
{
if(L.data[i] == dat)
{
loca=i+1;
return true;
}
}
return false;
}
void PrintList(SqList L)
{
for(int i=0;i<L.length;i++)
{
printf("L.data[%d]=%d\n",i,L.data[i]);
}
}
int main(){
SqList L;
L.data[0]=1;
L.data[1]=10;
L.data[2]=100;
L.length=3;
ElemType dat;
int loca;
bool ret;
ret=FindList(L,10,loca);
if(ret)
{
printf("查找成功\n");
printf("第一次出现的位置为:%d\n",loca);
}
else
{
printf("查找失败\n");
}
}
