线性表链式存储结构的实现的使用

 1 #ifndef _SIMPLELINKLIST_
 2 #define _SIMPLELINKLIST_
 3 #include<stddef.h>
 4 
 5 template<class ElemType>
 6 struct Node   //创建节点结构体
 7 {
 8     ElemType data;  //节点的数据
 9     Node<ElemType> *next;   //节点的指针
10 
11     Node();  //构造函数，创造一个节点
12     Node(ElemType item,Node<ElemType> *link=NULL);  //有参构造，创造有个有元素并且后继指针指向link的节点
13 };
14 
15 template<class ElemType>
16 class SimpleLinkList {
17 protected:
18     Node<ElemType> *head;   //头结点指针
19     Node<ElemType> *GetElemPtr(int position)const; //返回第position位置的指针
20 public:
21     SimpleLinkList();  //构造函数
22     void Mypush_back(ElemType e);   //向链表的尾部添加元素
23     void Myshow();  //遍历一遍链表
24     virtual ~SimpleLinkList();  //析构函数
25     int Lence()const;   //计算线性表的长度
26     bool Empty()const; //判断链表是否为空
27     void Clear();  //清空链表
28     bool GetElem(int position,ElemType &e)const;  //获取某一个位置的元素
29     bool SetElem(int position, const ElemType &e);  //在某一个位置设置元素
30     bool Insert(int position, const ElemType &e);  //在链表某位置插入元素/节点
31     bool Delete(int position, ElemType &e);  //删除某个位置的元素，并且将删除的值用e返回
32 };
33 
34 
35 
36 #endif // !_SIMPLELINKLIST_

  1 #include "SimpleLinkList.h"
  2 #include<stddef.h>
  3 #include<iostream>
  4 
  5 using namespace std;
  6 
  7 
  8 template<class ElemType>
  9 Node<ElemType>::Node() {
 10     next = NULL;
 11 }
 12 
 13 template<class ElemType>
 14 Node<ElemType>::Node(ElemType item, Node<ElemType> *link) {
 15     data = item;
 16     next = link;
 17 }
 18 
 19 template<class ElemType>
 20 Node<ElemType>* SimpleLinkList<ElemType>::GetElemPtr(int position)const {
 21     Node<ElemType> *tmpPtr = head;
 22     int pos = 0;
 23 
 24     while (tmpPtr!=NULL && pos<position) {
 25         pos++;
 26         tmpPtr = tmpPtr->next;
 27     }
 28     if (tmpPtr!=NULL && pos==position) {
 29         return tmpPtr;
 30     }
 31     else
 32     {
 33         return NULL;
 34     }
 35 }
 36 
 37 template<class ElemType>
 38 SimpleLinkList<ElemType>::SimpleLinkList() {  //创建一个新的链表
 39     head = new Node<ElemType>;
 40 }
 41 
 42 template<class ElemType>
 43 void SimpleLinkList<ElemType>::Mypush_back(ElemType e) {  //向链表中添加元素
 44     Node<ElemType> *newnode = new Node<ElemType>;
 45     newnode->data = e;
 46     newnode->next = NULL;
 47     Node<ElemType> *ptr = new Node<ElemType>;
 48     ptr = head;
 49     while (ptr->next!=NULL)
 50     {
 51         ptr = ptr->next;
 52     }
 53     if (ptr->next==NULL) {
 54         ptr->next = newnode;
 55     }
 56 }
 57 
 58 template<class ElemType>
 59 void SimpleLinkList<ElemType>::Myshow() {
 60     for (Node<ElemType> *p = head->next;p!=NULL;p=p->next) {
 61         cout << p->data << endl;
 62     }
 63 }
 64 
 65 template<class ElemType>
 66 SimpleLinkList<ElemType>::~SimpleLinkList() {  //创建一个新的链表
 67     //Clear();
 68     delete head;
 69 }
 70 
 71 template<class ElemType>
 72 int SimpleLinkList<ElemType>::Lence()const {
 73     int count = 0;
 74     for (Node<ElemType> *ptr = head->next; ptr != NULL;ptr=ptr->next) {
 75         count++;
 76     }
 77     return count;
 78 }
 79 
 80  template<class ElemType>
 81  bool SimpleLinkList<ElemType>::Empty()const {
 82      return head->next = NULL;
 83  }
 84 
 85  template<class ElemType>
 86  void SimpleLinkList<ElemType>::Clear() {
 87      ElemType e;
 88      if (!Empty()) {
 89          Delete(1,e);  //删除第一个位置处的元素即可
 90      }
 91  }
 92 
 93  template<class ElemType>
 94  bool SimpleLinkList<ElemType>::GetElem(int position, ElemType &e)const {
 95      if (position<1 || position>Lence()) {
 96          return false;
 97      }
 98      else {
 99          Node<ElemType> *ptr;
100          ptr = GetElemPtr(position);
101          e = ptr->data;
102          return true;
103      }
104  }
105 
106  template<class ElemType>
107  bool SimpleLinkList<ElemType>::SetElem(int position, const ElemType &e) {
108      if (position<1 || position>Lence()) {
109          return false;
110      }
111      else {
112          Node<ElemType> *ptr;
113          ptr = GetElemPtr(position);
114          ptr->data=e;
115          return true;
116      }
117  }
118 
119  template<class ElemType>
120  bool SimpleLinkList<ElemType>::Insert(int position, const ElemType &e) {
121      if (position<1 || position>Lence()+1) {
122          return false;
123      }
124      else {
125          Node<ElemType> *ptr;
126          ptr = GetElemPtr(position-1);
127          Node<ElemType> *newptr;
128          newptr = new Node<ElemType>(e,ptr->next);  //做一个新的节点，并且后继指针指向第position个节点
129          ptr->next = newptr; //让原来的ptr指向新的节点
130          return true;
131      }
132  }
133 
134  template<class ElemType>
135  bool SimpleLinkList<ElemType>::Delete(int position,ElemType &e) {
136      if (position<1 || position>Lence()) {
137          return false;
138      }
139      else {
140          Node<ElemType> *ptr;
141          ptr = GetElemPtr(position - 1);
142          Node<ElemType> *nextPtr = ptr->next;  //为了获取原链表第position+1个位置的指针
143          ptr->next = nextPtr->next;  //删除节点
144          e = nextPtr->data;
145          delete nextPtr;
146          return true;
147      }
148  }

 1 #include<iostream>
 2 #include "SimpleLinkList.cpp"
 3 
 4 using namespace std;
 5 
 6 void test() {
 7     SimpleLinkList<int> s;
 8     s.Mypush_back(10);
 9     s.Mypush_back(20);
10     s.Mypush_back(20);
11     s.Mypush_back(20);
12     s.Mypush_back(40);
13     s.SetElem(5,50);
14     s.Myshow();
15     cout << s.Lence() << endl;
16     int a;
17     s.Delete(2,a);
18     s.Myshow();
19     s.Insert(2,a);
20     s.Myshow();
21     s.Clear();
22     cout << s.Lence() << endl;
23 }
24 
25 int main() {
26     test();
27     system("pause");
28     return 0;
29 }