数据结构-单链表-类定义2-C++

上一次的C++链表实现两个单链表的连接不太理想，此次听了一些视频课，自己补了个尾插法，很好的实现了两个链表的连接，当然了，我也是刚接触，可能是C++的一些语法还不太清楚，不过硬是花了一些时间尽量在数据结构中将c++的语言特点表现出来。一开始也是不愿意读c++的数据结构，只是一种挑战心里，不想读着读着感觉自己太low了，c++的内容更加丰富，所以还得多多练习......

头文件

 #ifndef LIST_H

 #define LIST_H

 #include <iostream>

 template <class Type> class List;          //前置声明

 template <class Type> class ListIterator;  //前置声明

 //创建结点类

 template <class Type>  //类模板

 class ListNode

 {

     friend class List<Type>;           //友元函数--29行

     friend class ListIterator<Type>;   //友元函数--46行

 private:

     Type data;

     ListNode *link;

     ListNode(Type);

 };

 template <class Type>

 ListNode<Type>::ListNode(Type element)  //创建头结点

 {

     data = element;

     link = ;

 }

 //创建链表类

 template <class Type>

 class List

 {

     friend class ListIterator<Type>;  //友元函数--46行

 public:

     List() { first=tail= ; };

     void Insert(Type);      //头插法

     void Inserttail(Type);  //尾插法

     void Delete(Type);      //按值删除元素

     void Invert();          //反转链表

     void Concatenate(List<Type>);  //连接链表

     void Show();  //显示链表做测试用，创建迭代器后可以不用它显示

 private:

     ListNode<Type> *first, *tail;  // 创建头指针

 };

 /**************************************************************/

 //创建迭代器类

 template <class Type>

 class ListIterator

 {

 public:

     ListIterator(const List<Type>& l):list(l),current(l.first){}

     bool NotNull();

     bool NextNotNull();

     Type* First();

     Type* Next();

 private:

     const List<Type> &list;

     ListNode<Type>* current;

 };

 template <class Type>

 bool ListIterator<Type>::NotNull()

 {

     if (current) return true;

     else return false;

 }

 template <class Type>

 bool ListIterator<Type>::NextNotNull()

 {

     if (current && current->link) return true;

     else return false;

 }

 template <class Type>

 Type* ListIterator<Type>::First()

 {

     if (list.first) return &list.first->data;

     else return ;

 }

 template <class Type>

 Type* ListIterator<Type>::Next()

 {

     if (current)

     {

         current = current->link;

         return &current->data;

     }

     else return ;

 }

 /**************************************************************/

 // 前插法

 template <class Type>

 void List<Type>::Insert(Type k)

 {

     ListNode<Type> *newnode = new ListNode<Type>(k);  // 21行，新建结点并为data域赋值k

     //下面两行的意义就是头插法，将新建立的结点从头插入

     newnode->link = first;

     first = newnode;

 }

 template <class Type>

 void List<Type>::Inserttail(Type k)

 {

     if (tail != ) {

         tail->link = new ListNode<Type>(k);

         tail = tail->link;

     }

     else first = tail = new ListNode<Type>(k);

 }

 template <class Type>

 void List<Type>::Delete(Type k)

 {

     ListNode<Type> *previous = ;

     ListNode<Type> *current;

     for (current = first; current && current->data != k;

         previous = current, current = current->link);

     if (current)

     {

         if (previous) previous->link = current->link;

         else first = first->link;

         delete current;

     }

 }

 template <class Type>

 void List<Type>::Invert()

 {

     ListNode<Type> *p = first, *q = ;

     while (p)

     {

         ListNode<Type> *r = q; q = p;

         p = p->link;

         q->link = r;

     }

     first = q;

 }

 template <class Type>

 void List<Type>::Concatenate(List<Type> b)

 {

     if (!first) { first = b.first; return; }

     if (b.first)

     {

         ListNode<Type> *p;

         for (p = first; p->link; p = p->link);

         p->link = b.first;

     }

 }

 template <class Type>

 void List<Type>::Show()

 {

     for (ListNode<Type> *current = first; current; current = current->link)

     {

         std::cout << current->data;

         if (current->link) std::cout << "->";

     }

     std::cout << std::endl;

 }

 #endif

源文件

 #include<iostream>

 #include"List.h"

 using namespace std;

 int main()

 {

     cout << "测试" << endl;

     cout << "自建的迭代器" << endl;

     List<int> intList;

     intList.Insert();

     intList.Insert();

     intList.Insert();

     intList.Insert();

     /**************************************************************/

     //可以先注释这段迭代器输出

     ListIterator<int> li(intList);

     if (li.NotNull())

     {

         cout << *li.First();

         while (li.NextNotNull())

             cout << "->" << *li.Next();

         cout << endl;

     }

     /**************************************************************/

     intList.Show();

     intList.Invert();

     intList.Show();

     intList.Delete();

     intList.Show();

     intList.Delete();

     intList.Show();

     List<char> charList;

     charList.Insert('a');

     charList.Insert('b');

     charList.Insert('c');

     charList.Insert('d');

     charList.Show();

     charList.Invert();

     charList.Show();

     List<char> char2List;

     char2List.Insert('e');

     char2List.Insert('f');

     char2List.Show();

     char2List.Invert();

     char2List.Show();

     charList.Concatenate(char2List);

     charList.Show();

     List<int> intList2;

     intList2.Inserttail();

     intList2.Inserttail();

     intList2.Inserttail();

     intList2.Inserttail();

     intList2.Show();

     intList.Concatenate(intList2);

     ListIterator<int> li2(intList);

     if (li2.NotNull())

     {

         cout << *li2.First();

         while (li2.NextNotNull())

             cout << "->" << *li2.Next();

         cout << endl;

     }

     return ;

 }

巴特西

数据结构-单链表-类定义2-C++

最新文章

热门文章