双向链表的基本操作(头歌)_本关任务:根据所学双向链表的基础知识,完成双向链表插入结点功能的程序编写并通过

一、第1关：双向链表的插入操作

任务描述
本关任务：编写双向链表的插入操作函数。

相关知识
双链表中用两个指针表示结点间的逻辑关系：指向其前驱结点的指针域prior，指向其后继结点的指针域next。双向链表的结点结构如图所示：

双向链表的结点结构

双向链表结点类型定义如下：

typedef struct node
{ ElemType data; //数据域
struct node *prior,*next; //分别指向前驱结点和后继结点的指针
} DLinkNode,*DLinkList;
双向链表中数据类型ElemType可以多种多样，但是在编程实现算法时针对不同数据类型，每类数据元素的输入输出是有区别的，双向链表的基本操作算法要在计算机上执行，须针对ElemType类型数据编写输入、输出、比较等函数：

void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
首先讨论如何进行双向链表的初始化操作。

双向链表的初始化操作
创建一个空的双链表，它只有一个头结点，由L指向它，该结点的next域和prior域均为空，data域未设定任何值。

void InitList(DLinkList &L)
{ L=(DLinkNode *)malloc(sizeof(DLinkNode));
//创建头结点L
L->prior=L->next=NULL;
}
在带头结点的双向链表中，通常头结点的数据域可以不存储任何信息，尾结点的next域置为NULL。 如下图所示是一个带头结点的双向链表：

双向链表的逻辑示意图如下：
双向链表逻辑示意图

查找双向链表中第i个数据元素值的操作
其算法思想与单链表的求表中第i个元素运算算法完全相同。

int GetElem(DLinkList L,int i,ElemType &e)
{
int j=0;
DLinkNode *p=L; //p指向头结点，计数器j置为0
if (i<=0) return 0; //参数i错误返回0
while (p!=NULL && j<i)
{
j++;
p=p->next;
}
if (p==NULL) return 0; //未找到返回0
else
{
e=p->data;
return 1; //找到后返回1
}
}
双向链表的插入操作
先在双链表中查找到第i-1个结点，若成功找到该结点（由p所指向），创建一个以x为值的新结点s，将s结点插入到p之后即可。

在双链表中p结点之后插入s结点的操作步骤如下：
① 将结点s的next域指向结点p的下一个结点：
s->next=p->next;
② 若p不是最后结点（若p是最后结点，只插入s作为尾结点），则将p之后结点的prior域指向s：
p->next->prior=s;
③ 将s的prior域指向p结点：
s->prior=p;
④ 将p的next域指向s：
p->next=s;

双向链表插入示意图如下：

双向链表插入示意图
在双链表中可以通过一个结点找到其前驱结点，所以插入操作也可以改为：
在双链表中找到第i个结点p，然后在p结点之前插入新结点。

与单链表上的插入操作不同的是，在双链表中插入必须同时修改两个方向上的指针。

双向链表的遍历操作
其算法思想与单链表的输出元素值运算算法完全相同。

void DispList(DLinkList L)
{
DLinkNode *p=L->next;
while (p!=NULL)
{
vi( p->data );
p=p->next;
}
printf("\n");
}
在执行遍历函数时，用函数指针vi来实现对output()函数的调用。

编程要求
根据提示，在右侧编辑器 Begin-End 区间补充代码，完成双向链表的初始化操作，插入操作及遍历操作三个子函数的定义，具体要求如下：

void InitList(DLinkList &L);//构造一个空的双向链表L
int ListInsert(DLinkList &L,int i,ElemType e) ;//在双向链表L中第i个位置之前插入新的数据元素
void ListTraverse(DLinkList L,void(*vi)(ElemType));// 依次调用函数vi()输出双向链表L的每个数据元素
测试说明
平台会对你编写的代码进行测试：

测试输入：
5
12 47 5 8 69
1
99
预期输出：
插入成功，插入后双向链表如下：
99 12 47 5 8 69

