线性表：同类型数据元素 构成有序序列的线性结构
-表中元素个数称为长度
-没有元素称为空表
-表的起始位置称表头，结束位置称为表尾。
类型名称：List
数据对象集：数据表是N个元素构成的有序序列
操作集
List MakeEmpty() //初始化一个空线性表L
ElementType FinfKth(int K，List L);
int find(elementtype X,List L);


文章图片
image.png 利用数组的连续存储空间顺序存放
文章图片
image.png 链性存储
文章图片
image.png 广义表 【线性表】-线性表推广
-线性表：单元素
-广义表：元素也可以是另一个广义表
多重链表
指针域会有多个
但是包含两个指针域不一定是多重链表，比如在双向链表中不是多重链表。
多重链表用途：树、图等、
例子：矩阵
-数组的大小应该事先确定
-稀疏矩阵：0比较多 造成存储空间浪费
采用典型多重链表：十字链表
只存储非0元素项
节点的数据域：行坐标、列坐标、数值
每个节点通过两个指针域，把同行、同列穿起来

template class Node { public: Node(DataType inData):data(inData),next(nullptr) {} public: DataType data; Node *next; }; template class List { public: List(DataType inDummy):dummyNode(inDummy), listSize(0), lastNode(nullptr) {} ~List(); //析构函数，负责回收内存 void MakeEmpty(); //清空链表 bool IsEmpty(); //判断链表是否为空 Node *FindElement(DataType value); //查找一个元素并返回地址 Node *FindNthElement(int n); //查找第n个元素，返回地址或者nullptr void DeleteElement(DataType inData); //删除一个节点 void DeleteNthElement(int n); //删除第n个节点 void InsertElement(DataType inData, int n); //插入一个节点 int Length(); //返回链表长度 private: Node dummyNode; //哑节点 int listSize; //保存链表长度 Node *lastNode; //保存最后一个节点地址 };

//清空链表 template void List::MakeEmpty() { if (listSize <= 0 || dummyNode.next == nullptr) { return; } Node * tmp = nullptr; while (dummyNode.next != nullptr) { tmp = dummyNode.next; dummyNode.next = dummyNode.next->next; delete tmp; } listSize = 0; lastNode = nullptr; return; }//判断链表是否为空 template bool List::IsEmpty() { if (listSize <= 0 || dummyNode.next == nullptr) { return true; } return false; }//查找一个元素并返回地址 template Node * List::FindElement(DataType value) { Node *cycleIter = dummyNode.next; while (cycleIter != nullptr) { if (cycleIter->data =https://www.it610.com/article/= value) { return cycleIter; } cycleIter = cycleIter->next; } return nullptr; }//查找第n个常量template Node * List::FindNthElement(int n) { if (n <= 0) { return nullptr; } Node *cycleIter = dummyNode.next; while (--n > 0 && cycleIter != nullptr) { cycleIter = cycleIter->next; } return cycleIter; }//删除一个节点 template void List::DeleteElement(DataType inData) { Node *frontIter = &dummyNode; Node *cycleIter = frontIter->next; while (cycleIter != nullptr) { if (cycleIter->data =https://www.it610.com/article/= inData) { Node * tmp = cycleIter; frontIter->next = cycleIter->next; delete tmp; --listSize; return; } frontIter = frontIter->next; cycleIter = cycleIter->next; } return; }//插入一个节点 template void List::InsertElement(DataType inData, int n) { Node *insertElement = new Node(inData); if (n < 0 || n >= listSize) { if (lastNode == nullptr) { lastNode = &dummyNode; } lastNode->next = insertElement; lastNode = insertElement; ++listSize; return; } Node *cycleIter = &dummyNode; while (n-- > 0 && cycleIter != nullptr) { cycleIter = cycleIter->next; } if (n <= 0) { insertElement->next = cycleIter->next; cycleIter->next = insertElement; ++listSize; } return; }//返回链表长度template int List::Length() { return listSize; }//析构函数template List::~List() { MakeEmpty(); }int main(){ cout <<"o"<