链表
链表是将数据元素放在不连续的地址空间中的一种线性表。
单链表的每一个节点包含两部分：
- 数据域
- 指针域(下一个节点的地址)
链表结构：
- 一个链表通常有一个“表头”，用来存放第一结点的地址
- 每一个结点的后面一个结点称为该结点的后继，链表也会有一个“表尾”，表尾没有后继，所以尾结点的指针域为空指针(NULL)
特征：
- 单链表结点的物理位置不一定连续，单链表逻辑上通过指针实现连续
- 单链表有一个头结点和一个尾结点，并且只有尾结点没有后继结点，其他结点有且仅有一个后继结点
- 只有知道了链表的头结点，就可以遍历整个链表
链表结构
template<typename DataType>class LinkList { public: LinkList() { head = new ListNode<DataType>(); } LinkList(ListNode<DataType> *firestNode) { head = firestNode; } ~LinkList() { delete head; } //在第i个结点后插入结点 bool insertNode(int index, DataType newData); //在表尾添加新的结点 bool insertNode(DataType newData); //删除结点 bool removeNode(ListNode<DataType>*q); //查找指定值的结点并返回地址 ListNode<DataType>* findNode(DataType value); //清空链表 void cleanLink(); //获取第i个结点中的数据 DataType getNodeData(const int index); //获取链表长度 int getLength(); //查找链表第i个元素 ListNode<DataType>* getNode(int i); private: ListNode<DataType> *head;//头结点 };
链表结点
template<typename DataType>class ListNode { public: ListNode() { next = NULL; } ListNode(const DataType item, ListNode<DataType> *nodeNext = NULL) { data = item; next = nodeNext; } ~ListNode() { next = NULL; } //获取结点内的数据 DataType getData() { return data; } //获取指针域 ListNode* getNext() { return next; } private: friend class LinkList<DataType>; //将LinkList设为友元类，方便对node的成员数据和方法访问 ListNode<DataType> *next; //指向下一个结点的指针 DATATYPE data; //节点中的数据 };
链表插入
单链表的插入操作分两步实现：
- 创建一个待插入的结点p，为其分配内存空间，并将其指针域设为NULL
- 找到单链表的第i个结点位置，获取它的地址q，将结点p插入在结点q与其后继结点之间
在第i个结点后插入结点
template<typename DataType> bool LinkList<DataType>::insertNode(int i,DataType newData) { ListNode<DataType> *p = head; //设置游标指针，初始化为头结点地址 int j; for(j = 1;j<=i-1;j++) //查找第i个结点，指针需要移动i-1次 { p = p->next; if(p == NULL) //如果指针为空，则不存在该结点，或已到表尾 { break; } } if(p==NULL && j<(i-1)) //指针为空且没有到第i个位置，说明不存在第i个结点 { std::cout<<"插入位置无效！"<<endl; return false; } ListNode<DataType> *node = new ListNode<DataType>(newData); //建立新结点node node->next = p->next; //将node的next指针赋值为p的后继结点地址 p->next = node; //p的后继指针指向node return true; }
在表尾添加新的结点
template<typename DataType> bool LinkList<DataType>::insertNode(DataType newData) { ListNode<DataType> *p = head; //设置游标指针 ListNode<DataType> *node = new ListNode<DataType>(newData); //创建新结点 if(node == NULL) //如果新结点内存分配失败，返回false { return false; } while(p->next != NULL) //遍历单链表，找到尾结点 { p = p->next; } p->next = node; //将尾结点next指针指向新结点 return true; }
删除结点
template<typename DataType> bool LinkList<DataType>::removeNode(ListNode<DataType> *q) { if(q == NULL) //判断待删除结点是否存在 { std::cout<<"待删除结点不存在！"<<std::endl; return false; } ListNode<DataType> *tempPointer = head; //设置游标指针，初始化为头结点 while(tempPointer->next != q) //遍历单链表，找到q所指向的结点的前驱结点 { tempPointer = tempPointer->next; } tempPointer->next = q->next; //将q结点的后继结点地址赋值给其前驱结点的next指针 delete q; //回收结点q的空间 return true; }
查找指定值的结点并返回地址
template<typename DataType> ListNode<DataType>* LinkList<DataType>::findNode(DataType value) { ListNode<DataType> *currentPointer = head; //设置游标指针 //判定游标指针所指结点的值是否与value相等 while(currentPointer != NULL && currentPointer->data != value) { currentPointer = currentPointer->next; } if(currentPointer == NULL) //判定所找结点是否存在 { std::cout<<"没有找到该结点！程序退出！"<<endl; exit(1); }else { return currentPointer; //返回所找到的结点的指针 } }
清空链表
template<typename DataType> void LinkList<DataType>::cleanLink() { ListNode<DataType> *current = head; //设置游标指针 while(head->next != NULL) //判断head的后继结点是否为NULL { current = head->next; //将current指向head的后继结点 head->next = current->next; //将current的后继地址赋值给head的next域 delete current; //回收current结点所占的空间 } }
获取结点数据
template<typename DataType> DataType LinkList<DataType>::getNodeData(int index) { int linkLength = getLength(); if(index < 1 || index > linkLength) { std::cout<<"结点不存在！"<<std::endl; return false; } else { ListNode<DataType> *pmove = head->next; for(int i = 1;i<index&&pmove;i++) { pmove = pmove->next; } return pmove->getData(); } }
获取链表长度
template<typename DataType> int LinkList<DataType>::getLength() { int count = 0; ListNode<DataType> *p = head->next; while(p != NULL) { p = p->next; count++; } return count; }
查找链表第i个元素
template<typename DataType> ListNode<DataType>* LinkList<DataType>::getNode(int i) { ListNode<DataType> *p = head->next; int j; if(i<1 || i>getLength()-1) //带头结点所以实际节点数需减1 { return false; } for(j=1;j<i;j++) { p = p->next; if(p == NULL) { break; } } if(p == NULL && j<i-1) { return false; } return p; }