线性表的定义和基本操作

学习目标

线性表定义：具有相同数据类型的n个数据元素的有序序列。
顺序表定义：

特点

基本操作

1. 定义
   静态：

#include<stdio.h>
#include<stdlib.h>

#define MaxSize 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(void)
{
	SqList L;
	InitList(L);
	
	for(int i=0;i<L.length;i++){
		printf("the data %d is %d",i,L.data[i]);
	}
	
	return 0;
}

动态：

#include<stdio.h>
#include<stdlib.h>

#define InitSize 10

typedef struct{
	int *data;
	int MaxSize;//最大容量 
	int length;//当前长度 
}SeqList;

void Init(SeqList &L)
{
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}

int main(void){
	
	return 0;
}

2. 插入
   静态：

//插入操作,bool用于判断操作是否成功 (处理异常情况) 
bool ListInsert(SqList &L,int i,int e){
	if(i<1 || i>L.length+1) return false;//条件判断 
	if(L.length >= MaxSize) return false;
	
	for(int j=L.length;j>=i;i--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
}

动态：

3. 删除
   静态：

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;
}

动态顺序表以及各个操作

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10

typedef struct{
	int *data;
	int MaxSize;
	int length;
}SqList;

void debug(SqList L){
	printf("当前顺序表的数据为length=%d maxsize=%d\n",L.length,L.MaxSize);
}
//初始化
void InitList(SqList &L){
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}
 
//增加动态数组的长度
void IncreaseSize(SqList &L,int len){
	int *p=L.data;
	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];//将数据复制到新区域 
	}
    L.MaxSize=L.MaxSize+len;//顺序表最大长度增加len 
	free(p);//释放空间		
} 

//插入操作
bool ListInsert(SqList &L,int i,int e){
	//范围判断 
	if(i<1 || i>L.length+1)
		return false;
	if(L.length>L.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;
} 

删除操作,删除第i个数据并且返回被删除的数据 
bool ListDelete(SqList &L,int i,int &e)
{
	//范围判断
	 if(i<1 || i>L.length+1) return false;
	 else{
	 	//保存删除元素
		 e=L.data[i]; 
	 	for(int j=i;j<L.length;j++)
	 	{
		 L.data[j]=L.data[j+1];
	    }
	    L.length--;
	 } 
	 return true;
 } 

//按位查找
int getElemBybit(SqList L,int i){
	//Check if the line has been crossed
	if(i<1 || i>L.length){
		printf("Cross the border!");
		return 0;
	}
	
	return L.data[i-1];
} 

//按值查找
int getElemByValue(SqList L,int value){
	for(int i=0;i<L.length;i++)
	{
		if(L.data[i] == value)
		{
			return i-1;
		}
	}
	printf("Can`t find the elem!");
	
	return 0;
} 

//打印操作
void print(SqList L){
	for(int i=0;i<L.length;i++)
	{
		printf("%d ",L.data[i]);
	}
	printf("\n");
} 

//测试函数 
int main(void){
	SqList L;debug(L);
	InitList(L);debug(L);
	
	for(int i=0;i<L.MaxSize;i++)
	{
		L.data[i]=i;
	    L.length++;
	}
	IncreaseSize(L,5);debug(L);
	
	print(L);
	if(ListInsert(L,2,5)){
	printf("插入成功,插入后数值");
		print(L);
	}else printf("插入失败");
	
	int e=0;
	if(ListDelete(L,3,e))
	{
		print(L);
		printf("被删除元素为：%d",e);
	}

    int value,position;
	printf("\nPlease input the value and the position:");  
    scanf("%d %d", &value, &position);  
	printf("\nget the emlem by value :the elem position is%d\n",getElemByValue(L,value));
	printf("\nget the emlem by positon:the value is%d\n",getElemBybit(L,position));
	
	return 0;
}