双向链表的基本操作

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

任务描述

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

测试说明

平台会对你编写的代码进行测试：

测试输入：
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 = (DLinkList)malloc(sizeof(DLinkNode));
    L->prior = L->next = NULL;
	/********** End **********/	
}
int ListInsert(DLinkList &L,int i, ElemType e) 
{
	// 在带头结点的双向链表L的第i个元素之前插入元素e  
	/********** Begin **********/ 
	DLinkList p = L,node;
    int x = 0;
    while(p && x < i - 1){
        p = p -> next;
        x++;
    }
    if(!p || x>i-1){
        return 0;
    }
    node = (DLinkList)malloc(sizeof(DLinkNode));
    node -> data = e;
    node -> next = p -> next;
    p -> next = node;
    node -> prior = p;
    return 1;
	/********** End **********/
}

void ListTraverse(DLinkList L,void(*vi)(ElemType))
{ 
	// 输出带头结点的双向链表L的每个元素 
	/********** Begin **********/ 
	L = L -> next;
    while(L){
        vi(L->data);
        L = L -> next;
    } 
    
	/********** 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

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

任务描述

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

测试说明

平台会对你编写的代码进行测试：

测试输入：
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 = L,node;
    int x = 0;
    while(p -> next && x < i - 1){
        p = p -> next;
        x++;
    }
    if(!p -> next || x>i-1){
        return 0;
    }
    node = p -> next;
    if(p -> next -> next){
        p -> next = p -> next -> next;
        p -> next -> next -> prior = p;
    }else{
         p->next = NULL;
    }
    e = node -> data;
    free(node);
    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