数据结构实现-线性表

顺序存储

#include<iostream>
using namespace std;
#define MaxSize 50
//静态顺序表
template<typename ElemType>
struct sqList{ElemType data[MaxSize];//元素int length;//长度
};
//动态顺序表
#ifdef DEBUG //关闭启用
#define InitSize 100
template<typename ElemType>
struct seqList {ElemType* data;//元素int MaxSize;//最大容量int length;//长度
};
#endif // DEBUG//插入操作
template<typename ElemType>
/**	@param L 顺序表*	@param i 插入位置(从1开始)*	@param e 插入元素
*/
bool ListInsert(sqList<ElemType>& L, int i, ElemType e) {if (i<1 || i>L.length + 1)//判断插入范围是否合理(第1个元素到最后一个元素的下一个)return false;if (L.length >= MaxSize)//顺序表长度大于最大长度return false;for (int j = L.length; j >= i; --j) {//移动顺序表L.data[j] = L.data[j - 1];}L.data[i - 1] = e;//插入++L.length;  //长度+1return true; //表示插入成功
}//删除操作
template<typename ElemType>
/**	@param L 顺序表*	@param i 删除位置(从1开始)*	@param e 插入元素
*/
bool ListDelete(sqList<ElemType>& L, int i, ElemType& e) {if (i<1 || i>L.length) //删除元素下标范围return false;e = L.data[i - 1];  //复制删除内容for (int j = i ; j < L.length; ++j) {L.data[j - 1] = L.data[j];}--L.length; //顺序表长度-1return true; //操作成功
}//按值查找(顺序查找)
template<typename ElemType>
/**	@param L 顺序表*	@param e 查找元素
*/
int LocalElem(sqList<ElemType>& l, ElemType& e) {int i;for (i = 0; i < l.length; ++i) {if (l.data[i] == e) //找到待查找元素下标return i + 1;}return 0;
}

链式存储

#include<iostream>
using namespace std;//链表节点
template<typename ElemType>
struct LNode {ElemType data;//元素struct LNode *next;//长度
};//头插法建立链表
template<typename ElemType>
/**	@param L 顺序表
*/
LNode<ElemType>* List_HeadInsert(LNode<ElemType>* L) {LNode<ElemType>* s; ElemType x;L = new LNode<ElemType>;L->next = nullptr;cin >> x;while (x != 9999) {s = new LNode<ElemType>;s->data = x;s->next = L->next;L->next = s;cin >> x;}return L;
}//尾插法建立链表
template<typename ElemType>
/**	@param L 顺序表
*/
LNode<ElemType>* List_TailInsert(LNode<ElemType>* L) {ElemType x;L = new LNode<ElemType>;LNode<ElemType>* s, * r = L;cin >> x;while (x != 9999) {s = new LNode<ElemType>;s->data = x;r->next = s;r = s;cin >> x;}r->next = nullptr;return L;
}//按序号查找结点
template<typename ElemType>
/**	@param L 顺序表*	@param i 位置(从1开始)
*/
LNode<ElemType>* GetElem(LNode<ElemType>*L, int i) {if (i < 1)return nullptr;int j = 1;LNode<ElemType>* p = L->next;while (p != nullptr && j < i) {p = p->next;++j;}return p;
}//按值查找节点
template<class ElemType>
/**	@param L 顺序表*	@param e 插入元素
*/
LNode<ElemType>* LocateElem(LNode<ElemType>* L, ElemType e) {LNode<ElemType>* p = L;while (p!=nullptr&&p->data!=e){p = p->next;}return p;
}//在第i个前插入节点
template<class ElemType>
/**	@param L 顺序表*	@param i 插入位置(从1开始)*	@param e 插入元素
*/
bool Front_Insert(LNode<ElemType>* L, int i, ElemType e) {LNode<ElemType>* temp = GetElem(L, i - 1);if (temp == nullptr)return false;LNode<ElemType>* newNode = new LNode<ElemType>;newNode->data = e;newNode->next = temp->next;temp->next = newNode;return true;
}//删除第i个节点
template<class ElemType>
/**	@param L 顺序表*	@param i 位置(从1开始)
*/
bool Delete(LNode<ElemType>* L, int i) {LNode<ElemType>* temp = GetElem(L, i - 1);if (temp == nullptr)return false;LNode<ElemType>* next = temp->next;temp->next = temp->next->next;delete next;return true;
}//获取链表长度
template<class ElemType>
/**	@param L 顺序表
*/
int GetLinkLength(LNode<ElemType>* L) {int cnt = 0;LNode<ElemType>* cur = L->next;while (cur){++cnt;cur = cur->next;}return cnt;
}