数据结构线性表的综合实验——单链表
一、实验目的
1、熟练掌握线性表的结构特点,掌
握顺序表的基本操作。
2、巩固 C++相关的程序设计方法与技术。
3、学会使用顺序表解决实际问题。
二、实验内容
1、用C++编写完整程序。
2、建立两个单链表,一个用以存放学生信息,另一个用来存放学生成绩,利用指针实现单链表的基本操作。
3、用类模板构造函数实现相关的操作:输出,插入,删除,查找等功能。
三、源代码
#include<iostream>
#include<string>
using namespace std;
#include<string>
using namespace std;
class Score {
private:
struct Node {
string data;
struct Node *next;
};
struct Node *first1;
struct Node *first2;
public:
Score(string a[], string b[], int n, int m);
~Score();
string Get(string na);
string Locate(int i);
void Insert(string na, string im, int i);
string Delete(string na);
void Printlist();
};
private:
struct Node {
string data;
struct Node *next;
};
struct Node *first1;
struct Node *first2;
public:
Score(string a[], string b[], int n, int m);
~Score();
string Get(string na);
string Locate(int i);
void Insert(string na, string im, int i);
string Delete(string na);
void Printlist();
};
Score::Score(string a[], string b[], int n, int m) {
first1 = new Node; first2 = new Node;
first1->next = NULL; first2->next = NULL;
for (int i = 0; i < n; i++) {
struct Node *s = new Node;
s->data = a[i];
s->next = first1->next;
first1->next = s;
}
for (int i = 0; i < m; i++) {
struct Node*k = new Node;
k->data = b[i];
k->next = first2->next;
first2->next = k;
}
}
Score::~Score() {
while (first1 != NULL) {
struct Node*q = first1; struct Node*t = first2;
first1 = first1->next; delete q;
first2 = first2->next; delete t;
}
}
first1 = new Node; first2 = new Node;
first1->next = NULL; first2->next = NULL;
for (int i = 0; i < n; i++) {
struct Node *s = new Node;
s->data = a[i];
s->next = first1->next;
first1->next = s;
}
for (int i = 0; i < m; i++) {
struct Node*k = new Node;
k->data = b[i];
k->next = first2->next;
first2->next = k;
}
}
Score::~Score() {
while (first1 != NULL) {
struct Node*q = first1; struct Node*t = first2;
first1 = first1->next; delete q;
first2 = first2->next; delete t;
}
}
void Score::Insert(string na, string im, int i) {
struct Node*p = first1; struct Node*s = first2;
int count = 0;
while (p != NULL&&count < i - 1) {
p = p->next; count++;
}
if (p == NULL)throw"位置异常";
else {
struct Node*q = new Node;
q->data = na;
q->next = p->next;
p->next = q;
}
struct Node*p = first1; struct Node*s = first2;
int count = 0;
while (p != NULL&&count < i - 1) {
p = p->next; count++;
}
if (p == NULL)throw"位置异常";
else {
struct Node*q = new Node;
q->data = na;
q->next = p->next;
p->next = q;
}
while (s != NULL&&count < i - 1) {
s = s->next;
count++;
}
if (s == NULL)throw"位置异常";
else {
struct Node*j = new Node;
j->data = im;
j->next = s->next;
s->next = j;
}
cout << "输入学生姓名:" << na << endl;
cout << "输入学生成绩:" << im << endl;
}
s = s->next;
count++;
}
if (s == NULL)throw"位置异常";
else {
struct Node*j = new Node;
j->data = im;
j->next = s->next;
s->next = j;
}
cout << "输入学生姓名:" << na << endl;
cout << "输入学生成绩:" << im << endl;
}
string Score::Get(string na) {
struct Node*p = first1->next; struct Node*q = first2->next;
int count = 1;
while (p != NULL&&q != NULL) {
if (p->data == na) {
return q->data;
}
else { p = p->next; q = q->next; count++; }
}
}
struct Node*p = first1->next; struct Node*q = first2->next;
int count = 1;
while (p != NULL&&q != NULL) {
if (p->data == na) {
return q->data;
}
else { p = p->next; q = q->next; count++; }
}
}
string Score::Locate(int i) {
struct Node*p = first1->next;
int count = 1;
if (p == NULL)throw"位置异常";
while (p != NULL&&count<i) {
p = p->next;
count++;
}
return p->data;
}
struct Node*p = first1->next;
int count = 1;
if (p == NULL)throw"位置异常";
while (p != NULL&&count<i) {
p = p->next;
count++;
}
return p->data;
}
string Score::Delete(string na) {
struct Node*p = first1; struct Node*s = first2;
while (p->data != na) {
p = p->next;
if ((p->next)->data == na) {
struct Node*q = p->next; string x = q->data;
p->next = q->next;
delete q;
struct Node*j = s->next; string y = j->data;
s->next = j->next;
delete j;
return y; return x;
}
struct Node*p = first1; struct Node*s = first2;
while (p->data != na) {
p = p->next;
if ((p->next)->data == na) {
struct Node*q = p->next; string x = q->data;
p->next = q->next;
delete q;
struct Node*j = s->next; string y = j->data;
s->next = j->next;
delete j;
return y; return x;
}
}
if (p->next = NULL)throw"位置异常";
if (p->next = NULL)throw"位置异常";
}
void Score::Printlist() {
struct Node*p = first1->next; struct Node*s = first2->next;
while (p != NULL&&s != NULL) {
cout << "学生姓名为:" << p->data << endl;
p = p->next;
cout << "数据结构成绩为:" << s->data << endl;
s = s->next;
}
struct Node*p = first1->next; struct Node*s = first2->next;
while (p != NULL&&s != NULL) {
cout << "学生姓名为:" << p->data << endl;
p = p->next;
cout << "数据结构成绩为:" << s->data << endl;
s = s->next;
}
}
int main() {
string a[3] = { "kk","jm","woojin" };
string b[3] = { "99","89","87" };
cout << "-------------------------------------------" << endl;
Score K(a, b, 3, 3);
K.Printlist();
cout << "-------------------------------------------" << endl;
cout << "新输入学生数据:" << endl;
cout << " " << endl;
K.Insert("Daniel", "88", 2);
cout << "输出新添加学生信息后的全部数据:" << endl;
cout << " " << endl;
K.Printlist();
cout << "-------------------------------------------" << endl;
cout << "查询kk的成绩:" << K.Get("kk") << endl;
cout << "-------------------------------------------" << endl;
cout << "查询位于第二位置的学生:" << K.Locate(2) << endl;
cout << "-------------------------------------------" << endl;
cout << "删除名为jm的学生信息:" << K.Delete("jm") << endl;
K.Printlist();
string a[3] = { "kk","jm","woojin" };
string b[3] = { "99","89","87" };
cout << "-------------------------------------------" << endl;
Score K(a, b, 3, 3);
K.Printlist();
cout << "-------------------------------------------" << endl;
cout << "新输入学生数据:" << endl;
cout << " " << endl;
K.Insert("Daniel", "88", 2);
cout << "输出新添加学生信息后的全部数据:" << endl;
cout << " " << endl;
K.Printlist();
cout << "-------------------------------------------" << endl;
cout << "查询kk的成绩:" << K.Get("kk") << endl;
cout << "-------------------------------------------" << endl;
cout << "查询位于第二位置的学生:" << K.Locate(2) << endl;
cout << "-------------------------------------------" << endl;
cout << "删除名为jm的学生信息:" << K.Delete("jm") << endl;
K.Printlist();
}
四、实验结果
五、总结与疑惑
此次试验使用两个单链表,一个用于存储学生姓名,另一个用于存储学生成绩,因此建立了两个头指针。比较麻烦的是有时候指针多了会弄混。实验过程中有一个问题一直调试不好,就是delete函数里if函数中的条件问题,因为加了指针域经常搞混数据的位置,出现调试问题,很难发现,因此最好在敲代码之前把思路全理清记下易混淆的点再开始敲代码。