C语言线性链表（c语言线性链表建立）

本文实例讲述了C++语言实现线性表之链表实现方法。分享给大家供大家参考。具体分析如下：

插入、删除结点的代码有点多，但这样提高了代码的可读性，且不增加时间复杂度，不会影响程序性能

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 #include <iostream> using namespace std; template<typename T> class CList; template<class T> class Node { friend CList<T>; private: T m_data; Node *m_pNext; }; template<class T> class CList { public: CList(); ~CList(); bool IsEmpty(); void Append(const T &data); void Delete(const int &pos); void Print(); int GetLength(); T Find(const int &pos); void Insert(const int &pos,const T &data); private: Node<T> *m_pHead; Node<T> *m_pEnd; int m_len; void Create(); void Destroy(); }; //为头结点分配空间 template<class T> void CList<T>::Create() { m_pHead = new Node<T>; m_pEnd = new Node<T>; m_pHead->m_pNext = NULL; m_pEnd->m_pNext = m_pHead->m_pNext; m_len = 0; } template<class T> CList<T>::CList() { Create(); } //删除所有结点 template<class T> void CList<T>::Destroy() { Node<T> *pF = m_pHead->m_pNext; Node<T> *pT; while(pF) { pT = pF; pF = pF->m_pNext; delete pT; } } template<class T> CList<T>::~CList() { Destroy(); } //判断是否为空 template<class T> bool CList<T>::IsEmpty() { if(!m_pHead->m_pNext) { return true; } else { return false; } } //从表的最后加入一个元素 template<class T> void CList<T>::Append(const T &data) { Node<T> *pT = new Node<T>; pT->m_data = data; pT->m_pNext = NULL; if(!m_pHead->m_pNext) { m_pHead->m_pNext = pT; } else { (m_pEnd->m_pNext)->m_pNext = pT; } m_pEnd->m_pNext = pT; ++m_len; } //删除一个元素 template<class T> void CList<T>::Delete(const int &pos) { if(pos < 0 || pos < m_len) { cout<<"位置不合法"<<endl; return; } Node<T> *pPre = NULL;//存放前一个结点 Node<T> *pBehind = NULL;//存放后一个结点 Node<T> *pT = m_pHead->m_pNext;//目标结点 int ix = -1; while(pT) { ++ix; if(ix == pos - 1 - 1) { pPre = pT; } else if(ix == pos - 1) { pBehind = pT->m_pNext; break; } pT = pT->m_pNext; } if(!pPre)//如果指针为空则说明pos是指第一个元素 { delete pT; m_pHead->m_pNext = pBehind; --m_len; return; } if(!pBehind)//如果指针为空则说明pos是指最后一个元素 { m_pEnd = pPre; delete pT; } pPre->m_pNext = pBehind; --m_len; } //输出所有数据 template<class T> void CList<T>::Print() { Node<T> *pT = m_pHead->m_pNext; while(pT) { cout<<pT->m_data<<","; pT = pT->m_pNext; } cout<<endl; } template<class T> int CList<T>::GetLength() { return m_len; } //查找数据 template<class T> T CList<T>::Find(const int &pos) { if(pos <= 0) { cout<<"输入不合法"<<endl; return NULL; } if(pos > m_len) { cout<<"超出表长"<<endl; return NULL; } int i = 0; Node<T> *pT = m_pHead->m_pNext; while(pT) { ++i; if(i == pos) { return pT->m_data; } pT = pT->m_pNext; } return NULL; } template<class T> void CList<T>::Insert(const int &pos,const T &data) { if(pos <= 0 || pos >m_len) { cout<<"输入不合法"<<endl; return; } int i = 0; Node<T> *pT = m_pHead->m_pNext; Node<T> *pPre = NULL; Node<T> *pBehind = NULL; while(pT) { ++i; if(i == pos - 1) { pPre = pT; } if(i == pos) { pBehind = pT->m_pNext; break; } pT = pT->m_pNext; } Node<T> *pNew = new Node<T>; pNew->m_data = data; if(!pPre)//如果指针为空则说明pos是指第一个元素 { pNew->m_pNext = m_pHead->m_pNext; m_pHead->m_pNext = pNew; ++m_len; return; } if(!pBehind)//如果指针为空则说明pos是指最后一个元素 { m_pEnd->m_pNext = pNew; } pPre->m_pNext = pNew; pNew->m_pNext = pT; ++m_len; }