# 2-4 线性表之双链表

## 1、结点的结构

typedef struct Dul_node { int data; Dul_node *prior; Dul_node * next; } dul_node;

## 2、初始化函数

void InitList(dul_node **h) {

(*h) = new dul_node; (*h)->next = nullptr; (*h)->prior = nullptr; }

## 3.头文件：

```#ifndef DUL_LINK_LIST_H_

typedef struct Dul_node
{
int data;
struct Dul_node *prior;
struct Dul_node * next;
} dul_node;

void InitList(dul_node **h);
void DestroyList(dul_node **h);
void CreateList(dul_node **h);

int LenList(dul_node *h);
void ShowList(dul_node *h);

int GetIndex(dul_node *h, int k);
void InsertElem(dul_node *h, int k, int x);
void DeleteElem(dul_node *h, int k);

## 4.函数定义文件

```#include<iostream>
using std::cin;
using std::cout;
using std::endl;

/*初始化*/
void InitList(dul_node **h) {

(*h) = new dul_node;
(*h)->next = nullptr;//直接后继为空
(*h)->prior = nullptr;//直接前驱也为空
}

/*销毁链表*/
void DestroyList(dul_node **h) {
dul_node *p;
while ((*h) != nullptr) {
p = (*h)->next;
delete (*h);
(*h) = p;
}
}

void CreateList(dul_node **h) {

/*初始化*/
(*h) = new dul_node;
(*h)->next = nullptr;
(*h)->prior = nullptr;

/**/
dul_node *p = (*h);

int x = 0;
cout << "\n请依次输入数据以创建链表，以 q 为停止信号！" << endl;
while (cin >> x) {
/*由于是尾插法，所以首先后继是空，但是前驱先不指定值*/
dul_node *s = new dul_node;
s->data = x;
s->next = nullptr;

while (p->next != nullptr)
p = p->next;

p->next = s;
s->prior = p;//在这里讲新元素的前驱 赋值为原来的最后一个元素的地址
}
cin.clear();
while (cin.get() != '\n')
continue;
}

int LenList(dul_node *h) {
dul_node *p = h;
int j = 0;

while (p->next != nullptr) {
p = p->next;
j++;
}
return j;
}

void ShowList(dul_node *h) {
dul_node *p = h;
int j = 0;
while (p->next != nullptr) {
p = p->next;
j++;
cout << "List[" << j << "]=: " << p->data << "     ";
}
if (j == 0)
cout << endl << "\n这是一个空链表" << endl;
cout << endl;
}

int GetIndex(dul_node *h, int k) {
dul_node *p = h;
if (h->next == nullptr) {
cout << "\n链表为空，不执行查找操作！\n" << endl;
return NAN;
}

int j = 0;
while (p->next != nullptr && j < k) {
p = p->next;
j++;
}

if (j != k || k<1) {
cout << "输入的位置 " << k << " 不合理！\n" << endl;
return NAN;
}
return p->data;
}

void InsertElem(dul_node *h, int k, int x) {
dul_node *p = h;
int j = 0;

while (p->next != nullptr && j < k - 1) {
p = p->next;
j++;
}
if (j != k - 1) {
cout << "想要插入的位置_" << k << "_不合理！" << endl;
return;
}

dul_node *s = new dul_node;
s->data = x;

if (p->next != nullptr)
p->next->prior = s;//如果p还有后继元素，则其前驱改为s
s->next = p->next; //s的后继改为p的后继

//将s插入p后
p->next = s;// p的后继改为s
s->prior = p;//s的前驱改为p

}

void DeleteElem(dul_node *h, int k) {
if (h->next == nullptr) {
cout << "\n链表为空，不执行删除操作！" << endl;
return;
}

dul_node *p = h;
int j = 0;
while (p->next != nullptr && j < k - 1) {
p = p->next;
j++;
}
if (j != k - 1 || p->next == nullptr) {
cout << "想要删除的位置_" << k << "_不合理！不执行删除操作 " << endl;
return;
}

dul_node *s = p->next;//s指向待删除元素
p->next = s->next;//p的后继改为s的后继

if(s->next!=nullptr)
s->next->prior = p;//s的后继的前驱改为p

delete  s;
}```

## 5.主函数文件

```#include<iostream>

using std::cin;
using std::cout;
using std::endl;

int main() {

dul_node *list1, *list2;
InitList(&list1);
cout << "\nlength of list1 is: " << LenList(list1) << endl;

/*用Insert方法依次在被初始化过的链表list1尾部插入新元素，以此创建链表*/

cout << "\nPlease input the int number:\n";
int x1;
for (int k = 1; k < 9; k++) {
cin >> x1;
InsertElem(list1, k, x1);
}
cin.get();
cout << "\nthe length of list1: " << LenList(list1) << endl;
ShowList(list1);

/*也可以用我写的那个Create程序创建新链表，但是要注意一点：
我那个程序是针对没有被初始化过的链表指针，因为那个函数里面有初始化语句，
所以如果你输入一个已经被初始化过的链表，哪怕是空链表，的头指针，也会有个问题存在，
那就是头指针的值被更新为 程序中使用 new创建的那个内存块的地址，但是你又没有释放原来头指针指向的内存块的地址，
这样不符合程序规定，容易造成溢出， 所以应该使用没有被初始化过的链表指针，比如此程序中的list2*/
CreateList(&list2);
cout << "\nThe length of list2: " << LenList(list2) << endl;
ShowList(list2);

/*删除函数测试*/
cout << "\nnow test the Delete funtion, every we turn delete the 1st element of the list:\n";
for (int i = LenList(list2); i >0; i--) {
DeleteElem(list2, 1);
ShowList(list2);
}

cin.get();
DestroyList(&list1);
DestroyList(&list2);
return 0;
}```

89 篇文章42 人订阅

0 条评论