顺序表的定义，初始化，加工（插入，删除，修改），引用（遍历，查找）,实例_线性表数据元素为int类型 表示学生成绩 编写顺序定义,初始化,插入

线性表

抽象数据类型定义形式：

ADT List
{
数据对象 ；
数据关系;
基本操作；{初始化操作；销毁操作；引用类型操作；加工型操作；}
}

顺序储存

用一组连续的储存空间存放线性表中的各个数据元素，用位置相邻的储存空间关系白哦是线性表中数据元素的前驱和后继关系；

建立

定义时需包括：

1. 一片连续的存储空间（数组或数组的起始位置）
2. 容量（数组的大小，防止溢出）
3. 长度（已存入数据个数）

//方一，直接定义数组    常用！需掌握！
#define MAX 100
typedef struct
{
    ElemType data[MAX];    //ElemType表示数据元素的抽象类型
    int listSize;
    int length;
}SqList;    //顺序表，结构体数据类型

//方二：定义数组起始地址的指针变量    更灵活！难理解一些学有余力建议使用！
typedef struct
{
    ElemType *data;
    int size;
    int length;
} SqList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

当你的顺序表存储的东西比较复杂，比如一组学生数据时，你可以这样做：

//先定义学生数据的数据类型
typedef struct
{
    char name[20];    //姓名
    char no[20];    //学号
    float score;    //成绩
}STD;
//再定义顺序表数据类型
// typedef STD ElemType;    有时候会将STD重命名为ElemType
typedef struct
{
    STD *data;    //这里的STD就是上面的ElemType对应的实际数据类型
    int listsize;
    int length;
}SqList;    //现在顺序表里的一个元素就是一个指向STD类型的指针变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

使用：

SqList L, *p = &L;    //p指向L
1

在访问结构体变量的成员时，有两种访问方式：结构体变量访问（L.data[i]），和指针变量访问（p->data[i]）
顺序表建立好后，我们对其进行操作就是在通过参数进行数据的传递，同样两种情况

• 调用函数只读不影响实参
• 调用函数改变实参

