双链表的创建、插入、删除?
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef int ElemType;
typedef struct DNode{
ElemType data;
struct DNode* prior;
struct DNode* next;
}DNode,*DLinkNode;
void createDLinkNode(DLinkNode &L){
DLinkNode s;
L = (DLinkNode)malloc(sizeof(DNode)); //头节点 尾插法
L->prior = NULL;
DLinkNode r = L; //尾节点
int e;
cin>>e;
while(e!=-1){
s = (DLinkNode)malloc(sizeof(DNode));
s->data = e;
r->next = s;
s->prior = r; ///此时r是倒数第二个节点
r = s; //r放到最后一个节点
cin>>e;
}
r->next = NULL;
return ;
}
void printDLinkNode(DNode* L){
L = L->next;
//T通过next 输出
cout<<"通过next输出:\n";
while(L){
cout<<L->data<<" ";
if(L->next == NULL) break; //不加这一条链表直接走s 也就没有什么L->prior了，无法在逆向输出
L = L -> next;
}
cout<<endl;
//cout<<L->data<<endl;
cout<<"通过prior输出:\n";
while(L->prior){
cout<<L->data<<" ";
L = L -> prior;
}
cout<<endl;
}
//双链表的按值查找和按序号查找和单链表一样
DNode* getNoDNode(DLinkNode L,int i){
DLinkNode p = L; //该序号对应的节点
L = L->next;
int j = 1;
while(p&&j<i){
p = p->next;
j++;
}
return p;
}
//双链表的插入删除应为引入了前指针域prior，相比单链表shaowei复杂一些
void insertDLinkNode(DLinkNode &L,int i){ //
DLinkNode p;
p = getNoDNode(L,i);
//cout<<p->data<<endl;
DLinkNode s = (DNode*)malloc(sizeof(DNode));
s->data = 99; //插入结点的数据设为99
s->next = p->next; //s的下一个节点，是原p的下一个结点
//cout<<"hhhhhha\n";
p->next->prior = s; //原p的下一个结点的前一个结点变为s
s->prior = p; //s的前一个结点是p
//cout<<"hhhhhha\n";
p->next = s; //p的下一个结点变为s //插入成功
//return ;
}
void deleteDLinkNode(DLinkNode &L,int i){ //删除第i个结点
DLinkNode p = getNoDNode(L,i-1);
DLinkNode q = p->next; //q是p的下一个结点
p->next = q->next; //p的下一个结点变为q的下一个结点
q->next->prior = p; //q的下一个结点的prior指向p; //应该删除成功了
free(q); //释放q结点
}
int main()
{
DLinkNode L;
createDLinkNode(L);
printDLinkNode(L);
insertDLinkNode(L,3); //在第三个结点插入
//cout<<"hhhhhha\n";
printDLinkNode(L); //打印一下看结果
deleteDLinkNode(L,5); //删除第五个结点
printDLinkNode(L); //打印一下看结果
free(L);
return 0;
} 