测试输入：
5
12 47 5 8 69
7
99
预期输出：
插入位置不合法，插入失败！

输入说明
第一行输入双向链表的数据元素的个数M；
第二行输入双向链表M个整数；
第三行输入要插入元素的位置；
第四行输入要插入的数据元素的值。

输出说明
第一行输出插入是否成功的提示信息；
如果插入成功，第二行输出插入元素后的双向链表所有元素；如果插入失败，则不输出第二行。

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 双向链表类型定义 */
typedef struct node
{  ElemType data;		//数据域
   struct node *prior,*next;	//分别指向前驱结点和后继结点的指针
} DLinkNode,*DLinkList;

void InitList(DLinkList &L);
int ListInsert(DLinkList &L,int i, ElemType e) ;
void ListTraverse(DLinkList L,void(*vi)(ElemType));

int main()               //main() function 
{	
     DLinkList A;
     ElemType e;
     InitList(A);
      int n,i;
     // cout<<"Please input the list number ";
     cin>>n;
     for(i=1;i<=n;i++)
        { 
		   cin>>e;
         ListInsert(A, i, e);
       }
	//cout<<"请输入插入的位置："<<endl;
	cin>>i;
	//cout<<"请输入插入的值："<<endl;
	input(e);
	if(  ListInsert(A,i,e) )
    {
      cout<<"插入成功，插入后双向链表如下："<<endl;
      ListTraverse(A,output) ;
    }
    else
    	cout<<"插入位置不合法，插入失败！"<<endl;
    return  0;  
 }


/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****双向链表的基本操作*****/
void InitList(DLinkList &L)
{ 	//构造一个空的双向链表L
	/********** Begin **********/ 
L=(DLinkNode *)malloc(sizeof(DLinkNode));  
            //创建头结点L
L->prior=L->next=NULL;
	
	/********** End **********/	
}
int ListInsert(DLinkList &L,int i, ElemType e) 
{
	// 在带头结点的双向链表L的第i个元素之前插入元素e  
	/********** Begin **********/ 
	DLinkList p,q;
    p=L;
    q=(DLinkList)malloc(sizeof(DLinkList));
    int j=0;
    while(p!=NULL && j<i-1)
    {
        
        j++;
        p=p->next;
    }
    if (p==NULL) 
    return 0;    //未找到返回0
    q->data=e;
    q->next=p->next;
    p->next=q;
    q->prior=p;
    return 1;
	/********** End **********/
}

