[数据结构与算法]双链表实验

双链表实验

题目

建立数据结构，实现双链表，实现双链表的插入和删除操作。

头文件

#pragma once
struct Node {
	Node* prior, * next;
	int data;
	Node() {
		data = 0;
		prior = nullptr;
		next = nullptr;
	}
	Node(int x) {
		data = x;
		prior = nullptr;
		next = nullptr;
	}
};
class DLinkList
{
public:
	DLinkList(int a[],int n);
	~DLinkList();
	void insert(int i, int x);
	int del(int i);
	void printList();
private:
	Node* head;
};

源文件

#include "DLinkList.h"
#include<iostream>
using namespace std;

DLinkList::DLinkList(int a[], int n) {
	head = new Node();//申请头结点
	Node *h = head;//工作指针
	for (int i = 0; i < n; i++) {
		Node* s = new Node();//申请结点空间
		s->data = a[i];
		s->prior = h;//连接
		h->next = s;
		s->next = nullptr;
		h = s;//工作指针后移
	}
}

DLinkList::~DLinkList() {
	Node* p = head;
	//释放每一个结点
	while (head != nullptr) {
		head = head->next;//head指向被释放的下一个结点
		delete p;
		p = head;//工作指针后移
	}
}

void DLinkList::insert(int i,int x){
	Node *s = new Node(x);
	Node* p = head;
	//找到第i-1个结点
	int count = 0;
	while (p != nullptr && count < i - 1) {
		p = p->next;
		count++;
	}
	//插入结点
	s->prior = p;
	s->next = p->next;
	p->next->prior = s;
	p->next = s;
}

int DLinkList::del(int i) {
	Node* p = head;
	int count = 0;
	//找到第i-1个结点
	while (p != nullptr && count < i) {
		p = p->next;
		count++;
	}
	int tmp = p->data;//暂存将要删除的值
	//删除结点
	p->prior->next = p->next;
	p->next->prior = p->prior;
	return tmp;//返回删除结点的值
}

void DLinkList::printList() {
	Node *p = head->next;
	while (p != nullptr) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

测试函数

#include<iostream>
using namespace std;
#include"DLinkList.h"
int main() {
    int r[5] = { 1,2,3,4,5 };
    DLinkList L(r, 5);//构造出线性表
    cout << "执行插入操作前数据为:" << endl;
    L.printList();
    try {
        L.insert(2, 3);//尝试在第二个位置插入值为3的元素
    }
    catch (char* s) {
        cout << s << endl;
    }
    cout << "执行插入操作后数据为：" << endl;
    L.printList();
    cout << "执行删除操作前数据为：" << endl;
    L.printList();
    try {
        L.del(1);//尝试删除第一个元素
    }
    catch (char* s) {
        cout << s << endl;
    }
    cout << "执行删除操作后数据为：" << endl;
    L.printList();
}

测试结果