链表的定义
发布日期:2021-05-14 10:58:29 浏览次数:16 分类:博客文章

本文共 9905 字,大约阅读时间需要 33 分钟。

#include
#include"../../������������/������������������������/������������������������.cpp"#include"../../������������/Compare���������������/Compare���������������.cpp"using namespace std;template
struct LinkNode { ElemType data; struct LinkNode
* next;};#define LinkList LinkNode
*// ���������������template
Status InitLinkList(LinkList& linkList) { // ������������������������������������next������������NULL linkList = (LinkList)malloc(sizeof(LinkNode
)); if (!linkList) exit(OVERFLOW); linkList->next = NULL; return OK;}// ���������������������template
int LengthOfLinkList(LinkList linkList) { LinkNode
* p = linkList->next; int length = 0; while (p != NULL) { length++; p = p->next; } return length;}// ���������order������������������template
Status LocationInOrder(LinkList linkList, int order, LinkNode
*& p_linkNode) { // ������order������������: [0, length] if (0 <= order) { int index = 0; LinkNode
* cursor = linkList; /* * index < order : ���������������index=order���������p���������order��������� * cursor!=NULL : ���������order���������������������order<=length��� * ���������������index
next; index++; } if (!cursor) // ������order���length return ERROR; else { p_linkNode = cursor; return OK; } } else { return ERROR; }}// ���������������order������������������������template
Status LocationInRelativeOrder_Prior(LinkList linkList, int relativeOrder, LinkNode
* p_linkNode, LinkNode
*& p_relative) { p_relative = NULL; // relativeOrder������������: [0, p_linkNode-1]��� if (relativeOrder < 0) return ERROR; // ��������������������������� LinkNode
* cursor = linkList->next; int order = 1; // order������������������������ ��� o���r // ������cursor������relativeOrder������������������relativeOrder+1���������������������relativeOrder-1��������� while (order < relativeOrder + 1) { if (cursor == p_linkNode) return ERROR; cursor = cursor->next; order++; } p_relative = linkList->next; // ������p_relative���cursor���������������������cursor==p_linkNode��������� while (cursor != p_linkNode) { p_relative = p_relative->next; cursor = cursor->next; } return OK;}// ���������������order������������������������template
Status LocationInRelativeOrder_Next(LinkList linkList, int relativeOrder, LinkNode
* p_linkNode, LinkNode
*& p_relative) { p_relative = NULL; if (relativeOrder < 0) return ERROR; int order = 0; p_relative = p_linkNode; while (order < relativeOrder) { p_relative = p_relative->next; order++; if (!p_relative) return ERROR; } return OK;}// ���������������order������������������template
Status LocationInRelativeOrder(LinkList linkList, int relativeOrder, LinkNode
* p_linkNode, LinkNode
*& p_relative) { return relativeOrder <= 0 ? LocationInRelativeOrder_Prior(linkList, -relativeOrder, p_linkNode, p_relative) : LocationInRelativeOrder_Next(linkList, relativeOrder, p_linkNode, p_relative);}// ���������1���������compare���������data���������������������������template
int LocationOfLinkNode(LinkList linkList, ElemType data, LinkNode
*& p_linkNode, int (*compare)(ElemType, ElemType)) { LinkNode
* cursor = linkList->next; int index = 1; while (cursor) { if (compare(cursor->data, data)) break; cursor = cursor->next; index++; } p_linkNode = cursor; if (!cursor) index = -1; return index;}// ������������������������������(���������)template
Status InsertLinkList(LinkList& linkList, ElemType data) { // ���������������������data������������ LinkNode
* p_dataNode = (LinkNode
*)malloc(sizeof(LinkNode
)); if (!p_dataNode) return ERROR; else { p_dataNode->data = data; // ���������������next��������������� p_dataNode->next = linkList->next; // ���������������next������������������������������������������������������������ linkList->next = p_dataNode; return OK; }}// ������������p_linkNode���������������������template
Status InsertLinkListNext(LinkNode
* p_linkNode, ElemType data) { LinkNode
* nextNode = (LinkNode
*)malloc(sizeof(LinkNode
)); if (!nextNode) return ERROR; nextNode->data = data; nextNode->next = p_linkNode->next; p_linkNode->next = nextNode; return OK;}// ���������������order���������������datatemplate
Status InsertLinkList(LinkList& linkList, int order, ElemType data) { // ���������order-1��������� LinkNode
* p_preOfOrder = NULL; // order-1��������������������������������������������� if (LocationInOrder(linkList, order - 1, p_preOfOrder) == OK) { LinkNode
* p_dataNode = (LinkNode
*)malloc(sizeof(LinkNode
)); if (!p_dataNode) return OVERFLOW; else { p_dataNode->data = data; p_dataNode->next = p_preOfOrder->next; p_preOfOrder->next = p_dataNode; return OK; } } else { return ERROR; }}// ���������������order���������������������template
Status InsertLinkList(LinkList& linkList_dest, int order, LinkList linkList_source) { // ������order������������: [1, length+1] int index = order; LinkNode
* p_source = linkList_source->next; while (p_source) { if (InsertLinkList(linkList_dest, order++, p_source->data) != OK) return ERROR; p_source = p_source->next; } return OK;}// ������������������������������template
int InputLinkNodes(LinkList& linkList) { char finishFlag = '\n'; int length = 0; cout << "���������������" << typeid(ElemType).name() << "������(������������������)���"; do { ElemType data; cin >> data; InsertLinkList(linkList, ++length, data); finishFlag = getchar(); } while (finishFlag != '\n'); return length;}// ���������������order���������������template
Status DeleteLinkNode(LinkList& linkList, int order) { // ���������order-1��������� LinkNode
* p_preOfOrder = NULL; // order-1���������: [0, length-1]������������������������������: [0, length] if (LocationInOrder(linkList, order - 1, p_preOfOrder) == OK && p_preOfOrder->next) { // !p_preOfOrder->next���������order-1���������length������������order
* p_del = p_preOfOrder->next; p_preOfOrder->next = p_del->next; free(p_del); return OK; } else { return ERROR; }}// ���������������������������template
Status DeleteLinkNode(LinkList& linkList, LinkNode
* node_del) { // ������������������ LinkNode
* p_prior = NULL; if (LocationInRelativeOrder(linkList, -1, node_del, p_prior) == OK) { p_prior->next = node_del->next; free(node_del); } else { return ERROR; }}// ������������������������������������������template
Status DeleteNextLinkNode(LinkList& linkList, LinkNode
* node_del) { LinkNode
* node_del_next = node_del->next; node_del->next = node_del_next->next; free(node_del_next);}// ���������������template
Status ReverseLinkList(LinkList& linkList) { // ���������2������������������������������������linkList������������������2 LinkNode
* p_second = NULL; if (LocationInOrder(linkList, 2, p_second) == OK) { // ��������������������������������������������������������������� linkList->next->next = NULL; LinkNode
* preCursor, * cursor; preCursor = cursor = p_second; while (preCursor) { // cursor��������������������������������� cursor = cursor->next; // ���������������_linkList->next��������������� preCursor->next = linkList->next; linkList->next = preCursor; // _linkList������������������ preCursor = cursor; } return OK; } else { return ERROR; }}// ���������������������template
LinkList MergeLinkList(LinkList& linkList_dest, LinkList& linkList_source) { LinkNode
* p_dest = linkList_dest->next, * p_source = linkList_source->next; LinkNode
* p_tmp = linkList_dest; while (p_dest && p_source) { if (p_dest->data <= p_source->data) { p_tmp->next = p_dest; p_tmp = p_dest; p_dest = p_dest->next; } else { p_tmp->next = p_source; p_tmp = p_source; p_source = p_source->next; } } p_tmp->next = p_dest ? p_dest : p_source; free(linkList_source); return linkList_dest;}// ���������������������������������������template
void PrintLinkList(LinkList linkList) { LinkNode
* p = linkList; cout << "��������� ��� "; while (p->next) { p = p->next; cout << p->data << " ��� "; } cout << "NULL" << endl;}int main() { // ���������������12 23 34 45 56 67 78 89 90#define ElemType int LinkList linkList; InitLinkList(linkList); int length = InputLinkNodes(linkList); cout << "linkList���������������" << length << endl; cout << "linkList���������������"; PrintLinkList(linkList); int order_del; order_del = 1; DeleteLinkNode(linkList, order_del); cout << "���������" << order_del << "������������������"; PrintLinkList(linkList); order_del = 5; DeleteLinkNode(linkList, order_del); cout << "���������" << order_del << "������������������"; PrintLinkList(linkList); order_del = 3; DeleteLinkNode(linkList, order_del); cout << "���������" << order_del << "������������������"; PrintLinkList(linkList); cout << "linkList������������: "; ReverseLinkList(linkList); PrintLinkList(linkList); LinkNode
* p_linkNode = NULL, * p_relativePrior = NULL, * p_relativeNext = NULL; int coreOrder = 3; LocationInOrder(linkList, coreOrder, p_linkNode); LocationInRelativeOrder(linkList, -2, p_linkNode, p_relativePrior); LocationInRelativeOrder(linkList, 2, p_linkNode, p_relativeNext); cout << "������������������" << coreOrder << "���-2���" << p_relativePrior->data << endl; cout << "������������������" << coreOrder << "���+2���" << p_relativeNext->data << endl; cout << "���������" << coreOrder << "���������(" << p_linkNode->data << ")���������"; DeleteLinkNode(linkList, p_linkNode); PrintLinkList(linkList);#undef ElemType#define ElemType int LinkList linkList_source; InitLinkList(linkList_source); InsertLinkList(linkList_source, 3); InsertLinkList(linkList_source, 2); InsertLinkList(linkList_source, 1); cout << "linkList\t���\t"; PrintLinkList(linkList); cout << "linkList_source\t���\t"; PrintLinkList(linkList_source); cout << "���������linkList\t���\t"; InsertLinkList(linkList, 2, linkList_source); PrintLinkList(linkList); LinkNode
* p = NULL, * p_linkNode_2 = NULL; LocationInOrder(linkList, 2, p); cout << "���2������������������������" << p->data << endl; cout << "���1���" << p->data << "���������������" << LocationOfLinkNode(linkList, p->data, p_linkNode_2, Equal) << endl;#undef ElemType return 0;}
上一篇:矩阵旋转-Eigen应用(QTCreator编辑器)
下一篇:Telerik入门之Bar绘制

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2025年05月06日 01时47分56秒