实验二 线性表综合实验(单链表)
程序员文章站
2022-06-06 13:34:39
...
一.实验目的
巩固线性表的数据结构的存储方法和相关操作,学会针对具体应用,使用线性表的相关知识来解决具体问题。
二. 实验内容
1.建立一个由n个学生成绩的顺序表,n的大小由自己确定,每一个学生的成绩信息由自己确定,实现数据的对表进行插入、删除、查找等操作。分别输出结果。
单链表 源代码:
#include <iostream>
using namespace std;
template <class DataType>
struct Node
{
DataType data;
Node<DataType> *next;
};
template <class DataType>
class LinkList
{
public:
LinkList();
LinkList(DataType a[], int n);
~LinkList();
int Length();
DataType Get(int i);
int Locate(DataType x);
void Insert(DataType x, int i);
DataType Delete(int i);
void PrintList();
private:
Node<DataType> * first;
};
template <class DataType>
void LinkList<DataType> ::PrintList()
{
Node<DataType>*p=NULL;
p = first->next; //工作指针P初始化
cout << "[";
while (p != NULL)
{
cout << p->data<<" ";
p = p->next;
}
cout << "]"<<endl;
}
template <class DataType>
int LinkList<DataType>::Length()
{
Node<DataType>*p = NULL;
p = first->next;
int count = 0;
while (p != NULL)
{
p = p->next;
count++;
}
return count;
}
template <class DataType>
DataType LinkList<DataType>::Get(int i)
{
Node<DataType>*p = NULL;
p = first->next;
int count = 1;
while (p!=NULL&&count<i)
{
p = p->next;
count++;
}
if (p == NULL) throw"输入位置异常";
else
{
return p->data;
}
}
template <class DataType>
int LinkList<DataType>::Locate(DataType x)
{
Node<DataType>*p = NULL;
p = first->next;
int count = 1;
while (p != NULL)
{
if (p->data == x)
return count;
p = p->next;
count++;
}
return 0;
}
template <class DataType>
void LinkList<DataType>::Insert(DataType x, int i)
{
Node<DataType>*p,*s;
p = first;
int count = 0;
while (p != NULL && count < i - 1)
{
p = p->next;
count++;
}
if (p == NULL)throw "插入位置异常";
else
{
s = new Node<DataType>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
template <class DataType>
LinkList <DataType>::LinkList()
{
first = new Node<DataType>;
first->next = NULL;
}
template <class DataType>
LinkList<DataType>::LinkList(DataType a[], int n) //尾插法
{
Node<DataType> *s, *r;
first = new Node<DataType>;
r = first;
for (int i = 0; i < n; i++)
{
s = new Node<DataType>;
s->data = a[i];
r->next = s;
r= s;
}
r->next = NULL;
}
template <class DataType>
DataType LinkList<DataType>::Delete(int i)
{
Node<DataType>*p;
p = first;
int count = 0;
while (p != NULL&&count < i - 1)
{
p=p->next;
count++;
}
if (p == NULL || p->next == NULL)
throw "删除位置异常";
else
{
Node<DataType>*q = NULL;
q = p->next;
DataType x = q->data;
p->next = q->next;
delete q;
return x;
}
}
template <class DataType>
LinkList <DataType>::~LinkList()
{
Node<DataType>*q = NULL;
while (first != NULL)
{
q = first;
first = first->next;
delete q;
}
cout << "链表已成功删除。" <<endl;
}
int main()
{
int num;
cout << "请输入学生人数:";
cin >> num;
// int stu[50]; //最大容纳量
// for (int i = 0; i < num; i++)
// {
// cout << "请输入第"<<i+1<<"名学生成绩:";
// cin >> stu[i];
// }
int studemo[] = { 50,60,70,80,90 };
LinkList<int> demo(studemo, num);
demo.PrintList(); //展示学生成绩
cout << "--------------------" << endl;
cout << "查找第三名学生成绩:" << demo.Get(3) << endl;
cout << "--------------------" << endl;
cout << "查找成绩为90的学生的位置:" << demo.Locate(90) << endl;
cout << "--------------------" << endl;
cout << "在第四与第五之间插入成绩85:"<<endl;
cout << "结果为:";
demo.Insert(85, 5);
demo.PrintList();
cout << "--------------------" << endl;
cout << "链表总长为:";
cout << demo.Length() << endl;
cout << "--------------------" << endl;
cout << "删除第6位成绩:";
cout << demo.Delete(6)<<endl;
cout << "结果为:";
demo.PrintList();
cout << "--------------------" << endl;
cout << "析构链表"<<endl;
demo.~LinkList();
return 0;
}
实验截图:
实验总结和心得体会:
通过本次实验,我基本掌握了链表的基本操作。链表的内涵并非像数组、类、结构体、联合体等那样,链表不是C++语言中的关键词,链表是我们利用C++语言中的基本数据类型构造出来的结构,具有动态申请内存和增删效率高的特点。
实验前期,对链表的理解不足,只能参考书本的代码来写,实际上书本的代码段是伪代码,写出来无法运行。经过不断的查阅资料和修改,程序终于可以运行。
在最后调用析构函数时,“链表已成功删除”会被打印两次。经过试验后发现,原来当主函数结束时,系统就会自动调用构造函数,所以出现了两次调用的情况。
上一篇: canvas刮奖效果_html/css_WEB-ITnose
下一篇: 二分图