数据结构第二章 ——线性表之顺序表

文章目录

- 数据结构第二章 ——线性表之顺序表
- - 基本
  - 插入
  - 删除
  - 前驱
  - 后继
  - 逆置

基本

//INIT 初始化 
Status SqInit(Sqlist &L){
	L.elem=(ElemType *)malloc (List_Init_Size*sizeof(ElemType));
	if (!L.elem)
		exit(OVERFLOW);
	else
		printf("创建成功！n");
	L.length=0;
	L.listsize=List_Init_Size;
}
//SqEmpty 判空 
Status SqEmpty(Sqlist L){
	if (L.length==0)
		printf("空表n");
	else
	printf("不是空表n");
	return OK;	
}
//SqClear 重置线性表是将长度归零 
Status SqClear(Sqlist &L){
	if(!L.elem)		//判断线性表是否存在 
		exit(OVERFLOW);
	L.length=0;
	printf("重置成功!n");
	return OK;
}
//SqLength 返回线性表长度 
Status SqLength(Sqlist L){
	if(!L.elem)		//判断线性表是否存在 
		exit(OVERFLOW);
	return L.length;
} 
//SqDisplay 打印 
void SqDisplay(Sqlist L){
	int i;
    for (i=0;i
        printf("%5d",L.elem[i]);
    }
    printf("n");
}
//SqDestroy	销毁 
Status SqDestroy(Sqlist &L){
	if (L.elem) {			// 检查是否为空
		free(L.elem);	// 删除分配的内存
		L.elem = NULL;		// 基地址设为空
	}		
	L.length = 0;			// 表长设为0
	L.listsize = 0;				// 表空间设为0
}
//SqGetElem 取顺序表中某个元素
Status SqGetElem(Sqlist L,int pos,ElemType e){
	e = L.elem[pos-1];
	return e;
}
//SqLocateElem 返回第一次出现elem的位置
Status SqLocateElem(Sqlist L,ElemType e){
	int i;
	int number =0;
	int pos;
	for (i=0;i
		if (L.elem[i]==e){
			pos = i+1;
			number++;
		}
	}
	if(number == 0)
		pos =number;
	return pos;
}

插入

//SqInsert
//顺序表的插入需将插入位置（含）后面的元素都往后移
//	1.往后移，因为是顺序表，所以从后往前移动，故 i =  L.length-1
//	2.一直到插入位置（含）都需要移动，故 i =  i>=pos-1 （我们说的插入位置即 pos 是正序（从 1 开始），所以在数组中的位置为 pos-1 ，又因为含所以要 = 
// 	3.所谓后移，即右移 即  L.elem[i+1]=L.elem[i] （将左边的值赋给右边） 
Status SqInsert(Sqlist &L,int pos,ElemType e){
	int i;
//判断插入的合法性 
	if(pos<1 || pos>L.length+1)		//i值太小或太大，均不合法，注意可以插入到最后一个元素的后面那个空白处
		return ERROR;
	//再判断L是否空间已满，如果已满，需要拉大10个空间
	if(L.length>=L.listsize)
	{
		L.elem=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(L.elem==NULL)
		{
			printf("对不起，申请空间失败，程序将退出n");
			exit(OVERFLOW);
		}
		L.listsize+=LISTINCREMENT;		//总空间大小加10
	}
//核心 
	for (i=L.length-1;i>=pos-1;i--){
		L.elem[i+1]=L.elem[i];
	}
	L.elem[pos-1]=e;
	L.length++;
	return OK;
}

删除

//Delete
//顺序表的删除需将删除位置（不含）后面的元素都往前移
//	1.往前移，因为是顺序表，所以从插入位置往前移动，故 i = pos （不含，所以为 pos）   d
//	2.范围为直到末尾即 L.elem[i-1] 
// 	3.所谓前移，即左移 即  L.elem[i-1]=L.elem[i]（将右边的值赋值给左边） 
Status SqDelete(Sqlist &L,int pos,int &e){ 
	int i;
	e = L.elem[pos-1];
	
	if(pos<1 || pos>L.length+1){		//pos值太小或太大，均不合法，
		printf("删除位置不合法！n");
		return ERROR;
		} 
	
	for (i=pos;i
		L.elem[i-1]=L.elem[i];
	}
	L.length--;
}

前驱

//SqPriorElem    cur 在L第一次出现，则返回它的前面一个 pir		
Status SqPriorElem(Sqlist L,int cur,int pir){
	int i;
	int number = 0;
	
	for (i=0;i
		if (L.elem[i]==cur ){
			pir =L.elem[i-1];
			break;
		}
		number++;
	} 
	if(number==0){
		printf("当前为第一个元素，没有前驱！n");
		return ERROR;
	}
	else 
		printf("%d的前驱元素为：%dn",cur,pir);
}

