【数据结构C++代码】1 顺序表（数组）

#include<iostream>
#include<stdlib.h>
using namespace std;

#define maxsize 30 
#define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10// 线性表存储空间的分配增量

typedef struct
{
	int age;
	char sex;
}Elemtype;
//1.静态数组 
typedef struct
{
	Elemtype data[maxsize];
	int length;//当前长度 
	int listsize;//容量 规模 
}SqList001;//SqList001现在是一个顺序表数据类型；
//2.动态数组
typedef struct
{
	Elemtype *elem;//基地址
	int length;//当前长度 
	int listsize;  // 当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;//顺序表

//初始化

int initSq(SqList &L)
{
	L.elem=(Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype));//初分配
	if(!L.elem )
		return 0;
	L.listsize=LIST_INIT_SIZE; 
	L.length=0;
	return 1;
}//initSq

//摧毁线性表

int destorySq(SqList &L) 
{
	free(L.elem);
	return 0;
}

//判断顺序表是否为空

int listEmpty(SqList L)
{
	if(L.length==0)
		return 1;
	else
		return 0;
}

//求表长

int lengthSq(SqList L) 
{
	return L.length;
}

//求前驱的值 PriorElem

int priorElem(SqList L,int pos,Elemtype &pre)
{
	if(pos<=0 || L.length==0 ||pos>L.length )
		return 0;
	else
		pre=L.elem[pos-1];
	return 1;
} 

//插入 输入的是序号 实际是下标+1

int insertSq(SqList &L,int pos,Elemtype e)//在L的第i个元素之前插入
{//新元素应该在L.elem[i-1]这个下标 

	if(pos<1 || pos>L.length+1 )//位置不合法
		return 0;
	if(L.length>=L.listsize )//当前存储空间已满，增加分配
	{
		L.elem=(Elemtype*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(Elemtype));
		if(!L.elem )return 0;
		L.listsize=L.listsize+LISTINCREMENT;
	}
	//插入 倒序
	//1.数组实现 
	for(int j=L.length-1 ; j>=pos-1;j-- )
	{
		L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移
	}
	L.elem[pos-1]=e;
	L.length++;
	
	//2.指针实现 
	
//	Elemtype* q=&(L.elem[pos-1]);//应该在这个位置 
//	for( Elemtype* p=&(L.elem[L.length-1]; p>=q; p--))//从最后一个元素 
//	{
//		*(p+1)=*p;//后移 
//	} 
//	*q=e;
//	L.length++;
	
	 
	return 1; 
}

//删除元素

int deleteSq(SqList &L,int pos,Elemtype &e)//删除第POS个元素，下标为pos-1 
{
	if(pos<1 ||pos>L.length )
		return 0;
		
	//1.数组实现 
	e=L.elem[pos-1];//下标
	for(int i=pos-1;i<=L.length-2;i++) 
	{
		L.elem[i]=L.elem[i+1];
	}
	L.length--;
	
	//2.指针实现
//	Elemtype *p=&(L.elem[pos-1]);
//	e=*p;
//	Elemtype *last = &(L.elem[L.length-1]);
//	for(p;p<last;p++ )
//	{
//		*p=*(p+1);//后一位赋值给当前位
//	} 
//	L.length--;
	
	return 1;
} 

void traverseSq(SqList L)
{
	cout<<"\n---traverseSq----\n";
	for(int i=0;i<L.length;i++)
	{
		cout<<"age:"<<L.elem[i].age<<" sex:"<<L.elem[i].sex <<endl;
	}
}

//主函数

int main()
{
	SqList L;
	initSq(L);
	Elemtype e;
	
	for(int i=0;i<10;i++)
	{
		e.age=i+1;
		e.sex='m';
		insertSq(L,i+1,e);
	}
	traverseSq(L);
	deleteSq(L,3,e);
	cout<<"\ndelete:"<<"age:"<<e.age<<" sex:"<<e.sex <<endl;
	traverseSq(L);
	return 0;
}

/*

—traverseSq----
age:1 sex:m
age:2 sex:m
age:3 sex:m
age:4 sex:m
age:5 sex:m
age:6 sex:m
age:7 sex:m
age:8 sex:m
age:9 sex:m
age:10 sex:m

delete:age:3 sex:m

—traverseSq----
age:1 sex:m
age:2 sex:m
age:4 sex:m
age:5 sex:m
age:6 sex:m
age:7 sex:m
age:8 sex:m
age:9 sex:m
age:10 sex:m

*/