本关需要你设计一个程序,实现单链表的逆置。
单链表的逆置分为两种方法:头插法和就地逆置法,这两种方法虽然都能够达到逆置的效果,但还是有着不小的差别。
头插法
逆置链表初始为空,表中节点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空。
就地逆置法
先假定有一个函数,可以将以head
为头结点的单链表逆序,并返回新的头结点。利用这个函数对问题进行求解:将链表分为当前表头结点和其余部分,递归的过程就是,先将表头结点从链表中拆出来,然后对其余部分进行逆序,最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时,直接返回这个节点。
编程要求
按程序提示输入并创建一个单链表,带有头结点;
可自定义链表的长度,可自定义链表储存的数据类型,注意更改相应的输入输出方式;
实现单链表的逆置,直观地输出结果。
效果如下: 输入:
6
1 212 7 8 0 2
输出:
链表逆置前的数据:
1 212 7 8 0 2
链表逆置后的数据:
2 0 8 7 212 1
#include#include#includetypedef struct node {
int data;
struct node *next;
}NODE,* PNODE;
//函数声明
PNODE CreateList();
PNODE ReverseList(PNODE phead);
//CreateList函数创建链表
PNODE CreateList(){//先用尾插法创建一个链表
//创建一个头节点
PNODE phead=(PNODE)malloc(sizeof(NODE));
phead->next=NULL;
int len=0,i,val;
PNODE p=phead;//p指向头指针phead
scanf("%d",&len);//输入的链表长度len
for(i=0;inext = pNew;
pNew->data = val;
p=pNew;
}
p->next=NULL;
return phead;
}
//将单链表逆置的ReverseList函数
PNODE ReverseList(PNODE phead){
PNODE pHEAD=(PNODE)malloc(sizeof(NODE));//新建一个头节点pHEAD,然后依次读入phead中的每一个数据,并用头插法创建一个以pHEAD为头指针的新链表
pHEAD->next=NULL;
PNODE p = pHEAD->next;
int val;
PNODE q=phead->next;//p指向头指针phead
while(q!=NULL){
val = q->data;
q= q->next;
PNODE pNew=(PNODE)malloc(sizeof(NODE));//动态分配一个新节点pNew
pHEAD->next = pNew;
pNew->data = val;
pNew->next = p;
p=pNew;
}
//p=pHead;
return pHEAD;
}
void ShowList(PNODE phead){//遍历链表
PNODE p = phead->next;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
return;
}
int main(void)
{
PNODE phead;
phead = CreateList();
printf("链表逆置前的数据:\n");
ShowList(phead);
phead = ReverseList(phead);
printf("链表逆置后的数据:\n");
ShowList(phead);
return 0;
}
第2关:统计单链表中的节点数本小节需要你统计单链表中的节点数。
相关知识
根据上一关我们知道怎么创建单链表了,那么这一关让我们巩固一下单链表的知识。
编程要求
请仔细阅读右侧代码,根据方法内的提示,在Begin - End
区域内进行代码补充,具体任务如下:
编写程序,从键盘输入一串整数以及整数的个数,以单链表形式存储起来,计算单链表中结点的个数,输出单链表的数据及结点的个数。
效果如下:
输入:
8
12367802
输出:
12367802
8
#include#include#includetypedef struct node {
int data;
struct node *next;
}NODE,*PNODE;
int length_list(PNODE phead){
int cnt=0;
PNODE p = phead;
while(p->next!=NULL){
cnt++;
p=p->next;
}
return cnt;
}
PNODE CreatList(){
//创建头节点
PNODE phead = (PNODE)malloc(sizeof(NODE));
phead->next = NULL;
int i,len;
scanf("%d",&len);
PNODE p = phead;
for(i=0;idata);
p->next = pNew;
pNew->next = NULL;
p=pNew;
}
return phead;
}
void ShowList(PNODE phead){
PNODE p = phead->next;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
return;
}
int main(void)
{
PNODE phead;
phead = CreatList();
ShowList(phead);
printf("%d", length_list(phead));
return 0;
}
第1关:建单向链表本关需要你建立一个带头结点的单向链表。
相关知识
什么是链表?链表和二叉树是C
语言数据结构的基础和核心。
链表有多种形式,它可以是单链接的或者双链接的,可以是已排序的或未排序的,可以是循环的或非循环的。
编程要求
请仔细阅读右侧代码,根据方法内的提示,在Begin - End
区域内进行代码补充,具体任务如下:
键盘输入一组元素,建立一个带头结点的单向链表(无序)。
要求:
输入整数的长度以及整数;
输出无序的单向链表。
效果如下:
输入:
5
1 23 4 8 9
输出:
1 23 4 8 9
#include#includetypedef struct node {
int data;
struct node *next;
}NODE,* PNODE;
PNODE CreateList(){
//创建一个头节点
PNODE phead=(PNODE)malloc(sizeof(NODE));
phead->next=NULL;
int len=0,i,val;
PNODE p=phead;//p指向头指针phead
scanf("%d",&len);//输入的链表长度len
for(i=0;inext = pNew;
pNew->data = val;
pNew->next = NULL;
p=pNew;
}
//p=pHead;
return phead;
}
void ShowList(PNODE phead){//遍历链表
PNODE p = phead->next;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
return;
}
int main(void)
{
PNODE phead;
phead = CreateList();
ShowList(phead);
return 0;
}
如果文章对你有用的话,可不可以点一个赞鼓励我呢^o^
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页名称:C语言之链表练习题-创新互联
转载源于:https://www.cdcxhl.com/article20/dsoeco.html
成都网站建设公司_创新互联,为您提供企业网站制作、云服务器、定制开发、App开发、品牌网站设计、Google
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联