[原]第2章 线性表(4)
C++实现一个单向链表://Node.h#pragma once
#include "stdafx.h"
namespace Alexsoft
{
template<class T>
class Node
{
public:
T data;
Node<T> *next;
Node(T val,Node<T> *p){
data=val;
next=p;
}
Node(T val){
data=val;
next=0;
}
Node(){
data=0;
next=0;
}
};
}//LinkNode.h
#pragma once
#include "stdafx.h"
#include "Node.h"
#include <iostream>
using std::cout;
namespace Alexsoft
{
template<class T>
class LinkList{
public:
Node<T> *head;
LinkList(){
head=0;
}
LinkList(Node<T> &node){
head=&node;
}
int GetLength(){
Node<T> *p=head;
int len=0;
while(p!=0){
++len;
p=p->next;
}
return len;
}
void Clear(){
head=0;
}
bool IsEmpty(){
if(head==0)
return true;
else
return false;
}
void Append(T item){
Node<T> *q=new Node<T>(item);
if(head==0)
head=q;
else{
Node<T> *p=head;
while(p->next!=0){
p=p->next;
}
p->next=q;
}
}
void Insert(T item, int i){
if(IsEmpty()||i<0)
cout<<"List is empty or Position is error!";
Node<T> *q=new Node<T>(item);
if(i==0){
q->next=head;
head=q;
return;
}
else{
Node<T> *p=head;
Node<T> *post=p;
int index=0;
while(index<i&&p!=0){
post=p;
p=p->next;
++index;
}
if(index==i){
q->next=post->next;
post->next=q;
}
}
}
T Delete(int i){
if(IsEmpty()||i<0){
cout<<"Link is empty or position is error!";
return T();
}
if(i==0){
Node<T> *q=head;
head=head->next;
return q->data;
}
else{
int index=0;
Node<T> *p=head;
Node<T> *post;
while(p->next!=0&&index<i){
++index;
post=p;
p=p->next;
}
if(index==i){
post->next=p->next;
return p->data;
}
else{
cout<<"The 1th node is not exist!";
return T();
}
}
}
T GetItem(int i){
if(IsEmpty()){
cout<<"List is empty";
return T();
}
Node<T> *p=head;
int j=0;
while(p->next!=0&&j<i){
++j;
p=p->next;
}
if(j==i){
return p->data;
}
else{
cout<<"The target node is not exist!";
return T();
}
}
int Locate(T value){
if(IsEmpty()){
cout<<"List is Empty!";
return -1;
}
Node<T> *p=head;
int i=0;
while(p->data!=value&&p->next!=0){
p=p->next;
++i;
}
if(p->data==value){
return i;
}
else{
cout<<"Not found";
return -1;
}
}
};
}
Verify Codes:
// CCA.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "Algri.h"
#include <iostream>
#include "LinkNode.h"
using namespace std;
using namespace Jeffery;
using namespace Alexsoft;
int _tmain(int argc, _TCHAR* argv[])
{
LinkList<int> li= LinkList<int>();
for(int i=0;i<8;i++)
{
li.Append(i);
}
Node<int> *node=li.head;
do
{
cout<<node->data<<" ";
node=node->next;
}while(node!=0);
cout<<endl;
li.Insert(100,5);
node=li.head;
do
{
cout<<node->data<<" ";
node=node->next;
}while(node!=0);
cout<<endl;
li.Insert(1000,9);
node=li.head;
do
{
cout<<node->data<<" ";
node=node->next;
}while(node!=0);
cout<<endl;
li.Delete(2);
node=li.head;
do
{
cout<<node->data<<" ";
node=node->next;
}while(node!=0);
cout<<endl;
cout<<li.GetItem(7)<<endl;
cout<<li.Locate(4)<<endl;
return 0;
}
作者：xufei96 发表于2012-1-17 15:45:01 原文链接
页:
[1]