（C语言）顺序表实验_sequenlist

感兴趣的小伙伴可以先看看我的这篇文章哦，打开看看，说不定能帮到你一些~~

金陵科技学院软件工程学院软件工程专业

更新于2021.10.12晚：
之前写的那个版本的这几题非常的不规范，于是乎花了点时间重写了一下这几题，差点误导了各位（捂脸）。

1.（1）：编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。

实现代码：

#include <stdio.h>
#define MAXSIZE 100
typedef struct{
	int data[MAXSIZE];
	int last;
}sequenlist;
sequenlist CreateSequenlist(int n){
	int i;
	sequenlist L;
	printf("请输入%d个数：\n",n);
	for (i = 0;i < n;i++){
		scanf("%d",&L.data[i]);
	}
	L.last = n-1;
	return L;
}
void PrintSequenlist(sequenlist L){
	int i;
	for (i = 0;i <= L.last;i++){
		printf("%d ",L.data[i]);
	}
}
int main(){
	int n;
	printf("请输入顺序表中的元素个数：");
	scanf("%d",&n);
	sequenlist L = CreateSequenlist(n);
	printf("该顺序表中的所有元素为：");
    PrintSequenlist(L);
	return 0;
}
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

运行结果：

分析：

该程序中用于输出顺序表中所有元素的函数的时间复杂度与空间复杂度均为线性阶O（n）。

（2）：编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。

实现代码：

#include <stdio.h>
#define MAXSIZE 100
typedef struct{
	int data[MAXSIZE];
	int last;
}sequenlist;
sequenlist CreateSequenlist(int n){
	int i;
	sequenlist L;
	printf("请输入%d个数：\n",n);
	for (i = 0;i < n;i++){
		scanf("%d",&L.data[i]);
	}
	L.last = n-1;
	return L;
} 
void PrintSequenlist(sequenlist L){
	int i;
	for (i = 0;i <= L.last;i++){
		printf("%d ",L.data[i]);
	}
}
int Search(sequenlist L,int x){
	int i;
	for (i = 0;i <= L.last;i++){
		if (x == L.data[i]){
			return i;
		}
	}
	return -1;
}
int main(){
	int n,x;
	printf("请输入顺序表中的元素个数：");
	scanf("%d",&n);
	sequenlist L = CreateSequenlist(n);
	printf("该顺序表中的所有元素为：");
    PrintSequenlist(L);
    printf("\n请输入想要查找的数据元素：");
    scanf("%d",&x);
    if(Search(L,x) != -1){
    	printf("顺序表中和该元素值相等的第1个数据元素的序号为：%d",Search(L,x));
	}else{
	    printf("%d",Search(L,x)); 
	}
	return 0;
} 
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

运行结果：


分析：

该程序中顺序表定位操作子函数的时间复杂度和空间复杂度均为线性阶O（n）。

（3）：在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。

实现代码：

#include <stdio.h>
#define MAXSIZE 100
typedef struct{
	int data[MAXSIZE];
	int last;
}sequenlist;
sequenlist CreateSequenlist(int n){
	int i;
	sequenlist L;
	printf("请输入%d个数：\n",n);
	for (i = 0;i < n;i++){
		scanf("%d",&L.data[i]);
	}
	L.last = n-1;
	return L;
}
void PrintSequenlist(sequenlist L){
	int i;
	for (i = 0;i <= L.last;i++){
		printf("%d ",L.data[i]);
	}
}
void Insert(sequenlist *L,int x){
	int i,j,loc;
	for (i = 0;i <= (*L).last;i++){
		if ((*L).data[i] > x){
			loc = i;
			break;
		}
	}
	if (i > (*L).last){
		loc = i;
		(*L).data[loc] = x;
	}else{
		for (j = (*L).last;j >= loc;j--){
			(*L).data[j+1] = (*L).data[j];
		}
		(*L).data[loc] = x;
	}
	(*L).last++;
} 
int main(){
	int n,x;
	printf("请输入顺序表中的元素个数：");
	scanf("%d",&n);
	sequenlist L = CreateSequenlist(n);
	printf("该顺序表中的所有元素为：");
    PrintSequenlist(L);
    printf("\n请输入想要插入的新结点x的元素值："); 
    scanf("%d",&x);
    sequenlist *s = &L;
    Insert(s,x);
    printf("在顺序表中插入一个新结点x后，顺序表中的所有元素为：");
    PrintSequenlist(L);
	return 0;
}
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

