线性表综合实验——静态链表
一、实验目的
1、熟练掌握线性表的结构特点,掌握顺序表的基本操作。
2、巩固 C++相关的程序设计方法与技术。
3、学会使用顺序表解决实际问题。
二、实验内容
1、用C++编写完整程序。
2、建立一个静态链表,用数组来表示单链表,即用数组元素的下标来模拟单链表的指针,利用两个伪指针first 和 avail进行数据操作。
3、用类和结构体实现相关的操作:输出,插入,删除,查找等功能。
三、源代码
#include<iostream>
#include<string>
using namespace std;
#include<string>
using namespace std;
const int Max = 100;
struct Node {
int data;
int next;
}List[Max];
struct Node {
int data;
int next;
}List[Max];
class Score {
private:
int first;
int avail;
public:
Score() {}
Score(int a[], int n) {
int s;
if (n >= Max || n <= 0)throw"输入有误";
first = 0;//初始化静态链表的头指针
List[0].next = avail = 1;//初始化空闲链的头指针
for (int i = 0; i < Max - 1; i++)
{
List[i].next = i + 1;
}
List[Max - 1].next = -1;
for (int i = 0; i < n; i++)
{
s = avail;
avail = List[avail].next;//将此时空闲链最前端赋给空闲链的头指针
List[s].data = a[i];//将数据放入空闲链最前端
}
List[s].next = -1;
}
void Insert(int x, int i);//将数据x插入第i个结点后;
int Get(int x);//查找数值为x的结点位置
int Locate(int i);//查找下标为i的结点
int Delete(int i);//删除下标为i的结点
void Printlist();
};
{
s = avail;
avail = List[avail].next;//将此时空闲链最前端赋给空闲链的头指针
List[s].data = a[i];//将数据放入空闲链最前端
}
List[s].next = -1;
}
void Insert(int x, int i);//将数据x插入第i个结点后;
int Get(int x);//查找数值为x的结点位置
int Locate(int i);//查找下标为i的结点
int Delete(int i);//删除下标为i的结点
void Printlist();
};
void Score::Insert(int x, int i) {
int s;
s = avail;
avail = List[avail].next;
List[s].data = x;
for (int p = 0; p<Max - 1; p++)
{
if (p == i)
{
List[s].next = List[p].next;
List[p].next = s;
cout << List[s].data << endl;
}
}
}
int Score::Get(int x) {
int count;
count = List[first].next;
int s;
s = avail;
avail = List[avail].next;
List[s].data = x;
for (int p = 0; p<Max - 1; p++)
{
if (p == i)
{
List[s].next = List[p].next;
List[p].next = s;
cout << List[s].data << endl;
}
}
}
int Score::Get(int x) {
int count;
count = List[first].next;
for (count; count != -1; count++)
{
if (List[count].data == x)
{
return count;
}
}
return 0;
}
{
if (List[count].data == x)
{
return count;
}
}
return 0;
}
int Score::Locate(int i) {
if (i >= 0 && i <= Max)
{
return List[i].data;
}
else {
throw"位置";
return 0;
}
}
if (i >= 0 && i <= Max)
{
return List[i].data;
}
else {
throw"位置";
return 0;
}
}
int Score::Delete(int i) {
if (i>0 && i<Max)
{
int q;
i = i - 1;
q = List[i].next;//暂存被删除节点的下标
List[i].next = List[q].next;//摘链
List[q].next = avail;//将节点q插在空闲连的最前端
avail = q;//空闲链头指针avail指向节点q
return List[q].data;
}
else
{
throw"位置";
return 0;
}
}
if (i>0 && i<Max)
{
int q;
i = i - 1;
q = List[i].next;//暂存被删除节点的下标
List[i].next = List[q].next;//摘链
List[q].next = avail;//将节点q插在空闲连的最前端
avail = q;//空闲链头指针avail指向节点q
return List[q].data;
}
else
{
throw"位置";
return 0;
}
}
void Score::Printlist() {
int p;
p = List[first].next;
int p;
p = List[first].next;
while (p != -1)
{
cout << List[p].data << ",";
p = List[p].next;
}
}
{
cout << List[p].data << ",";
p = List[p].next;
}
}
int main() {
int a[4] = { 88,89,87,85 };
Score K(a, 4);
cout << "输入数据:";
K.Printlist();
cout << "\n";
cout << "--------------------------------------------------------------" << endl;
cout << "在第二个位置插入数据:";
K.Insert(99, 2);
cout << "--------------------------------------------------------------" << endl;
cout << "显示所有数据:";
K.Printlist();
cout << "\n";
cout << "--------------------------------------------------------------" << endl;
cout << "在第三个位置插入数据:";
K.Insert(56, 3);
cout << "显示所有数据:";
K.Printlist();
cout << "\n";
cout << "--------------------------------------------------------------" << endl;
cout << "查找成绩为87的所在位置:" << K.Get(87) << endl;
cout << "\n";
cout << "--------------------------------------------------------------" << endl;
cout << "查找第一个数据:" << K.Locate(1) << endl;
cout << "--------------------------------------------------------------" << endl;
cout << "删除第3个的数据结构成绩:" << K.Delete(3) << endl;
cout << "显示所有数据:";
K.Printlist();
}
四、实验结果
五、总结与反思
一开始不是很明白静态链表的构成,一开始按照单链表的结构输入数据,改了输入与删除函数,最后发现错误很多,思路一下子断了,于是重新从头敲。静态链表比单链表更复杂的一点在于,有时候会把next指针与数组下标弄混,所以我敲完后再次查看是需要自己根据代码画出图来辨别。插入操作需要将空闲链的前一个结点摘下,放入first链;删除操作则是把first链需要删除的结点放入avail链中。
为何第一个插入数据可以第二个插入数据就没法按照要求位置插入?