数据结构-顺序表操作

1、插入操作：

        （1）判断插入的位置是否合理。

                ①不能大于所有元素再加1的值，否则按一次插入一个元素来讲，多出两个空位是不合理的。防止上溢出。

                ②不能插入小于1的值，防止下溢出。

        （2）给新插入的元素分配空间。

                ①这里使用realloc()函数用来给动态数组额外申请更多的物理空间。

                size+1:把顺序表的实际容量增加一个单位。

        （3）进行插入操作时，要目标位置开始的元素依次向后移动，最后将目标位置腾出，把元素放入其中。

                length++:是顺序表中存放的数据加一。

 
//向数据表中插入元素
table insertTable(table t,int elem,int pos)//t:顺序表结构体、elem：要插入的元素 pos:插入的位置 
{
	//1、检测插入位置是否合理：如果大于长度+1或者小于1则不合理
	if(pos>t.length+1||pos<1)
	{
		printf("插入位置有问题\n");
		return t;	
	}	
	//2、插入操作前，先检查顺序表中是否有空余位置，如果没有动态分配一个位置
	if(t.length>=t.size)//逻辑表长==实际空间大小
	{
		t.head=(int*)realloc(t.head,(t.size+1)*sizeof(int));
		if(!t.head)
		{
			printf("存储分配失败。\n");
			return t;	
		}	
		//分配成功，实际大小加一
		t.size+=1; 
	} 
	//3、插入操作，从插入位置开始的后续元素逐个后移
	for(int i=t.length-1;i>=pos-1;i--)
	{
		t.head[i+1]=t.head[i];	
	} 
	//4、向腾出的位置中插入目标元素
	t.head[pos-1]=elem;
	//5、逻辑表长+1
	t.length++;
	
	return t; 
} 

2、删除操作： 

        （1）判断删除元素的位置是否正确。

                        ①不能大于所有元素的实际个数，否则没有意义。

                        ②不能小于1，否则无意义。       

（2）进行删除操作，从目标元素开始，将它后面的元素依次向前一个元素进行覆盖。

table delTable(table t,int pos)
{
	//1、判断删除位置是否有误 
	if(pos>t.length||pos<1)
	{
		printf("被删除元素的位置有误\n");
		return t;		
	}
	
	//2、删除操作
	for(int i=pos;i
	{
		t.head[i-1]=t.head[i];	
	} 
	
	//3、长度-1
	t.length--; 
	
	return t;
}

3、查找操作：

        （1）从顺序表的第一个元素开始进行顺序查找。

//顺序表查找操作
int selectTable(table t,int elem)
{
	for(int i=0;i
	{
		if(t.head[i]==elem)
		{
			return i+1;	
		}	
	}	
	return -1;//查找失败返回-1	
} 

4、修改操作：

        （1）可以通过函数嵌套，用查找函数找到目标位置，然后通过数组下标进行赋值。

//顺序表修改元素
table changeTable(table t,int elem,int newElem)
{
	int pos=selectTable(t,elem);//1、先查找到目标元素位置
	t.head[pos-1]=newElem;//2、用新的值进行原来位置的覆盖
	return t;	
} 

5、完整代码：

#include
#include
#define Size 5
 
//定义顺序表 
typedef struct Table{
	int *head;//动态数组首地址 
	int length;//数组逻辑长度 
	int size;//数组物理长度 
}table;//给struct Table起的别名
 
//顺序表的初始化 
table initTable(){
	table t;
	t.head=(int*)malloc(Size*sizeof(int));//给数组分配整块的地址空间
	if(!t.head)
	{
		printf("初始化失败\n");
		exit(0);	
	}
	t.length=0;
	t.size=Size;
	return t; 
} 
 
//顺序表的插入
table insertTable(table t,int elem,int pos){
	//1、判断插入位置是否合理
	if(pos<1||pos>t.length+1){
		printf("插入位置错误！\n");
		return t;	
	} 
	//2、为插入值新分配一个空间
	if(t.length>=t.size){
		t.head=(int*)realloc(t.head,(t.size+1)*sizeof(int));
		if(!t.head)
		{
			printf("新分配空间失败！\n");
		}
		t.size+=1;
	} 
	//3、插入操作
	for(int i=t.length-1;i>=pos-1;i--){
		t.head[i+1]=t.head[i];
	} 
	t.head[pos-1]=elem;
	t.length++;
	return t;
}
 
//顺序表的删除
table delTable(table t,int pos){
	//1、判断删除位置是否合理
	if(pos>t.length||pos<1){
		printf("删除位置错误！\n"); 
		return t;
	}
	//2、删除操作 
	for(int i=pos-1;i
		t.head[i]=t.head[i+1];
	}
	t.length--;
	return t;
	 
} 
 
//顺序表的查找
int searchTable(table t,int elem){
	for(int i=0;i
		if(t.head[i]==elem){
			return i+1;
		}
	}
}
 
 
//顺序表的修改
table changeTable(table t,int elem,int newElem){
	int pos = searchTable(t,elem);
	t.head[pos-1]=newElem;
	return t;
}
 
 
//输出顺序表中的元素
void displayTable(table t){
	for(int i=0;i
		printf("%d ",*(t.head+i));
	}
	printf("\n");
}
 
int main()
{
	//顺序表初始化并赋值 
	table t=initTable();
	for(int i=0;i
		t.head[i]=i;
		t.length++;
	}
	//原顺序 
	printf("顺序表原顺序 : "); 
	displayTable(t);
	
	//向t中插入元素 
	printf("第二个位置插入元素 9 : "); 
	t=insertTable(t,9,2);
	displayTable(t);
	
	//删除t中元素
	printf("删除位置三中的元素 : "); 
	t=delTable(t,3);
	displayTable(t);
	
	//查找t中元素
	int a = searchTable(t,3);
	printf("查找顺序表中3的位置 : %d\n",a); 
	
	//修改t中元素 
	printf("将顺序表中的2修改成8 : "); 
	t=changeTable(t,2,8);
	displayTable(t);
	
	return 0;
} 

输出结果：