2-4 线性表之双链表

#ifndef DUL_LINK_LIST_H_
#define 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);

#endif // !DUL_LINKLIST_H_

#include<iostream>
#include"dul_link_list.h"
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;
}

#include<iostream>
#include"dul_link_list.h"

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;
}