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; 
补充：软件开发 , C++ ,

上一个：NYOJ 214 单调递增子序列
下一个：算法排序系列之插入排序