C++实现单链表的12种基本操作
2018-06-17 21:26:01来源：未知 阅读 ()
C++单链表的操作
2017-12-25
1 // 单链表.cpp: 定义控制台应用程序的入口点。 2 //Author:kgvito 3 //Date: 2017.12.25 4 5 6 #include "stdafx.h" 7 #include<iostream> 8 using namespace std; 9 10 typedef int DataType; 11 #define Node ElemType 12 #define ERROR NULL 13 14 //构建一个节点类 15 class Node 16 { 17 public: 18 int data; //数据域 19 Node * next; //指针域 20 }; 21 22 //构建一个单链表类 23 class LinkList 24 { 25 public: 26 LinkList(); //构建一个单链表; 27 ~LinkList(); //销毁一个单链表; 28 void CreateLinkList(int n); //创建一个单链表 29 void TravalLinkList(); //遍历线性表 30 int GetLength(); //获取线性表长度 31 bool IsEmpty(); //判断单链表是否为空 32 ElemType * Find(DataType data); //查找节点 33 void InsertElemAtEnd(DataType data); //在尾部插入指定的元素 34 void InsertElemAtIndex(DataType data,int n); //在指定位置插入指定元素 35 void InsertElemAtHead(DataType data); //在头部插入指定元素 36 void DeleteElemAtEnd(); //在尾部删除元素 37 void DeleteAll(); //删除所有数据 38 void DeleteElemAtPoint(DataType data); //删除指定的数据 39 void DeleteElemAtHead(); //在头部删除节点 40 private: 41 ElemType * head; //头结点 42 }; 43 44 //初始化单链表 45 LinkList::LinkList() 46 { 47 head = new ElemType; 48 head->data = 0; //将头结点的数据域定义为0 49 head->next = NULL; //头结点的下一个定义为NULL 50 } 51 52 //销毁单链表 53 LinkList::~LinkList() 54 { 55 delete head; //删除头结点 56 } 57 58 //创建一个单链表 59 void LinkList::CreateLinkList(int n) 60 { 61 ElemType *pnew, *ptemp; 62 ptemp = head; 63 if (n < 0) { //当输入的值有误时，处理异常 64 cout << "输入的节点个数有误" << endl; 65 exit(EXIT_FAILURE); 66 } 67 for (int i = 0; i < n;i++) { //将值一个一个插入单链表中 68 pnew = new ElemType; 69 cout << "请输入第" << i + 1 << "个值: " ; 70 cin >> pnew->data; 71 pnew->next = NULL; //新节点的下一个地址为NULL 72 ptemp->next = pnew; //当前结点的下一个地址设为新节点 73 ptemp = pnew; //将当前结点设为新节点 74 } 75 } 76 77 //遍历单链表 78 void LinkList::TravalLinkList() 79 { 80 if (head == NULL || head->next ==NULL) { 81 cout << "链表为空表" << endl; 82 } 83 ElemType *p = head; //另指针指向头结点 84 while (p->next != NULL) //当指针的下一个地址不为空时，循环输出p的数据域 85 { 86 p = p->next; //p指向p的下一个地址 87 cout << p->data << " "; 88 } 89 } 90 91 //获取单链表的长度 92 int LinkList::GetLength() 93 { 94 int count = 0; //定义count计数 95 ElemType *p = head->next; //定义p指向头结点 96 while (p != NULL) //当指针的下一个地址不为空时，count+1 97 { 98 count++; 99 p = p->next; //p指向p的下一个地址 100 } 101 return count; //返回count的数据 102 } 103 104 //判断单链表是否为空 105 bool LinkList::IsEmpty() 106 { 107 if (head->next == NULL) { 108 return true; 109 } 110 return false; 111 } 112 113 //查找节点 114 ElemType * LinkList::Find(DataType data) 115 { 116 ElemType * p = head; 117 if (p == NULL) { //当为空表时，报异常 118 cout << "此链表为空链表" << endl; 119 return ERROR; 120 } 121 else 122 { 123 while (p->next != NULL) //循环每一个节点 124 { 125 if (p->data == data) { 126 return p; //返回指针域 127 } 128 p = p->next; 129 } 130 return NULL; //未查询到结果 131 } 132 } 133 134 //在尾部插入指定的元素 135 void LinkList::InsertElemAtEnd(DataType data) 136 { 137 ElemType * newNode = new ElemType; //定义一个Node结点指针newNode 138 newNode->next = NULL; //定义newNode的数据域和指针域 139 newNode->data = data; 140 ElemType * p = head; //定义指针p指向头结点 141 if (head == NULL) { //当头结点为空时，设置newNode为头结点 142 head = newNode; 143 } 144 else //循环知道最后一个节点，将newNode放置在最后 145 { 146 while (p->next != NULL) 147 { 148 p = p->next; 149 } 150 p->next = newNode; 151 } 152 } 153 154 //在指定位置插入指定元素 155 void LinkList::InsertElemAtIndex(DataType data,int n) 156 { 157 if (n<1 || n>GetLength()) //输入有误报异常 158 cout << "输入的值错误" << endl; 159 else 160 { 161 ElemType * ptemp = new ElemType; //创建一个新的节点 162 ptemp->data = data; //定义数据域 163 ElemType * p = head; //创建一个指针指向头结点 164 int i = 1; 165 while (n > i) //遍历到指定的位置 166 { 167 p = p->next; 168 i++; 169 } 170 ptemp->next = p->next; //将新节点插入到指定位置 171 p->next = ptemp; 172 } 173 } 174 175 //在头部插入指定元素 176 void LinkList::InsertElemAtHead(DataType data) 177 { 178 ElemType * newNode = new ElemType; //定义一个Node结点指针newNode 179 newNode->data = data; 180 ElemType * p = head; //定义指针p指向头结点 181 if (head == NULL) { //当头结点为空时，设置newNode为头结点 182 head = newNode; 183 } 184 newNode->next = p->next; //将新节点插入到指定位置 185 p->next = newNode; 186 } 187 188 //在尾部删除元素 189 void LinkList::DeleteElemAtEnd() 190 { 191 ElemType * p = head; //创建一个指针指向头结点 192 ElemType * ptemp = NULL; //创建一个占位节点 193 if (p->next == NULL) { //判断链表是否为空 194 cout << "单链表空" << endl; 195 } 196 else 197 { 198 while (p->next != NULL) //循环到尾部的前一个 199 { 200 ptemp = p; //将ptemp指向尾部的前一个节点 201 p = p->next; //p指向最后一个节点 202 } 203 delete p; //删除尾部节点 204 p = NULL; 205 ptemp->next = NULL; 206 } 207 } 208 209 //删除所有数据 210 void LinkList::DeleteAll() 211 { 212 ElemType * p = head->next; 213 ElemType * ptemp = new ElemType; 214 while (p != NULL) //在头结点的下一个节点逐个删除节点 215 { 216 ptemp = p; 217 p = p->next; 218 head->next = p; 219 ptemp->next = NULL; 220 delete ptemp; 221 } 222 head->next = NULL; //头结点的下一个节点指向NULL 223 } 224 225 //删除指定的数据 226 void LinkList::DeleteElemAtPoint(DataType data) 227 { 228 ElemType * ptemp = Find(data); //查找到指定数据的节点位置 229 if (ptemp == head->next) { //判断是不是头结点的下一个节点，如果是就从头部删了它 230 DeleteElemAtHead(); 231 } 232 else 233 { 234 ElemType * p = head; //p指向头结点 235 while (p->next != ptemp) //p循环到指定位置的前一个节点 236 { 237 p = p->next; 238 } 239 p->next = ptemp->next; //删除指定位置的节点 240 delete ptemp; 241 ptemp = NULL; 242 } 243 244 } 245 246 //在头部删除节点 247 void LinkList::DeleteElemAtHead() 248 { 249 ElemType * p = head; 250 if (p == NULL || p->next == NULL) { //判断是否为空表，报异常 251 cout << "该链表为空表" << endl; 252 } 253 else 254 { 255 ElemType * ptemp = NULL; //创建一个占位节点 256 p = p->next; 257 ptemp = p->next; //将头结点的下下个节点指向占位节点 258 delete p; //删除头结点的下一个节点 259 p = NULL; 260 head->next = ptemp; //头结点的指针更换 261 } 262 } 263 264 //测试函数 265 int main() 266 { 267 LinkList l; 268 int i; 269 cout << "1.创建单链表 2.遍历单链表 3.获取单链表的长度 4.判断单链表是否为空 5.获取节点\n"; 270 cout << "6.在尾部插入指定元素 7.在指定位置插入指定元素 8.在头部插入指定元素\n"; 271 cout<<"9.在尾部删除元素 10.删除所有元素 11.删除指定元素 12.在头部删除元素 0.退出" << endl; 272 do 273 { 274 cout << "请输入要执行的操作: "; 275 cin >> i; 276 switch (i) 277 { 278 case 1: 279 int n; 280 cout << "请输入单链表的长度: "; 281 cin >> n; 282 l.CreateLinkList(n); 283 break; 284 case 2: 285 l.TravalLinkList(); 286 break; 287 case 3: 288 cout << "该单链表的长度为" << l.GetLength() << endl; 289 break; 290 case 4: 291 if (l.IsEmpty() == 1) 292 cout << "该单链表是空表" << endl; 293 else 294 { 295 cout << "该单链表不是空表" << endl; 296 } 297 break; 298 case 5: 299 DataType data; 300 cout << "请输入要获取节点的值: "; 301 cin >> data; 302 cout << "该节点的值为" << l.Find(data)->data << endl; 303 break; 304 case 6: 305 DataType endData; 306 cout << "请输入要在尾部插入的值: "; 307 cin >> endData; 308 l.InsertElemAtEnd(endData); 309 break; 310 case 7: 311 DataType pointData; 312 int index; 313 cout << "请输入要插入的数据: "; 314 cin >> pointData; 315 cout << "请输入要插入数据的位置: "; 316 cin >> index; 317 l.InsertElemAtIndex(pointData, index); 318 break; 319 case 8: 320 DataType headData; 321 cout << "请输入要在头部插入的值: "; 322 cin >> headData; 323 l.InsertElemAtHead(headData); 324 break; 325 case 9: 326 l.DeleteElemAtEnd(); 327 break; 328 case 10: 329 l.DeleteAll(); 330 break; 331 case 11: 332 DataType pointDeleteData; 333 cout << "请输入要删除的数据: "; 334 cin >> pointDeleteData; 335 l.DeleteElemAtPoint(pointDeleteData); 336 break; 337 case 12: 338 l.DeleteElemAtHead(); 339 break; 340 default: 341 break; 342 } 343 }while (i != 0); 344 345 system("pause"); 346 return 0; 347 }
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：BZOJ1468: Tree
下一篇：森炊的预算方案
相关文章
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换（用户自定义类类型） 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签