网站导航
> 文档中心 > 数据结构与算法设计3 顺序表和链表

数据结构与算法设计3 顺序表和链表

网友: 文档中心 2022-04-23 11:24:51

目录

1.线性表的定义

2.线性表的逻辑特征

3.数据元素的特性

4.顺序表的类模板定义

5.顺序表的优缺点

6.单链表的类模板定义

7.双向循环链表的类模板定义

 如果觉得我写得还行的话，希望三连，鼓励一下哦！！！ 

1.线性表的定义

一个线性表是n个相同类型的数据元素的有限序列。

2.线性表的逻辑特征

（1）有且仅有一个开始结点a_{1}（无前趋）；

（2）有且仅有一个终端结点a_{n}（无后继）；

（3）其余结点ai都有且仅有一个前趋a_{i-1}和一个后继a_{i+1};

3.数据元素的特性

（1）线性表中的所有数据元素的数据类型是一致的；

（2）数据元素在线性表中的位置只取决于它的序号；

（3）数据元素间的逻辑关系是线性的；

4.顺序表的类模板定义

#pragma once#include#include#includeusing namespace std; typedef enum {    NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW，DEFAULT_SIZE}Status;template class SeqList {protected:int length;    //顺序表的当前长度    int maxLength;  //顺序表的最大容量    ElemType* elems;   //元素存储空间的首地址public:    SeqList(int size = DEFAULT_SIZE); //构造函数    SeqList(ElemType v[], int n, int size = DEFAULT_SIZE);    //构造函数，跟据数组v的内容构造顺序表    virtual ~SeqList();  //析构函数    int GetLength() const;  //取顺序表的长度    bool IsEmpty() const;  //判断顺序表是否为空    void Clear();  //清空顺序表    void Traverse(void (*visit)(const ElemType&)) const;  //遍历顺序表    int LocateElem(const ElemType& e)const; //元素定位    Status GetElem(int i, ElemType& e) const; //取得顺序表第i个元素的值    Status SetElem(int i, const ElemType& e); //修改顺序表第i个元素的值    Status DeleteElem(int i, ElemType& e); //删除顺序表第i个元素的值    Status InsertElem(int i, const ElemType& e); //在任意位置插入    Status InsertElem(const ElemType& e); //尾插    SeqList(const SeqList& sa); //拷贝构造    SeqList& operator=(const SeqList& sa);//赋值运算符重载};template //构造空顺序表SeqList::SeqList(int size){    elems = new ElemType[size];//申请内存空间    assert(elems);//判断是否成功    maxLength = size;//设置顺序表最大容量    length = 0;//空线性表的长度为0}template //根据数组内容构造顺序表SeqList::SeqList(ElemType v[], int n, int size) {    elems = new ElemType[size];//申请内存空间    assert(elems);//判断是否成功    maxLength = size;//设置顺序表最大容量    length = n;//线性表的长度为n    for (int i = 0; i < length; i++)//将数组v中的元素依次存放到elems数组中 elems[i] = v[i];}template //析构函数SeqList::~SeqList(){    delete[]elems;}template //清空顺序表void SeqList::Clear(){    length = 0;}template //遍历顺序表void SeqList::Traverse(void (*visit)(const ElemType&)) const{    for (int i = 1; i <= length; i++) (*visit)(elems[i - 1]);}template //定位函数int SeqList::LocateElem(const ElemType& e) const{    int i = 0;    while (i < length && elems[i] != e) i++;    return i < length ? i + 1 : 0;}template //取指定的值Status SeqList::GetElem(int i, ElemType& e) const{    if (i  length)return NOT_PRESENT;    else { e = elems[i - 1]; return ENTRY_FOUND;    }}template //修改指定的值Status SeqList::SetElem(int i, const ElemType& e){    if (i  length)return RANGE_ERROR;    else { elems[i - 1] = e; return SUCCESS;    }}template //删除指定的值Status SeqList::DeleteElem(int i, ElemType& e){    if (i  length) return RANGE_ERROR;    else { e = elems[i - 1]; for (int j = i; j < length; j++) //移动元素     elems[j - 1] = elems[j]; length--; return SUCCESS;    }}template //在任意位置插入数据Status SeqList::InsertElem(int i, const ElemType& e){    if (length == maxLength)return OVER_FLOW;    else if (i  length + 1)   return RANGE_ERROR;    else { for (int j = length; j >= i; j--)  //移动元素     elems[j] = elems[j - 1]; elems[i - 1] = e; length++; return SUCCESS;    }}template //在顺序表尾部插入数据Status SeqList::InsertElem(const ElemType& e){    if (this->length == this->maxLength) return OVER_FLOW;    else { this->elems[this->length] = e; this->length++; return SUCCESS;    }}//取顺序表的长度template int SeqList::GetLength() const {    return length;}//判断顺序表是否为空template bool SeqList::IsEmpty() const {    return length ? false : true;}//拷贝构造函数template SeqList::SeqList(const SeqList& sa) {    elems = new ElemType[sa.maxLength];    assert(elems);    maxLength = sa.maxLength;    length = sa.length;    for (int i = 0; i < length; i++) elems[i] = sa.elems[i];}//赋值运算符重载template SeqList& SeqList::operator=(const SeqList& sa) {    if (this == &sa)return *this;    if (elems)delete[]elems;    elems = new ElemType[sa.maxLength];    assert(elems);    maxLength = sa.maxLength;    length = sa.length;    for (int i = 0; i < length; i++)    elems[i] = sa.elems[i];    return *this;}

