【数据结构】——顺序表的基本操作_数据结构顺序表的基本操作

01
//(较简易)

顺序表

线性表：由n(n>=0)个数据特性相同的元素构成的有限序列。
顺序表：用顺序存储的方式实现线性表。
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表特点：
（1）随机访问；
（2）存储密度高，每个节点只存储数据元素；
（3）拓展容量不方便；
（4）插入、删除操作不方便，需移动大量元素。

顺序表的结构体

//顺序表的结构 
typedef struct SqList
{
	int length;
	ElemType *elem;
}SqList;

1
2
3
4
5
6
7

构造顺序表

//创建一个空的顺序表 
Status InitList(SqList &L)
{
	L.elem=new ElemType[MAXSIZE];
	if(!L.elem) exit(OVERFLOW);
	L.length=0;
	return OK;
}
1
2
3
4
5
6
7
8

按值查找

时间复杂度为O(n)

//按值查找
Status LocateElem(SqList L,ElemType e){
	if(L.length==0)
	{
		printf("空表\n"); return ERROR;
	}
	for(int i=0;i<L.length;i++) 
	if(L.elem[i]==e)
	return i+1;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11

##按位查找
时间复杂度为O(1)

//按位查找
Status ItemElem(SqList L,ElemType i){
	if(L.length==0)
	{
		printf("空表！\n");
		return ERROR;
	}
	return L.elem[i-1];
}

1
2
3
4
5
6
7
8
9
10

插入

时间复杂度为O(n)

//插入
Status ListInsert(SqList &L,int i,ElemType e){
	if((i<1)||(i>L.length+1)) return ERROR;
	if(L.length==MAXSIZE) return ERROR;
	for(int j=L.length-1;j>=i-1;j--)
	{
		L.elem[j+1]=L.elem[j];
	}
	L.elem[i-1]=e;
	++L.length;
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

删除

时间复杂度为O(n)

//删除
Status ListDelete(SqList &L,int i){
	if((i<1)||(i>L.length+1)) return ERROR;
	for(int j=i;j<=L.length;j++)
	L.elem[j-1]=L.elem[j];
	--L.length;
	return OK;
}
1
2
3
4
5
6
7
8

输出表

//显示顺序表
void display(SqList L){
	if(L.length==0){
		printf("空表\n"); return  ; 
	} 
	printf("表中元素依次为："); 
	for(int i=0;i<L.length;i++)
	printf("%d ",L.elem[i]);
	printf("\n一共%d个元素\n",L.length);
} 
1
2
3
4
5
6
7
8
9
10

完整代码

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int ElemType;
typedef int Status;
//顺序表的结构 
typedef struct SqList
{
	int length;
	ElemType *elem;
}SqList;

//创建一个空的顺序表 
Status InitList(SqList &L)
{
	L.elem=new ElemType[MAXSIZE];
	if(!L.elem) exit(OVERFLOW);
	L.length=0;
	return OK;
}

//顺序表的取值及位置
Status GetElem(SqList L,int i,ElemType &e){
	if(i<1||i>L.length)
	return ERROR;
	e=L.elem[i-1];
	return OK;
}
 
//按值查找
Status LocateElem(SqList L,ElemType e){
	if(L.length==0)
	{
		printf("空表\n"); return ERROR;
	}
	for(int i=0;i<L.length;i++) 
	if(L.elem[i]==e)
	return i+1;
	return 0;
} 

//按位查找
Status ItemElem(SqList L,ElemType i){
	if(L.length==0)
	{
		printf("空表！\n");
		return ERROR;
	}
	return L.elem[i-1];
}

//插入
Status ListInsert(SqList &L,int i,ElemType e){
	if((i<1)||(i>L.length+1)) return ERROR;
	if(L.length==MAXSIZE) return ERROR;
	for(int j=L.length-1;j>=i-1;j--)
	{
		L.elem[j+1]=L.elem[j];
	}
	L.elem[i-1]=e;
	++L.length;
	return OK;
}

//删除
Status ListDelete(SqList &L,int i){
	if((i<1)||(i>L.length+1)) return ERROR;
	for(int j=i;j<=L.length;j++)
	L.elem[j-1]=L.elem[j];
	--L.length;
	return OK;
}

//显示顺序表
void display(SqList L){
	if(L.length==0){
		printf("空表\n"); return  ; 
	} 
	printf("表中元素依次为："); 
	for(int i=0;i<L.length;i++)
	printf("%d ",L.elem[i]);
	printf("\n一共%d个元素\n",L.length);
} 

int main()
{
	SqList L;
	int i,count,temp=0,choose;
	ElemType x;
	choose=-1;
	count=0;
	while(choose!=0)
	{
		if(count%5==0)
		{
			printf("\n                       *****************************************************************\n");
			printf("                       ** 1.建立空表                         2.在表中输入指定个数元素 **\n");
			printf("                       ** 3.按值查找                         4.按位查找               **\n");
			printf("                       ** 5.插入                             6.删除                   **\n");
			printf("                       ** 0.退出                                                      **\n");
			printf("                       *****************************************************************\n");
		}
		count++;
		printf("\n请选择：\n");
		scanf("%d",&choose);
		switch(choose)
		{
			case 1:
				if(InitList(L))
				printf("\n成功构建！\n\n");
				else 
				printf("构建失败！\n\n");
				break;
			case 2:
			printf("输入元素总数：");
			scanf("%d",&L.length);
		 	printf("请输入各个元素：");
		 	for(i=0;i<L.length;i++)
		 	{
		 		scanf("%d",&L.elem[i]);
			}
			display(L);
			break;  
			case 3:
				printf("输入要查找的数：");
				scanf("%d",&x);
				i=LocateElem(L,x);
				if(i){
					printf("查找成功！\n");
					printf("它位于第%d位,位序为%d",i,i-1);
				}else{
					printf("查找失败！\n");
				}
				break;
			case 4:
				printf("输入要查找的位置：");
				scanf("%d",&i);
				printf("%d",ItemElem(L,i));
				break;
			case 5:
				display(L);
				printf("输入要插入的位置和数值：");
				scanf("%d %d",&i,&x);
				if(ListInsert(L,i,x))
				{
					printf("插入成功！\n");
					display(L);
				 } else{
				 	printf("插入失败！\n");
				 }
				 break;
			case 6:
				display(L);
				printf("输入要删除的位置：");
				scanf("%d",&x); 
				i=ListDelete(L,x);
				if(i)
				{
					printf("删除成功！\n");
					display(L);
				 } else{
				 	printf("删除失败！\n");
				 }
				 break; 		  
		 } 
	}
}
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