线性表之链表C++版

    xiaoxiao2025-06-24  15

    拓展阅读及参考

    http://blog.csdn.net/feixiaoxing/article/details/6848077/ http://blog.csdn.net/hackbuteer1/article/details/6591486/ http://blog.csdn.net/xubin341719/article/details/7091583/

    链表 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。每个结点都应包括两个部分:一为用户需要用的实际数据,即数据域,二为下一个结点的地址,即指针域。链表有一个“头指针”变量,以head表示,它的指针域存放一个地址,它也可以有数据域,但是没有意义,不过可用于存放链表长度。该地址指向一个元素。链表中每一个元素称为“结点”,因此,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。

    链表的优点和缺点 对于存放同类数据的集合来说,数组是十分方便的。但是也存在一定的弊端,比如说在使用数组之前需要指定数组的长度。指定数组过长和过短都不行。而且,往数组中插入和删除元素需要进行很大的移动,这会造成时间上的浪费。所以链表的出现正是弥补了这些缺点,链表可以动态的分配内存,并且链表在插入和删除元素时十分灵活。但是链表也有一定的缺点,链表就像一根筋的牛,遍历元素时到了下个元素就不能回头了(除了特殊的链表外),而且要在表中到某点的元素,需要遍历表。

    链表分类 分为单向链表,双向链表,循环链表(单向和双向)等。

    链表的操作 链表的各类操作包括:单向链表的创建、删除、 插入(无序、有序)、输出、 排序(选择、插入、冒泡)、反序等等。 先看头文件

    头文件:LinkList.h class Node //定义节点 { public: int data; //数据域 Node *next; //指针域 }; class LinkList { public: LinkList(); //初始化链表 ~LinkList(); //构销链表 int getLength(); //得到链表长度 void clearList(); //清空链表 bool isEmpty(); //判断链表是否为空 bool insertList(Node *pNode,int n); //在n处插入 bool deleteList(int *e,int n); //删除n处节点 bool getElement(int *e,int n); //得到n处节点数据 bool getPreElement(int *e, int n); //得到元素值为n的前一个数据 bool getNextElement(int *e, int n); //得到元素值为n的后一个数据 int eleLocation(int n); //得到元素值为n的位置 void listTravel(); //遍历链表 private: Node *m_pLinkList; //链表头 int m_iLength; //链表长度 };

    下面主要讲以下几个函数: 先讲构销函数和清空链表函数。构销函数是指将整个链表构销,不能再用了。而清空链表只是将表中所有数据都清空,保留表头。而比较特殊的是清空链表函数:

    清空链表,要从链表头开始往下一个个删除节点。好比抓特务,抓到一个特务,要让他交出下一级的特务,等他交出后,便将这一级的特务干掉,然后再重复直到没有下级特务为止。清空链表也如此,找到一个节点,获取到他的下一个节点,然后在删除。

    void LinkList::clearList() //清空链表 { //先用currentNode指向表头下一个,即有数据的节点 Node *currentNode = m_pLinkList->next; while (currentNode != NULL) { Node *tempNode = currentNode; //保存当前节点以到达下一节点,然后再删除当前节点 currentNode = currentNode->next; delete(tempNode); tempNode = NULL; } m_pLinkList->next = NULL; //将表头的指针域置空 m_iLength = 0; //长度归零 }

    构销函数只需在调用clearList函数后,再将表头删除即可。

    另外两个是插入和删除。 插入,删除的操作基本算是套路了,所以这里不再多提。插入主要算法是将新节点s的next指向当前节点p的next,然后再将当前节点p的next指向新节点s。 删除主要算法是,先保存要删除的节点q的前一节点p,让前一节点p的next指向要删除节点q的next。此时节点q已经被独立出来。

    而主要难题是遍历链表的时候,因为头结点不存任何数据,所以循环起始条件是n=1,与传入位置参数相对应的。而插入和删除循环终止条件是不同的,因为插入是在n-1处结点的next指针处进行插入,所以不必到下一个节点,即n处。而删除是删除当前n处这个节点这个指针,所以需要到n处这个节点进行删除。 下面举个例子:

    以下是所有文件:

    文件LinkList.cpp: #include<iostream> #include "LinkList.h" using namespace std; LinkList::LinkList() //初始化链表,申请表头内存,数据域不存,指针域置空,长度为零 { m_pLinkList = new Node; m_iLength = 0; m_pLinkList->next = NULL; } LinkList::~LinkList() //构销链表 { clearList(); //删除表头后的所有节点 delete m_pLinkList; //删除表头 m_pLinkList = NULL; } void LinkList::clearList() //清空链表 { Node *currentNode = m_pLinkList->next; //先用currentNode指向表头下一个,即有数据的节点 while (currentNode != NULL) { Node *tempNode = currentNode; //保存当前节点以到达下一节点,然后再删除当前节点 currentNode = currentNode->next; delete(tempNode); tempNode = NULL; } m_pLinkList->next = NULL; //将表头的指针域置空 m_iLength = 0; //长度归零 } bool LinkList::isEmpty() //链表判空 { if (m_pLinkList->next == NULL) //表头的指针域为空则表为空 { return true; } return false; } bool LinkList::insertList(Node *pNode, int n) //插入节点 { Node *currentNode = m_pLinkList; Node *newNode = new Node; //一定要从堆中申请内存,否则执行完函数后,从栈申请的内存会回收 if (newNode == NULL||n<=0||n>m_iLength+1) //当申请内存失败或n值不合法(小于0或比链表还长) { cout << "can not insert!" << endl; return false; } for (int i = 1; i < n; i++) { currentNode = currentNode->next; //到达插入的地方 } newNode->data = pNode->data; newNode->next = currentNode->next; //新节点的指针域指向currentnode的下个节点 currentNode->next = newNode; //currentNode的指针域指向newnode,这样就连起来了 m_iLength++; //长度加一 return true; } bool LinkList::deleteList(int *e, int n) //删除节点 { Node *currentNode = m_pLinkList; Node *tempNode = NULL; if (isEmpty()||n<=0||n>m_iLength) //当表为空或n值不合法时(n<=0或n比长度大)则失败 { cout << "can not delete!" << endl; return false; } for (int i = 1; i <= n; i++) //注意这里的循环条件与插入不同 { tempNode = currentNode; //这里要保存currentNode的上一个节点,用以删除 currentNode = currentNode->next; } Node *newNode = new Node; //currentNode的上一个节点指针域指向currentNode的下一节点,即此时currentNode已被独立出来 tempNode->next = currentNode->next; *e = currentNode->data; delete(currentNode); m_iLength--; return true; } bool LinkList::getElement(int *e, int n) //得到元素 { Node *currentNode = m_pLinkList; if (isEmpty() || n <= 0||n>m_iLength) //当表为空和n值不合法则失败 { return false; } for (int i = 0; i < n; i++) { currentNode = currentNode->next; //到达n处节点 } *e = currentNode->data; return true; } int LinkList::getLength() //得到表长度 { return m_iLength; } void LinkList::listTravel() //遍历表 { Node *currentNode = m_pLinkList; while (currentNode->next != NULL) //当下个节点指针域为空则停 { currentNode = currentNode->next; //到下一个节点 cout << currentNode->data << endl; } } bool LinkList::getPreElement(int *e, int n) //得到前驱元素 { Node *currentNode = m_pLinkList; int localtion = eleLocation(n); if (localtion <=1|| localtion > m_iLength || isEmpty()) //当表为空或n不合法时失败 { return false; } for (int i = 0; i < localtion -1; i++) //遍历到n的前一个元素就停止 { currentNode = currentNode->next; } *e = currentNode->data; return true; } bool LinkList::getNextElement(int *e, int n) //得到后继元素 { Node *currentNode = m_pLinkList; int localtion = eleLocation(n); if (localtion < 0 || localtion >= m_iLength || isEmpty()) { return false; } for (int i = 0; i < localtion + 1; i++) { currentNode = currentNode->next; } *e = currentNode->data; return true; } int LinkList::eleLocation(int n) //得到元素n的位置 { int count = 0; Node* currentList = m_pLinkList->next; while (currentList!=NULL) { count++; if (currentList->data == n) { return count; } currentList = currentList->next; } return -1; } 文件main.cpp: #include <iostream> #include "LinkList.h" using namespace std; int main() { LinkList *list = new LinkList; //if (list->isEmpty()) cout << "empty!" << endl; //打印出empty //cout << list->getLength() << endl; //此时长度为0 Node node1; //插入节点 node1.data = 1; list->insertList(&node1,1); Node node2; node2.data = 2; list->insertList(&node2, 2); Node node3; node3.data = 3; list->insertList(&node3, 3); cout <<"the location is: "<<list->eleLocation(3) << endl; //得到元素3的位置为3 int e = 0; list->getPreElement(&e, 2); //得到2的前驱元素1 cout << "previous element is " << e << endl; list->getNextElement(&e, 2); //得到2的后继元素3 cout << "next element is " << e << endl; list->getElement(&e, 2); //得到位置为2的元素2 cout <<"element is "<< e << endl; cout << "the travel is:" << endl; list->listTravel(); //将打印出1,2,3 cout <<"length:"<< list->getLength() << endl; //此时长度为3 list->clearList(); //清空链表 list->listTravel(); //此时长度为0,什么都打印不出 cout << "length:" << list->getLength() << endl; delete list; return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-1300266.html
    最新回复(0)