5.顺序表的优缺点

优点： （1）无须为表示数据元素之间的逻辑关系而增加额外的存储空间。

           （2）可以方便地随机访问表中的任一数据元素。

缺点： （1）插入和删除平均须移动一半结点。

           （2）存储分配只能预先进行（静态）  过大  \rightarrow  浪费    过小  \rightarrow  溢出

6.单链表的类模板定义

 结点类的定义

#pragma oncetemplatestruct Node {private:Node* next;ElemType data;public:Node();Node(ElemType e, Node* link = NULL);};templateNode::Node() {next = NULL;}templateNode::Node(ElemType e, Node* link ) {data = e;next = link;}

Status枚举类型定义 

#pragma oncetypedef enum{ NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW }Status;
#pragma once#include"Node.h"#include"Status.h"#include"assert.h"templateclass LinkList {private:Node * head;int length;public:LinkList();LinkList( ElemType v[], int n);virtual~LinkList();int Getlength()const;bool IsEmpty();void clear();void Traverse( void(*visit)( const ElemType& ))const;int LocateElem(const ElemType& e);Status GetElem(int i, ElemType& e)const;Status SetElem(int i, const ElemType& e);Status DeletElem(int i, ElemType& e);Status InsertElem(int i, const ElemType& e);Status InsertElem(const ElemType& e);LinkList(const LinkList & ee);LinkList& operator=(const LinkList & ee);};templateLinkList ::LinkList() {head = new Node;length = 0;}templateLinkList ::LinkList(ElemType v[], int n) {Node * p;head = new Node ;p = head;for (int i = 0; i next = new Node(v[i], NULL);assert(p->next);p = p->next;}length = n;}templateLinkList::~LinkList() {clear();delete head;}templateint LinkList::Getlength()const {return length;}templatebool LinkList::IsEmpty() {return length ? false : true;}templatevoid LinkList::clear() {Node * p = head->next;while (p != NULL) {head->next = p->next;delete p;p = head->next;}length = 0;}templatevoid LinkList::Traverse(void(*visit)(const ElemType&))const {Node* p = head->next;while (p!=NULL){(*visit)(p->data);p = p->next;}}templateint LinkList::LocateElem(const ElemType& e) {int count = 1;Node* p = head->next;while (p!=NUll &&p->data!=e){p = p->next;count++;}return  p != NUll ? count : 0;}templateStatus LinkList::GetElem(int i, ElemType& e)const {if (ilength) {return RANGE_ERROR;}else {Node* p = head->next;for (int count = 1; count next;}e = p->data;return ENTRY_FOUND;}}templateStatus  LinkList::SetElem(int i, const ElemType& e) {if (ilength) {return RANGE_ERROR;}else{Node* p = head->next;for (int count = 1; count next;}p->data = e;}return SUCCESS;}templateStatus LinkList::DeletElem(int i, ElemType& e){if (ilength) {return RANGE_ERROR;}else {Node* p = head, * q;for (int count = 1; count next; q = p->next;p->next = q->next;e = q->data;length--;delete q;return SUCCESS;}}templateStatus LinkList::InsertElem(int i, const ElemType& e){if (ilength+1) {return RANGE_ERROR;}else {Node* p = head, q;for (int count = 1; count next;}q = new Node(e, p->next);p->next = q;length++;return SUCCESS;}}templateStatus LinkList::InsertElem(const ElemType& e){if (ilength + 1) {return RANGE_ERROR;}else {Node* p, q;q = new Node (e, NULL);for (p = head; p->next!= NULL; p = p->next) p->next = q;length++;return SUCCESS;}}templateLinkList::LinkList(const LinkList & ee){head = new Node; assert(head);ElemType temp;for (int i = 1; i <= Getlength(); i++) {ee.GetElem(i, temp);InsertElem(i, temp);}length = ee.Getlength();}templateLinkList& LinkList::operator=(const LinkList & ee){head = new Node;assert(head);if (this == &ee)return *this;if (head != NULL) {delete head;}ElemType temp;for (int i = 1; i <= Getlength(); i++) {ee.GetElem(i, temp);InsertElem(i, temp);}length = ee.Getlength();}

