2-4 线性表之双链表

2-4 线性表之双链表

双向链表除了相当于在单链表的基础上,每个结点多了一个指针域prior用于存储其直接前驱的地址。同时保留有next,用于存储其直接后继的地址。

所以对于带头结点的双链表,其实很多操作都和 带头结点的单链表是一样的,因为你完全可以忽视掉它有个 prior指针,这样就可以当做单链表来使用。所以,这里只写一下定义和初始化的过程,其他的操作基本可以参照带头结点的单链表。

另外因为有了prior指针,所以在插入和删除新元素时,应该考虑到这一点,

所以如果在队尾插入元素时,就不用改动后面指针的prior指针,因为后面为空,如果在其他位置插入,就需要改动;

删除操作也是一样。

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_
#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_

4.函数定义文件

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

5.主函数文件

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

若有错误,请不吝指出,谢谢

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券