双向链表的基本操作
实验三：双向链表的基本操作
- 利用尾插法建立一个双向链表。
- 遍历双向链表。
- 实现双向链表中删除一个指定元素。
- 在非递减有序双向链表中实现插入元素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;
}DuLNode, * DuLinkList;
/* 创建双链表 */
Status InsertDuLinkList_real( DuLinkList L )
{
int n, i, c;
printf( "请输入要创建双链表的长度n=" );
scanf( "%d", &n );
DuLinkList p, dl;
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);
}
/* 遍历双链表 */
Status pDuLinkList( DuLinkList L )
{
DuLinkList dl;
dl = L->next;
while ( dl->next != L )
{
printf( "%d ", dl->data );
dl = dl->next;
}
printf( "%d\n", dl->data );
return(OK);
}
DuLinkList GetElemP_DuL( DuLinkList L, ElemType i )
{
DuLinkList dl;
dl = L->next;
while ( dl != L )
{
if ( dl->data == i )
return(dl);
}
return(NULL);
}
/* 双链表的删除,实现双向链表中删除一个指定元素 */
Status LinkDelete_Dul( DuLinkList L, int i )
{
DuLinkList p;
if ( !(p = GetElemP_DuL( L, i ) ) )
return(ERROR);
p->prior->next =
p->next;
p->next->prior =
p->prior;
free( p );
return(OK);
}
Status GetLengthOfDL( DuLinkList L )
{
int n = 0;
DuLinkList dl;
dl = L->next;
while ( dl != L )
{
n++;
dl = dl->next;
}
return(n);
}
/* 实现双链表的指定位置的删除 */
Status LinkDelete_Dd( DuLinkList L, int i )
{
if ( i > GetLengthOfDL( L ) || i < 1 )
{
printf( "删除下标非法!\n" );
return(ERROR);
}
DuLinkList dl;
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);
}
/* 排序 */
Status sortDuLinkList( DuLinkList L )
{
int n = GetLengthOfDL( L );
/* printf("%d",n); */
int t;
DuLinkList p;
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"); */
DuLinkList p, dl;
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);
}
/* 判断双链表是否对称 */
Status isReturnDuL( DuLinkList L )
{
DuLinkList p, q;
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);
}
}
/* 实现算法把所有奇数排列在偶数之前 */
Status inLawSort( DuLinkList L )
{
DuLinkList p, dl, p1;
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()
{
DuLinkList L;
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" );
sortDuLinkList( L );
pDuLinkList( L );
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" );
pDuLinkList( L );
}else
printf( "奇前偶后排序失败!\n" );
break;
default:
printf( "输入错误！\n" );
}
if ( !flag )
break;
}
return(0);
}