数据结构之线性表（顺序表）

目录

一、概念

1、线性表的定义

2、线性表的存储结构

3、顺序表的优缺点

二、顺序表的结构体定义和基本操作

1、顺序表的结构体定义

2、创建顺序表

3、查找数据元素

4、插入数据元素

5、删除数据元素

三、总结

四、源代码 

一、概念

1、线性表的定义

线性表是具有相同特性数据元素的一个有限序列。

线性表的长度：该序列中所含元素的个数（n>=0）;

n=0,表示线性表是一个空表。

2、线性表的存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种。

3、顺序表的优缺点

优点：存储密度大；可以随机存取表中任一元素。

缺点：在插入、删除某一元素时，需要移动大量元素；浪费存储空间；属于静态存储形式，数据元素的个数不能自由扩充。

二、顺序表的结构体定义和基本操作

1、顺序表的结构体定义

• 头文件以及宏定义

  #include
  #include 
  #define maxsize 100

• 顺序表的结构体定义

  typedef struct{
  	int data[maxsize];  //存放顺序表元素的数组
  	int length;        //存放顺序表的长度
  }SqList;

typedef：可以理解为给这个结构体取了个别名（SqList）,在后续的程序中就直接可以用SqList来定义结构体变量。 

2、创建顺序表

由数组元素num[0,...n-1 ]创建顺序表L。其方法是将数组num中的每个元素依次放入到顺序表中。

•   主函数

  #include
  #include 
  #define maxsize 100
  typedef struct{
  	int data[maxsize];
  	int length;
  }SqList;
  
  void createList(SqList &L,int a[],int n);   //创建顺序表
  void printList(SqList L);    //输出顺序表
  
  
  
  //方法二   直接用数组a中的元素来创建顺序表
  int main(){
  	SqList L;
  	int a[10]={1,2,3,4,5,6,7,8}; //定义一个数组存放数据元素
  
  	createList(L,a,6);   //创建一个顺序表 
  	
  	return 0;
  } 

• 创建顺序表

  //创建顺序表
  void createList(SqList &L,int a[],int n){
  	int i=0,k=0;           //k表示L中元素的个数,初始值位0; 
  	while(k  

• 输出顺序表

  //输出顺序表
  void printList(SqList L){
  	int i;
  	for(i=0;i  

结果：

3、查找数据元素

• 查找i位置上数据元素的值

  //找在i位置上是数据元素的值 （注意数组下标和物理位置的区别）
  int GetElement(SqList L,int i){
  	int e;    //定义一个变量保存查找到的元素
  	if(i<1||i>L.length)
  		return 0;   
  	e=L.data[i-1];
  	return e; 
  } 

•  按元素值查找,返回其下标 

  //按元素值查找,返回其下标 
  int  LocatElem(SqList L,int e){
  	int i=0;
  	while(L.data[i]!=e){
  		i++;
  	}
  	if(i>=L.length){    //没有找到返回-1 
  		return -1;
  	}
  	return i;          //找到了返回其下标 
  } 

4、插入数据元素

//插入数据元素
int insertList(SqList &L,int k,int e){
	int i;
	if(k<0||k>L.length-1||L.length==maxsize){   //位置错误或已经到达表长
		return 0;                            //此时插入不成功，返回0
	}
	for(i=L.length-1;i>=k;i--){
		L.data[i+1]=L.data[i];          //从后往前，逐个将元素后移一个位置
	}
	L.data[k]=e;               //将e放在k位置上
	L.length++;                //表长增1
	return 1;
} 

5、删除数据元素

//删除某个数据元素
int deleteList(SqList &L,int k) {
	int i;
	if(k<0||k>L.length-1)     //位置不对，返回0，表示删除不成功
		return 0;
	for(i=k;i 
三、总结 
 
 
重点掌握顺序表的查找、插入和删除；
 
四、源代码  
#include
#include 
#define maxsize 100
typedef struct{
	int data[maxsize];
	int length;
}SqList;


void createList(SqList &L,int a[],int n);   //创建顺序表

void initList(SqList &L);    //初始化线性表

void printList(SqList L);    //输出顺序表
 
bool ListEmpty(SqList L);   //判断顺序表是否为空

int Listlength(SqList L);   //求顺序表的长度 

int GetElement(SqList L,int i); //找在i位置上是数据元素的值 

int  LocatElem(SqList L,int e); //按元素值查找,返回其下标 

int insertList(SqList &L,int k,int e);  //插入数据元素

int deleteList(SqList &L,int k);  //删除某个数据元素


int main(){
	SqList L;
	int n;
//	scanf("%d",&n);
//	int num[n];
//	for(int i=0;iL.length)
		return 0;
	e=L.data[i-1];
	return e; 
} 

//按元素值查找,返回其下标 
int  LocatElem(SqList L,int e){
	int i=0;
	while(L.data[i]!=e){
		i++;
	}
	if(i>=L.length){    //没有找到返回-1 
		return -1;
	}
	return i;          //找到了返回其下标 
} 

//插入数据元素
int insertList(SqList &L,int k,int e){
	int i;
	if(k<0||k>L.length-1||L.length==maxsize){
		return 0;
	}
	for(i=L.length-1;i>=k;i--){
		L.data[i+1]=L.data[i];
	}
	L.data[k]=e;
	L.length++;
	return 1;
} 

//删除某个数据元素
int deleteList(SqList &L,int k) {
	int i;
	if(k<0||k>L.length-1)
		return 0;
	for(i=k;i 
此代码的结果图：