C++中如何建立一个顺序表.docx
《C++中如何建立一个顺序表.docx》由会员分享，可在线阅读，更多相关《C++中如何建立一个顺序表.docx（25页珍藏版）》请在冰点文库上搜索。
C++中如何建立一个顺序表
C++中如何建立一个顺序表
1.准备数据
2.初始化顺序表
3.计算线性表的长度
4.插入结点
5.追加结点
6.删除结点
7.查找结点
1.按照序号查找结点
2.按照关键字查找结点
8.显示所有的结点
9.顺序表操作完整示例
准备数据
[cpp]viewplaincopyprint?
1.#defineMAXLEN100//定义顺序表的最大长度
2.structDATA
3.{
4.charkey[10];//结点的关键字
5.charname[20];
6.intage;
7.};
8.structSLType//定义顺序表结构
9.{
10.DATAListData[MAXLEN+1];//保存顺序表的结构数组
11.intListLen;//顺序表已存结点的数量
12.};#defineMAXLEN100//定义顺序表的最大长度
structDATA
{
charkey[10];//结点的关键字
charname[20];
intage;
};
structSLType//定义顺序表结构
{
DATAListData[MAXLEN+1];//保存顺序表的结构数组
intListLen;//顺序表已存结点的数量
};
定义了顺序表的最大长度MAXLEN、顺序表数据元素的类型DATA以及顺序表的数据结构SLType。
在数据结构SLType中，Listen为顺序表已存结点的数量，也就是当前顺序表的长度，ListData是一个结构数组，用来存放各个数据结点。
我们认为该顺序表是一个班级学生的记录。
其中，key为学号，name为学生的名称，age为年龄。
因为数组都是从下标0开始的，为了使用方便，我们从下标1开始记录数据结点，下标0的位置不可用。
初始化顺序表
在使用顺序表之前，首先创建一个空的顺序表，也就是初始化顺序表。
这里，在程序中只需设置顺序表的结点数量ListLen为0即可。
这样，后面需要添加的数据元素将从顺序表的第一个位置存储。
示例代码：
[cpp]viewplaincopyprint?
1.voidSLInit（SLType*SL）//初始化顺序表
2.{
3.SL->Listlen=0;
4.}
voidSLInit（SLType*SL）//初始化顺序表
{
SL->Listlen=0;
}
计算线性表的长度
计算线性表的长度也就是计算线性表中结点的个数，由于我们在SLType中定义了ListLen来表示结点的数量，所以我们只需要获得这个变量的值即可。
[cpp]viewplaincopyprint?
1.intSLLenght（SLType*SL）
2.{
3.return（SL->ListLen）;//返回顺序表的元素数量
4.}intSLLenght（SLType*SL）
{
return（SL->ListLen）;//返回顺序表的元素数量
}
插入结点
插入节点就是在线性表L的第i个位置上插入一个新的结点，使其后的结点编号依次加1。
这时，插入一个新节点之后，线性表L的长度将变为n+1。
插入结点操作的难点在于随后的每个结点数据都要向后移动，计算机比较大，示例代码如下：
[cpp]viewplaincopyprint?
1.intSLInsert（SLType*SL,intn,DATAdata）
2.{
3.inti;
4.if（SL->ListLen>=MAXLEN）//顺序表结点数量已超过最大数量
5.{
6.cout<<"顺序表已满，不能插入结点！
"<7.return0;//返回0表示插入不成功
8.}
9.if（n<1||n>SL->ListLen）//插入结点的序号不合法
10.{
11.cout<<"插入序号错误！
"<12.return0;
13.}
14.for（i=SL->ListLen;i>=n;i--）//将顺序表中的数据向后移动
15.{
16.SL->ListData[i+1]=SL->ListData[i];
17.}
18.SL->ListData[n]=data;
19.SL->ListLen++;
20.return1;
21.}intSLInsert（SLType*SL,intn,DATAdata）
{
inti;
if（SL->ListLen>=MAXLEN）//顺序表结点数量已超过最大数量
{
cout<<"顺序表已满，不能插入结点！
"<return0;//返回0表示插入不成功
}
if（n<1||n>SL->ListLen）//插入结点的序号不合法
{
cout<<"插入序号错误！
"<return0;
}
for（i=SL->ListLen;i>=n;i--）//将顺序表中的数据向后移动
{
SL->ListData[i+1]=SL->ListData[i];
}
SL->ListData[n]=data;
SL->ListLen++;
return1;
}
在程序中首先判断顺序表结点数量时候已超过最大数量，以及插入点的序号是否正确。
前面条件都瞒住以后，便将顺序表中的数据向后移动，同时插入结点，并更新结点数量ListLen。
追加结点
追加结点就是在顺序表的尾部插入结点，因此不必进行大量数据的移动，代码实现与插入结点相比就要简单的多。
[cpp]viewplaincopyprint?
1.intSLAdd（SLType*SL,DATAdata）
2.{
3.if（SL->ListLen>=MAXLEN）
4.{
5.cout<<"顺序表已满，不能再添加结点了！
"<6.return0;
7.}
8.SL->ListData[++SL->ListLen]=data;
9.return1;
10.}
intSLAdd（SLType*SL,DATAdata）
{
if（SL->ListLen>=MAXLEN）
{
cout<<"顺序表已满，不能再添加结点了！
"<return0;
}
SL->ListData[++SL->ListLen]=data;
return1;
}
删除结点
删除结点就是删除线性表L中的第i个结点，使得其后的所有节点编号依次减1.这是，删除一个结点之后，线性表L的长度将变为n-1。
删除结点和插入结点类似，都需要进行大量数据的移动。
[cpp]viewplaincopyprint?
1.intSLDelete（SLType*SL,intn）//删除顺序表中的数据元素
2.{
3.inti;
4.if（n<1||n>SL->ListLen）//删除结点的序号不合法
5.{
6.cout<<"删除序号错误！
"<7.return0;
8.}
9.for（i=n;iListLen;i++）//将顺序表中的数据向前移动
10.{
11.SL->ListData[i]=SL->ListData[i+1];
12.}
13.SL->ListLen--;//顺序表元素数量减1
14.return1;//成功删除返回1
15.}intSLDelete（SLType*SL,intn）//删除顺序表中的数据元素
{
inti;
if（n<1||n>SL->ListLen）//删除结点的序号不合法
{
cout<<"删除序号错误！
"<return0;
}
for（i=n;iListLen;i++）//将顺序表中的数据向前移动
{
SL->ListData[i]=SL->ListData[i+1];
}
SL->ListLen--;//顺序表元素数量减1
return1;//成功删除返回1
}
查找结点
查找节点就是在线性表L中查找值为x的结点，并返回该节点在线性表L中的位置。
如果在线性表中没有找到值为x的结点，则返回一个错误标志。
根据x的类型不同，查找结点可以分为：
按照序号查找结点
对于一个顺序表，序号就是数据元素在数组中的位置，也就是数组的下标标号。
按照序号查找结点是顺序表查找结点最常用的方法，这是因为顺序表的存储本身就是一个数组，示例代码如下：
[cpp]viewplaincopyprint?
1.DATA*SLFindByNum（SLType*SL,intn）//根据呼号返回数据元素
2.{
3.if（n<1||n>SL->ListLen）//查询结点的序号不合法
4.{
5.cout<<"查询序号错误！
"<6.return0;
7.}
8.return&（SL->ListData[n]）;
9.}DATA*SLFindByNum（SLType*SL,intn）//根据呼号返回数据元素
{
if（n<1||n>SL->ListLen）//查询结点的序号不合法
{
cout<<"查询序号错误！
"<return0;
}
return&（SL->ListData[n]）;
}
按照关键字查找结点
关键字可以是数据元素中的任意一项。
这里以key关键字为例进行介绍，例如，可以通过key查找学生的信息。
示例代码如下：
[cpp]viewplaincopyprint?
1.intSLFindByCont（SLType*SL,char*key）//按关键字查询结点
2.{
3.inti;
4.for（i=1;i<=SL->ListLen;i++）
5.{
6.if（strcmp（SL->ListData[i].key,key）==0）//如果找到结点
7.{
8.returni;
9.}
10.}
11.return0;//在整个表中都没有找到，返回0intSLFindByCont（SLType*SL,char*key）//按关键字查询结点
{
inti;
for（i=1;i<=SL->ListLen;i++）
{
if（strcmp（SL->ListData[i].key,key）==0）//如果找到结点
{
returni;
}
}
return0;//在整个表中都没有找到，返回0
}
显示所有的结点
示例代码如下
[cpp]viewplaincopyprint?
1.voidSLALL（SLType*SL）
2.{
3.inti;
4.for（i=1;iListLen;i++）
5.{
6.cout<<"key:
"<ListData[i].key<7.cout<<"name:
"<ListData[i].name<8.cout<<"age:
"<ListData[i].age<9.cout<<"============================="<10.}
11.}
voidSLALL（SLType*SL）
{
inti;
for（i=1;iListLen;i++）
{
cout<<"key:
"<ListData[i].key<cout<<"name:
"<ListData[i].name<cout<<"age:
"<ListData[i].age<cout<<"============================="<}
}
顺序表操作完整示例：
基本上就是把上面的函数放到一块，集中展示了一下功能，代码有些长，请耐心阅读^.^
[cpp]viewplaincopyprint?
1.#include
2.#include
3.usingnamespacestd;
4.#defineMAXLEN100//定义顺序表的最大长度
5./**************顺序表的定义部分*****************/
6.structDATA
7.{
8.stringkey;//结点的关键字
9.stringname;
10.intage;
11.};
12.structSLType//定义顺序表结构
13.{
14.DATAListData[MAXLEN+1];//保存顺序表的结构数组
15.intListLen;//顺序表已存结点的数量
16.};
17./************顺序表的初始化函数*****************/
18.voidSLInit（SLType*SL）//初始化顺序表
19.{
20.SL->ListLen=0;
21.}
22./***********计算线性表的长度*******************/
23.intSLLenght（SLType*SL）
24.{
25.return（SL->ListLen）;//返回顺序表的元素数量
26.}
27./*********插入结点*******************************/
28.intSLInsert（SLType*SL,intn,DATAdata）
29.{
30.inti;
31.if（SL->ListLen>=MAXLEN）//顺序表结点数量已超过最大数量
32.{
33.cout<<"顺序表已满，不能插入结点！
"<34.return0;//返回0表示插入不成功
35.}
36.if（n<1||n>SL->ListLen）//插入结点的序号不合法
37.{
38.cout<<"插入序号错误！
"<39.return0;
40.}
41.for（i=SL->ListLen;i>=n;i--）//将顺序表中的数据向后移动
42.{
43.SL->ListData[i+1]=SL->ListData[i];
44.}
45.SL->ListData[n]=data;
46.SL->ListLen++;
47.return1;//成功插入，返回1
48.}
49./***********************追加结点*************************/
50.intSLAdd（SLType*SL,DATAdata）
51.{
52.if（SL->ListLen>=MAXLEN）
53.{
54.cout<<"顺序表已满，不能再添加结点了！
"<55.return0;
56.}
57.SL->ListData[++SL->ListLen]=data;
58.return1;
59.}
60./***********************删除结点*************************/
61.intSLDelete（SLType*SL,intn）//删除顺序表中的数据元素
62.{
63.inti;
64.if（n<1||n>SL->ListLen）//删除结点的序号不合法
65.{
66.cout<<"删除序号错误！
"<67.return0;
68.}
69.for（i=n;iListLen;i++）//将顺序表中的数据向前移动
70.{
71.SL->ListData[i]=SL->ListData[i+1];
72.}
73.SL->ListLen--;//顺序表元素数量减1
74.return1;//成功删除返回1
75.}
76./*******************按照序号查找结点********************/
77.DATA*SLFindByNum（SLType*SL,intn）//根据序号返回数据元素
78.{
79.if（n<1||n>SL->ListLen）//查询结点的序号不合法
80.{
81.cout<<"查询序号错误！
"<82.return0;
83.}
84.return&（SL->ListData[n]）;
85.}
86./*******************按照关键字查找结点********************/
87.DATA*SLFindByCont（SLType*SL,stringname）//按关键字查询结点
88.{
89.inti;
90.for（i=1;i<=SL->ListLen;i++）
91.{
92.if（SL->ListData[i].name==name）//如果找到结点
93.{
94.return&（SL->ListData[i]）;
95.}
96.}
97.return0;//在整个表中都没有找到，返回0
98.}
99./*******************显示所有的结点********************/
100.voidSLALL（SLType*SL）
101.{
102.inti;
103.for（i=1;i<=SL->ListLen;i++）
104.{
105.cout<<"key:
"<ListData[i].key<<",name:
"<ListData[i].name<<",age:
"<ListData[i].age<106.}
107.}
108.intmain（）
109.{
110.inti;
111.SLTypeSL;//定义顺序表变量
112.DATAdata;//定义结点保存数据类型变量
113.DATA*pdata;//定义指向结点的指针变量
114.stringname;
115.cout<<"顺序表操作演示：
"<116.SLInit（&SL）;//初始化顺序表
117.do
118.{//循环添加结点数据
119.cout<<"请输入要添加的结点（学号姓名年龄）：
";
120.cin>>data.key>>data.name>>data.age;
121.if（data.age）//若年龄不为0
122.{
123.if（!
SLAdd（&SL,data））//若添加结点失败
124.{
125.break;//退出循环
126.}
127.}else
128.{
129.break;
130.}
131.}while
（1）;
132.cout<<"顺序表中的结点顺序为：
"<133.SLALL（&SL）;//显示所有的结点
134.cout<<"请输入要取出的结点序号：
";
135.cin>>i;
136.pdata=SLFindByNum（&SL,i）;//按序号查找结点
137.if（pdata）
138.{
139.cout<<"第"<key:
"<key<<",name:
"<name<<",age:
"<age<140.}
141.cout<<"请输入要查找的姓名：
";
142.cin>>name;
143.pdata=SLFindByCont（&SL,name）;
144.if（pdata）
145.{
146.cout<<"key:
"<key<<",name:
"<name<<",age:
"<age<147.}
148.cout<<"请输入您要删除的结点的序号：
";
149.cin>>i;
150.if（SLDelete（&SL,i））
151.{
152.cout<<"数据删除成功"<153.SLALL（&SL）;
154.}
155.cout<<"请输入您要插入的结点的序号：
";
156.cin>>i;
157.cout<<"请输入第"<158.cin>>data.key>>data.name>>data.age;
159.if（SLInsert（&SL,i,data））
160.{
161.cout<<"插入数据成功"<162.SLALL（&SL）;
163.}
164.return0;
165.}#include
#include
usingnamespacestd;
#defineMAXLEN100//定义顺序表的最大长度
/**************顺序表的定义部分*****************/
structDATA
{
stringkey;//结点的关键字
stringname;
intage;
};
structSLType//定义顺序表结构
{
DATAListData[MAXLEN+1];//保存顺序表的结构数组
intListLen;//顺序表已存结点的数量
};
/************顺序表的初始化函数*****************/
voidSLInit（SLType*SL）//初始化顺序表
{
SL->ListLen=0;
}
/***********计算线性表的长度*******************/
intSLLenght（SLType*SL）
{
return（SL->ListLen）;//返回顺序表的元素数量
}
/*********插入结点*******************************/
intSLInsert（SLType*SL,intn,DATAdata）
{
inti;
if（SL->ListLen>=MA
升级会员 