• 主要为大家详细介绍了C++实现双向链表，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
• C++实现双链表#include #include using namespace std; typedef int DataType; struct ListNode { DataType _data; ListNode *_next; ListNode *_prev; ListNode(const DataType x)
C++实现双链表

#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
struct ListNode
{
DataType _data;
ListNode *_next;
ListNode *_prev;
ListNode(const DataType x)
:_data(x), _next(NULL), _prev(NULL)
{}
};
class List
{
typedef ListNode Node;
public:
List()
{
}
void PushBack(DataType x)
{
{
_head = _tail = new Node(x);
}
else
{
Node* tmp = new Node(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = _tail->_next;
}
}
void PushFront(DataType x)
{
{
_head = _tail = new Node(x);
}
else
{
Node *tmp = new Node(x);
}
}
void Display()
{
return;
else
{
while (cur != NULL)
{
cout << cur->_data << " ";
cur = cur->_next;
}
cout << endl;
}
}
void PopBack()
{
{
delete _tail;
}
else
{
_tail = _tail->_prev;
delete _tail->_next;
}
}
void PopFront()
{
{
delete _tail;
}
else
{
}
}
void Destroy()
{
{
delete _tail;
}
else
{
{
}
delete _tail;
}
}
Node* Find(DataType x)
{
return NULL;
else
{
while (cur != NULL)
{
if (cur->_data == x)
{
break;
}
cur = cur->_next;
}
return cur;
}
}
void Insert(Node* pos, DataType x)
{
assert(pos);
{
PushFront(x);
}
else
{
Node *tmp = new Node(x);
tmp->_next = pos;
pos->_prev->_next = tmp;
tmp->_prev = pos->_prev;
pos->_prev = tmp;
}
}
void Erase(Node* pos)
{
assert(pos);
{
delete pos;
}
else
{
pos->_next->_prev = pos->_prev;
pos->_prev->_next = pos->_next;
delete pos;
pos = NULL;
}
}
{
{
return;
}
else
{
ListNode* tmp = cur;
while (cur)
{
tmp = cur;
cur = cur->_next;
tmp->_prev = cur;
}
}
}
private:
Node *_tail;
};
void test()
{
List l1;
l1.PushBack(0);
l1.PushBack(1);
l1.PushBack(2);
l1.PushBack(3);
/*l1.PushFront(2);
l1.PushFront(1);
l1.PushFront(0);*/
/*l1.PopBack();
l1.PopBack();
l1.PopBack();*/
//l1.PopFront();
//l1.PopFront();
//l1.PopFront();
//l1.Destroy();
//l1.Find(1);
//l1.Insert(l1.Find(5), 9);
//l1.Insert(l1.Find(1), 6);
//l1.Insert(l1.Find(3), 5);
//l1.Insert(l1.Find(0), 9);
//l1.Erase(l1.Find(1));
//l1.Erase(l1.Find(10));
l1.Reverse();
l1.Display();
}
int main()
{
test();
system("pause");
return 0;
}
展开全文
• * 在C++实现双链表中，双向链表的声明和实现都在头文件中。 * 这与&quot;将声明和实现分离，头文件中尽量只包含声明&quot;是相矛盾的！ 那么为什么要这么做呢？ * 这是因为，在实现双向链表的实现，采用了...
DoublyLinkedList.h

#pragma once

#include <iostream>
using namespace std;

/**
* 在C++实现的双链表中，双向链表的声明和实现都在头文件中。
* 这与"将声明和实现分离，头文件中尽量只包含声明"是相矛盾的！ 那么为什么要这么做呢？
* 这是因为，在实现双向链表的实现，采用了模板；而C++编译器不能支持对模板的分离式编译！
*/

template<class T>
struct Node
{
public:
T value;
Node *prev;
Node *next;

Node() {}
Node(T t, Node *prev, Node *next)
{
this->value = t;
this->prev = prev;
this->next = next;
}
};

template<class T>
{
public:

int Size();
int IsEmpty();

T Get(int index);
T GetFirst();
T GetLast();

int Insert(int index, T t);
int InsertFirst(T t);
int InsertLast(T t);

int Del(int index);
int DeleteFirst();
int DeleteLast();

private:
int count;
Node<T>* GetNode(int index);
};

// 构造函数
template<class T>
{
// 创建表头。这里表头不存储数据。

//count = 0;
}

//析构函数
template<class T>
{
Node *ptmp;
{
ptmp = pnode;
pnode = pnode->next;
delete ptmp;
}

}

template<class T>
{
return count;
}

template<class T>
{
return count == 0;
}

template<class T>
{
if (index < 0 || index >= count)
{
cout << "GetNode failed! Index is out of range." << endl;
return NULL;
}

/// count = 6
///   ↓—————————————————————————————————————————————————↑
///  □□□  <-> □□□ <-> □□□ <-> □□□ <-> □□□ <-> □□□ <-> □□□
///  ↓—————————————————————————————————————————————————↑
///  head      0       1       2       3       4       5

// 正向查找
if (index < count / 2)
{
int i = 0;
while ((i++) < index)
{
pnode = pnode->next;
}
return pnode;
}

int i = count - 1;
while ((i--) > index)
{
pnode = pnode->prev;
}
return pnode;
}

template<class T>
{
return GetNode(index)->value;
}

template<class T>
{
return GetNode(0)->value;
}

template<class T>
{
return GetNode(count - 1)->value;
}

template<class T>
{
if (index == 0)
return InsertFirst(t);

Node<T> *pindex = GetNode(index);

Node<T> *pnode = new Node<T>(t, pindex->prev, pindex);
pindex->prev->next = pnode;
pindex->prev = pnode;

count++;

return 0;
}

template<class T>
{

count++;

return 0;
}

template<class T>
{

count++;

return 0;
}

template<class T>
{
Node<T> *pnode = GetNode(index);

pnode->next->prev = pnode->prev;
pnode->prev->next = pnode->next;

delete pnode;
count--;

return 0;
}

template<class T>
{
return Del(0);
}

template<class T>
{
return Del(count - 1);
}

#include <iostream>
#include <sstream>
using namespace std;

void int_test()
{
int iarr[4] = { 10, 20, 30, 40 };

cout << "\n----int_test----" << endl;

cout << "IsEmpty:" << link->IsEmpty() << endl;
cout << "Size:" << link->Size() << endl;

for (int i = 0; i < size; i++)
{
cout << "第" << i << "个元素为：" << link->Get(i) << endl;
}
}

void string_test()
{
string sarr[4] = { "one", "two", "three", "four" };

cout << "\n----string_test----" << endl;

cout << "IsEmpty:" << link->IsEmpty() << endl;
cout << "Size:" << link->Size() << endl;

for (int i = 0; i < size; i++)
{
cout << "第" << i << "个元素为：" << link->Get(i) << endl;
}
}

struct stu
{
int id;
char name[20];
};

static stu arr_stu[] =
{
{ 10,"andy" },
{ 20,"baby" },
{ 30,"city" },
{ 40,"dog" },
};

#define ARR_STU_SIZE ((sizeof(arrstu))/(sizeof(arrstu[0])))

void object_test()
{
cout << "\n----object_test----" << endl;

cout << "IsEmpty:" << link->IsEmpty() << endl;
cout << "Size:" << link->Size() << endl;

for (int i = 0; i < size; i++)
{
cout << "第" << i << "个元素为：" << link->Get(i).id << " " << link->Get(i).name << endl;
}
}

int main()
{
int_test();
string_test();
object_test();
cout << endl;
system("pause");
return 0;
}


测试结果

参考：http://wangkuiwu.github.io/2013/01/01/dlink/
展开全文
• 是这样的，因为学生的作业嘛，也不是很难，只要实现基本的JDBC操作数据库就可以，但是每次写的时候都要去找以前的笔记，让我有点烦，所以我就索性专门写一篇博客来方便自己也方便他们写一个Java原生JDBC操作数据库的...
#include “pch.h”
#include “framework.h”
#include “one.h”
#include “oneDlg.h”
#include “afxdialogex.h”
#include
#include
#include
#include
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#endif
{
public:
// 对话框数据
#ifdef AFX_DESIGN_TIME
enum { IDD = IDD_ABOUTBOX };
#endif
protected:
virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

// 实现
protected:
DECLARE_MESSAGE_MAP()
};
{
}
{
CDialogEx::DoDataExchange(pDX);
}
END_MESSAGE_MAP()
// ConeDlg 对话框

ConeDlg::ConeDlg(CWnd* pParent /=nullptr/)
CDialogEx(IDD_ONE_DIALOG, pParent)
, lenn(0)
, m_value(0)
, n_value(0)
{
}

void ConeDlg::DoDataExchange(CDataExchange* pDX)
{
CDialogEx::DoDataExchange(pDX);
DDX_Text(pDX, IDC_EDIT1, lenn);
DDX_Text(pDX, IDC_EDIT2, m_value);
DDX_Text(pDX, IDC_EDIT3, n_value);
}
BEGIN_MESSAGE_MAP(ConeDlg, CDialogEx)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON1, &ConeDlg::OnBnClickedButton1)
ON_BN_CLICKED(IDC_BUTTON2, &ConeDlg::OnBnClickedButton2)
ON_BN_CLICKED(IDC_BUTTON3, &ConeDlg::OnBnClickedButton3)
ON_BN_CLICKED(IDC_BUTTON4, &ConeDlg::OnBnClickedButton4)
ON_BN_CLICKED(IDC_BUTTON5, &ConeDlg::OnBnClickedButton5)
END_MESSAGE_MAP()
// ConeDlg 消息处理程序
BOOL ConeDlg::OnInitDialog()
{
CDialogEx::OnInitDialog();
// 将“关于...”菜单项添加到系统菜单中。

{
BOOL bNameValid;
ASSERT(bNameValid);
{
}
}

// 设置此对话框的图标。  当应用程序主窗口不是对话框时，框架将自动
//  执行此操作
SetIcon(m_hIcon, TRUE);			// 设置大图标
SetIcon(m_hIcon, FALSE);		// 设置小图标

// TODO: 在此添加额外的初始化代码
GetDlgItem(IDC_EDIT1)->SetWindowText(jesus);
return TRUE;  // 除非将焦点设置到控件，否则返回 TRUE

}
void ConeDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
}
else
{
CDialogEx::OnSysCommand(nID, lParam);
}
}
// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。  对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。
void ConeDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // 用于绘制的设备上下文
	SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

