数据结构 线性表 插入 删除_线性表插入x到位置i

数据结构线性表的插入，删除

任务描述
本关任务：实现 step1/Seqlist.cpp 中的SL_InsAt、SL_DelAt和SL_DelValue三个操作函数，以实现线性表中数据的插入、删除与查找等功能。

相关知识)
线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间通过一对一首尾相接的方式连接起来。具体实现时，线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表实现方案：

该方案将线性表存储在一片连续空间里，并通过data、len和max三个属性元素。组织成为一个结构：

data: 给出线性表存储空间的起始地址；
max: 指明线性表存储空间最多可存储的数据元素个数；
len: 当前线性表里的数据元素个数。
为了讨论简化，我们假设每个数据元素是一个整数:

typedef int T; // 数据元素的数据类型
该线性表的结构定义如下：

struct SeqList{
T* data; // 数据元素存储空间的开始地址
int len; // 线性表的当前长度
int max; // 线性表的最大长度
};
以上示意图中的slist是指向该结构的一个指针，只要给定slist指针，就可对线性表进行操作。

对数据元素进行操作处理是一个数据结构的重要组成部分。线性表涉及的主要操作如下：

创建线性表：创建一个最多可存储max个数据元素的顺序存储的线性表，并将其初始状态设置为len=0。该操作函数具体定义如下，其返回值为slist：
SeqList* SL_Create(int max)

释放线性表存储空间：释放slist->data所指向的用于存储线性表数据元素的存储空间。该操作函数具体定义如下：
void SL_Free(SeqList* slist)

置空线性表：将当前线性表变为一个空表，实现方法是将slist->len设置为0。该操作函数具体定义如下：
void SL_MakeEmpty(SeqList* slist)

获取线性表当前长度：获取并返回线性表的当前长度slist->len。该操作函数具体定义如下：
int SL_Length(SeqList* slist)

判断线性表是否为空：若当前线性表是空表，则返回false，否则返回true。该操作函数具体定义如下：
BOOL SL_IsEmpty(SeqList* slist)

判断线性表是否已满：若线性表达到最大长度，则返回 true，否则返回false。该操作函数具体定义如下：
BOOL SL_IsFull(SeqList* slist)

返回线性表第i个数据元素：返回线性表的第i个数据元素slist->data[i]。该操作函数具体定义如下：
T SL_GetAt(SeqList* slist, int i)

修改线性表第i个数据元素： 将线性表的第 i个数据元素的值修改为 x。该操作函数具体定义如下：
void SL_SetAt(SeqList* slist, int i, T x)

在线性表位置i插入数据元素x： 将x插入slist->data[i]之前。若插入失败(i>slist->len 或i<0时，无法插入)，返回 false，否则返回 true。该操作函数具体定义如下：
BOOL SL_InsAt(SeqList* slist, int i, T x)

删除线性表位置i处的数据元素： 删除线性表的i号数据元素。输入参数i范围应在[0,slist->len-1]内，否则会产生不能预料的异常或错误。返回被删除的数据元素的值。该操作函数具体定义如下：
T SL_DelAt(SeqList* slist, int i)

查找线性表中第一个值为x的数据元素的位置： 找到线性表中第一个值为x的数据元素的编号。返回值-1表示没有找到，返回值>=0表示该元素位置。该操作函数具体定义如下：
int SL_FindValue(SeqList* slist, T x)

删除线性表中第一个值为x的数据元素： 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。该操作函数具体定义如下：
int SL_DelValue(SeqList* slist, T x)

打印线性表： 打印整个线性表。该操作函数具体定义如下：
void SL_Print(SeqList* slist)

编程要求
本关任务是实现 step1/Seqlist.cpp 中的SL_InsAt、SL_DelAt和SL_DelValue三个操作函数，以实现线性表中数据的插入、删除与查找等功能。具体要求如下：

SL_InsAT: 在顺序表的位置i插入结点x，即插入d[i]之前，i的有效范围[0,slist->len]；

SL_DelAt：删除顺序表slist的第i号结点， i的有效范围应在[0,slist->len)内，否则会产生异常或错误。返回被删除的数据元素的值；

SL_DelValue：删除第一个值为x的结点，存在值为x的结点则返回结点编号，未找到返回－1；

输入输出格式请参见后续测试样例。

