数据结构之顺序表

线性表的逻辑结构

线性表是由n个类型相同的数据元素组成的有限序列，记为（a1，a2，…，ai-1，ai，ai+1，…，an）。其中，这里的数据元素可以是原子类型，也可以是结构类型。线性表的数据元素存在着序偶关系，即数据元素之间具有一定的次序。在线性表中，数据元素ai-1在ai的前面，ai又在ai+1的前面，可以把ai-1称为ai的直接前驱元素，ai称为ai+1的直接前驱元素。ai称为ai-1的直接后继元素，ai+1称为ai的直接后继元素。

线性表的顺序存储结构—顺序表

顺序表：用一段地址连续的存储单元依次存储线性表的数据元素。由图可知数据元素的存储地址是其序号的线性函数，即计算任意一个存储结构的时间是相等的，具有这个特点的存储结构被称为随机存取结构

顺序表的C语言实现：

#include<stdio.h>
#include<stdlib.h>
//顺序表的定义

//定义顺序表的最多存放100个元素
#define MaxSize 100 
//定义顺序表的元素类型为int 
typedef int DataType;

//定义顺序表的结构体
typedef struct{
	//存放数据元素的数组
	DataType data[MaxSize];
	//顺序表的长度
	int length;
}SeqList;

//初始化顺序表,设置长度为零

void InitList(SeqList *L){
	L->length = 0;
}

//建立顺序表
int CreateList(SeqList * L , DataType a[],int n ){
	
	if (n>MaxSize){
		printf("顺序表存储空间不够，无法创建数据表\n");
		return 0;
	}
	for (int i = 0 ; i<n ; i++){
	
		L->data[i] = a[i];
	
	}
	L->length = n;
	return 1;
}

//销毁顺序表
//由于顺序表是静态存储分配，在顺序表变量退出作用域的时候自动释放变量所占用的内存单元
//因此顺序表无需销毁


//判空操作
int Empty(SeqList * L){
	
	if(L->length == 0) return 1;
	else return 0;
	
}


//取长度操作

int Length(SeqList *L){
	return L->length;
}

//遍历操作

void PrintList(SeqList * L){
	for(int i = 0;i<L->length;i++){
		printf("%d\t",L->data[i]);
	}
}

//按值查找
int Locate(SeqList * L,DataType x){

	for(int i = 0 ; i < L->length ; i++){
		
		if (x == L->data[i]){
			return i+1;
		}
	}
	
	return 0;

}

//按位查找
int Get(SeqList * L,int n,DataType * ptr){
	
	if(n>L->length || n< 1){
		printf("查找位置非法，查找失败\n");
		return 0;
	}else{
		*ptr = L->data[n];
		return 1;
	}
}

//插入操作
int Insert(SeqList * L,int n ,DataType x){
	if(L->length >= MaxSize ) {
		printf("上溢错误，插入失败\n");
	}
	
	if( n<1 || n>(L->length+1)) {
		printf("位置错误，插入失败\n");
	}
	
	for(int j = L->length;j>=n;j--){
		
		L->data[j] = L->data[j-1];
	}
	L->data[n-1] = x;
	L->length++;
	return 1;
}

//删除操作

int Delete(SeqList * L,int n,DataType * ptr){
	if(L->length == 0){
		printf("下溢错误，失败\n");
		return 0;
	}
	if(n<1 || n > L->length ){
	
		printf("位置错误，删除失败\n");
		return 0;
	}
	
	for(int i = n; i < L->length ; i ++){
		L->data[i-1] = L->data[i];
	}
	L->length--;
	return 1;
	
	
}


//顺序表的使用
int main(){
	
	 int r[5] = {1,2,3,4,5};
	 int x,i;
	 
	 SeqList L;
	 
	 printf("建立顺序表");
	 CreateList(&L,r,5);
	 PrintList(&L);
	 
	 printf("执行插入\n");
	 Insert(&L,2,8);
	 printf("执行插入后的顺序表\n");
	 PrintList(&L);
	 
	 printf("顺序表的长度%d:\t" ,Length(&L));
	 
	 printf("请输入查找的值\n");
	 scanf("%d",&x);
	 i = Locate(&L,x);
	 
	 if(i == 0){
		 
		 printf("查找失败\n");
	 }else{
		 printf("元素%d的位置是：%d\n",x,i);
	 }
	 
	 
	 printf("请输入要查找第几个元素值\n");
	 scanf("%d",&i);
	 if(Get(&L,i,&x) == 1){
		 printf("第%d个元素的值为%d\n",i,x);
	 }
	 else{
		 printf("线性表中没有第%d个元素\n",i);
	 }
	 
	 
	 printf("请输入要删除第几个元素：\n");
	 scanf("%d",&i);
	 
	 if(Delete(&L,i,&x) == 1){
		 printf("删除第%d个元素是%d,删除数据为：\n",i,x);
		 PrintList(&L);
	 }else{
		 printf("删除失败\n");
	 } 
	 return 0; 
}