单链表和双链表的倒序
-
2024-01-04 06:06:09 - 来源：未知
-
在手机上看
扫一扫立即进入手机端
#include
using namespace std;
//single link
struct slink_t{
struct slink_t* next;
int data;
slink_t(): next(0), data(0){
}
slink_t(slink_t* p, int d): next(p), data(d){
}
};
/*output data of single link */
ostream& operator<< (ostream& os, const struct slink_t* p)
{
cout << “Output : “;
while (p && cout << p->data << ' ')
p = p->next;
return os;
}
/* reverse the single link */
struct slink_t* slink_reverse(struct slink_t* p)
{
struct slink_t* t = NULL, *tp = NULL;
while (p)
{
tp = t;
t = p;
p = p->next;
t->next = tp;
}
return t;
}
//double link
struct dlink_t{
struct dlink_t* next;
struct dlink_t* prev;
int data;
dlink_t(): next(0), prev(0), data(0){
}
dlink_t(dlink_t* n, dlink_t* p, int d): next(n), prev(p), data(d){
}
};
/* output data of double link */
ostream& operator<< (ostream& os, const struct dlink_t* p)
{
cout << “Output : “;
while (p && cout << p->data << ' ')
p = p->next;
return os;
}
/* reverse the double link */
struct dlink_t* dlink_reverse(struct dlink_t* p)
{
struct dlink_t* t = NULL;
while (p)
{
t = p;
p = p->next;
t->next = t->prev;
t->prev = p;
}
return t;
}
#define TEST__
#ifdef TEST__
/* test */
int main()
{
struct slink_t* sl = new slink_t(new slink_t(new slink_t(new slink_t(new slink_t(new slink_t(NULL, 6), 5), 4), 3), 2), 1);
cout << sl << endl;
sl = slink_reverse(sl);
cout << sl << endl;
struct dlink_t* dl = NULL;
struct dlink_t* h = new dlink_t(NULL, dl, 1);
dl = h;
for (int i = 2; i < 10; i++)
{
struct dlink_t* t = new dlink_t(NULL, dl, i);
dl->next = t;
dl = t;
// dl->prev->next = dl;
}
cout << h << endl;
h = dlink_reverse(h);
cout << h << endl;
cout << “Hello world“ << endl;
return 0;
}
#endif
