建立双向链表 实现对双向链表的插入 删除 *** 作·

#include <iostream>

using namespace std

struct Node

{

int data //节点中的数据 结构体Node的成员变量

Node* next//指向下一节点的指针，习惯用next命名 结构体Node的成员变量

Node( const int&d=int() ) //结构体也可以有构造函数 ,d=T()来指定默认值

:data(d),next(NULL) //用构造函数来初始化成员变量data和指针

{} //所有数据类型，默认初始化都为0，这里data默认初始化为0

}

class Chain //封装链表

{

private: //数据成员通常都是private的

Node* head//首先，我们要一个Node型的指针来保存链表的第一个节点；

int length//再用一个整型变量来记录当前链表内的节点数

public:

Chain()//在构造函数里建立一个空链表，即head指向NULL

:head(NULL),length(0){}//节点数为0

//当我们在类中定义函数时（不是声明），相当于在前面加上一个inline修饰

void delall() //这个函数用来删除链表中的所有节点

{

Node* pdel //定义一个Node型指针用来保存要删除的节点

while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点

{

pdel = head //这里备份head的当前指向节点

head = head->next//把head的指向改变为下一节点

delete pdel //把head的原指向给删除掉

} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候

//head就被赋值为NULL，不满足循环条件，退出循环

length = 0 //把节点数归零

}

~Chain(){ delall()} //在析构函数中调用delall函数，来完成对象销毁时清理工作

//这样一个链表必须具备的功能就实现了。下面我们来实现他的增、删、查、改功能

Node*&getpoint( int position ) //对链表的 *** 作，其实全部通过指针来实现的，

{//那就需要定义一个函数来返回当前节点的指针（引用）

if( position<0 || position>length ) //对节点编号进行合法检查

position = length //如果是非法节点编号，那么就把他修改为最后一个节点编号

if( position==0 )//如果编号为0，那就是第一个节点了，

return head//直接返回head就是指向第一个节点的，注意返回的是head本身

Node* head_bak = head //如果编号合法并且不是第一个节点，就开始遍历链表

for( int i=1i <positioni++ )//为什么不直接用head

{//注意这里修改的是成员变量。你把head改了，以后到哪找链表

//我们都是通过head一个一个的往下找节点的。head被修改了。后果显而易见

head_bak = head_bak->next //通过备份的指针来遍历到指定编号前一个节点

}//i不从0开始，减少运算，提高效率

return head_bak->next //这里如果返回head_bak的话。那就是需要的前一个节点了

}

void insert( const int&data, int position ) //如果不修改参数的话，使用引用做参数的时候，最好加上const

{

Node* pin = new Node(data) //需要调用Node的构造函数

pin->next = getpoint(position) //把指定位置的指针返回给新节点的指针

//也就是说，把新的节点的next指向原来这个位置的节点。

getpoint(position) = pin //getpoint()返回的是引用，我们可以直接修改它

//前面的一个节点的next指向我们新的节点。

length++ //链表的节点数+1

}

int del( const int&data )

{

int position = find(data)

if( position !=-1 ) //-1代表没找到

{

Node* &pnext = getpoint(position) //用getponit()来获得指定节点的指向信息

Node* pbak = pnext //用来备份节点的指向信息

pnext = pnext->next//把next指向改为下下个节点。

delete pbak

length--

}

return position

}

//把<<重载，直接输出链表

friend ostream&operator<<( ostream&os, const Chain&oc )

{

Node* phead = oc.head

os <<"[ "

while( phead !=NULL )//判断是否到尾节点

{

os <<phead->data <<' '

phead = phead->next

}

os <<"] " //这个函数，应该没什么好说的了

return os //如果还是不理解，当成固定模式去背吧

}

}

void show()

{

cout <<"******************************" <<endl

cout <<"2- 向链表内添加节点（数据，节点号）" <<endl

cout <<"3- 删除链表内某一个数据（数据）" <<endl

cout <<"0- 退出" <<endl

cout <<"******************************" <<endl

}

int main()

{

Chain link

int position, data, choice, data_new

while( choice != 0 )

{

show()

cout <<"请选择："

cin >>choice

switch ( choice )

{

case 2 :

cout <<"请输入要插入的数据和插入位置："

cin >>data >>position

link.insert( data,position )

cout <<link <<endl

break

case 3 :

cout <<"请输入要删除的数据："

cin >>data

link.del( data )

cout <<link <<endl

break

default :

break

}

}

}

#include <iostream>

using namespace std

typedef struct node {

int data

node *prior,*next

}*DLinkList

DLinkList p,q,head

void CreateList(int n) { // 创建双向环形链表

head = new node

head->data = 0

p = head

for(int i = 0i <ni++) {

q = new node

cout <<"请输入第" <<i + 1 <<"/" <<n <<"个数 : "

cin >>q->data

p->next = q// 顺向连接新结点

q->next = head // 始终保持环形连接

q->prior = p // 新结点的反向链接

p = q // 为连接新节点做准备

}

head->prior = p// 头结点的prior指向最后的结点，是实现双向环形链表的最后一步

}

void print() { // 顺向输出链表数据

p = head->next

while(p != head) {

cout<<p->data<<' '

p = p->next

}

cout<<endl

}

void DCprint() { // 反向输出链表数据

p = head->prior

while(p != head) {

cout<<p->data<<' '

p = p->prior

}

cout<<endl

}

void deleteheap() { // 释放占用的堆空间

p = head

q = p->next

while(q != head) {

p = q

q = p->next

delete [] p

}

delete [] head

}

int main () {

int n

cout <<"请输入链表结点数 : "

cin >>n

CreateList(n)

print()

DCprint()

deleteheap()

return 0

}

---