注意：本关必读中提及的其他操作已经由平台实现，你在实现本关任务的三个操作函数时，在函数体内可调用其他操作。`

本关涉及的代码文件 Seqlist.cpp 中的 3 个操作函数的代码框架如下：

bool SL_InsAt(SeqList* slist, int i, T x)
// 在顺序表的位置i插入结点x, 插入在d[i]之前。i的有效范围[0,slist->len]
{
// 请在这里补充代码，完成本关任务
/********** Begin /
/* End /
}
T SL_DelAt(SeqList slist, int i)
// 删除顺序表slist的第i号结点（i的有效范围应在[0,slist->len)内，否则会产生异常或错误）。返回被删除的数据元素的值。
{
// 请在这里补充代码，完成本关任务
/* Begin /
/* End /
}
int SL_DelValue(SeqList slist, T x)
// 删除第一个值为x的结点。存在值为x的结点则返回结点编号, 未找到则返回－1
{
// 请在这里补充代码，完成本关任务
/* Begin /
/* End **********/
}

以下是代码：

#include <stdio.h>
#include <stdlib.h>
#include "Seqlist.h"
SeqList* SL_Create(int maxlen)
// 创建一个顺序表。
// 与SqLst_Free()配对。
{
	SeqList* slist=(SeqList*)malloc(sizeof(SeqList));
	slist->data = (T*)malloc(sizeof(T)*maxlen);
	slist->max=maxlen;
	slist->len=0;
	return slist;
}
void SL_Free(SeqList* slist)
// 释放/删除 顺序表。
// 与SqLst_Create()配对。
{
	free(slist->data);
	free(slist);
}
void SL_MakeEmpty(SeqList* slist)
// 置为空表。
{
	slist->len=0;
}
int SL_Length(SeqList* slist)
// 获取长度。
{
	return slist->len;
}
bool SL_IsEmpty(SeqList* slist)
// 判断顺序表是否空。
{
	return 0==slist->len;
}
bool SL_IsFull(SeqList* slist)
// 判断顺序表是否满。
{
	return slist->len==slist->max;
}
T SL_GetAt(SeqList* slist, int i)
// 获取顺序表slist的第i号结点数据。
// 返回第i号结点的值。
{
	if(i<0||i>=slist->len) {
		printf("SL_GetAt(): location error when reading elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		return slist->data[i];
}
void SL_SetAt(SeqList* slist, int i, T x)
// 设置第i号结点的值（对第i号结点的数据进行写）。
{
	if(i<0||i>=slist->len) {
		printf("SL_SetAt(): location error when setting elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		slist->data[i]=x;
}
bool SL_InsAt(SeqList* slist, int i, T x)
// 在顺序表的位置i插入结点x, 插入d[i]之前。
// i 的有效范围[0,plist->len]。
{
    // 请在下面的Begin-End之间补充代码，插入结点。
    /********** Begin *********/
	int j;
	{
		for(j=i;j<slist->len;j++){
			slist->data[j+1]=slist->data[j];
		}
		slist->data[i]=x;
		slist->len++;
	}
    /********** End **********/
}
T SL_DelAt(SeqList* slist, int i)
// 删除顺序表plist的第i号结点。
// i的有效范围应在[0,plist->len)内，否则会产生异常或错误。
// 返回被删除的数据元素的值。
{
    // 在下面的Begin-End之间补充代码，删除第i号结点。
    /********** Begin *********/
	for(;i<slist->len;i++)
	{
		slist->data[i]=slist->data[i+1];
	}
	slist->len--;
    /********** End **********/
}
int SL_FindValue(SeqList* slist, T x)
// 在顺序表表中查找第一个值为x的结点，返回结点的编号。
// 返回值大于等于0时表示找到值为x的结点的编号，-1表示没有找到。
{
	int i=0;
	while(i<slist->len && slist->data[i]!=x) i++;
	if (i<slist->len) return i;
	else return -1;
}
int SL_DelValue(SeqList* slist, T x)
// 删除第一个值为x的结点。
// 存在值为x的结点则返回结点编号, 未找到返回－1。
{
    // 在下面的Begin-End之间补充代码，删除第一个值为 x 的结点。
    /********** Begin *********/
	int i=0;
	for(i=0;i<slist->len;i++)
	{
		if(slist->data[i]==x)
		{
			int j=i;
			for(;i<slist->len-1;i++){
				slist->data[i]=slist->data[i+1];
			}
			slist->len--;
			return j;
		}
		return -1;
	}
    /********** End **********/
}
void SL_Print(SeqList* slist)
// 打印整个顺序表。
{
	if (slist->len==0) {
		printf("The slist is empty.\n");		
		return;
	}
	//printf("The slist contains: ");
	for (int i=0; i<slist->len; i++) {
		printf("%d  ", slist->data[i]);
	}
	printf("\n");	
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138