# C++ 双向链表的基本操作

## 实验三：双向链表的基本操作

• 利用尾插法建立一个双向链表。
• 遍历双向链表。
• 实现双向链表中删除一个指定元素。
• 在非递减有序双向链表中实现插入元素e仍有序算法。
• 判断双向链表中元素是否对称若对称返回1否则返回0。
• 设元素为正整型,实现算法把所有奇数排列在偶数之前。
• 在主函数中设计一个简单的菜单调试上述算法。

## 源码

``````#include <stdio.h>
#include <stdlib.h>
#define ERROR       -1
#define OK      1
#define OVERFLOW    -2
typedef int ElemType;
typedef int Status;
typedef struct DuLNode {
ElemType    data;
struct DuLNode  *prior;
struct DuLNode  *next;
/* 创建双链表 */
{
int n, i, c;
printf( "请输入要创建双链表的长度n=" );
scanf( "%d", &n );
dl = L;
printf( "请依次输入数据：" );
for ( i = 0; i < n; i++ )
{
if ( !(p = (DuLinkList) malloc( sizeof(DuLNode) ) ) )
return(OVERFLOW);
scanf( "%d", &c );
p->data     = c;
dl->next    = p;
p->prior    = dl;
p->next     = L;
L->prior    = p;
dl      = p;
}
return(OK);
}

/* 遍历双链表 */
{
dl = L->next;
while ( dl->next != L )
{
printf( "%d ", dl->data );
dl = dl->next;
}
printf( "%d\n", dl->data );
return(OK);
}

{
dl = L->next;
while ( dl != L )
{
if ( dl->data == i )
return(dl);
}
return(NULL);
}

/* 双链表的删除,实现双向链表中删除一个指定元素 */
{
if ( !(p = GetElemP_DuL( L, i ) ) )
return(ERROR);
p->prior->next =
p->next;
p->next->prior =
p->prior;
free( p );
return(OK);
}

{
int     n = 0;
dl = L->next;
while ( dl != L )
{
n++;
dl = dl->next;
}
return(n);
}

/* 实现双链表的指定位置的删除 */
{
if ( i > GetLengthOfDL( L ) || i < 1 )
{
printf( "删除下标非法!\n" );
return(ERROR);
}
int     n = 1;
dl = L->next;
while ( n < i )
{
n++;
dl = dl->next;
}
/* p = dl->prior; */
dl->prior->next =
dl->next;
dl->next->prior =
dl->prior;
free( dl );
return(OK);
}

/* 排序 */
{
int n = GetLengthOfDL( L );
/* printf("%d",n); */
int     t;
for ( int i = 1; i < n; i++ )
{
p = L->next;
for ( int j = 0; j < n - i; j++ )
{
if ( p->data >
p->next->data )
{
t   = p->data;
p->data =
p->next->data;
p->next->data = t;
}
p = p->next;
}
}
return(OK);
}

/* 插入 */
Status InsertDuL( DuLinkList L, int n )
{
/* printf("dd"); */
if ( !(dl = (DuLinkList) malloc( sizeof(DuLNode) ) ) )
return(OVERFLOW);
p       = L->next;
dl->data    = n;
while ( p->data < n )
p = p->next;
printf( "%d", p->data );
p->prior->next  = dl;
dl->prior   = p->prior;
p->prior    = dl;
dl->next    = p;
return(OK);
}

/* 判断双链表是否对称 */
{
p   = L->next;
q   = L->prior;
int n = GetLengthOfDL( L );
if ( n % 2 )
{
while ( p->data == q->data && p != q )
{
p = p->next; q = q->prior;
}
if ( q == p )
return(1);
else
return(0);
}else{
while ( p->data == q->data && p->next != q )
{
p = p->next; q = q->prior;
}
if ( p->data == q->data )
return(1);
else
return(0);
}
}

/* 实现算法把所有奇数排列在偶数之前 */
{
int     i, n = GetLengthOfDL( L );
i   = 0;
p   = L->next;
dl  = L->prior;
while ( i < n )
{
if ( (p->data) % 2 != 0 )
{
i++;
p = p->next;
}else  {
p1      = p->next;
p->next->prior  =
p->prior;
p->prior->next =
p->next;
p->next     = L;
p->prior    = dl;
dl->next    = p;
L->prior    = p;
dl      = p;
p       = p1;
i++;
}
}
return(OK);
}

void print()
{
printf( "欢迎测试双链表,菜单如下：\n" );
printf( "1.运用尾差法创建双链表\n" );
printf( "2.遍历双向链表\n" );
printf( "3.实现双链表删除一个指定元素\n" );
printf( "4.在非递减有序双向链表中实现插入元素e仍有序\n" );
printf( "5.判断双向链表中元素是否对称若对称返回1否则返回0\n" );
printf( "6.实现算法把所有奇数排列在偶数之前\n" );
printf( "0.EXIT\n" );
printf( "请选择操作序号：" );
}

int main()
{
Status      e, ch, n;
bool        flag = true;
L       = (DuLinkList) malloc( sizeof(DuLNode) );
L->prior    = NULL;
L->next     = NULL;
print();
while ( scanf( "%d", &ch ) != EOF )
{
switch ( ch )
{
case 0:
flag = false;
break;
case 1:
if ( InsertDuLinkList_real( L ) )
printf( "创建成功！\n" );
else
printf( "创建失败!\n" );
break;
case 2:
if ( pDuLinkList( L ) )
printf( "遍历成功!\n" );
else
printf( "遍历失败!\n" );
break;
case 3:
printf( "请选择删除方式：1.删除指定元素  2.删除制定下标\n" );
printf( "请输入选择序号e=" );
scanf( "%d", &e );
switch ( e )
{
case 1:
printf( "请输入指定元素n=" );

scanf( "%d", &n );

if ( LinkDelete_Dul( L, n ) )

printf( "指定元素已删除!\n" );
else

printf( "指定元素删除失败!\n" );
break;
case 2:
printf( "请输入指定下标n=" );
scanf( "%d", &n );
if ( LinkDelete_Dd( L, n ) )

printf( "指定下标删除成功!\n" );
else

printf( "指定下标删除失败!\n" );
}
break;
case 4:
printf( "按非递减排序双链表!\n" );
printf( "请输入插入的元素n=" );
scanf( "%d", &n );
if ( InsertDuL( L, n ) )
printf( "插入成功!\n" );
else
printf( "插入失败!\n" );
break;
case 5:
if ( isReturnDuL( L ) )
printf( "1\n" );
else
printf( "0\n" );
break;
case 6:
if ( inLawSort( L ) )
{
printf( "奇前偶后排序成功!\n" );
}else
printf( "奇前偶后排序失败!\n" );
break;
default:
printf( "输入错误！\n" );
}
if ( !flag )
break;
}
return(0);
}
``````