后继

//SqSubsequent    cur 在L第一次出现，则返回它的后面一个 sub	
Status SqSubsequent(Sqlist L,int cur,int sub){
	int i;
	int number = 0;
	
	for (i=0;i
		if (L.elem[i]==cur ){
			sub =L.elem[i+1];
			break;
		}
		number++;
	}
	if(number==L.length-1){
		printf("当前为最后一个元素，没有后继！n");
		return ERROR;
	}else 
		printf("%d的后继元素为：%dn",cur,sub);
}

逆置

//SqConver 以对称位置，两两互换
Status SqConver(Sqlist &L){
	int t;
	int i,j;
	for(i=0,j=L.length-1;i<=L.length/2&&j>=L.length/2;i++,j--){
		t=L.elem[i];
		L.elem[i]=L.elem[j];
		L.elem[j]=t;
	}
}

合：

//数据结构第二章  
//线性表之顺序表 
#include
#include

#define  TRUE    			1
#define  FLASE   			0
#define  OK     			1
#define  ERROR   			0
#define  INFEASIBLE 		-1
#define  OVERFLOW       	-2

typedef int Status;
typedef int ElemType; 


#define List_Init_Size 100
#define LISTINCREMENT 10

//顺序表的结构体定义 
typedef struct 
{
	ElemType *elem; 					//元素数组 
	int length; 	     				//长度 
	int listsize;						//当前分配的存储容量 
 }Sqlist;								//顺序表类型的定义 
 
Status SqClear(Sqlist &L);
Status SqDelete(Sqlist &L,int pos,int &e);
void SqDisplay(Sqlist L);
Status SqEmpty(Sqlist L);
Status SqGetElem(Sqlist L,int pos,ElemType e);
Status SqInit(Sqlist &L);
Status SqInsert(Sqlist &L,int pos,ElemType e);
Status SqLength(Sqlist L);
Status SqLocateElem(Sqlist L,ElemType e);
Status SqPriorElem(Sqlist L,int cur,int pir);
Status SqSubsequent(Sqlist L,int cur,int sub);
Status SqConver(Sqlist &L);
Status SqDestroy(Sqlist &L);