// 使图标在工作区矩形中居中
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;

// 绘制图标
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialogEx::OnPaint();
}

}
//当用户拖动最小化窗口时系统调用此函数取得光标
//显示。
HCURSOR ConeDlg::OnQueryDragIcon()
{
return static_cast(m_hIcon);
}
void ConeDlg::OnBnClickedButton1()
{
// TODO: 在此添加控件通知处理程序代码
UpdateData(1);
int len = lenn;
srand((unsigned)time(NULL));
string buff = “”;
for (int i= 1; i <= len; i++) {
cur->data= (rand() % (999 - 100)) + 100;
JList * newnode = new JList();
cur->next = newnode;
buff += to_string(cur->data);
if (i != len) {
buff += “→”;
cur = cur->next;
}
else {
cur->next = nullptr;
}
}
CString jesus(buff.c_str());
GetDlgItem(IDCANCEL)->SetWindowText(jesus);
UpdateData(0);
}
void ConeDlg::OnBnClickedButton2()
{
// TODO: 在此添加控件通知处理程序代码
UpdateData(1);
string buff1 = “”, buff2 = “”;
while(cur!=nullptr){
if (Mnode==nullptr&&cur->data == m_value) {
Mnode = cur;
continue;
}
if (Nnode == nullptr && cur->data == n_value) {
Nnode = cur;
cur->next = Mnode;
break;
}
cur = cur->next;
}
while (listtail2->next != nullptr) {
listtail2 = listtail2->next;
}
listtail2->next = Mnode;
while (cur != Nnode) {
buff1 += to_string(cur->data);
if (cur->next == Mnode) {
buff1 += “↑”;
}
else {
buff1 += “→”;
}
cur = cur->next;
}
buff1 += to_string(cur->data);
while (cur != Mnode) {
buff2 += to_string(cur->data);
if (cur->next !=Mnode ) {
buff2 += “→”;
}
else {
buff2 += “↑”;
}
cur = cur->next;
}
string buff3="", buff4="";
while (cur != Nnode) {
if (cur->next == Mnode) {
buff3 += “↑”;
}
else {
buff3 += "         “;
}
cur = cur->next;
}
while (cur != Mnode) {
if (cur->next != Mnode) {
buff4 += "         “;
}
else {
buff4 += “↑”;
}
cur = cur->next;
}
GetDlgItem(IDCANCEL)->SetWindowText(jesus);
UpdateData(0);
}
void ConeDlg::OnBnClickedButton3()
{
// TODO: 在此添加控件通知处理程序代码
JList* slow = listhead->next; // 初始时，慢指针从头节点开始走1步
int i = 0;
bool cir = 0;
JList* fast = slow->next; // 初始时，快指针从头节点开始走2步
while (fast != NULL && slow != NULL) { // 当单链表没有环时，循环到链表尾结束
i+=2;
if (fast == slow) {
MessageBox(TEXT(“检测出有环！”));
cir = 1;
break;
}
slow = slow->next; // 慢指针每次走一步
cur = cur->next;
fast = fast->next;
if (fast != nullptr)
fast = fast->next;
}
if (!cir) {
MessageBox(TEXT(“检测出无环！”));
}
GetDlgItem(IDC_EDIT4)->SetWindowText(jesus);
GetDlgItem(IDC_EDIT5)->SetWindowText(jesus2);
}
void ConeDlg::OnBnClickedButton4()
{
// TODO: 在此添加控件通知处理程序代码
listtail2->next = nullptr;
string buff = “”;
while (cur != nullptr) {
buff += to_string(cur->data);
if (cur->next != nullptr) {
buff += “→”;
}
cur = cur->next;
}
CString jesus2(buff.c_str());
GetDlgItem(IDCANCEL)->SetWindowText(jesus2);
int fu = 0;
while (cur != nullptr) {
cur = cur->next;
fu++;
}
for (int i = 1; i <= fu / 2; i++) {
cur = cur->next;
}
MessageBox(TEXT(“找到了中间节点！内存地址为：”) + jesus+TEXT(“值为：”)+jesus22);
}
void ConeDlg::OnBnClickedButton5()
{
// TODO: 在此添加控件通知处理程序代码
bool intersect = 0;
// * * * * * * * * * * * E
// S * * * * *
//把E和S连起来，然后判断是否有环即可。
JList* slow = listhead->next; // 初始时，慢指针从头节点开始走1步
JList* fast = slow->next; // 初始时，快指针从头节点开始走2步
while (fast != NULL && slow != NULL) { // 当单链表没有环时，循环到链表尾结束
if (fast == slow) {
MessageBox(TEXT(“检测出有相交！”));
intersect = 1;
break;
}
slow = slow->next; // 慢指针每次走一步
cur = cur->next;
fast = fast->next;
if (fast != nullptr)
fast = fast->next;
}
if (!intersect) {
MessageBox(TEXT(“检测出无相交！”));
}
}