void ListTraverse(DLinkList L,void(*vi)(ElemType))
{ 
	// 输出带头结点的双向链表L的每个元素 
	/********** Begin **********/ 
	DLinkList p=L->next;
    while (p!=NULL)
    { 
        vi( p->data );    
        p=p->next;
    }
    printf("\n");
    
	/********** End **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

二、第2关：双向链表的删除操作

任务描述
本关任务：编写双向链表的删除操作函数。

相关知识
先在双向链表中查找到第i个结点，若成功找到该结点（由p所指向），通过前驱结点和后继结点的指针域改变来删除p结点。

在双链表中删除p结点（其前驱结点为pre）的操作：　　
① 若p不是尾结点，则将其后继结点的prior域指向pre结点：
p->next->prior=pre
② 将pre结点的next域改为指向p结点的后继结点：
pre->next=p->next

双向链表删除示意图

在双向链表中删除也必须同时修改两个方向上的指针。

在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，但对于插入和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

编程要求
根据提示，在右侧编辑器 Begin-End 区间补充代码，完成双向链表的删除操作函数的定义，具体要求如下：

int ListDelete(DLinkList L,int i,ElemType &e);// 在双向链表L中删除第i个元素，并由e返回其值
测试说明
平台会对你编写的代码进行测试：

测试输入：
5
12 47 5 8 69
1
预期输出：
删除成功，删除后双向链表如下：
47 5 8 69
删除元素的值：12

测试输入：
5
12 47 5 8 69
6
预期输出：
删除位置不合法，删除失败！

输入说明
第一行输入双向链表的长度M；
第二行输入双向链表的M个整数；
第三行输入要删除元素的位置；

输出说明
第一行输出删除是否成功的提示信息；
如果删除成功，第二行输出删除元素后的双向链表；第三行输出删除的数据元素；如果删除位置不合法，不输出第二行和第三行。

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

/* 定义ElemType为int类型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);

/* 双向链表类型定义 */
typedef struct node
{  ElemType data;		//数据域
   struct node *prior,*next;	//分别指向前驱结点和后继结点的指针
} DLinkNode,*DLinkList;

void InitList(DLinkList &L);
int ListInsert(DLinkList &L,int i, ElemType e) ;
int ListDelete(DLinkList L,int i,ElemType &e);
void ListTraverse(DLinkList L,void(*vi)(ElemType));

int main()               //main() function 
{	
	DLinkList A;
	ElemType e;
	InitList(A);
	int n,i;
	// cout<<"Please input the list number ";
	cin>>n;
	for(i=1;i<=n;i++)
	{ 
		cin>>e;
		ListInsert(A, i, e);
	}
	//ListTraverse(A,output) ;
	//cout<<"请输入删除的位置："<<endl;
	cin>>i;
	if(  ListDelete(A,i,e) )
	{
		cout<<"删除成功，删除后双向链表如下："<<endl;
		ListTraverse(A,output) ;
		cout<<"删除元素的值：";
	    output(e);
    cout<<endl;
	}
	else
		cout<<"删除位置不合法，删除失败！"<<endl;
}


/*****ElemType类型元素的基本操作*****/
void input(ElemType &s)
{
	cin>>s;
}
void output(ElemType s)
{
	cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
	if(a==b)
		return  1;
	else
		return  0;
}

/*****双向链表的基本操作*****/
void InitList(DLinkList &L)
{ 	//构造一个空的双向链表L
	L=(DLinkList)malloc(sizeof(DLinkNode)); // 产生头结点，并使L指向此头结点
	L->next=NULL; // 指针域为空
	L->prior=NULL; 	
}

int ListInsert(DLinkList &L,int i, ElemType e) 
{
	// 在带头结点的双向链表L的第i个元素之前插入元素e  
	int j=0;
	DLinkNode *p=L,*s;
	if (i<=0) return 0;	      //参数i错误返回0
	while (p!=NULL && j<i-1)	   //查找第i-1个结点p
	{	
		j++;
		p=p->next;
	}
   if (p==NULL) 
		return 0;	   //未找到返回0
   else
   {	
        s=(DLinkNode *)malloc(sizeof(DLinkNode));
        s->data=e;		//创建一个存放元素x的新结点
        s->next=p->next;	//对应插入操作的步骤①
        if (p->next!=NULL)	//对应插入操作的步骤②
        p->next->prior=s;
        s->prior=p;		//对应插入操作的步骤③
        p->next=s;		//对应插入操作的步骤④
        return 1;		//插入运算成功,返回1
    }
	
}

void ListTraverse(DLinkList L,void(*vi)(ElemType))
{ 
	// 输出带头结点的双向链表L的每个元素 
	DLinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");	
}

int  ListDelete(DLinkList L,int i,ElemType &e)    // 不改变L
{ 
	// 在带头结点的双向链表L中，删除第i个元素，并由e返回其值
	/********** Begin **********/ 
	DLinkList p,q;
    p=L;
    int n=0;
    while(p->next&&n<i-1)
    {
        n++;
        p=p->next;

    }
    if(!p->next||n>i-1)
    {
        return 0;
    }
    q=p->next;
    if(p->next->next)
    {
        p->next=p->next->next;
        p->next->next->prior=p;

    }
    else{
        p->next=NULL;
    }
    e=q->data;
    free(q);
    return e;
	/********** End **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147