7.双向循环链表的类模板定义

结点类的定义 

#pragma oncetemplatestruct DblNode{private:DblNode* next;DblNode* prior;ElemType data;public:DblNode();DblNode(ElemType e, DblNode* linkprior, DblNode* linknext  );};templateDblNode::DblNode() {next = NULL;prior = NULL;}templateDblNode::DblNode(ElemType e, DblNode* linkprior, DblNode* linknext) {data = e;prior = linkprior;next = linknext;}

 枚举类型Status的定义

#pragma oncetypedef enum{ NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW }Status;
#pragma once#include"DblNode.h"#include"Status.h"#include"assert.h"template class DblLinkList{private:int length;DblNode* head;public:DblLinkList();DblLinkList(ElemType v[], int n);virtual~DblLinkList();int Getlength()const;bool IsEmpty()const;void Clear();int LocateElem(const ElemType& e);void Traverse(void(*visit)(const ElemType &))const;Status GetElem(int i, ElemType& e)const;Status SetElem(int i, const ElemType& e);Status DeletElem(int i, ElemType& e);Status InsertElem(int i, const ElemType& e);Status InsertElem(const ElemType& e);DblLinkList(const ElemType& sa);DblLinkList& operator=(const DblLinkList& sa);}; template DblLinkList::DblLinkList() {head = new DblNode;head->next = head;head->prior =head;length = 0;}template DblLinkList::DblLinkList(ElemType v[], int n) {DblNode* p;p = head = new DblNode;for (int i = 0; i next = new DblNode(v[i], p);p = p->next;}length = n;head->prior = p;p->next = head;}template DblLinkList::~DblLinkList() {Clear();delete head;}template int DblLinkList::Getlength()const {return length;}template bool DblLinkList::IsEmpty()const{return (length == 0);}template void DblLinkList::Clear() {ElemType a;while (length>0){DeletElem(1, a);}}template int DblLinkList::LocateElem(const ElemType& e) {DblNode* p = head->next;int count = 1;while (p!=head && p->data!= e){count++;p = p->next;}if (p != head)return count;else{return 0;}}template void DblLinkList::Traverse(void(*visit)(const ElemType&))const {DblNode* p;for (p = head->next; p != head; p = p->next) {(*visit)(p->data);}}template Status DblLinkList::GetElem(int i, ElemType& e)const{DblNode* p = head->next;int count;if (i length) {return NOT_PRESENT;}else{for (count = 1; count next;e = p->data;}return ENTRY_FOUND;}}template Status DblLinkList::SetElem(int i, const ElemType& e) {DblNode* p = head->next;int count;if (i length) {return NOT_PRESENT;}else{for (count = 1; count next;p->data = e;}return ENTRY_FOUND;}}template Status DblLinkList::DeletElem(int i, ElemType& e) {DblNode* p = head->next;int count;if (i length) {return NOT_PRESENT;}for (count = 1; count next;}p->prior->next = p->next;p->next->prior = p->prior;e = p->data;length--;delete p;return SUCCESS;}template Status DblLinkList::InsertElem(int i, const ElemType& e) {DblNode* p = head->next, * q;int count;if (i length) {return NOT_PRESENT;}else {for (count = 1; count next;}q = new DblNode(e, p->prior, p);p->prior->next = q;p->prior = q;length++;return SUCCESS;}}template Status DblLinkList::InsertElem(const ElemType& e) {DblNode* p;p = new DblNode(e, head->prior, head);head->prior->next = p;head->prior = p;length++;return SUCCESS;}template DblLinkList::DblLinkList(const ElemType& ee) {head = new Node;assert(head);ElemType temp;for (int i = 1; i <= Getlength(); i++) {ee.GetElem(i, temp);InsertElem(i, temp);}length = ee.Getlength();}template DblLinkList& DblLinkList::operator=(const DblLinkList& ee) {head = new Node;assert(head);if (this == &ee)return *this;if (head != NULL) {delete head;}ElemType temp;for (int i = 1; i <= Getlength(); i++) {ee.GetElem(i, temp);InsertElem(i, temp);}length = ee.Getlength();}

网络标签：

相关问题