C++实现：单链表的反转(序)操作
[cpp]
//main.cpp
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <string>
#include <vector>
#include "linklist.cpp"
#define MAXINTLEN 10
using namespace std;
int main(int argc, char *argv[])
{
int tmp[MAXINTLEN];
double runtime = 0;
clock_t s,e;
linklist sl;
for (int i = 0; i < MAXINTLEN; i++)
{
//srand((unsigned)time(i));
tmp[i] = rand()%100;
}
s = clock();
sl.construct_link(tmp,MAXINTLEN);
cout<<"this linklist..."<<endl;
sl.print_link();
sl.reverse();
cout<<"after reverse..."<<endl;
sl.print_link();
e = clock();
runtime = (double)(e - s);//CLOCKS_PER_SEC;
cout<<"runtime is:"<<runtime<<endl;
return 0;
}
//main.cpp
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <string>
#include <vector>
#include "linklist.cpp"
#define MAXINTLEN 10
using namespace std;
int main(int argc, char *argv[])
{
int tmp[MAXINTLEN];
double runtime = 0;
clock_t s,e;
linklist sl;
for (int i = 0; i < MAXINTLEN; i++)
{
//srand((unsigned)time(i));
tmp[i] = rand()%100;
}
s = clock();
sl.construct_link(tmp,MAXINTLEN);
cout<<"this linklist..."<<endl;
sl.print_link();
sl.reverse();
cout<<"after reverse..."<<endl;
sl.print_link();
e = clock();
runtime = (double)(e - s);//CLOCKS_PER_SEC;
cout<<"runtime is:"<<runtime<<endl;
return 0;
}
[cpp]
// linklist.hxx
#ifndef LINKLIST_H_
#define LINKLIST_H_
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
};
class linklist
{
private:
struct node *head;
int length;
public:
linklist();
~linklist();
struct node* get_link(void);
void construct_link(int *arr, int num);
int get_length(void);
void reverse(void);
void print_link(void);
};
#endif
// linklist.hxx
#ifndef LINKLIST_H_
#define LINKLIST_H_
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
};
class linklist
{
private:
struct node *head;
int length;
public:
linklist();
~linklist();
struct node* get_link(void);
void construct_link(int *arr, int num);
int get_length(void);
void reverse(void);
void print_link(void);
};
#endif
[cpp]
// linklist.cpp
#include "linklist.hxx"
linklist::linklist()
{
this->head = NULL;
this->length = 0;
}
struct node* linklist::get_link(void)
{
return this->head;
}
void linklist::construct_link(int *arr, int num)
{ // use int array to construct linklist
struct node *tmp, *cur;
for (int i = 0; i < num; ++i)
{
tmp = new (struct node);
tmp->data = arr[i];
tmp->next = NULL;
if (0 == i){
this->head = tmp;
}else{
cur->next = tmp;
}
cur = tmp;
this->length ++;
}
return;
}
int linklist::get_length(void)
{
if (NULL == this->head)
return 0;
struct node *cur = this->head;
int len = 0;
while (cur){
len++;
cur = cur->next;
}
return len;
}
void linklist::reverse(void)
{ // reverse the linklist
if (!this->head) return;
if (!this->head->next) return; // only one element
struct node *cur = this->head->next;
struct node *pre = this->head;
struct node *tmp = NULL;
pre->next = NULL;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
this->head = pre;
return;
}
void linklist::print_link(void)
{ // print the linklist content
if (!this->head){
cout<<"this link is null."<<endl;
return;
}
struct node* head = this->head;
struct node *cur = head;
