数据结构

您所在的位置：网站首页 › 线性表的特点是每个元素都有一个前驱和一个后区 › 数据结构

数据结构

2024-07-04 05:36| 来源: 网络整理| 查看: 265

简述：

线性表是 n (≥0) 个数据元素的有限序列记作L =（a1, a2, …, an），ai 是表中数据元素（也叫表项），n 是线性表的长度，L是表名。n=0是空表, 第1个表项叫表头（head)，最后1个表项叫表尾(tail)。

原则上讲，线性表中元素的数据类型可以不相同。由于采用的存储结构不同，会对元素的数据类型有限制。为简单起见，假定各元素类型相同。

线性表特点 1.除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。

2.除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。

3.直接前驱和直接后继描述了结点之间的逻辑关系，即邻接关系，表示为。

一、顺序表

将线性表中元素相继存放在一个连续的存储空间中。可利用一维数组实现。顺序表特点：逻辑顺序与物理存储顺序一致，可随机访问。

具体实现：

#include using namespace std; const int kDefaultSize = 100; //线性表中存放不同的数据类型，可以用union实现 //union T //{ // int val; // char ch; // float dir; // T* link; //}; template class SeqList { public: SeqList(int size=kDefaultSize); ~Seqlist(); SeqList(SeqList& L);//拷贝构造 SeqList& operator=(SeqList& L);//重载运算符= bool GetData(int i, T& x) const; void SetData(int i, T& x); bool IsEmpty()const; bool IsFull()const; int Size() const;//表中最大容纳的元素的个数 int Length() const;//表长度 void Sort(); int Locate(int i) const;//定位第i个元素，返回表项序号 bool Insert(int i, const T& x);//在第i个元素位置插入数据x bool Remove(int i, T& x);//删除第i个元素，通过x返回该元素的值 int Search(const T& x) const; //顺序表的静态存储 // T data[kDefaultSize]; // int n;//表示当前元素个数 //顺序表的动态存储 private: T* data; int n; int MAXSIZE;//表示最大能够容纳的元素个数 void resize(int newSize);//改变数组空间的大小 }; template SeqList::SeqList(int size) { if (size > 0) { maxSize = size; n = 0; data = new T[maxSize]; if (data = nullptr) { cerr data; return true; } return false; } template void List::InputFront(const T& elem) { ListNode* newNode = new ListNode(elem); if (newNode == nullptr) return; newNode->next = first; first = newNode; } template void List::InputRear(const T& elem) { ListNode* newNode = new ListNode(elem); if (newNode == nullptr) return; if (first == nullptr) { first = newNode; } else { ListNode* rear = first; while (rear->next != nullptr) { rear = rear->next; } rear->next = newNode; } } template bool List::Insert(int i, const T& x)//让第i个结点的值，变成插入的x { if (in) return false; else { if (first->next=NULL)//表头节点没有直接前驱 { InputFront(x); return true; } else { pre = first; for (int j = 1; j < i - 1; j++) { if (pre = nullptr) break; pre = pre->next; } /*定位当前位置的前驱结点pre listNodeM* pre = locate(i - 1);*/ if (pre = nullptr) { ceer next; pre->next; return true; } } } } template bool List::Remove(int i, T& x) { ListNode* del; ListNode* pre = Locate(i - 1); // 定位当前位置的前驱节点pre if (pre == nullptr || pre->next == nullptr) // 空表或者表链太短 return false; del = pre->next; // 当前位置 pre->next = del->next; x = del->data; //保存删除结点的数据 delete del; return true; } template void List::MakeEmpty() { ListNode* pnd = NULL; while (first != NULL) { pnd = first; first = first->next; delete pnd; } } template List::~List() { MakeEmpty(); } template void List::CopyList(const List& L) { if (L.first == NULL) return; ListNode* newNode = new ListNode(L.first->data); first = newNode; iter = L.first->next; rear = newNode; while (iter) { newNode= new LinkNode(iter->data); rear->next = newNode; iter = iter->next; rear = rear->next; } } template List::List(const List& L) { first = nullptr; CopyList(L); } template List& List::operator=(const List& L) { //首先判断是否是自复制，如果不是，调用CopyList函数完成链表的复制。 if (this == &L) return *this; MakeEmpty(); CopyList(L); return *this; } 三、循环链表

循环链表（circular list）是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的next域中不是NULL，而是存放了一个指向链表开始结点的指针。

链表表尾的特点不再是其next域指向NULL，而是其next区域指向表头结点。

在表头位置插入或删除结点，不仅需要修改first指针指向，也需要修改表尾结点next域的指向。

实现过程及举例

#include using namespace std; template struct CircLinkNode { T data; CircLinkNode* next; CircLinkNode(const T& item, CircLinkNode* ptr = NULL) { data = item; next = ptr; } CircLinkNode(CircLinkNode* ptr = NULL) { next = ptr; } }; template //链表类定义 class CircList { private: CircLinkNode* first, * last; //头指针, 尾指针 public: CircList(const T& x); //构造函数 CircList(const CircList& L); //复制构造函数 CircList operator=(const CircList& L); // 赋值运算符函数 ~CircList(); //析构函数 bool Insert(int i, const T& x); //插入 bool Remove(int i, T& x); //删除 CircLinkNode* Search(const T& x); //搜索 CircLinkNode* Locate(int i); //定位 T* getData(int i); //提取 void setData(int i, T x); //修改 int Length() const; //计算链表长度 bool IsEmpty();//判表空否 CircLinkNode* getHead() const; //返回表头结点地址 void setHead(CircLinkNode* p); //设置表头结点地址 }; //功能举例实现： template CircLinkNode* CircList::Search(const T& x) { //在链表中从头搜索其数据值为 x 的结点 current = first->next; while (current != first && current->data != x) current = current->next; return current; } 四、双向循环链表

双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。

双向链表通常采用带表头结点的循环链表形式。

具体实现：

#include using namespace std; template struct DblNode { T data; DblNode* rLink, * lLink; DblNode(DblNode* l = NULL, DblNode* r = NULL) { lLink = l; rLink = r; } DblNode(T value, DblNode* l = NULL, DblNode* r = NULL) { data = value; lLink = l; rLink = r; } }; template class DblList { private: DblNode* first; public: DblList(); DblList(const DblList& L); DblList& operator=(const DblList& L); ~DblList(); void MakeEmpty(); //清空 void CopyList(); //复制链表 DblNode* GetFirst()const; //返回头结点 DblNode* Locate(int i, int d = 1); //判断第i个结点是否在链表中 bool Insert(int i, const T& x, int d = 1);//在第i个位置插入结点 bool Remove(int i, T& x, int d);//在第i个位置删除节点 DblNode* Search(const T& x, int d = 1);// 搜索x void SetData(int i, const T& x);// 设置第i个位置上的结点 bool GetData(int, T& x); //返回第i位置上的结点 bool IsEmpty(); //判空 bool IsFull(); //判满 friend istream& operator >> (istream& in, DblList& dbl); friend ostream& operator

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