当前位置:   article > 正文

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

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

一、第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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/781980
推荐阅读
相关标签
  

闽ICP备14008679号