Vijos数据结构基础C++实验整理（四）——链式描述线性表

实验内容：
1、链表实现
（一）封装链表类，链表迭代器类
（二）链表类需提供操作：在指定位置插入元素，删除指定元素，搜索链表中是否有指定元素，原地逆置链表，输出链表
2、链表合并
使用题目链表实现中实现的链表类、迭代器类完成

样例：
1、
输入
10 10
6863 35084 11427 53377 34937 14116 5000 49692 70281 73704
4 6863
1 2 44199
5
4 21466
1 6 11483
5
4 34937
5
4 6863
1 10 18635
输出
0
398665
-1
410141
5
410141
0

2、
输入
3 0
3 1 2
输出
5
0
5

代码实现：

#include<iostream>
using namespace std;
template <class T>
struct chainNode {
T element;
chainNode<T>* next;
chainNode() {}
chainNode(const T& element) {
this->element = element;
}
chainNode(const T& element, chainNode<T>* next) {
this->element = element; this->next = next;
}
};
template <class T>
class chain {
public:
void preset(T* a, int length) {
chainNode<T>* first;
first = new chainNode<T>(a[0]);
first->next = new chainNode<T>(a[1]);
first->next->next = NULL;
if (length > 1) {
for (int i = 2; i < length; i++) {
chainNode<T>* p = new chainNode<T>(a[i]);
p->next = first->next;
first->next = p;
}
}firstNode = first;
listSize = length;
}
~chain();
void output() {
int sum = 0;
int i = 0;
for (chainNode<T>* currentNode = firstNode; currentNode != NULL; currentNode = currentNode->next) {
sum = sum + ((currentNode->element) ^ i);
i++;
}
cout << sum<<endl;
}
int firstIndexOf(T theElement);
void reverse();
void reverse2();
void insert(int theIndex, const T& theElement);
void erase(T theElement);
void Output(ostream& out) const;
// iterators to start and end of list
class iterator;
iterator begin() { return iterator(firstNode); }
iterator end() { return iterator(NULL); }
// iterator for chain
class iterator
{
public:
// typedefs required by C++ for a forward iterator
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
// constructor
iterator(chainNode<T>* theNode = NULL)
{
node = theNode;
}
// dereferencing operators
T& operator*() const { return node->element; }
T* operator->() const { return &node->element; }
// increment
iterator& operator++()
// preincrement
{
node = node->next; return *this;
}
iterator operator++(int) // postincrement
{
iterator old = *this;
node = node->next;
return old;
}
// equality testing
bool operator!=(const iterator right) const
{
return node != right.node;
}
bool operator==(const iterator right) const
{
return node == right.node;
}
protected:
chainNode<T>* node;
};
// end of iterator class
protected:
chainNode<T>* firstNode;
int listSize;
};
template<class T>
void chain<T>::Output(ostream& out) const
{// Put the list into the stream out.
for (chainNode<T>* currentNode = firstNode;
currentNode != NULL;
currentNode = currentNode->next)
out << currentNode->element << "
";
}
template<class T>
void chain<T>::insert(int theIndex, const T& theElement){
if (theIndex == 0)
firstNode = new chainNode<T>(theElement, firstNode);
else{
chainNode<T>* p = firstNode;
for (int i = 0; i < theIndex - 1;i++)
p = p->next;
p->next =new chainNode<T>(theElement, p->next);
}
listSize++;
}
template<class T>
void chain<T>::erase(T theElement)
{
chainNode<T>* p;
if (firstNode->element == theElement)
{
p = firstNode;
firstNode = firstNode->next;
delete p;
listSize--;
return;
}
for (chainNode<T>* pguard = firstNode; pguard->next; pguard = pguard->next)
{
if (pguard->next->element == theElement)
{
p = pguard->next;
pguard->next = p->next;
delete p;
listSize--;
return;
}
}
cout <<-1<<endl;
}
template <class T>
chain<T>::~chain()
{
while (firstNode != NULL) {
chainNode<T>* nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
template<class T>
int chain<T>::firstIndexOf(T theElement) {
chainNode<T>* p = firstNode;
int i = 0, j = -1;
if (p->element == theElement) {
j = 0;
}
else {
for (i = 1; i < listSize; i++) {
p = p->next;
if (p->element == theElement) {
j = i;
break;
}
}
}
return j;
}
template<class T>
void chain<T>::reverse() {
chainNode<T>* p = firstNode;
firstNode = firstNode->next;
p->next = NULL;
chainNode<T>* q = firstNode->next;
for (int i = 0; i < listSize - 3; i++)
{
firstNode->next = p;
p = firstNode;
firstNode = q;
q = firstNode->next;
}
firstNode->next = p;
q->next = firstNode;
firstNode = q;
}
template<class T>
void chain<T>::reverse2() {
T trans;
int i, j;
chainNode<T>* p = firstNode->next;
chainNode<T>* q = firstNode;
for (i = 0; i < listSize / 2; i++) {
for (j = 0; j < listSize - i - 1; j++) {
q = q->next;
}
trans = p->element;
p->element = q->element;
q->element = trans;
p = p->next;
q = firstNode;
}
}
int main() {
int N, Q;
cin >> N >> Q;
int* a = new int[N];
chain<int> b;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
b.preset(a, N);
b.reverse2();
int t, idx, val;
for (int j = 0; j < Q; j++) {
cin >> t;
switch (t) {
case 1:
cin >> idx >> val;
b.insert(idx, val);
break;
case 2:
cin >> val;
b.erase(val);
break;
case 3:
b.reverse();
break;
case 4:
cin >> val;
cout << b.firstIndexOf(val)<<endl;
break;
case 5:
int sum = 0, j = 0;
for (chain<int>::iterator i = b.begin();i != b.end(); i++) {
sum = sum + ((*i)^j);
j++;
}
cout <<sum<<endl;
break;
}
}
return 0;
}
4-2：
#include<iostream>
using namespace std;
template <class T>
struct chainNode {
T element;
chainNode<T>* next;
chainNode() {}
chainNode(const T& element) {
this->element = element;
}
chainNode(const T& element, chainNode<T>* next) {
this->element = element; this->next = next;
}
};
template <class T>
class chain {
public:
chain() {
firstNode=NULL;
listSize = 0;
}
void preset(T* a, int length) {
chainNode<T>* first;
first = new chainNode<T>(a[0]);
first->next = new chainNode<T>(a[1]);
first->next->next = NULL;
if (length > 1) {
for (int i = 2; i < length; i++) {
chainNode<T>* p = new chainNode<T>(a[i]);
p->next = first->next;
first->next = p;
}
}firstNode = first;
listSize = length;
}
~chain();
void clear()
{
while (firstNode != NULL)
{
chainNode<T>* nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
void insert(int theIndex, const T& theElement);
void Output(ostream& out) const;
void Listsort();
void MergerList(chain &a, chain &b);
// iterators to start and end of list
class iterator;
iterator begin() { return iterator(firstNode); }
iterator end() { return iterator(NULL); }
// iterator for chain
class iterator
{
public:
// typedefs required by C++ for a forward iterator
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
// constructor
iterator(chainNode<T>* theNode = NULL)
{
node = theNode;
}
// dereferencing operators
T& operator*() const { return node->element; }
T* operator->() const { return &node->element; }
// increment
iterator& operator++()
// preincrement
{
node = node->next; return *this;
}
iterator operator++(int) // postincrement
{
iterator old = *this;
node = node->next;
return old;
}
// equality testing
bool operator!=(const iterator right) const
{
return node != right.node;
}
bool operator==(const iterator right) const
{
return node == right.node;
}
protected:
chainNode<T>* node;
};
// end of iterator class
protected:
chainNode<T>* firstNode;
int listSize;
};
template<class T>
void chain<T>::Output(ostream& out) const
{// Put the list into the stream out.
for (chainNode<T>* currentNode = firstNode;
currentNode != NULL;
currentNode = currentNode->next)
out << currentNode->element << "
";
cout << endl;
}
template<class T>
void chain<T>::insert(int theIndex, const T& theElement) {
if (theIndex == 0)
firstNode = new chainNode<T>(theElement, firstNode);
else {
chainNode<T>* p = firstNode;
for (int i = 0; i < theIndex - 1; i++)
p = p->next;
p->next = new chainNode<T>(theElement, p->next);
}
listSize++;
}
template<class T>
void chain<T>::Listsort() {
if (listSize < 1) return;
chainNode<T> *p = NULL;
chainNode<T> *q = NULL;
for (p = firstNode; p != NULL; p = p->next)
{
for (q = p->next; q != NULL; q = q->next)
{
if (p->element > q->element)
{
T tmp = q->element;
q->element = p->element;
p->element = tmp;
}
}
}
}
template <class T>
chain<T>::~chain()
{
while (firstNode != NULL) {
chainNode<T>* nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
template<class T>
void chain<T>::MergerList(chain &a,chain &b) {
this->clear();
chain::iterator t1 = a.begin();
chain::iterator t2 = b.begin();
for (int i = 0; i < b.listSize; i++)
{
insert(i, *t2);
t2++;
}
for (int i = 0; i < a.listSize; i++)
{
insert(i, *t1);
t1++;
}
listSize = a.listSize + b.listSize;
}
int main() {
int N, M;
cin >> N >> M;
int* a1 = new int[N];
int* a2 = new int[M];
chain<int> b1, b2, c;
for (int i = 0; i < N; i++) {
cin >> a1[i];
}
for (int i = 0; i < M; i++) {
cin >> a2[i];
}
if(N>0) b1.preset(a1, N);
if(M>0) b2.preset(a2, M);
if (N == 0) {
cout << 0 << endl;
}
else {
b1.Listsort();
int sum = 0, j = 0;
for (chain<int>::iterator i = b1.begin(); i != b1.end(); i++) {
sum = sum + ((*i) ^ j);
j++;
}
cout << sum << endl;
}
if (M == 0) {
cout << 0 << endl;
}
else {
b2.Listsort();
int sum = 0, j = 0;
for (chain<int>::iterator i = b2.begin(); i != b2.end(); i++) {
sum = sum + ((*i) ^ j);
j++;
}
cout << sum << endl;
}
if (N == 0 && M == 0) {
cout << 0 << endl;
}
else if (N == 0 && M != 0) {
b2.Listsort();
int sum = 0, j = 0;
for (chain<int>::iterator i = b2.begin(); i != b2.end(); i++) {
sum = sum + ((*i) ^ j);
j++;
}
cout << sum << endl;
}
else if (N != 0 && M == 0) {
b1.Listsort();
int sum = 0, j = 0;
for (chain<int>::iterator i = b1.begin(); i != b1.end(); i++) {
sum = sum + ((*i) ^ j);
j++;
}
cout << sum << endl;
}
else {
c.MergerList(b1, b2);
c.Listsort();
int sum = 0, j = 0;
for (chain<int>::iterator i = c.begin(); i != c.end(); i++) {
sum = sum + ((*i) ^ j);
j++;
}
cout << sum << endl;
}
return 0;
}

最后

以上就是刻苦紫菜为你收集整理的Vijos数据结构基础C++实验整理（四）——链式描述线性表的全部内容，希望文章能够帮你解决Vijos数据结构基础C++实验整理（四）——链式描述线性表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。