-->
当前位置:首页 > 题库 > 正文内容

函数题:带头结点的双向循环链表操作集

Luz3年前 (2021-05-10)题库527
本题要求实现一个带头结点的双向循环链表操作集。

### 函数接口定义:
```c++
typedef int dataType;

typedef struct _node
{
dataType data;
struct _node *prev;//指向前驱的指针
struct _node *next;//指向后继的指针
}node;

typedef node* List;

List create_list();//创建一个空的循环链表,返回指向头节点的指针。
void insert(List L, dataType x);//用尾插法向链表L中插入数据域等于x的结点
bool is_empty(List L);//如果链表为空,则返回true,否则返回false。
void traverse(List L);//顺序遍历链表L。输出所有结点的数据域。如果链表为空则输出NULL
void traverse_back(List L);//逆序遍历链表L。输出所有结点的数据域。如果链表为空则输出NULL
node* search(List L, dataType x);//返回第1个指向数据域等于x的结点的指针。如果没有则返回NULL。
void delete_node(List L, node* p);//删除指针p指向的结点。调用者保证p是合法的。
void remove_node(List L, dataType x);//删除链表L中所有数据域等于x的结点
void make_empty(List L);//使链表L成为一个空链表
void destroy_list(List L);//销毁链表L
```


### 裁判测试程序样例:
```c++
#include
#include
#include

typedef int dataType;

typedef struct _node
{
dataType data;
struct _node *prev;//指向前驱的指针
struct _node *next;//指向后继的指针
}node;

typedef node* List;

List create_list();//创建一个空的循环链表,返回指向头节点的指针。
void insert(List L, dataType x);//用尾插法向链表L中插入数据域等于x的结点
bool is_empty(List L);//如果链表为空,则返回true,否则返回false。
void traverse(List L);//顺序遍历链表L。输出所有结点的数据域。如果链表为空则输出NULL
void traverse_back(List L);//逆序遍历链表L。输出所有结点的数据域。如果链表为空则输出NULL
node* search(List L, dataType x);//返回第1个指向数据域等于x的结点的指针。如果没有则返回NULL。
void delete_node(List L, node* p);//删除指针p指向的结点。调用者保证p是合法的。
void remove_node(List L, dataType x);//删除链表L中所有数据域等于x的结点
void make_empty(List L);//使链表L成为一个空链表
void destroy_list(List L);//销毁链表L

int main()
{
int x;
List mylist = create_list();
//输入一系列正整数,输入0表示输入结束
//用尾插法插入链表
scanf("%d", &x);
while (x != 0)
{
insert(mylist, x);
scanf("%d", &x);
}
//顺序遍历链表
traverse(mylist);
//逆序遍历链表
traverse_back(mylist);
//输入要删除的结点数据域
scanf("%d", &x);
node *p = search(mylist, x);
if (p != NULL)
{
delete_node(mylist, p);
}
//顺序遍历链表
traverse(mylist);
//逆序遍历链表
traverse_back(mylist);
//输入要删除的结点数据域
scanf("%d", &x);
remove_node(mylist, x);
//顺序遍历链表
traverse(mylist);
//逆序遍历链表
traverse_back(mylist);
//销毁链表
destroy_list(mylist);
return 0;
}

/* 请在这里填写答案 */
```

### 输入样例:

在这里给出一组输入。例如:

```in
10 20 10 10 20 30 0
20
10
```

### 输出样例:

在这里给出相应的输出。例如:

```out
10 20 10 10 20 30
30 20 10 10 20 10
10 10 10 20 30
30 20 10 10 10
20 30
30 20
```
### 输入输出样例解释:
程序首先创建一个空的双向循环链表,如下图所示:

![捕获3.PNG](~/a340ab07-9908-4544-ab2b-e683bbc51a87.PNG)

输入的第1行是

10 20 10 10 20 30 0

此时程序创建一个带头节点的双向循环链表,如下图所示:

![捕获.PNG](~/3d2ad6f9-b515-435b-8bf0-5f83bd10c49d.PNG)
此时顺序输出

10 20 10 10 20 30

逆序输出

30 20 10 10 20 10


输入的第2行是

20

此时程序删除从头结点向后的第1个数据域等于20的结点,所以链表如下图所示:

![捕获1.PNG](~/9a5c4bf0-3a59-4ca5-a7ce-291d6ca6a436.PNG)
此时顺序输出

10 10 10 20 30

逆序输出

30 20 10 10 10


输入的第3行是

10

此时程序删除链表中所有数据域等于10的结点,所以链表如下图所示:

![捕获2.PNG](~/91b0106f-2537-4dee-a2d9-eca00fcc05e0.PNG)

此时顺序输出

20 30

逆序输出

30 20






答案:若无答案欢迎评论

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。