展开全文
• 主要介绍了C++ 实现双向链表的实例的相关资料,需要的朋友可以参考下
• 如何实现一个双向链表呢，这就要求每个结点里，有两个指针，一个指向前一个结点，一个指向下一个结点。 实现功能包括尾插，尾删，头插，头删，逆序，查找，插入，打印等等 话不多说直接上代码，里面解释的很详细 ...
如何实现一个双向链表呢，这就要求每个结点里，有两个指针，一个指向前一个结点，一个指向下一个结点。
实现功能包括尾插，尾删，头插，头删，逆序，查找，插入，打印等等
话不多说直接上代码，里面解释的很详细
#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
struct ListNode
{
ListNode*_next;
ListNode*_prev;
DataType _data;
ListNode(DataType x)//结点构造函数
:_data(x)
, _next(NULL)
, _prev(NULL)
{}
};
class List
{
typedef  ListNode Node;
public:
List()
, _tail(NULL)
{
}
~List()
{
while (cur)
{
Node*del = cur;
cur = cur->_next;
delete del;
}
}
void PushBack(DataType x)//尾插
{//1.空  2.不为空
if (_tail == NULL)
{
_head = _tail = new Node(x);//记得补充结点构造函数

}
else
{
Node*tmp = new Node(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = tmp;

}

}
void PopBack()尾删
{
//1.没有结点 2.一个结点  3.多个节点

{
return;
}
{
}
/*else
{
_tail->_prev->_next=NULL;
delete _tail; 会出错tail找不到3
}*/
else
{
Node*prev = _tail->_prev;
prev->_next = NULL;//先把前一个节点_next制成空，
delete _tail;//销毁最后一个结点
_tail = prev;//使_tail指向前一个结点
}
}
void PushFront(DataType x)//头插
{
//1.有结点 2.无结点
{
_head = _tail = new Node(x);
}
else
{
Node*tmp = new Node(x);

}
}
void PopFront()//头删
{
{
return;
}
{
}
else
{
}
}
Node*Find(DataType x)//查找某一值为x的结点
{
while (cur)
{
if (cur->_data == x)
{
return cur;
}
cur = cur->_next;
}
return NULL;

}
void Insert(Node*pos, DataType x)//向某一位置插入一个元素
{
assert(pos);
{
PushFront(x);
}
/*else
{
Node*prev = pos->_prev;
Node* tmp = new Node(x);
prev->_next = tmp;
tmp->_prev = prev;
tmp->_next = pos;
pos->_prev = tmp;

}*/
else{
Node* tmp = new Node(x);
pos->_prev->_next = tmp;
tmp->_prev = pos->_prev;
tmp->_next = pos;
pos->_prev = tmp;
}

}
void Erase(Node*pos)//删除某一位置的元素
{

assert(pos);
{
PopFront();
}
else if (pos == _tail)//尾删
{
PopBack();
}
else//中间删
{
Node* prev = pos->_prev;
Node*next = pos->_next;
prev->_next = next;
next->_prev = prev;
delete pos;
}
}
/*void Reverse()//逆序
{
Node* end = _tail;
while ((begin!=end)&&(begin->_prev !=end))
{
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
}

}*/
void Reverse()//逆序
{
while (cur)
{
swap(cur->_next, cur->_prev);
cur = cur->_prev;
}
}
void Print()//打印
{
while (cur)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
private:
Node* _tail;

};
void TestList()
{
List s1;
s1.PushBack(1);
s1.PushBack(2);
s1.PushBack(3);
s1.PushBack(4);
s1.Print();
s1.PopBack();
s1.PopBack();
s1.PopBack();
s1.PopBack();
s1.PopBack();
s1.Print();
s1.PushFront(1);
s1.PushFront(2);
s1.PushFront(3);
s1.PushFront(4);
s1.Print();
s1.PopFront();
s1.PopFront();
s1.PopFront();
s1.PopFront();
s1.PopFront();
s1.Print();
}
void Funtest()
{
List s2;
s2.PushBack(1);
s2.PushBack(2);
s2.PushBack(3);
s2.PushBack(4);
s2.Print();
ListNode* pos = s2.Find(1);
s2.Insert(pos, 0);
pos = s2.Find(3);
s2.Insert(pos, 30);
s2.Print();
s2.Erase(pos);
s2.Print();
pos = s2.Find(0);
s2.Erase(pos);
s2.Print();
pos = s2.Find(4);

s2.Erase(pos);
s2.Print();
s2.Reverse();
s2.Print();

}

int main()
{
//TestList();
Funtest();
system("pause");
return 0;
}运行结果：
Funtest()运行结果

TestList（）运行结果


展开全文
• 为什么要使用双向链表？ 1.单链表的结点都只有一个指向下一结点的指针。 2.单链表的数据元素无法直接访问其前驱元素。 逆序访问单链表是极其耗费时间的。 void Reverse(pList* pplist) { assert(pplist); if...

...

c++ 订阅