int main(){
	int i,j,t,m;
	ElemType e;
	int h;
	int num; 
	int k;
	int p1,p2;
//SqInit	
	Sqlist L;
	SqInit(L);
//SqInsert
	for ( i=1; i<=10 ;i++) {
        L.elem[i-1]=i;
        L.length++;
    }
    printf("插入前数据为：n");
    SqDisplay(L);
    SqEmpty(L); 
    printf("顺序表长度为：%2dn",SqLength(L));
    //num=SqPriorElem(L,5,num);
    //printf("5第一次出现在%d",num);
	SqInsert(L,5,100);
	
	printf("插入后数据为：n");
	SqDisplay(L);
    printf("顺序表长度为：%2dn",SqLength(L));
//SqGetElem
    printf("请输入要返回元素的位置：");
    scanf("%d",&h);
    e=SqGetElem(L,h,e);
    printf("顺序表中第%2d个元素为%2dn",h,e);
    
    printf("请输入要查找元素：");
    scanf("%d",&m);
    t=SqLocateElem(L,m);
    if (t==0)
    	printf("顺序表中没有找到%dn",m);
    else 
    	printf("顺序表中出现%d的位置是%dn",m,t);
    SqDisplay(L);
//SqPriorElem

	SqPriorElem(L,m,k);
//SqSubsequent
	SqSubsequent(L,m,k);
	SqDisplay(L);
//SqDelete
	SqDelete(L,m,j);
	printf("删除元素%2d成功n",j);
	printf("删除元素后为:n");
	SqDisplay(L);
	
    printf("逆置后：n");
    SqConver(L);
    SqDisplay(L);
	
	SqLength(L);
	printf("顺序表长度为：%2dn",SqLength(L)); 

	//SqClear(L);
	SqDestroy(L);
	SqDisplay(L);

	return 0;
}
//INIT 初始化 
Status SqInit(Sqlist &L){
	L.elem=(ElemType *)malloc (List_Init_Size*sizeof(ElemType));
	if (!L.elem)
		exit(OVERFLOW);
	else
		printf("创建成功！n");
	L.length=0;
	L.listsize=List_Init_Size;
}
//SqEmpty 判空 
Status SqEmpty(Sqlist L){
	if (L.length==0)
		printf("空表n");
	else
	printf("不是空表n");
	return OK;	
}
//SqClear 重置线性表是将长度归零 
Status SqClear(Sqlist &L){
	if(!L.elem)		//判断线性表是否存在 
		exit(OVERFLOW);
	L.length=0;
	printf("重置成功!n");
	return OK;
}
//SqLength 返回线性表长度 
Status SqLength(Sqlist L){
	if(!L.elem)		//判断线性表是否存在 
		exit(OVERFLOW);
	return L.length;
} 
//SqDisplay 打印 
void SqDisplay(Sqlist L){
	int i;
    for (i=0;i
        printf("%5d",L.elem[i]);
    }
    printf("n");
}
//SqDestroy	销毁 
Status SqDestroy(Sqlist &L){
	if (L.elem) {			// 检查是否为空
		free(L.elem);	// 删除分配的内存
		L.elem = NULL;		// 基地址设为空
	}		
	L.length = 0;			// 表长设为0
	L.listsize = 0;				// 表空间设为0
}
//SqGetElem 取顺序表中某个元素
Status SqGetElem(Sqlist L,int pos,ElemType e){
	e = L.elem[pos-1];
	return e;
}
//SqLocateElem 返回第一次出现elem的位置
Status SqLocateElem(Sqlist L,ElemType e){
	int i;
	int number =0;
	int pos;
	for (i=0;i
		if (L.elem[i]==e){
			pos = i+1;
			number++;
		}
	}
	if(number == 0)
		pos =number;
	return pos;
}
//SqInsert
//顺序表的插入需将插入位置（含）后面的元素都往后移
//	1.往后移，因为是顺序表，所以从后往前移动，故 i =  L.length-1
//	2.一直到插入位置（含）都需要移动，故 i =  i>=pos-1 （我们说的插入位置即 pos 是正序（从 1 开始），所以在数组中的位置为 pos-1 ，又因为含所以要 = 
// 	3.所谓后移，即右移 即  L.elem[i+1]=L.elem[i] （将左边的值赋给右边） 
Status SqInsert(Sqlist &L,int pos,ElemType e){
	int i;
//判断插入的合法性 
	if(pos<1 || pos>L.length+1)		//i值太小或太大，均不合法，注意可以插入到最后一个元素的后面那个空白处
		return ERROR;
	//再判断L是否空间已满，如果已满，需要拉大10个空间
	if(L.length>=L.listsize)
	{
		L.elem=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(L.elem==NULL)
		{
			printf("对不起，申请空间失败，程序将退出n");
			exit(OVERFLOW);
		}
		L.listsize+=LISTINCREMENT;		//总空间大小加10
	}
//核心 
	for (i=L.length-1;i>=pos-1;i--){
		L.elem[i+1]=L.elem[i];
	}
	L.elem[pos-1]=e;
	L.length++;
	return OK;
}
//Delete
//顺序表的删除需将删除位置（不含）后面的元素都往前移
//	1.往前移，因为是顺序表，所以从插入位置往前移动，故 i = pos （不含，所以为 pos）   d
//	2.范围为直到末尾即 L.elem[i-1] 
// 	3.所谓前移，即左移 即  L.elem[i-1]=L.elem[i]（将右边的值赋值给左边） 
Status SqDelete(Sqlist &L,int pos,int &e){ 
	int i;
	e = L.elem[pos-1];
	
	if(pos<1 || pos>L.length+1){		//pos值太小或太大，均不合法，
		printf("删除位置不合法！n");
		return ERROR;
		} 
	
	for (i=pos;i
		L.elem[i-1]=L.elem[i];
	}
	L.length--;
} 
//SqPriorElem    cur 在L第一次出现，则返回它的前面一个 pir		
Status SqPriorElem(Sqlist L,int cur,int pir){
	int i;
	int number = 0;
	
	for (i=0;i
		if (L.elem[i]==cur ){
			pir =L.elem[i-1];
			break;
		}
		number++;
	} 
	if(number==0){
		printf("当前为第一个元素，没有前驱！n");
		return ERROR;
	}
	else 
		printf("%d的前驱元素为：%dn",cur,pir);
}
//SqSubsequent    cur 在L第一次出现，则返回它的后面一个 sub	
Status SqSubsequent(Sqlist L,int cur,int sub){
	int i;
	int number = 0;
	
	for (i=0;i
		if (L.elem[i]==cur ){
			sub =L.elem[i+1];
			break;
		}
		number++;
	}
	if(number==L.length-1){
		printf("当前为最后一个元素，没有后继！n");
		return ERROR;
	}else 
		printf("%d的后继元素为：%dn",cur,sub);
}
//逆置
//以对称位置，两两互换
Status SqConver(Sqlist &L){
	int t;
	int i,j;
	for(i=0,j=L.length-1;i<=L.length/2&&j>=L.length/2;i++,j--){
		t=L.elem[i];
		L.elem[i]=L.elem[j];
		L.elem[j]=t;
	}
}

数据结构第二章 ——线性表之顺序表

C/C++/C#相关栏目本月热门文章