定义一个双向链表
// 定义双向链表
typedef struct LinkNode {
int data; //数据域
LinkNode *next; //下一个节点
LinkNode *last; //上一个节点
}LinkNode, //节点域
LinkList; //头结点
初始化空的双向链表
// 初始化空的双向链表
bool List_Init(LinkList *&list) {
list = new LinkNode;
if (!list) return false;
list->next = NULL; //下一个节点置空
list->last = NULL; //上一个节点置空
return true;
}
前插法插入节点
// 前插法插入节点
bool List_Add_front(LinkList *&list, LinkNode *node) {
LinkNode *p = list; //临时指针变量
if (!list || !node)return false;
if (list->next == NULL) { //从头节点后插入元素
node->next = NULL; //新节点的下一个元素指向空
node->last = list; //新节点的上一个指向头节点
list->next = node; //p指向新元素
} else {
list->next->last = node; //头结点往后一个节点的上一个指向新元素
node->next = list->next; //新节点的下一个指向之前头结点指向的节点
node->last = list; //新节点的上一个指向头节点
list->next = node; //头节点的下一个指向新节点
}
return true;
}
尾插法插入节点
// 尾插法插入节点
bool List_Add_Back(LinkList *&list, LinkNode *node) {
LinkNode *last = NULL;
if (!list || !node) return false;
last = list;
while (last->next) {
last = last->next; //指向最后一个
}
node->next = NULL; // 新节点下一个置空
node->last = last; // 新节点的上一个节点指向最后一个
last->next = node; // 最后一个节点的下一个指向新节点
return true;
}
指定位置插入节点
// 指定位置插入节点
bool List_Insert(LinkList *&list, int i, int &e) {
if (!list || !list->next) return false;
if (i < 1) return false;
int j = 0;
LinkList *p = NULL, *s = NULL;
p = list;
while (p && j < i) { //查找第i个节点,然后p指向该节点
p = p->next;
j++;
}
if (!p || j != i) {
cout << "要插入的节点不存在" << endl;
return false;
}
s = new LinkNode;
s->data = e;
p->last->next = s; // p的上一个节点的下一个指向新节点
s->last = p->last; // 新节点的上一个指向p的上一个节点
s->next = p; // 新节点的下一个指向p
p->last = s; // p的上一个指向新节点
return true;
}
获取指定节点的数据
bool List_GetElem(LinkList *&list, int i, int &e) {
//在带头结点的双向链表 list 中查找第 i 个元素
//用 e 记录 list中第 i 个数据元素的值
LinkList *p = NULL; //临时指针
int index; //计数
if (!list || !list->next) return false;
p = list->next;
index = 1;
while (p && index < i) { //找到第i个节点
p = p->next;
index++;
}
if (!p || index > i) return false; //i 值不合法,i>index 或 i<=0
e = p->data; //找到的数据赋值给e
return true;
}
删除指定位置的节点
// 删除指定位置的节点
bool List_Delete(LinkList *&list, int i) {
LinkNode *p = NULL; //临时查找节点
int j = 0; //计数
if (!list || !list->next) return false;
if (i < 1) return false;
p = list;
while (p && j < i) {
p = p->next;
j++;
}
if (!p) {
return false;
}
if (!p->next) { //删除最后一个节点
p->last->next = NULL; //最后一个节点的上一个节点置空
delete p;
return true;
}
p->last->next = p->next;
p->next->last = p->last;
delete p;
return true;
}
销毁双向链表
// 销毁双向链表
void List_Destroy(LinkList *&list) {
LinkList *p = list;
cout << "销毁链表!" << endl;
while (p) {
list = list->next;
delete p;
p = list;
}
}
输出双向链表
// 输出双向链表
void List_Print(LinkList *&list) {
LinkNode *p = NULL;
if (!list) return;
p = list;
while (p->next) {
cout << p->next->data << "\t";
p = p->next;
}
cout << endl;
/*cout << endl << "逆向输出" << endl;
while (p && p!=list) {
cout << p->data << "\t";
p = p->last;
}
cout << endl;*/
}
main函数
int main(void) {
LinkList *list = NULL;
LinkNode *node = NULL;
int n = 0;
// 1.初始化双向链表
List_Init(list);
// 2.前插法
cout << "请输入插入的数量: ";
cin >> n;
for (int i = 0; i < n; i++) {
node = new LinkNode; //生成新节点
node->data = i+1;
List_Add_front(list, node); //插入node元素
}
// 输出链表
List_Print(list);
尾插法
//cout << "请输入插入的数量: ";
//cin >> n;
//for (int i = 0; i < n; i++) {
// node = new LinkNode; //生成新节点
// node->data = i + 1;
// List_Add_Back(list, node); //插入node元素
//}
指定位置插入数据
//int site = 0; //位置
//int data = 0; //数据
//cout << "请输入要插入的位置: ";
//cin >> site;
//cout << "请输入要插入的数据: ";
//cin >> data;
//if (List_Insert(list, site, data)) {
// cout << site << "位置插入数据: " << data << "成功!" << endl;
//} else {
// cout << site << "位置插入数据: " << data << "失败!" << endl;
//}
从链表中获取指定位置节点的数据
//int site = 0; //位置
//int data = 0; //数据
//cout << "请输入要获取数据的位置: ";
//cin >> site;
//if (List_GetElem(list, site, data)) {
// cout << "查找第" << site << "个节点成功, 数据:" << data << endl;
//} else {
// cout << "查找第" << site << "个节点失败!" << endl;
//}
//删除指定位置的节点
int n;
cout << "请输入要删除节点的位置: ";
cin >> n;
if (List_Delete(list, n)) {
cout << "删除第" << n << "个节点成功!" << endl;
} else {
cout << "删除第" << n << "个节点失败!" << endl;
}
//销毁双向链表
List_Destroy(list);
// 输出链表
List_Print(list);
system("pause");
return 0;
}