简单来说，就是前者只是分享数据，后者是需要修改main方法中的数据(比如我们现在要做的），后者通过指针传递实参地址来实现

初始化

//使用int定义函数，返回函数值可以提高操作的健壮性
int initList(SqList *L, int max)
{
   L->data = (STD* )malloc(max *sizeof(STD));
   //不改变数组大小的话
   //L->data = (STD* )malloc(sizeof(STD));
   //直接new一个数组也是可以的
   //L->data = new int[MAX];
   if(L->data == NULL)(printf("空间申请失败！");return 0;}
   L->listSize = max;
   L->length = 0;
   return 1;
}
//或者
int initList(SqList &L, int max)
{
   L.data = (STD* )malloc(max *sizeof(STD));
   ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

调用时：

int main()
{
    SqList L;
    if(initList(&L,10))printf("创建成功！");    //创建一个大小为10的顺序表
    else{
    printf("创建失败！");
    exit(0);    //创建失败就退出程序，不必要但是个好习惯
    }
}
//第二种
if(initList(L,10)printf("创建成功！");
1
2
3
4
5
6
7
8
9
10
11

这两种方法各有什么优缺点呢，还需要组织一下语言，争取下次更新的时候补上OTZ
初始化就是申请了一片连续的存储空间，给成员变量赋予了初值
理论上来说new 和malloc 都是可以的，但是一般都用malloc (要配合free()使用），同样下次更新分析

关于malloc函数的参考资料：
[1]https://www.cnblogs.com/Commence/p/5785912.html.
[2]https://blog.csdn.net/qq_27871973.

加工型操作

改变线性表本身
初始条件是线性表已存在

• 置空
• 插入
• 删除
• 修改

置空

插入

将新数据插入指定位置，线性表长度加一

int insertList(SqList *L,int i,ElemType e)    //传递数据的指针，插入位置，插入数据
{
    int k;
    if(i<1||i>L->length + 1) {printf("插入位置异常!\n");return 0;}    //判读插入位置是否合理
    if(L->length>=L->ListSize){printf("数据溢出！\n");return 0;}    //判断顺序表是否已满
    for(k = L->length;k>=i;k--)
        L->data[k] = L->data[k-1];    //将插入位置后的数据全部后移一位
    L->data[i-1] = x;    //插入数据
    L->length = L->length + 1;    //表长加一
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11

排序插入，不指定位置

int insertList(SqList *L, ElemType e) {
	if (L->length == ListSize) 
	{
	    printf("数据溢出，无法操作！\n");
	    return 0;
	}    //判断是否已满
	else if(L->length== 0)
	{
		L->data[0] = e;    //第一个数据，不需要排序
		L->length++;
		return 1;
	}
	else {
		int j;
		j = p->length;
		p->elem[j] = e;
		while(j > 0 && p->elem[j-1].year > e.year){
			p->elem[j] = p->elem[j-1];
			p->elem[j-1] = e;
			j--;	
		}
		p->length++;
		return 1;                                                                                                                                                                                      
	}
}
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

删除

删除指定位置的数据

int deleteList(SqList *L,int i,ElemType e)    //传递数据的指针，插入位置，插入数据
{
    ...    //判断语句
    *e = L->data[i-1];
    for(int k = i;k<L->length;k++)
        L->data[k -1] = L->data[k];    //将删除位置前的数据全部前移一位，最后一位i = L->length-1删除不需要前移
    L->length = L->length - 1;    //表长减一
    return 1;
}
1
2
3
4
5
6
7
8
9

调用：

int main()
{ 
    ElemType e;
    if(deleteList(&L,2,&e))
       printf("删除的数据为:%s%s%d\n");
// 如果不需要打印，去掉参数e就好
    else
        printf("删除失败！");
}
1
2
3
4
5
6
7
8
9

修改

将指定位置的数据修改为新数据

int reviseList(SqList *L,int i,ElemType *e)
{
    ...   //判断
    L.data[i-1] = e;
    return 1;
}
1
2
3
4
5
6

调用：

int main()
{
    ElemType e = {"张三","007",99};   //不同的赋值方式
    e.name = "张三";
    strcpy(e.no,"007");    //这样给字符串赋值也可以
    e.score = 99;
    if(reviseList(&L,2,&x)) printf("修改成功！");
    else printf("修改失败！");
}
1
2
3
4
5
6
7
8
9

引用型操作

只使用线性表中的元素，但并没有改变线性表本身
初始条件是线性表已存在

• 判断是否为空
• 求长度
• 按位读取
• 按值求位
• 遍历（输出）

判断是否为空&&求长度

L->length
1

按位获取

int getList(SqList *L,int i,ElemType *e)
{
    ...  //判断
    *e = L->data[i-1];
    return 1;
}
1
2
3
4
5
6

调用：

int main()
{
    ElemType e;
    if(getList(&L,2,&e))
       printf("获取的数据是%s %s %d\n",e.name,e.no,e.score);
    else ...
}
1
2
3
4
5
6
7

定位

int locationList(SqList *L,char *x)
{
    int i;
    if(L->length == 0) {printf("没有数据！");return 0;} 
    for(int i = 0;i<L->length;i++)
        if(strcmp(L->data[i].name,x) == 0)
            return i + 1;
    return 0;
}
1
2
3
4
5
6
7
8
9

调用：

int main()
{
    ElemType e;
    if(locationList(&L,e.name) != 0)
        printf("在第%d个位置上找到！",locationList(&L,e.name));
    else ...
}
1
2
3
4
5
6
7

遍历(打印）

int print(SqList *L）
{
    for(int i = 0;i<L->length;i++)
        printf("%s\n",L->data[i].name);
    return 1;
}
1
2
3
4
5
6

• 时间复杂度
  T(n) = O(1)，没有涉及循环：初始化，修改、获取
  T(n) = O(n)：插入、删除、定位、遍历

实例

设计顺序表，实现中国超算发展历史知识的管理，功能可以包括：创建，查找，增加，删除，修改，遍历输出，初始化，等。

#include<stdio.h>
#include<string.h>
#define MAXSIZE 100
typedef struct
{
	char name[20];
	char people[30];
	int year;
}BOOK;
typedef BOOK ElemType;
typedef struct
{
	ElemType* elem;
	int length;
	int listsize;
}SqList;
//初始化创建一个空表
void InitList(SqList *p)
{
	p->elem = new ElemType[MAXSIZE];
	p->length = 0;
	p->listsize = 100;
}
//排序插入 
int  ListInsert(SqList *p, ElemType e) {
	if (p->length == MAXSIZE)
		return 0;
	else if (p->length == 0) {
		p->elem[0] = e;
		p->length++;
		return 1;
	}
	else {
		int j;
		j = p->length;
		p->elem[j] = e;
		while(j > 0 && p->elem[j-1].year > e.year){
			p->elem[j] = p->elem[j-1];
			p->elem[j-1] = e;
			j--;	
		}
		p->length++;
		return 1;
	}
}
//任意位置删除
int ListDelete(SqList *p, int n) {
	if ((n < 0) || (n >= p->length))
		return 0;
	else {
		for (int j = n; j <= p->length - 1; j++)
			p->elem[j - 1] = p->elem[j];
		p->length--;
		return 1;
	}
}
//定位
int locationList(SqList *p,char *x)
{
    int i;
    if(p->length == 0) {printf("没有数据！");return 0;} 
    for(int i = 0;i<p->length;i++)
        if(strcmp(p->elem[i].name,x) == 0)
            return i + 1;
    return 0;
}
//按指定位置查找
int LocateElem(SqList* p, int i, ElemType *e) {
	if (i < 0 || i > p->length)
		return 0;
	else
    {
    	*e = p->elem[i-1];
		return 1;	
    }
}
//修改某条记录
int ReviseElem(SqList* p,int i,ElemType e)
{
	if (i < 0 || i >= p->length)
		return 0;
	else
	{
		p->elem[i] = e;
		return 1;
	}
}
//输出顺序表
void PrintList(SqList *p) {
	for (int i = 0; i < p->length; i++) 
		printf("姓名 : %s 开发人员 : %s 年份 : %d\n", p->elem[i].name, p->elem[i].people, p->elem[i].year);
}
//创建
int creatList(SqList* L)
{
	int n = 0;
	ElemType e;
	char yn;
	InitList(L);
	do
	{
		printf("请输入超算发展历史数据,用空格隔开：");
		scanf("%s %s %d", &e.name, &e.people, &e.year);
		getchar();
		ListInsert(L, e);
		n++;
		printf("是否继续输入？Y/N");
		yn = getchar();
	} while (yn == 'Y' || yn == 'y');
}
int main()
{
	printf("欢迎使用超算历史发展知识管理系统！\n");
	SqList L;
	creatList(&L);
	/*可用以下代码代替creat函数
	InitList(&L);
	printf("初始化成功！\n");
	printf("请输入三条超算发展历史：\n");
	for (int i = 0; i < 3; i++) {
		ElemType x;
		scanf("%s %s %d", &x.name, &x.people, &x.year);
		ListInsert(&L, x);
	}
	printf("输入成功！\n");
	*/
	PrintList(&L);
	printf("\n请选择你要执行的操作\n");
	printf("1 : 插入新数据\n");
	printf("2 : 删除数据\n");
	printf("3 : 根据超算名称查找\n");
	printf("4 : 查询某条记录\n");	
	printf("5 : 记录某条修改\n");

	int op;
	while (scanf("%d", &op) && op) {
		if (op == 1) {
			printf("请输入数据：\n");
			ElemType x;
    		scanf("%s %s %d", &x.name, &x.people, &x.year);
			if(ListInsert(&L, x))
				printf("插入成功！\n");
			PrintList(&L);
		}
		else if (op == 2) {
			printf("请输入想要删除第几条数据：");
			int j;
			scanf("%d",&j); 
			if(ListDelete(&L, j-1))
				printf("删除成功！\n");
			PrintList(&L);
		}
		else if (op == 3) {
			printf("请输入超算名称：\n");
			char name[20];
            scanf("%s", &name);
			if (locationList(&L, name) != 0)
				printf("该超算是第%d条记录！\n", locationList(&L,name));
			else
				printf("没有查询到这台超算！\n");
		}
		else if(op == 4){
			printf("请输入想要查询的位置：\n");
		    int num;
		    ElemType e;
			scanf("%d",&num);
			if(LocateElem(&L,num,&e) != 0)
        		printf("姓名 : %s 开发人员 : %s 年份 : %d\n", e.name, e.people, e.year);
			else
				printf("位置有误！\n");
		} 
		else if (op == 5) {
			printf("请输入需要修改第几条数据：\n");
			int local;
			scanf("%d",&local); 
			printf("请输入准备修改的数据：\n");
			ElemType x;
			scanf("%s %s %d", &x.name, &x.people, &x.year);
			if(ReviseElem(&L,local-1, x))
				printf("插入成功！\n");
			PrintList(&L);
		}
		else
				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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190