外贸型网站建设,wordpress微博功能,码制作官网,免费的企业邮箱本程序List链表用两种方式实现#xff0c;一种是双向链表#xff0c;一种是双向循环链表。循环双向链表和双向链表#xff0c;它们的编码差别很小#xff1b;但是循环链表在插入效率上胜出很多#xff0c;同时查询时候更灵活。综合考虑#xff0c;循环链表是首选。
另外…本程序List链表用两种方式实现一种是双向链表一种是双向循环链表。循环双向链表和双向链表它们的编码差别很小但是循环链表在插入效率上胜出很多同时查询时候更灵活。综合考虑循环链表是首选。
另外不同于Windows上的ListEntry结构本LIST结构没有链表头。对于链表头各有各的说法但是天下没有免费的午餐某个地方得了好处必然会在别的地方承担一定的损失。总之一句话我个人的理念是中间代码尽可能简单易用以此链表头弃之不用。
非常简单的两种链表实现主要是查询、插入、删除几个功能的实现总共的cpp代码不过300行左右在座的各位都是软件开发小能手功能实现不再赘述。
完整工程代码https://github.com/satadriver/dataStruct
头文件
#pragma once#include Element.h#pragma pack(1)typedef struct _LIST
{_LIST* prev;_LIST* next;ELEMENT* e;
}LIST;#pragma pack()class List {
public:List();~List();int insert(ELEMENT* e);int remove(ELEMENT* e);protected:LIST* search(ELEMENT* e);LIST* mList;int mSize;
};class CList {
public:CList();~CList();int insert(ELEMENT* e);int remove(ELEMENT* e);protected:LIST* search(ELEMENT* e);LIST* mList;int mSize;
};循环双向链表实现代码如下
int CList::clear() {LIST* l mList;int cnt 0;do{if (l 0){break;}LIST* next l;delete l-e;delete l;l next;cnt;} while (l ! mList);return cnt;
}CList::CList() {mList 0;mSize 0;
}CList::CList(LIST* l) {mList l;mSize 0;
}CList::~CList() {if (mList){delete[] mList;mList 0;}
}LIST* CList::search(ELEMENT* e) {LIST* list mList;int cnt 0;do{if (list 0){break;}if (list-e-e e-e){return list;}list list-next;cnt;} while (list ! mList);return 0;
}int CList::insert(ELEMENT* e) {LIST* list search(e);if (list){return 0;}list new LIST;ELEMENT* e_new new ELEMENT;memcpy(e_new, e, sizeof(ELEMENT));list-e e_new;if (mList 0){list-next list;list-prev list;mList list;}else {LIST* prev mList-prev;list-next mList;list-prev mList-prev;if (prev){prev-next list;}mList-prev list;}mSize;return 1;
}int CList::remove(ELEMENT* e) {LIST* list search(e);if (list 0){return 0;}LIST* next list-next;LIST* prev list-prev;if (next){next-prev prev;}if (prev){prev-next next;}delete list-e;if (list mList){if (mList-next mList || mList-prev mList){mList 0;}else {mList mList-next;}}delete list;int result mSize;mSize--;return result;
}双向链表实现代码
List::List() {mList 0;mSize 0;
}List::List(LIST* l) {mList l;mSize 0;
}List::~List() {if (mList){delete[] mList;mList 0;}
}LIST* List::search(ELEMENT* e) {LIST* list mList;int cnt 0;while (list){if (list-e-e e-e){return list;}list list-next;cnt;}return 0;
}int List::insert(ELEMENT* e) {LIST* list search(e);if (list){return 0;}list new LIST;ELEMENT* e_new new ELEMENT;memcpy(e_new, e, sizeof(ELEMENT));list-e e_new;int cnt 0;if (mList 0){list-next 0;list-prev 0;mList list;cnt;}else {cnt;LIST* tmp mList;while (tmp-next){tmp tmp-next;cnt;}list-next 0;list-prev tmp;tmp-next list;cnt;}mSize cnt;return cnt;
}int List::clear() {LIST* l mList;int cnt 0;do{if (l 0){break;}LIST* next l;delete l-e;delete l;l next;cnt;} while (l ! mList);return cnt;
}int List::remove(ELEMENT* e) {LIST* list search(e);if (list 0){return 0;}LIST* next list-next;LIST* prev list-prev;if (next){next-prev prev;}if (prev){prev-next next;}delete list-e;if (list mList){if (mList-next 0){mList 0;}else {mList mList-next;}}delete list;int result mSize;mSize--;return result;
}