运行结果：


分析：

该插入操作的时间复杂度和空间复杂度均为线性阶O（n）。

（4）：删除顺序表中所有等于X的数据元素。

实现代码：

#include <stdio.h>
#define MAXSIZE 100
typedef struct{
	int data[MAXSIZE];
	int last;
}sequenlist; 
sequenlist CreateSequenlist(int n){
	int i;
	sequenlist L;
	printf("请输入%d个数：\n",n);
	for (i = 0;i < n;i++){
		scanf("%d",&L.data[i]);
	}
	L.last = n-1;
	return L;
}
void PrintSequenlist(sequenlist L){
	int i;
	for (i = 0;i <= L.last;i++){
		printf("%d ",L.data[i]);
	}
}
void Delete(sequenlist *L,int x){
	int i,j,loc = -1;
	for (i = 0;i <= (*L).last;i++){
		if (x == (*L).data[i]){
			loc = i;
			for (j = loc+1;j <= (*L).last;j++){
				(*L).data[j-1] = (*L).data[j];
			}
			(*L).last--;
			i--;
		}
	}
	if (loc == -1){
		printf("顺序表中不存在等于x的数据元素！\n");
	}
}
int main(){
	int n,x;
	printf("请输入顺序表中的元素个数：");
	scanf("%d",&n);
	sequenlist L = CreateSequenlist(n);
	printf("该顺序表中的所有元素为：");
    PrintSequenlist(L);
    printf("\n请输入想要删除的数据元素x："); 
    scanf("%d",&x);
    sequenlist *s = &L;
    Delete(s,x); 
    printf("删除顺序表中所有等于X的数据元素后，顺序表中的所有元素为：");
    PrintSequenlist(L);
    return 0; 
}
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

运行结果：


分析：

该删除操作的时间复杂度为O(n²)，空间复杂度为O（n）。

2.已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。

实现代码：

#include <stdio.h>
#define MAXSIZE 100
typedef struct{
	int data[MAXSIZE];
	int last;
}sequenlist;
sequenlist CreateSequenlist(int n){
	int i;
	sequenlist L;
	if (n != 0 ){
	    printf("请输入%d个数：\n",n);
	    for (i = 0;i < n;i++){
		    scanf("%d",&L.data[i]);
	    }
	    L.last = n-1;
	}
	return L;
}
void PrintSequenlist(sequenlist L){
	int i;
	for (i = 0;i <= L.last;i++){
		printf("%d ",L.data[i]);
	}
}
void MergeSequenlist(sequenlist *la,sequenlist *lb,sequenlist *lc){
	int i = (*la).last,j = (*lb).last,k = 0;
	while(i!=-1&&j!=-1){
	    if((*la).data[i] >= (*lb).data[j]){
	       (*lc).data[k++]=(*la).data[i];
	       i--;
		}else{
		   (*lc).data[k++]=(*lb).data[j];
		   j--;
		}
	}
	while(i!=-1){
	    (*lc).data[k++] = (*la).data[i];
	    i--;
	}
	while(j!=-1){
	 	(*lc).data[k++] = (*lb).data[j];
	 	j--;
	}
}
int main(){
	int n,m;
	printf("请输入顺序表A中的元素个数：");
	scanf("%d",&n);
	sequenlist A = CreateSequenlist(n);
	printf("请输入顺序表B中的元素个数：");
	scanf("%d",&m);
	sequenlist B = CreateSequenlist(m);
	printf("顺序表A中的所有元素为：");
    PrintSequenlist(A);
    printf("\n顺序表B中的所有元素为：");
    PrintSequenlist(B);
    sequenlist C = CreateSequenlist(0);
    C.last = A.last + B.last + 1;
    sequenlist *la = &A;
	sequenlist *lb = &B;
	sequenlist *lc = &C;
	MergeSequenlist(la,lb,lc);
	printf("\n顺序表A和顺序表B归并成一个按元素值递减有序排列的顺序表后，所得顺序表中的所有元素为：");
	PrintSequenlist(C);
	return 0;
}
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

运行结果：

分析：

假设顺序表A和顺序表B中均有n个元素，则该归并操作的时间复杂度与空间复杂度均为线性阶O（n）。