王紅梅、胡明、王濤が編著した「データ構造c++」(第2版)テンプレート類チェーンテーブル超詳細コード
主に思想の参考と王紅梅、胡明、王濤が編纂した「データ構造c+」(第2版)を実現する.
および参考とブログ:https://blog.csdn.net/qq_37934101/article/details/80747366
何か不正確なところや不適切なところがありましたらご指摘ください
メールアドレス:[email protected]
yx.telstudy.xyz
および参考とブログ:https://blog.csdn.net/qq_37934101/article/details/80747366
何か不正確なところや不適切なところがありましたらご指摘ください
メールアドレス:[email protected]
yx.telstudy.xyz
#include
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
/**
* This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz
* created:2019.9.16
* crested:2019.9.18
* crested:2019.9.19
* crested:2019.9.21
* crested:2019.9.22
* crested:2019.9.23
* LinkList
*/
using namespace std;
template<class T> class LinkList;
template<class T>
class node {
public:
//
node(const T rdata, node<T> *rnext = NULL):data(rdata),next(rnext) {};
// ,
node(node<T> * rnext = NULL):next(rnext) {};
//
~node() {}
//
friend class LinkList<T>;
private:
//
T data;
//
node<T> *next;
};
// T LinkList
template<class T>
class LinkList {
public:
// ,
LinkList();
//
LinkList(LinkList<T> &rlist);
//
LinkList(T a[], int n);
// item i , i i
void Insert(int i, T item);
// i ,i ,
T Delete(int i);
//
T Findplace(int i);
//
int Finddata(T fdata);
//
int length () const;
// item ;
T Next(T item)const;
// item ;
T Prior(T item)const;
//
bool Empty() const;
//
bool Full()const;
bool IsIn(T)const;
//
LinkList<T>& operator=(const LinkList<T> &alist);
// , i ;
T operator[](int i)const;
// ;
void MakeEmpty();
//
void printLinkList();
//
~LinkList();
private:
//
node<T> * first;
};
//
template<class T>
LinkList<T>::LinkList() {
LinkList first = new node<T>;
if(!first) {
throw " ";
} else {
cout << " " << '
';
first->next = NULL;
}
}
template<class T>
LinkList<T>::LinkList(T a[], int n) {
first = new node<T>;//
if(!first) {
throw " ";
}
node<T> *s;
first->next = NULL;//
REP(i, 0, n) {
s = new node<T>;
if(!s) {
throw" ";
}
s->data = a[i];
s->next = first->next;
first->next = s;
}
}
//
template<class T>
void LinkList<T>::Insert(int i, T x) {
node<T>*p, *s;
p = first;
int cnt = 0;
while(p && cnt < i-1) {
p = p->next;
cnt++;
}
if(p == NULL) {
throw " ";
} else {
s = new node<T>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
template<class T>
T LinkList<T>::Delete(int i) {
// i
node<T> *p = first;
int cnt = 0;
while(p && cnt < i - 1) {
p = p->next;
cnt++;
}
if(p == NULL || p->next == NULL) {
throw " ";
} else {
node<T> *q = p->next;
T x = q->data;
p->next = q->next;
delete q;
return x;
}
}
template <class T>
int LinkList<T>::Finddata(T fdata) {
//
int cnt = 1;
node<T> *p = first->next;//
while(p) {
if(p->data == fdata){
return cnt;
}
cnt++;
p = p->next;
}
if(p == NULL) {
throw " ";
} else {
return cnt;
}
}
template <class T>
T LinkList<T>::Findplace(int i) {
//
int cnt = 0;
node<T> *p = first->next;
while(cnt < i && p) {
p = p->next;
cnt++;
}
if(p == NULL) {
throw " ";
} else {
return p->data;
}
}
template <class T>
void LinkList<T>::printLinkList() {
node<T> *p = first->next;
if(Empty()) {
cout << " , " << '
';
}
while(p) {
cout << p->data << '
';
p = p->next;
}
cout << '
';
return ;
}
template <class T>
int LinkList<T>::length()const {
int cnt = 0;
node<T> *p = first->next;
while(p) {
p = p->next;
cnt++;
}
return cnt;
}
template <class T>
LinkList<T>::~LinkList() {
node<T> *p;
while(first != NULL) {
p = first;
first = first->next;
delete p;
}
cout << " " << '
';
}
template <class T>
bool LinkList<T>::IsIn(T item) const {
node<T> *p = first->next;//
while(p) {
if(p->data == item)
return true;
p = p->next;
}
return false;
}
template <class T>
bool LinkList<T>::Full() const {
return false;
//
}
//
template<class T>
LinkList<T>& LinkList<T>::operator = (const LinkList & rlist) {
if(first == rlist.first) {
cout << " " ;
return *this;
}
MakeEmpty();
cout << " " << '
';
node<T> *p , *q;//
q = first->next;
p = rlist.first->next;
REP(i, 0, rlist.length()) {
T x = p->data;
Insert(i+1, x);
p = p->next;
}
return *this;
}
//
template<class T>
T LinkList<T>::operator[](int t) const {
node<T> *p;
p = first->next;
int cnt = 1;
while(p && cnt < t) {
p = p->next;
cnt++;
}
if(p == NULL) {
return 0;
} else {
return p->data;
}
}
template<class T>
void LinkList<T>::MakeEmpty() {
node<T> *p, *q;
p = first->next;
while(p) {
q = p->next;
delete p;
p = q;
}
first->next = NULL;
}
template<class T>
bool LinkList<T>:: Empty() const { //
if(first->next == NULL)
return true;
else
return false;
}
int main() {
printf(" , n = ");
int n;
cin >> n;
int *a = new int [n];
sort(a, a+n);
cout << " n ";
for(int i = 0; i < n; i++) {
cin >> a[i];
}
cout << "--------- : ---------" << '
';
LinkList<int> l(a, n);
l.printLinkList();
cout << "--------- ---------" << '
';
cout << "--------- : x item
x" << endl;
int x;
cin >> x;
cout << " item__" ;
int item;
cin >> item;
l.Insert(x, item);
l.printLinkList();
cout << "--------- ---------" << '
';
cout << "--------- : ---------" << '
';
l.printLinkList();
int i;
cout << " i";
cin >> i;
cout << " :" << l[i] << endl;
int fdata;
cout << " fdata" << '
';
cin >> fdata;
cout << fdata << " " << l.Finddata(fdata) << endl;
cout << "--------- ---------" << '
';
}