【慕课-数据结构-C++语言】线性表篇
原文地址：https://www.cloudcrossing.xyz/post/30/
线性表是n个数据元素的有限序列。可应用与通讯录、一元多项式等等。
顺序表
新建List.h和List.cpp
#List.h
#ifndef LIST_H
#define LIST_H
class List
{
public:
List(int size); //创建线性表
~List(); //销毁线性表
void CleanList(); //清空线性表
bool ListEmpty(); //判断线性表是否为空
bool ListFull(); //判断线性表是否为满
int ListLength(); //获取线性表长度（元素个数）
bool GetElem(int i, int *e); //获取指定元素
int LocateElem(int *e); //寻找第一个满足e的数据元素的位序
bool PriorElem(int *currentElem, int *preElem); //获取指定元素的前驱
bool NextElem(int *currentElem, int *nextElem); //获取指定元素的后继
bool ListInsert(int i, int *e); //在第i个位置插入元素
bool ListDelete(int i, int *e); //删除第i个位置的元素
void ListTraverse(); //遍历线性表
public:
int *m_pList;
int m_iSize;
int m_iLength;
};
#endif // LIST_H
#List.cpp
#include "stdafx.h"
#include "List.h"
#include "iostream"
using namespace std;
List::List(int size)
{
m_iSize = size;
m_pList = new int[m_iSize];
m_iLength = 0;
}
List::~List()
{
delete[]m_pList;
m_pList = NULL;
}
void List::CleanList()
{
m_iLength = 0;
}
bool List::ListEmpty()
{
return m_iLength == 0 ? true : false;
}
int List::ListLength()
{
return m_iLength;
}
bool List::GetElem(int i, int *e)
{
if (i < 0 || i >= m_iSize)
{
return false;
}
*e = m_pList[i];
return true;
}
int List::LocateElem(int *e)
{
for (int i = 0; i < m_iLength; i++)
{
if (m_pList[i] == *e)
{
return i;
}
}
return -1;
}
bool List::PriorElem(int *currentElem, int *preElem)
{
int temp = LocateElem(currentElem);
if (temp == -1)
{
return false;
}
else
{
if (temp == 0)
{
return false;
}
else
{
*preElem = m_pList[temp - 1];
return true;
}
}
}
bool List::NextElem(int *currentElem, int *nextElem)
{
int temp = LocateElem(currentElem);
if (temp == -1)
{
return false;
}
else
{
if (temp == m_iLength - 1)
{
return false;
}
else
{
*nextElem = m_pList[temp + 1];
return true;
}
}
}
void List::ListTraverse()
{
for (int i = 0; i < m_iLength; i++)
{
cout << m_pList[i] << endl;
}
}
bool List::ListInsert(int i, int *e)
{
if (ListFull())
{
cout << "栈满，插入失败" << endl;
return false;
}
if (i < 0 || i > m_iLength)
{
return false;
}
for (int k = m_iLength - 1; k >= i; k--)
{
m_pList[k + 1] = m_pList[k];
}
m_pList[i] = *e;
m_iLength++;
return true;
}
bool List::ListDelete(int i, int *e)
{
if (ListEmpty())
{
cout << "栈空，删除失败" << endl;
return false;
}
if (i < 0 || i >= m_iLength)
{
return false;
}
*e = m_pList[i];
for (int k = i + 1; k < m_iLength; k++)
{
m_pList[k - 1] = m_pList[k];
}
m_iLength--;
return true;
}
测试用例demo.cpp
#demo.cpp
#include "stdafx.h"
#include "List.h"
#include "iostream"
using namespace std;
int main(void)
{
int e1 = 3;
int e2 = 5;
int e3 = 7;
int e4 = 2;
int e5 = 9;
int e6 = 1;
int e7 = 8;
int temp = 0;
List * list1 = new List(7);
cout << "before length:" << list1->ListLength() << endl;
list1->ListDelete(0, &temp);
list1->ListInsert(0, &e1);
list1->ListInsert(1, &e2);
list1->ListInsert(2, &e3);
list1->ListInsert(3, &e4);
list1->ListInsert(4, &e5);
list1->ListInsert(5, &e6);
list1->ListInsert(6, &e7);
list1->ListInsert(6, &e7);
cout << "after length:" << list1->ListLength() << endl;
list1->ListTraverse();
list1->GetElem(0, &temp);
cout << "[0] is:" << temp << endl;
temp = 5;
cout << "where 5 in " << list1->LocateElem(&temp) << endl;
list1->NextElem(&e4, &temp);
cout << "4 next is: " << temp << endl;
list1->PriorElem(&e4, &temp);
cout << "4 prior is: " << temp << endl;
list1->ListDelete(0, &temp);
if (!list1->ListEmpty())
{
cout << "not empty" << endl;
}
list1->CleanList();
if (list1->ListEmpty())
{
cout << "empty" << endl;
}
delete list1;
system("pause");
return 0;
}
运行结果：
单链表
首先新建节点类 Node.h 和 Node.cpp。
#Node.h
#ifndef NODE_H
#define NODE_H
class Node
{
public:
int data; //数据域
Node *next; //指针域，指向Node类的指针变量
void printNode();
};
#endif // NODE_H
PS：class 默认访问修饰符是 private 而不是 public，所以在这里为了能访问类的元素，把数据和指针域放到了 public 下。.
#Node.cpp
#include "Node.h"
#include "iostream"
#include "stdafx.h"
using namespace std;
void Node::printNode()
{
cout << data << endl ;
}
接着新建单链表类 List_one.h 和 List.cpp
#List_one.h
#ifndef LIST_ONE_H
#define LIST_ONE_H
#include "Node.h"
class List_one
{
public:
List_one(); //创建链表
~List_one(); //销毁链表
void CleanList(); //清空链表
bool ListEmpty(); //判断链表是否为空
int ListLength(); //获取链表长度（元素个数）
bool GetElem(int i, Node *pNode); //获取指定元素
int LocateElem(Node *pNode); //寻找第一个满足e的数据元素的位序
bool PriorElem(Node *pCurrentNode, Node *pPreNode); //获取指定元素的前驱
bool NextElem(Node *pCurrentNode, Node *pNextNode); //获取指定元素的后继
bool ListInsert(int i, Node *pNode); //在第i个位置插入元素
bool ListDelete(int i, Node *pNode); //删除第i个位置的元素
void ListTraverse(); //遍历线性表
bool ListInsertHead(Node *pNode); //在链表头插入元素
bool ListInsertTail(Node *pNode); //在链表头插入元素
public:
Node *m_pList;
int m_iLength;
};
#endif // LIST_ONE_H
#List_one.cpp
#include "List_one.h"
#include "stdafx.h"
#include "iostream"
using namespace std;
List_one::List_one()
{
m_pList = new Node;
m_pList->data = 0;
m_pList->next = NULL;
m_iLength = 0;
}
List_one::~List_one()
{
CleanList();
delete m_pList;
m_pList = NULL;
}
void List_one::CleanList()
{
Node *currentNode = m_pList->next;
while (currentNode != NULL)
{
Node *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList->next = NULL;
m_iLength = 0;
}
bool List_one::ListEmpty()
{
return m_iLength == 0 ? true : false;
}
int List_one::ListLength()
{
return m_iLength;
}
bool List_one::GetElem(int i, Node *pNode)
{
if (i < 0 || i >= m_iLength)
{
return false;
}
Node *currentNode = m_pList;
for (int k = 0; k <= i; k++)
{
currentNode = currentNode->next;
}
pNode->data = currentNode->data;
return true;
}
int List_one::LocateElem(Node *pNode)
{
Node *currentNode = m_pList;
int count = 0;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
if (currentNode->data == pNode->data)
{
return count;
}
count++;
}
return -1;
}
bool List_one::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
Node *currentNode = m_pList;
Node *tempNode = NULL;
while (currentNode->next != NULL)
{
tempNode = currentNode;
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (tempNode == m_pList) //判断是否为第一个节点
{
return false;
}
pPreNode->data = tempNode->data;
return true;
}
}
return false;
}
bool List_one::NextElem(Node *pCurrentNode, Node *pNextNode)
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (currentNode->next == NULL) //判断是否为最后一个节点
{
return false;
}
pNextNode->data = currentNode->next->data;
return true;
}
}
return false;
}
void List_one::ListTraverse()
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
currentNode->printNode();
}
}
bool List_one::ListInsert(int i, Node *pNode)
{
if (i < 0 || i > m_iLength)
{
return false;
}
Node *currentNode = m_pList;
for (int k = 0; k < i; k++)
{
currentNode = currentNode->next;
}
Node *newNode = new Node;
if (newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
newNode->next = currentNode->next;
currentNode->next = newNode;
return true;
}
bool List_one::ListDelete(int i, Node *pNode)
{
if (ListEmpty())
{
cout << "链空，删除失败" << endl;
return false;
}
if (i < 0 || i >= m_iLength)
{
return false;
}
Node *currentNode = m_pList; //保存头节点
Node *currentNodeBefore = NULL; //头节点前一个节点不存在，为NULL
for (int k = 0; k < i; k++) //查找第i个节点
{
currentNodeBefore = currentNode; //找到第i-1个节点
currentNode = currentNode->next; //循环结束代表currentNode就是第i节点
}
currentNodeBefore->next = currentNode->next; // 第i个节点指针域赋给第i - 1节点指针域
pNode->data = currentNode->data; //删掉节点的数据域赋给pNode输出
delete currentNode; //释放删除节点的内存
currentNode = NULL;
m_iLength--;
return true;
}
bool List_one::ListInsertHead(Node *pNode)
{
Node *newNode = new Node;
if (newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
newNode->next = m_pList->next;
m_pList->next = newNode;
m_iLength++;
return true;
}
bool List_one::ListInsertTail(Node *pNode)
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
}
Node *newNode = new Node;
if (newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
newNode->next = NULL;
currentNode->next = newNode;
m_iLength++;
return true;
}
首先构造函数实质上就是创建链表的头结点，所以其数据域data赋值为0，指针域next赋值为NULL，当然，长度m_iLength也应赋值为0。
接着析构函数先放放，这里先讲清空链表的函数void CleanList()。首先先创建一个节点类指针currentNode并赋值为头结点的next；然后利用while循环释放每一个节点，直到currentNode指向NULL。最后将头结点的next也指向NULL，初始化链表长度。在循环里边，先创建一个节点类指针temp，用来存放currentNode->next，为了在后面释放currentNode时（也就是当前循环的节点）能把currentNode->next赋值给currentNode（保证不断链）。
- 其中，delete只是将currentnode指向的内存给回收了，并不是这个指针就不能用了。回收了的意思就是之后使用这个指针不能再对原来指向的这块内存区域进行操作。指针变量是存放在栈中的，作用周期完了之后才会被回收。
讲完清空链表函数来说说析构函数，因为析构函数实质就是释放链表所有元素，包括头结点，所以我们可以利用利用清空链表函数先把链表清空，接着释放头结点，并将头结点指向NULL，done。
判空和获取长度类似，略。
接着讲讲GetElem(int i, Node *pNode)获取指定元素的函数。首先传入的参数有两个，位序和存放（也就是取来要存放的变量）。在寻找元素之前，需要先判断位序是否合法；然后按照惯例，创建一个节点类指针currentNode存放头结点；然后利用for循环找到链表的第i个元素赋值给currentNode；最后将currentNode->data赋值给参数pNode->data。
int LocateElem(Node *pNode)寻找第一个满足pNode的数据元素的位序的函数。因为找的是位序，所以函数返回的类型为int。首先创建一个节点类指针currentNode存放头结点，并创建一个 int count=0 用来表示当前元素（头结点）的位序；然后利用while进行遍历，在每一次循环里边进行判断 currentNode->data == pNode->data 是否成立，如果成立返回当前count，如果不成立，count++进入下一次循环；最后也没找到的话，返回-1.
bool PriorElem(Node *pCurrentNode, Node *pPreNode)获取指定元素的前驱函数，传入的参数有两个，一个是指定的节点，一个是存放节点。和前边两个函数类似，首先创建一个节点类指针赋值为头结点，还需创建一个临时节点类指针tempNode指向NULL，然后利用while循环遍历链表。在每一次循环中，先将当前节点currentNode赋值给临时节点，将currentNode->next赋值给当前节点currentNode，然后判断currentNode（其实是当前节点的next）的数据域是否和指定节点的相等。如果相等时继续判断临时节点（即当前节点）是否为头结点，如果不是头结点，则当前节点为指定节点的前驱。
bool NextElem(Node *pCurrentNode, Node *pNextNode)获取指定元素的后继和获取前驱类似，这里不再需要创建临时节点。在遍历的每一次循环中，先进行节点的移动（从前一节点移动到当前节点），然后直接将判断当前节点的数据域是否和指定节点的相等。如果相等，继续判断当前节点next的指针域是否指向NULL（即判断指定**节点是否为最后一个节点）。如果不是，则将当前节点的 next 的数据域（即当前节点的后继数据域）取出。
void ListTraverse()遍历线性表，略。
接着来讲bool ListInsertHead(Node *pNode)在链表头插入元素。首先创建一个节点类指针newNode，将要插入节点的数据域赋值给newNode->data，然后将newNode->next = m_pList->next，最后将头结点的指针域指向newNode，不要忘记m_iLength++。
bool ListInsertTail(Node *pNode)在链表头插入元素。首先创建一个节点类指针currentNode指向头节点，接着遍历到链表尾指针，然后创建一个节点类指针newNode，将要插入节点的数据域赋值给newNode->data，然后将newNode->next 指向NULL，最后将链表尾的指针域指向newNode，m_iLength++。
bool ListInsert(int i, Node *pNode)在第 i 个位置插入元素。和上边两个函数类x似，不同的是需要先判断插入的位置合不合法。之后创建一个节点类指针currentNode指向头节点，然后遍历到插入位置的前一个节点。接着创建一个节点类newNode，将要插入节点的数据域赋值给newNode->data，然后将newNode->next 指向currentNode->next（要插入的位置的节点），最后将currentNode->next（插入位置的前一个节点的指针域）指向newNode，m_iLength++。
最后讲bool ListDelete(int i, Node *pNode)删除第 i 个位置的元素。首先需要判空以及判断删除位置是否合法，接着创建两个节点类，currentNode指向头节点，currentNodeBefore指向NULL。然后遍历到第 i 个节点（要删除的节点）时，currentNodeBefore为第 i-1 个节点，currentNode为第 i 个节点。接着将第 i 个节点指针域赋给第 i-1 节点指针域（即跳过了第 i 个节点），把第 i 节点的数据域赋给pNode输出，释放删除节点的内存，m_iLength--。
【注意】在插入操作中，不能直接对pNode进行链接操作，而不用新建newNode节点。直接将传入的结点作为链表中新添加的结点内存，是不安全的。因为传入的结点内存是有可能在链表外被释放掉的，如果被释放掉，则链表就会断开失效；而申请一个新的结点内存作为链表的结点内存，则该内存只有在链表中才可以被释放掉，这样保证了链表内存是安全释放的。
运行一个例子看看
#demo_one.cpp
#include "stdafx.h"
#include "iostream"
#include "List_one.h"
#include "Node.h"
using namespace std;
int main(void)
{
Node node1; node1.data = 3;
Node node2; node2.data = 4;
Node node3; node3.data = 5;
Node node4; node4.data = 6;
//Node node5; node5.data = 7;
Node temp; temp.data = 0;
List_one *pList = new List_one;
/*pList->ListInsertHead(&node1);
pList->ListInsertHead(&node2);
pList->ListInsertHead(&node3);
pList->ListInsertHead(&node4);*/
pList->ListInsertTail(&node1);
pList->ListInsertTail(&node2);
pList->ListInsertTail(&node3);
pList->ListInsertTail(&node4);
//pList->ListInsert(1, &node5);
pList->ListDelete(2, &temp);
//pList->NextElem(&node1, &temp);
cout << "temp:" << temp.data << endl;
pList->ListTraverse();
delete pList;
pList = NULL;
system("pause");
return 0;
}
运行结果：
顺序表的应用以及单链表的应用的代码我上传到了github。
