数据结构之双向链表（非循环双向链表）
代码中为非循环的双向链表，包括结点的插入、删除等操作
[cpp]
// LinkList_D.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
typedef int DataType;
typedef struct DLNode
{
DataType data;
struct DLNode * prior;
struct DLNode * next;
}DLNode,*DLinkList;
void CreateDList(DLinkList &L,int n);
void PrintDLinkList(DLinkList &L);
int DListInset(DLinkList &L,int i,DataType e);
int DListDelete(DLinkList &L,int i,DataType &e);
int _tmain(int argc, _TCHAR* argv[])
{
// 创建链表
DLinkList L;
CreateDList(L,5); //创建具有5个结点的双向链表
PrintDLinkList(L); // 输出链表
// 测试插入元素
DListInset(L,1,100); //在第一个元素前插入元素
PrintDLinkList(L);
DListInset(L,2,200);
PrintDLinkList(L);
// 测试删除一个元素
printf("node deleted\n");
int e;
DListDelete(L,2,e);
PrintDLinkList(L);
// 测试删除一个元素
printf("node deleted\n");
DListDelete(L,6,e);
PrintDLinkList(L);
getchar();
getchar();
return 0;
}
// 创建长度为n的链表,在头结点之前插入新的结点,非循环链表
void CreateDList(DLinkList &L,int n)
{
L=(DLinkList)malloc(sizeof(DLNode));
L->next=NULL;
L->prior=NULL;
printf("please input n nodes:\n");
DLinkList p=(DLinkList)malloc(sizeof(DLNode)); // 插入第一个结点
scanf("%d",&p->data);
L->next=p;
p->prior=L;
p->next=NULL;
// 插入其他的剩余结点
for(int i=n-1;i>0;--i)
{
DLinkList p=(DLinkList)malloc(sizeof(DLNode));
scanf("%d",&p->data);
p->prior=L;
L->next->prior=p;
p->next=L->next;
L->next=p;
}
}
// 输出结点
void PrintDLinkList(DLinkList &L)
{
DLinkList p=L->next; //指向第一个结点
while (p!=NULL)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
}
// 在第i个元素之前插入元素
int DListInset(DLinkList &L,int i,DataType e)
{
DLinkList p=L->next; //指向第一个元素
int j=1;
while(p&&j<i)
{
p=p->next;
j++;
}
if (!p||j>i)
{
return -1;
}
DLinkList s=(DLinkList)malloc(sizeof(DLNode));
if(!s) return -1;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return 1;
}
// 删除指定位置的元素
int DListDelete(DLinkList &L,int i,DataType &e)
{
DLinkList p=L->next; // 指向第一个元素
int j=1;
while(p&&j<i)
{
p=p->next;
j++;
} // 指向第i个元素
if(!p||j>i) return -1;
if (p->next==NULL) // 删除的元素为最后一个元素
{
p->prior->next=p->next;
}
else
{
// 删除的元素不是最后一个元素
p->prior->next=p->next;
p->next->prior=p->prior;
}
}
// LinkList_D.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
typedef int DataType;
typedef struct DLNode
{
DataType data;
struct DLNode * prior;
struct DLNode * next;
}DLNode,*DLinkList;
void CreateDList(DLinkList &L,int n);
void PrintDLinkList(DLinkList &L);
int DListInset(DLinkList &L,int i,DataType e);
int DListDelete(DLinkList &L,int i,DataType &e);
int _tmain(int argc, _TCHAR* argv[])
{
// 创建链表
DLinkList L;
CreateDList(L,5); //创建具有5个结点的双向链表
PrintDLinkList(L); // 输出链表
// 测试插入元素
DListInset(L,1,100); //在第一个元素前插入元素
PrintDLinkList(L);
DListInset(L,2,200);
