数据结构线性表（1）顺序表C语言代码实现

100 阅读 0 评论 66 点赞

我是靠谱客的博主傲娇画笔，这篇文章主要介绍数据结构线性表（1）顺序表C语言代码实现，现在分享给大家，希望可以做个参考。

顺序表C语言代码实现

实验要求：编写一个头文件SqList.h，实现顺序表的各种基本操作，并在此基础上设计一个主程序（exp2_1.cpp）完成如下功能：

（1）初始化顺序表L

（2）依次采用尾插法插入a,b,c,d,e元素

（3）输出顺序表L

（4）输出顺序表L的长度

（5）判断顺序表L是否为空

（6）输出顺序表L的第3个元素

（7）输出元素a的位置

（8）在第4个元素位置上插入f元素

（9）输出顺序表L

（10）删除L的第3个元素

（11）输出顺序表L

（12）释放顺序表L

注意：在exp2_1.cpp中用以下语句加入头文件：

# include “SqList.h”

我作为初学者，有很多错误与不足，望大家能够指出，我会很乐意接受大家的建议，谢谢大家！！！

头文件：

复制代码

/*文件名：SqList.h*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//定义函数返回的类型
typedef int Status;
#define LIST_INIT_SIZE 100
//线性表存储空间的初始分配量
#define LISTINCREMENT 10
//线性表存储空间的分配增量
typedef char ElemType;
//定义数据元素的类型为字符型
//定义顺序表的存储结构
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList
&L)
//构造一个空的顺序表L
{
L.elem =(ElemType*)malloc(LIST_INIT_SIZE * sizeof (ElemType));
if(!L.elem)
exit (OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
void DestroyList(SqList &L)
//销毁顺序表L
{
if (!L.elem)
{
return ERROR;
//表不存在
}
free(L.elem);
//释放内存
}
Status
ListEmpty(SqList
&L)
//判断顺序表是否为空，为空返回ture，否则返回false
{
if (!L.elem)
{
return ERROR;
//表不存在
}
if(L.length==0)
return TRUE;
else
return FALSE;
}
int ListLength(SqList &L)
//返回线性表L的长度
{
if (!L.elem)
{
return ERROR;
//表不存在
}
int i;
while (i<L.length)
{
i++;
}
return L.length;
}
void DispList (SqList &L)
//打印单链表中的元素
{
int i;
if (ListEmpty(L))
printf("数组为空");
for(i=0;i<10;i++)
printf("%c",L.elem[i]);
printf("%cn");
return;
}
Status GetElem(SqList L, int i, char &e)
//从顺序表L中查找第i个元素，由参数e返回其元素的值
{
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i < 1 || i > L.length - 1)
{
return ERROR;
//i值不合法
}
char * q = L.elem ;
e = *(q + i -1);
//把第i个元素给e
return OK;
}
int LocateElem(SqList L, int e)
//在顺序表L中查找元素e的位置，不存在则返回0
{
if (!L.elem)
{
return ERROR;
//表不存在
}
int i = 1;
char * p = L.elem ;
while (i < L.length && *p++ != e ) {//查找与e相等的值的位置
++i;
}
if (i <= L.length )
{
return i;
}
return 0;
}
Status ListInsert(SqList &L, int i, char e)
//在顺序表L中第i个位置前插入元素e
{
int k;
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i > L.length + 1 || i < 1)
{
//i值不合法
return ERROR;
}
if (L.length >= L.listsize)
{
char * newbase;
//空间不足，重新分配
newbase = (char *)realloc(L.elem,sizeof(char) * ( L.listsize+LISTINCREMENT));
L.elem = newbase;
if (!L.elem)
{
return OVERFLOW;
//分配失败
}
L.elem=newbase;
L.listsize += LISTINCREMENT;
//新空间容量
}
for(k=L.length-1;k>=i-1;k--)
L.elem [k+1]=L.elem[k];
L.elem[i-1]=e;
L.length++;
return OK;
}//ListInsert
Status ListDelete(SqList &L, int i, char &e)
//在顺序表L中删除第i个值并用e返回这个值
{
int k;
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i < 1 || i > L.length )
{
return ERROR;
//i值不合法
}
e=L.elem[i-1];
for (k=i;k<L.length;k++)
L.elem[k-1]=L.elem[k];
--L.length;
//L的长度减1
return OK;
}

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
/*文件名：SqList.h*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//定义函数返回的类型
typedef int Status;
#define LIST_INIT_SIZE 100
//线性表存储空间的初始分配量
#define LISTINCREMENT 10
//线性表存储空间的分配增量
typedef char ElemType;
//定义数据元素的类型为字符型
//定义顺序表的存储结构
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList
&L)
//构造一个空的顺序表L
{
L.elem =(ElemType*)malloc(LIST_INIT_SIZE * sizeof (ElemType));
if(!L.elem)
exit (OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
void DestroyList(SqList &L)
//销毁顺序表L
{
if (!L.elem)
{
return ERROR;
//表不存在
}
free(L.elem);
//释放内存
}
Status
ListEmpty(SqList
&L)
//判断顺序表是否为空，为空返回ture，否则返回false
{
if (!L.elem)
{
return ERROR;
//表不存在
}
if(L.length==0)
return TRUE;
else
return FALSE;
}
int ListLength(SqList &L)
//返回线性表L的长度
{
if (!L.elem)
{
return ERROR;
//表不存在
}
int i;
while (i<L.length)
{
i++;
}
return L.length;
}
void DispList (SqList &L)
//打印单链表中的元素
{
int i;
if (ListEmpty(L))
printf("数组为空");
for(i=0;i<10;i++)
printf("%c",L.elem[i]);
printf("%cn");
return;
}
Status GetElem(SqList L, int i, char &e)
//从顺序表L中查找第i个元素，由参数e返回其元素的值
{
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i < 1 || i > L.length - 1)
{
return ERROR;
//i值不合法
}
char * q = L.elem ;
e = *(q + i -1);
//把第i个元素给e
return OK;
}
int LocateElem(SqList L, int e)
//在顺序表L中查找元素e的位置，不存在则返回0
{
if (!L.elem)
{
return ERROR;
//表不存在
}
int i = 1;
char * p = L.elem ;
while (i < L.length && *p++ != e ) {//查找与e相等的值的位置
++i;
}
if (i <= L.length )
{
return i;
}
return 0;
}
Status ListInsert(SqList &L, int i, char e)
//在顺序表L中第i个位置前插入元素e
{
int k;
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i > L.length + 1 || i < 1)
{
//i值不合法
return ERROR;
}
if (L.length >= L.listsize)
{
char * newbase;
//空间不足，重新分配
newbase = (char *)realloc(L.elem,sizeof(char) * ( L.listsize+LISTINCREMENT));
L.elem = newbase;
if (!L.elem)
{
return OVERFLOW;
//分配失败
}
L.elem=newbase;
L.listsize += LISTINCREMENT;
//新空间容量
}
for(k=L.length-1;k>=i-1;k--)
L.elem [k+1]=L.elem[k];
L.elem[i-1]=e;
L.length++;
return OK;
}//ListInsert
Status ListDelete(SqList &L, int i, char &e)
//在顺序表L中删除第i个值并用e返回这个值
{
int k;
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i < 1 || i > L.length )
{
return ERROR;
//i值不合法
}
e=L.elem[i-1];
for (k=i;k<L.length;k++)
L.elem[k-1]=L.elem[k];
--L.length;
//L的长度减1
return OK;
}

源程序：

复制代码

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
#include "SqList.h"
int main ()
{
SqList(L);
ElemType e;
printf("初始化顺序表Ln");
InitList(L);
printf("依次采用尾插法插入a,b,c,d,e元素n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("输出顺序表L:");
DispList(L);
printf("顺序表长度L=%dn",L.length);
printf("顺序表L为%sn",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf("顺序表的第3个元素=%cn",e);
printf ("元素a的位置=%dn",LocateElem(L,'a'));
printf("在第4个元素位置上插入f元素n");
ListInsert(L,4,'f');
printf("输出顺序表L:");
DispList(L);
printf("删除L的第3个元素n");
ListDelete(L,3,e);
printf("输出顺序表L:");
DispList(L);
printf("释放顺序表Ln");
free(L.elem);
}