数据结构学习贴....《学习的开始》
因为刚刚开始学习数据结构
...开一个帖子发我做数据结构后面习题的答案
....大概就这样吧
....另外...我用的是C++和C
...虽然大部分都是用C++没怎么用C
....各位看官请不必手下留情，尽情吐槽
首先是链式线性表
.#ifndef CHAIN_H
#define CHAIN_H
#include <iostream>
using namespace std;
template<class T>
class Chain{
private:
template<class T>
class ChainNode{
friend Chain<T>;
private:
T data;
ChainNode<T> *link;
};
public:
Chain()
{ first = 0; length = 0; }
Chain(const Chain<T> &c);
~Chain();
bool isEmpty() const
{ return length == 0; }
int Length() const
{ return length; }
bool Find(int k, T &x)const;
int Search(const T &x) const;
Chain<T>& Delete(int k, T &x);
Chain<T>& Insert(int k, const T &x);
void Output(ostream &out);
void Reverse();
void Alternate(const Chain<T> &a, const Chain<T> &b);
void Merge(const Chain<T> &a, const Chain<T> &b);
void Split(Chain<T> &a, Chain<T> &b);
private:
ChainNode<T> *first;
int length;
};
template<class T>
void Chain<T>::Split(Chain<T> &a, Chain<T> &b)
{
ChainNode<T> *p = first;
int n = 1, m = 1;
for(int i = 0; i != length; i++){
if((i+1)%2){
a.Insert(n++, p->data);
}else{
b.Insert(m++, p->data);
}
p = p->link;
}
}
template<class T>
void Chain<T>::Merge(const Chain<T> &a, const Chain<T> &b){
ChainNode<T> *a1 = a.first, *b1 = b.first;
int value = 0;// 0 1 2 3
int i = 1, n = 0, m = 0;
while(1){
if(value == 0){
if(b.length == m){
value = 2;
continue;
}else{
value = 1;
}
if(a1->data >= b1->data){
value = 1;
continue;
}
Insert(i++, a1->data);
a1 = a1->link;
n++;
if(b.length == m){
value = 2;
}else{
value = 1;
}
}else if(value == 1){
if(a.length == n){
value = 3;
continue;
}else{
value = 0;
}
if(a1->data <= b1->data){
value = 1;
continue;
}
Insert(i++, b1->data);
b1 = b1->link;
m++;
if(a.length == n){
value = 3;
}else{
value = 0;
}
}else if(value == 2){
;
for(int j = i; n != a.length; ++n){
Insert(j++, a1->data);
a1 = a1->link;
}
break;
}else{
;
for(int j = i; m != b.length; ++m){
Insert(j++, b1->data);
b1 = b1->link;
}
break;
}
}
}
template<class T>
void Chain<T>::Alternate(const Chain<T> &a, const Chain<T> &b)
{
ChainNode<T> *a1 = a.first, *b1 = b.first;
int value = 0;// 0 1 2 3
int i = 1, n = 0, m = 0;
while(1){
if(value == 0){
Insert(i++, a1->data);
a1 = a1->link;
n++;
if(b.length == m){
value = 2;
}else{
value = 1;
}
}else if(value == 1){
Insert(i++, b1->data);
b1 = b1->link;
m++;
if(a.length == n){
value = 3;
}else{
value = 0;
}
}else if(value == 2){
for(int j = i; n != a.length; ++n){
Insert(j++, a1->data);
a1 = a1->link;
}
break;
}else{
for(int j = i; m != b.length; ++m){
Insert(j++, b1->data);
b1 = b1->link;
}
break;
}
}
}
template<class T>
void Chain<T>::Reverse()
{
int value;
if(length % 2){
value = 0;
}else{
value = 1;
}
T x;
ChainNode<T> *p = first, *q = first;
for(int i = 0; i != length/2-value; ++i){
for(int j = 1; j != length - i; ++j){
q = q->link;
}
x = p->data;
p->data = q->data;
q->data = x;
p = p->link;
}
}
template<class T>
bool Chain<T>::Find(int k, T &x) const
{
if (k <= 0 && k >= length){
cerr << "Find:error input for K.";
return false;
}
for(int i = 0; i != k; i++){
first = first->link;
}
x = first->data;
return true;
}
template<class T>
int Chain<T>::Search(const T &x) const
{
for(int i = 0; i != length; i++){
if(first->data == x)
return i+1;
first = first->link;
}
return 0;
}
template<class T>
void Chain<T>::Output(ostream &out)
{
ChainNode<T> *p = first;
for(int i = 0; i != length; i++){
cout << p->data << " ";
p = p->link;
}
}
template<class T>
Chain<T>& Chain<T>::Delete(int k, T &x)
{
if (k <= 0 && k >= length){
cerr << "Delete:error input for K.";
return *this;
}
ChainNode<T> *p;
for(int i = 1; i != k; i++){
first = first->link;
}
x = first->data;
p = first->link;
first->link = p->link;
delete p;
--length;
return *this;
}
template<class T>
Chain<T>& Chain<T>::Insert(int k, const T &x)
{
if(k <= 0){
cerr << "Insert: error";
return *this;
}
ChainNode<T> *p = new ChainNode<T>;
if(k == 1){
p->data = x;
if(length != 0)
p->link = first;
else
p->link = 0;
first = p;
}else if(k >= length){
p->data = x;
p->link = 0;
ChainNode<T> *q = first;
for(int j = 1; j != length; j++){
q = q->link;
}
q->link = p;
}else{
p->data = x;
p->link = first->link;
first->link = p;
}
++length;
return *this;
}
template<class T>
Chain<T>::Chain(const Chain<T> &c)
{
Chain<T> *c1 = new Chain<T>;
ChainNode<T> *p = c.first;
for(int i = 0; i != c.length; i++){
c1->Insert(i+1, p->data);
p = p->link;
}
first = c1->first;
length = c1->length;
}
template<class T>
Chain<T>::~Chain()
{
ChainNode<T> *p = first;
for(int i = 0; i != length; i++){
first = p;
p = p->link;
delete first;
}
}
#endif
[ 本帖最后由 z286503288 于 2011-8-27 22:34 编辑 ]
....难道都要做完吗？
