[数据结构与算法]线性表的顺序表删除-----数据结构与算法笔记

一、线性表的顺序删除操作

参考书（《数据结构（C语言）》–严蔚敏等编著，清华大学出版社）
在实现顺序表的删除操作的同时，还要对表进行合法性的判断，具体相关步骤如下：
删除思想：

1、在使用删除函数时判断删除位置的合法性，i<1 || i>length都是不合法的；
2、将第i位置的元素删除；
3、将第i+1之后的元素前移，补齐位置；
4、表长-1；

相关代码：

#include "stdio.h"
#include "stdlib.h"
#define 	ERROR	0
#define		OK		1
#define 	TRUE	1
#define		FALSE	0
#define		OVERFLOW	-2
#define 	LIST_INIT_SIZE	100
#define		LISTINCREMENT	10

typedef int Status;
typedef int ElemType;
typedef struct {
	ElemType	*elem;	//存储空间基址
	int		length;		//当前长度
	int 	listsize;	//当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;

Status InitList_Sq(SqList &L);
//初始化创建一个空的顺序表L
Status InitList_Sq(SqList &L) {
	L.elem = (ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem) exit(OVERFLOW);	//判存储分配情况
	L.length=0;		//空表
	L.listsize=LIST_INIT_SIZE;	//定义初始容量
	return OK;
}

Status ListAdd_Sq(SqList &L,int n);
//顺序表的元素添加,此函数适用于存入12345....的元素，可自行修改 
Status ListAdd_Sq(SqList &L,int n) {
	if (L.length+1 >= L.listsize) { //当线性表长度已经大于存储空间，就分配更多的空间
		ElemType* newbase = (ElemType*)realloc(L.elem,
		       (L.listsize + LISTINCREMENT) * sizeof(ElemType)); //每次多分配十个
		if (!newbase)exit(OVERFLOW);
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	//int num = L.length;
	for(int i=0; i<n; i++) {
		L.elem[i] = i+1;
		L.length++;
	}
	return OK;
}

Status ListInsert_Sq(SqList &L, int i, ElemType e);
//在L中的第i个位置之前添加新的元素e
Status ListInsert_Sq(SqList &L, int i, ElemType e) {
//i的合法值为1<=i<=ListLength_Sq(L)+1
	if(i<1 || i>L.length+1) return ERROR;	//当i小于1或者i大于顺序线性表L的值，则不合法。当i等于L.length时，表示插入到线性表结尾
	if(L.length >= L.listsize) {	//当线性表长度已经大于存储空间，就分配更多的空间
		ElemType *newbase = (ElemType *) realloc (L.elem,
		        (L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase) exit(OVERFLOW);
		L.elem = newbase;
		L.listsize+=LISTINCREMENT;
	}
	/*
	ElemType* q = &(L.elem[i-1]);   //q为插入位置的地址，i-1是因为数组下标从零开始
	for (ElemType* p = &(L.elem[L.length - 1]); p >= q; --p)*(p + 1) = *p;
	*q = e;
	++L.length;
	*/
	for(int j=L.length-1; j>=i-1; j--)
		L.elem[j+1] = L.elem[j];	//往后赋值(后移
	L.elem[i-1] = e;	//将e值赋值到i-1的位置
	L.length++;
	return OK;
}

Status ListDelete_Sq(SqList &L, int i, ElemType e);
//在L中删除第i个元素，并用e返回其值
Status ListDelete_Sq(SqList &L, int i, ElemType e) {
	if(i<1 || i>L.length) return ERROR;	//删除位置不合法
	ElemType *p=&(L.elem[i-1]);	//p为被删除元素的位置
	e = *p;
	ElemType *q = L.elem + L.length - 1;	//表尾的元素位置
	for(p++; p<=q; p++)   //因为p为被删除元素的位置，所以要从被删除元素的后一位开始往前面移动
		*(p - 1) = *p;
	L.length--;
	return OK;
}

Status DestoryList_Sq(SqList &L);
//销毁顺序表L
Status DestoryList_Sq(SqList &L) {
	if(L.elem) delete L.elem;
}

Status LocateElem_Sq(SqList L,ElemType e);
//查找定位第一个元素e的位置
Status LocateElem_Sq(SqList L,ElemType e) {
	int i;
	for(i=0; i<L.length; i++)
		if(L.elem[i]==e) return i+1;
	return OK;
}

Status GetElem_Sq(SqList L, int i, ElemType &e);
//取顺序表中i的位置的元素
Status GetElem_Sq(SqList L, int i, ElemType &e) {
	if(i<1 || i>L.length) return ERROR;	//取值位置合法性
	e=L.elem[i-1];
	return OK;
}

Status DisplayList_Sq(SqList L);
//打印顺序表(如1,2,3,4,5,6...)
Status DisplayList_Sq(SqList L) {
	if(!L.elem) return ERROR;
	for(int i=0; i<L.length; i++) {
		if(i<L.length-1) printf("%d,",L.elem[i]);
		else printf("%d",L.elem[i]);
	}
	return OK;
}

int main(void) {
	SqList L;
	InitList_Sq(L);
	int n,i,e;
	//scanf("%d",&n);
	ListAdd_Sq(L,5);
	scanf("%d",&i);	//删除位置
	if(ListDelete_Sq(L,i,e))
		DisplayList_Sq(L);
	else
		printf("删除位置非法");
	return OK;
}

实现：