双向循环列表的插入和删除_双向循环链表插入

插入 ：

DuLNode* InitInsertNode(DuLinkedList &L, ElemType x) {
	DuLNode *p = new DuLNode;
	p->element = x;
	return p;
}
void InsertList(DuLinkedList &L, ElemType x) /* 在 L 的第一个元素前插入新元素 x */ {
	DuLNode *p = InitInsertNode(L, x); //犯过的错误，调用L不是&L
	p->prior = L;
	p->next = L->next;
	L->next->prior = p; //犯过的错误，要先修改L->next->prior再修改L->next
	L->next = p;
	//prior和next都是指向元素本身。指向元素本身就是指向p。L。
}

删除：

DuLNode* InitInsertNode(DuLinkedList &L, ElemType x) {
	DuLNode *p = new DuLNode;
	p->element = x;
	return p;
}
void InsertList(DuLinkedList &L, ElemType x) /* 在 L 的第一个元素前插入新元素 x */ {
	DuLNode *p = InitInsertNode(L, x);
	p->prior = L;
	p->next = L->next;
	L->next->prior = p;
	L->next = p;
	//prior和next都是指向元素本身。元素本身就是p。L。
}
Status DeleteList(DuLinkedList &L, ElemType x)
/* 删除 L 中值为 x 的元素:
   若 L 中存在值为 x 的元素，删除之，且函数返回值 1，
   否则，即L中没有值为 x 的元素，不做删除，函数返回值 0。
   假设 L 中没有值相同的元素 */ {
	if (L->next == L && L->next == L) { return 0;/*L里没有元素了*/ }
	DuLinkedList temp = L->next;
	while (temp != L) {
		if (temp->element == x) {
			temp->next->prior = temp->prior;
			temp->prior->next = temp->next;
			return 1;
		}
		temp = temp->next;
	}
	return 0;
}

 题干

已知 L 为带头结点的双向循环链表，即 L 为头结点指针，如下图所示。

基本信息及结点结构声明如下：

#define INSERT 1
#define DELETE 2
 
typedef int Status;
typedef int ElemType;
typedef struct DuLNode * ptrDuLNode;
typedef struct DuLNode{
    ElemType  element;     /* 数据元素 */
    ptrDuLNode prior;      /* 前驱结点指针 */
    ptrDuLNode next;       /* 后继结点指针 */
}DuLNode, *DuLinkedList;

本题要求实现如下说明的 InsertList 及 DeleteList 函数，其余函数均有判题测试程序完成，且判题测试程序完成所需要的数据输出。题目测试数据保证正确。

函数接口定义：

void InsertList ( DuLinkedList &L, ElemType x );    /* 在 L 的第一个元素前插入新元素 x */
 
Status DeleteList ( DuLinkedList &L, ElemType x );
    /* 删除 L 中值为 x 的元素:
       若 L 中存在值为 x 的元素，删除之，且函数返回值 1，
       否则，即L中没有值为 x 的元素，不做删除，函数返回值 0。
       假设 L 中没有值相同的元素 */

判题程序样例如下所示：
 
int main ( ) {
    DuLinkedList L;
    ElemType x;
    int op;
 
    InitList ( L );
 
    while ( 1 )
    {
        scanf ( "%d%d", &op, &x );
        if ( op == INSERT )
        {
            InsertList ( L, x );
            printf ( "Success: Insert %d\n", x);
        }
        else if ( op == DELETE )
        {
            if ( DeleteList ( L, x ) )
                printf ( "Success: Delete %d\n", x);
            else
                printf ( "Failure: Delete %d\n", x);
        }
        else
            break;
    }
 
    PrintList( L );
    DestroyList ( L );
 
    return 0;
}
 
void InitList ( DuLinkedList &L )  /* 将 L 初始化为空的双向循环链表。判题测试程序完成 */
{
    L = ( ptrDuLNode ) malloc( sizeof ( DuLNode ) );
    L->next = L->prior = L;
}
 
void PrintList( DuLinkedList L )  /* 按头到尾输出线性表 L。判题测试程序完成 */
{
    /* 判题测试程序完成，此处略*/
}
 
void DestroyList ( DuLinkedList &L )  /* 销毁 L 并释放所占用的存储空间。判题测试程序完成 */
{
    /* 判题测试程序完成，此处略*/
}
 
/* 你实现的函数将被插入这里 */

 

假设初始时 L 为空，即 L = ( )。输入数据格式为 op value，其中 op 值为 1 、2 或 0，分别表示插入、删除，或结束；value 为待插入或删除的值。

读入的数据及操作结果说明如下：

1 3，表示插入元素 3，则 插入后 L = ( 3 )；

1 2，表示插入元素 2，则 插入后 L = ( 2 3 )；

2 1，表示删除元素 1，则 删除后 L = ( 2 3 )，DeleteList函数返回值 0；

2 3，表示删除元素 3，则 删除后 L = ( 2 )，DeleteList函数返回值 1；

0 1，表示操作结束

裁判测试程序样例：

输入样例 1：

1 3
1 2
2 1
2 3
0 1

输出样例 1：

Success: Insert 3
Success: Insert 2
Failure: Delete 1
Success: Delete 3
Finally L: 2

输入样例 2：

1 5
2 5
1 1
2 1
0 0

输出样例 2：

Success: Insert 5
Success: Delete 5
Success: Insert 1
Success: Delete 1
Finally L: The List is empty.