我是靠谱客的博主 想人陪外套,这篇文章主要介绍C++中如何建立一个顺序表,现在分享给大家,希望可以做个参考。

准备数据

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MAXLEN 100 //定义顺序表的最大长度 struct DATA { char key[10]; //结点的关键字 char name[20]; int age; }; struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen; //顺序表已存结点的数量 };

定义了顺序表的最大长度MAXLEN、顺序表数据元素的类型DATA以及顺序表的数据结构SLType。

在数据结构SLType中,Listen为顺序表已存结点的数量,也就是当前顺序表的长度,ListData是一个结构数组,用来存放各个数据结点。

我们认为该顺序表是一个班级学生的记录。其中,key为学号,name为学生的名称,age为年龄。

因为数组都是从下标0开始的,为了使用方便,我们从下标1开始记录数据结点,下标0的位置不可用。


初始化顺序表


在使用顺序表之前,首先创建一个空的顺序表,也就是初始化顺序表。这里,在程序中只需设置顺序表的结点数量ListLen为0即可。这样,后面需要添加的数据元素将从顺序表的第一个位置存储。
示例代码:
复制代码
1
2
3
4
void SLInit(SLType * SL) //初始化顺序表 { SL->Listlen=0; }

计算线性表的长度


计算线性表的长度也就是计算线性表中结点的个数,由于我们在SLType中定义了ListLen来表示结点的数量,所以我们只需要获得这个变量的值即可。
复制代码
1
2
3
4
int SLLenght(SLType *SL) { return(SL->ListLen); //返回顺序表的元素数量 }

插入结点


插入节点就是在线性表L的第i个位置上插入一个新的结点,使其后的结点编号依次加1。
这时,插入一个新节点之后,线性表L的长度将变为n+1。插入结点操作的难点在于随后的每个结点数据都要向后移动,计算机比较大,示例代码如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int SLInsert(SLType *SL,int n,DATA data) { int i; if(SL->ListLen>=MAXLEN) //顺序表结点数量已超过最大数量 { cout<<"顺序表已满,不能插入结点!"<<endl; return 0; //返回0表示插入不成功 } if(n<1||n>SL->ListLen) //插入结点的序号不合法 { cout<<"插入序号错误!"<<endl; return 0; } for(i=SL->ListLen;i>=n;i--) //将顺序表中的数据向后移动 { SL->ListData[i+1]=SL->ListData[i]; } SL->ListData[n]=data; SL->ListLen++; return 1; }

在程序中首先判断顺序表结点数量时候已超过最大数量,以及插入点的序号是否正确。前面条件都瞒住以后,便将顺序表中的数据向后移动,同时插入结点,并更新结点数量ListLen。

追加结点


追加结点就是在顺序表的尾部插入结点,因此不必进行大量数据的移动,代码实现与插入结点相比就要简单的多。
复制代码
1
2
3
4
5
6
7
8
9
10
int SLAdd(SLType * SL,DATA data) { if(SL->ListLen>=MAXLEN) { cout<<"顺序表已满,不能再添加结点了!"<<endl; return 0; } SL->ListData[++SL->ListLen]=data; return 1; }

删除结点


删除结点就是删除线性表L中的第i个结点,使得其后的所有节点编号依次减1.这是,删除一个结点之后,线性表L的长度将变为n-1。删除结点和插入结点类似,都需要进行大量数据的移动。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int SLDelete(SLType *SL,int n) //删除顺序表中的数据元素 { int i; if(n<1||n>SL->ListLen) //删除结点的序号不合法 { cout<<"删除序号错误!"<<endl; return 0; } for(i=n;i<SL->ListLen;i++)//将顺序表中的数据向前移动 { SL->ListData[i]=SL->ListData[i+1]; } SL->ListLen--; //顺序表元素数量减1 return 1; //成功删除返回1 }

查找结点


查找节点就是在线性表L中查找值为x的结点,并返回该节点在线性表L中的位置。如果在线性表中没有找到值为x的结点,则返回一个错误标志。
根据x的类型不同,查找结点可以分为:

按照序号查找结点


对于一个顺序表,序号就是数据元素在数组中的位置,也就是数组的下标标号。按照序号查找结点是顺序表查找结点最常用的方法,这是因为顺序表的存储本身就是一个数组,示例代码如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
DATA * SLFindByNum(SLType *SL,int n)//根据呼号返回数据元素 { if(n<1||n>SL->ListLen) //查询结点的序号不合法 { cout<<"查询序号错误!"<<endl; return 0; } return &(SL->ListData[n]); }


按照关键字查找结点


关键字可以是数据元素中的任意一项。
这里以key关键字为例进行介绍,例如,可以通过key查找学生的信息。示例代码如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int SLFindByCont(SLType * SL,char *key)//按关键字查询结点 { int i; for(i=1;i<=SL->ListLen;i++) { if(strcmp(SL->ListData[i].key,key)==0)//如果找到结点 { return i; } } return 0; //在整个表中都没有找到,返回0 }

显示所有的结点


示例代码如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
void SLALL(SLType *SL) { int i; for(i=1;i<SL->ListLen;i++) { cout<<"key:"<<SL->ListData[i].key<<endl; cout<<"name:"<<SL->ListData[i].name<<endl; cout<<"age:"<<SL->ListData[i].age<<endl; cout<<"============================="<<endl; } }

顺序表操作完整示例:


基本上就是把上面的函数放到一块,集中展示了一下功能,代码有些长,请耐心阅读^.^

复制代码
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
#include<iostream> #include<string> using namespace std; #define MAXLEN 100 //定义顺序表的最大长度 /**************顺序表的定义部分*****************/ struct DATA { string key; //结点的关键字 string name; int age; }; struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen; //顺序表已存结点的数量 }; /************顺序表的初始化函数*****************/ void SLInit(SLType * SL) //初始化顺序表 { SL->ListLen=0; } /***********计算线性表的长度*******************/ int SLLenght(SLType *SL) { return(SL->ListLen); //返回顺序表的元素数量 } /*********插入结点*******************************/ int SLInsert(SLType *SL,int n,DATA data) { int i; if(SL->ListLen>=MAXLEN) //顺序表结点数量已超过最大数量 { cout<<"顺序表已满,不能插入结点!"<<endl; return 0; //返回0表示插入不成功 } if(n<1||n>SL->ListLen) //插入结点的序号不合法 { cout<<"插入序号错误!"<<endl; return 0; } for(i=SL->ListLen;i>=n;i--) //将顺序表中的数据向后移动 { SL->ListData[i+1]=SL->ListData[i]; } SL->ListData[n]=data; SL->ListLen++; return 1; //成功插入,返回1 } /***********************追加结点*************************/ int SLAdd(SLType * SL,DATA data) { if(SL->ListLen>=MAXLEN) { cout<<"顺序表已满,不能再添加结点了!"<<endl; return 0; } SL->ListData[++SL->ListLen]=data; return 1; } /***********************删除结点*************************/ int SLDelete(SLType *SL,int n) //删除顺序表中的数据元素 { int i; if(n<1||n>SL->ListLen) //删除结点的序号不合法 { cout<<"删除序号错误!"<<endl; return 0; } for(i=n;i<SL->ListLen;i++)//将顺序表中的数据向前移动 { SL->ListData[i]=SL->ListData[i+1]; } SL->ListLen--; //顺序表元素数量减1 return 1; //成功删除返回1 } /*******************按照序号查找结点********************/ DATA * SLFindByNum(SLType *SL,int n)//根据序号返回数据元素 { if(n<1||n>SL->ListLen) //查询结点的序号不合法 { cout<<"查询序号错误!"<<endl; return 0; } return &(SL->ListData[n]); } /*******************按照关键字查找结点********************/ DATA *SLFindByCont(SLType * SL,string name)//按关键字查询结点 { int i; for(i=1;i<=SL->ListLen;i++) { if(SL->ListData[i].name==name)//如果找到结点 { return &(SL->ListData[i]); } } return 0; //在整个表中都没有找到,返回0 } /*******************显示所有的结点********************/ void SLALL(SLType *SL) { int i; for(i=1;i<=SL->ListLen;i++) { cout<<"key:"<<SL->ListData[i].key<<",name:"<<SL->ListData[i].name<<",age:"<<SL->ListData[i].age<<endl; } } int main() { int i; SLType SL; //定义顺序表变量 DATA data; //定义结点保存数据类型变量 DATA *pdata;//定义指向结点的指针变量 string name; cout<<"顺序表操作演示:"<<endl; SLInit(&SL);//初始化顺序表 do { //循环添加结点数据 cout<<"请输入要添加的结点(学号 姓名 年龄):"; cin>>data.key>>data.name>>data.age; if(data.age) //若年龄不为0 { if(!SLAdd(&SL,data))//若添加结点失败 { break; //退出循环 } }else { break; } }while(1); cout<<"顺序表中的结点顺序为:" <<endl; SLALL(&SL); //显示所有的结点 cout<<"请输入要取出的结点序号:"; cin>>i; pdata=SLFindByNum(&SL,i);//按序号查找结点 if(pdata) { cout<<"第"<<i<<"个结点为:key:"<<pdata->key<<",name:"<<pdata->name<<",age:"<<pdata->age<<endl; } cout<<"请输入要查找的姓名:"; cin>>name; pdata=SLFindByCont(&SL,name); if(pdata) { cout<<"key:"<<pdata->key<<",name:"<<pdata->name<<",age:"<<pdata->age<<endl; } cout<<"请输入您要删除的结点的序号:"; cin>>i; if(SLDelete(&SL,i)) { cout<<"数据删除成功"<<endl; SLALL(&SL); } cout<<"请输入您要插入的结点的序号:"; cin>>i; cout<<"请输入第"<<i<<"号结点的key,name,以及age"<<endl; cin>>data.key>>data.name>>data.age; if(SLInsert(&SL,i,data)) { cout<<"插入数据成功"<<endl; SLALL(&SL); } return 0; }

运行界面:
好啦,时间不早了,大家晚安~

转载于:https://www.cnblogs.com/zhezh/p/3773391.html

最后

以上就是想人陪外套最近收集整理的关于C++中如何建立一个顺序表的全部内容,更多相关C++中如何建立一个顺序表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(82)

评论列表共有 0 条评论

立即
投稿
返回
顶部