SDUT c语言程序设计基础2实验2链表

在学习链表部分时推荐背诵本套代码1.全部是代码块的形式所有题目具有相同套路背诵一个函数可重复使用2.逻辑清楚为后续学习打下坚实基础。3.与学习通课程内容相符合配合使用更佳点击蓝色字体快捷食用如出现错误可联系作者修改7-1 sdut-C语言实验-顺序建立链表7-2 sdut-C语言实验-逆序建立链表7-3 sdut-C语言实验-链表的结点插入7-4 sdut-C语言实验-单链表中重复元素的删除7-5 sdut-C语言实验-链表的逆置7-6 sdut-C语言实验-有序链表的归并7-7 sdut-C语言实验-单链表的拆分7-8 sdut-C语言实验-双向链表7-9 sdut-C语言实验-约瑟夫问题7-10 sdut-C语言实验-不敢死队问题7-1 sdut-C语言实验-顺序建立链表分数 20作者 马新娟单位 山东理工大学输入N个整数按照输入的顺序建立单链表存储并遍历所建立的单链表输出这些数据。输入格式:第一行输入整数的个数N第二行依次输入每个整数。输出格式:输出这组整数。输入样例:812 56 4 6 55 15 33 62输出样例:12 56 4 6 55 15 33 62#includestdio.h #includestdlib.h struct node{ int data; struct node *next;//指针域指向下一结点 };//结构体定义结点结构 struct node *creat(int n);//链表建立函数 void output(struct node *head);//输出函数; int main(){ int n; scanf(%d,n); struct node *headcreat(n);//引入建立链表函数 output(head);//引入输出函数 return 0; } struct node *creat(int n){//尾插法建立链表函数 struct node *head,*tail,*p;//同时定义头尾指针游动指针 head(struct node *)malloc(sizeof(struct node));//分配空间给头结点 head-nextNULL;//头结点置为空 tailhead;//尾结点和头结点的指针指向同一结点 while(n--){ p(struct node *)malloc(sizeof(struct node));//分配空间给结点p; scanf(%d,p-data); p-nextNULL; tail-nextp; tailp;//确定指针域 } return (head); } void output(struct node *head){ struct node *phead-next;//注意容易遗漏 while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } }7-2 sdut-C语言实验-逆序建立链表分数 20作者 马新娟单位 山东理工大学输入整数个数N再输入N个整数按照这些整数输入的相反顺序建立单链表并依次遍历输出单链表的数据。输入格式:第一行输入整数N;第二行依次输入N个整数逆序建立单链表。输出格式:依次输出单链表所存放的数据。输入样例:1011 3 5 27 9 12 43 16 84 22输出样例:22 84 16 43 12 9 27 5 3 11#includestdio.h #includestdlib.h struct node{ int data; struct node *next; };//结构体定义结点结构 struct node *creat(int n);//链表建立函数 void output(struct node *head);//输出函数; int main(){ int n; scanf(%d,n); struct node *headcreat(n);//引入建立链表函数 output(head);//引入输出函数 return 0; } struct node *creat(int n){//头插法建立链表函数 struct node *head,*p;//定义 head(struct node *)malloc(sizeof(struct node));//分配空间给头结点 head-nextNULL;//头结点置为空 while(n--){ p(struct node *)malloc(sizeof(struct node)); scanf(%d,p-data); p-nexthead-next;//注意先记上 head-nextp;//确定指针域 } return (head);//返回建立好的链表 } void output(struct node *head){//链表输出函数 struct node *phead-next;//对p进行赋值此时p已经分配过空间不需要再分配 while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } }7-3 sdut-C语言实验-链表的结点插入分数 20作者 马新娟单位 山东理工大学给出一个只有头指针的链表和 n 次操作每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。输入格式:多组输入。每组数据首先输入一个整数n(n∈[1,100])代表有n次操作。接下来的n行每行有两个整数Mi(Mi∈[0,10000])Xi。输出格式:对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。输入样例:41 11 20 3100 4输出样例:3 1 2 4#includestdio.h #includestdlib.h struct node{ int data; struct node *next; }; void insert(struct node *p,int key); void output(struct node *head); int main(){ int n,m,x; struct node *head,*p; while(~scanf(%d,n))//注意多组输入 {//~是按位取反运算符当scanf函数调用的返回值为0循环体内的代码将会执行可以用于循环直到成功获取到输入 head(struct node *)malloc(sizeof(struct node)); head-nextNULL;//顺序建立链表 while(n--){//等同于while(n0)n--;//这个循环才是真正需要的 phead;//将游动指针p放在头指针位置处进行初始化有可能插入到头结点之后 //head作为第一个元素题目中定义 scanf(%d %d,m,x);//p此时只是一个游动指针。不是结点不需要为其申请空间 while(m--p-next){//while循环的作用确定题目中给的目标位置 pp-next; } insert(p,x); } output(head); } return 0; } void insert(struct node *p,int key){ struct node *q; q(struct node *)malloc(sizeof(struct node)); if(!q){//如果非q为真那么q为0条件成立 printf(不能分配内存空间); exit(0);//电脑函数正常退出 }//这个if语句如果去掉更简单; q-datakey; q-nextNULL; q-nextp-next; p-nextq; } void output(struct node *head){ struct node *phead-next;//一一定要有 while(p!NULL){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } }7-4 sdut-C语言实验-单链表中重复元素的删除分数 20作者 马新娟单位 山东理工大学按照数据输入的相反顺序逆位序建立一个单链表并将单链表中重复的元素删除值相同的元素只保留最后输入的一个。输入格式:第一行输入元素个数 n (1 n 15)第二行输入 n 个整数保证在 int 范围内。输出格式:第一行输出初始链表元素个数第二行输出按照逆位序所建立的初始链表第三行输出删除重复元素后的单链表元素个数第四行输出删除重复元素后的单链表。输入样例:1021 30 14 55 32 63 11 30 55 30输出样例:1030 55 30 11 63 32 55 14 30 21730 55 11 63 32 14 21#includestdio.h #includestdlib.h struct node{ int data; struct node *next; }; struct node *creat(int n);//链表建立 int delete(struct node *head,int n);//重复结点删除 void output(struct node *head,int n);//链表输出 int main(){ struct node *head,*p;//定义 int n; scanf(%d,n);//输入n; headcreat(n);//建立链表 output(head,n);//输出链表 ndelete(head,n);//删除结点//对n进行赋值一定要有 output(head,n);//输出链表 return 0; } struct node *creat(int n){//链表建立 struct node *head,*p; head(struct node *)malloc(sizeof(struct node)); head-nextNULL; for(int i0;in;i){ p(struct node *)malloc(sizeof(struct node)); scanf(%d,p-data); p-nexthead-next; head-nextp;//逆序建立 } return (head); } int delete(struct node *head,int n){//删除重复结点 struct node *phead; while(p-next){ pp-next;//每次后移一位 struct node *qp,*qiq-next;//两个游动指针qi对比q辅助 while(qi){ if(p-dataqi-data)//p和qi比较q作为辅助 {//注意等号情况双等号 q-nextqi-next; free(qi);//释放已经删除的结点空间 qiq-next; n--; } else{ qiqi-next; qq-next; } } } return n; } void output(struct node *head,int n){//链表输出函数 struct node *phead-next; printf(%d\n,n); while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next;//注意不要遗落 } }7-5 sdut-C语言实验-链表的逆置分数 20作者 马新娟单位 山东理工大学输入多个整数以-1作为结束标志顺序建立一个带头结点的单链表之后对该单链表的数据进行逆置并输出逆置后的单链表数据。输入格式:输入多个整数以-1作为结束标志。输出格式:输出逆置后的单链表数据。输入样例:12 56 4 6 55 15 33 62 -1输出样例:62 33 15 55 6 4 56 12#includestdio.h #includestdlib.h struct node{ int data; struct node *next; }; struct node *creat(){ int a; struct node *head,*p; head(struct node *)malloc(sizeof(struct node)); head-nextNULL; while(scanf(%d,a)a!-1){ p(struct node *)malloc(sizeof(struct node)); p-dataa; p-nexthead-next; head-nextp; } return (head); } void output(struct node *head){ struct node *phead-next; while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } } int main(){ struct node *headcreat(); output(head); return 0; }#includestdio.h #includestdlib.h struct node{ int data; struct node *next; }; struct node *creat(); void reverse(struct node *head);//不需要返回值 void output(struct node *head); int main(){ struct node *head; headcreat(); reverse(head); output(head); return 0; } struct node *creat(){ struct node *head,*p,*tail; head(struct node *)malloc(sizeof(struct node)); head-nextNULL; tailhead; int a; scanf(%d,a); while(a!-1){ p(struct node *)malloc(sizeof(struct node)); p-dataa; tail-nextp; tailp; scanf(%d,a); } return (head); } void reverse(struct node *head){ struct node *p,*q; phead-next; head-nextNULL; qp-next; while(p){ p-nexthead-next; head-nextp; pq; if(q){ qq-next; } } } void output(struct node *head){ struct node *p; phead-next; while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } }7-6 sdut-C语言实验-有序链表的归并分数 20作者 马新娟单位 山东理工大学分别输入两个有序的整数序列分别包含M和N个数据建立两个有序的单链表将这两个有序单链表合并成为一个大的有序单链表并依次输出合并后的单链表数据。输入格式:第一行输入M与N的值第二行依次输入M个有序的整数第三行依次输入N个有序的整数。输出格式:输出合并后的单链表所包含的MN个有序的整数。输入样例:6 51 23 26 45 66 9914 21 28 50 100输出样例:1 14 21 23 26 28 45 50 66 99 100#includestdio.h #includestdlib.h struct node{ int data; struct node *next; }; struct node *creat(int n); struct node *merge(struct node *head1,struct node *head2); void output(struct node *head); int main(){ int m,n; scanf(%d %d,m,n); struct node *head1creat(m); struct node *head2creat(n); head1merge(head1,head2); output(head1); return 0; } struct node *creat(int n){ struct node *head,*p,*tail; head(struct node *)malloc(sizeof(struct node)); head-nextNULL; tailhead; while(n--){ p(struct node *)malloc(sizeof(struct node)); scanf(%d,p-data); p-nextNULL; tail-nextp; tailp; } return (head); } struct node *merge(struct node *head1,struct node *head2){ struct node *tail,*p1,*p2; p1head1-next; p2head2-next; tailhead1; free(head2); while(p1p2){ if(p1-datap2-data){//由题目中给的数据判断大于小于符号 tail-nextp1; tailp1; p1p1-next; } else{ tail-nextp2; tailp2; p2p2-next; } } if(p1) tail-nextp1; else tail-nextp2; return (head1); } void output(struct node *head){ struct node *p; phead-next; while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } }7-7 sdut-C语言实验-单链表的拆分分数 20作者 马新娟单位 山东理工大学输入N个整数顺序建立一个单链表将该单链表拆分成两个子链表第一个子链表存放了所有的偶数第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。输入格式:第一行输入整数N;第二行依次输入N个整数。输出格式:第一行分别输出偶数链表与奇数链表的元素个数第二行依次输出偶数子链表的所有数据第三行依次输出奇数子链表的所有数据。输入样例:101 3 22 8 15 999 9 44 6 1001输出样例:4 622 8 44 61 3 15 999 9 1001#includestdio.h #includestdlib.h struct node{ int data; struct node *next; }; struct node *creat(int n); struct node *split(struct node *head1); void output(struct node *head); int main(){ int n; scanf(%d,n); struct node *head1creat(n); struct node *head2split(head1); output(head1); output(head2); return 0; } struct node *creat(int n){ struct node *head,*p,*tail; head(struct node *)malloc(sizeof(struct node)); head-nextNULL; tailhead; while(n--){ p(struct node *)malloc(sizeof(struct node)); scanf(%d,p-data); p-nextNULL; tail-nextp; tailp; } return (head); } struct node *split(struct node *head1){ struct node *head2,*tail1,*tail2,*p; tail1head1; head2(struct node *)malloc(sizeof(struct node)); head2-nextNULL; tail2head2; phead1-next; head1-nextNULL; int c10,c20; while(p){ if(p-data%20){ tail1-nextp; tail1p; c1; } else{ tail2-nextp; tail2p; c2; } pp-next; } tail1-nextNULL; tail2-nextNULL; printf(%d %d\n,c1,c2); return (head2); } void output(struct node *head){ struct node *phead-next; while(p){ if(p-next) printf(%d ,p-data); else printf(%d\n,p-data); pp-next; } }7-8 sdut-C语言实验-双向链表分数 20作者 马新娟单位 山东理工大学学会了单向链表我们又多了一种解决问题的能力单链表利用一个指针就能在内存中找到下一个位置这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B他们的关系是B是A的后继A指向了B便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中A有一个指针指向了节点B同时B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点也能从链表尾节点开始遍历所有节点。对于给定的一列数据按照给定的顺序建立双向链表按照关键字找到相应节点输出此节点的前驱节点关键字及后继节点关键字。输入格式:第一行两个正整数n代表节点个数m代表要找的关键字的个数。第二行是n个数n个数没有重复利用这n个数建立双向链表。接下来有m个关键字每个占一行。输出格式:对给定的每个关键字输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继则不输出。注意每个给定关键字的输出占一行。一行输出的数据之间有一个空格行首、行末无空格。输入样例:10 31 2 3 4 5 6 7 8 9 0350输出样例:在这里给出相应的输出。例如2 44 69#includestdio.h #includestdlib.h struct node{ int data; struct node *prev; struct node *next; }; struct node *creat(int n); void search(struct node *head); int main(){ int n,m; scanf(%d %d,n,m); struct node *headcreat(n); while(m--) search(head); return 0; } struct node *creat(int n){ struct node *head,*tail,*p; head(struct node *)malloc(sizeof(struct node)); head-prevNULL; head-nextNULL; tailhead; while(n--){ p(struct node *)malloc(sizeof(struct node)); scanf(%d,p-data); p-nextNULL; p-prevtail;//对p进行初始化 tail-nextp; tailp; } return (head); } void search(struct node *head){ int t; scanf(%d,t); struct node *phead-next; while(p){ if(p-datat){ struct node *prevp-prev; struct node *nextp-next; if(prev!head) printf(%d,prev-data); if(next!NULL){ if(prev!head) printf( %d,next-data); else printf(%d,next-data); } printf(\n); // break; } pp-next; } }7-9 sdut-C语言实验-约瑟夫问题分数 20作者 马新娟单位 山东理工大学n个人想玩残酷的死亡游戏游戏规则如下n个人进行编号分别从1到n排成一个圈顺时针从1开始数到m数到m的人被杀剩下的人继续游戏活到最后的一个人是胜利者。请输出最后一个人的编号。输入格式:输入n和m值。输出格式:输出胜利者的编号。输入样例:5 3输出样例:4#include stdio.h//可写成#includestdio.h #include malloc.h//可写成#inlcudestdlib.h typedef struct mon{//结构体的定义typedef为结构体定义一个别名mon int num; struct mon *next; }mon; mon *creat(int n){// 循环链表的创建函数 int i; mon *p,*tail,*head; p(mon *)malloc(sizeof(mon)); p-num1; p-nextNULL; // 第一个结点的生成 headp; tailp; for(i2;in;i){// 顺序建链表完成其余n-1个结点的插入 p(mon *)malloc(sizeof(mon)); p-numi; p-nextNULL; tail-nextp; tailp; } tail-nexthead; // 最后一个结点的指针域指向第一个结点 return head; } int sel(mon *head,int m,int n) // n只猴子报数m出圈的控制函数 { int num0; // 表示猴子报数的计数变量 int count0; // 用以统计出圈猴子数目的计数变量 mon *p,*q; // 分别指向当前结点及其前驱结点的指针 qhead;//此处不能用qtail;因为tail未被定义因此用head while(q-next!head) qq-next; // 前驱指针指向尾结点 //printf(被删除的猴子序号依次是); while(countn-1){ pq-next; num; if(num%m0) { // 找到一个被删结点完成删除、计数、输出 q-nextp-next; //printf(%3d,p-num); free(p); count; } else qp; } return q-num; // 最后一个结点的数据域即为留在圈内猴王的序号 } int main(){ int n,m; mon *head; scanf(%d %d,n,m); headcreat(n); printf(%d\n,sel(head,m,n)); return 0; }7-10 sdut-C语言实验-不敢死队问题分数 20作者 马新娟单位 山东理工大学说到“敢死队”大家不要以为我来介绍电影了因为数据结构里真有这么道程序设计题目原题如下有M个敢死队员要炸掉敌人的一个碉堡谁都不想去排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务则要再派一个战士上去。现给每个战士编一个号大家围坐成一圈随便从某一个战士开始计数当数到5时对应的战士就去执行任务且此战士不再参加下一轮计数。如果此战士没完成任务再从下一个战士开始数数被数到第5时此战士接着去执行任务。以此类推直到任务完成为止。这题本来就叫“敢死队”。“谁都不想去”就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号按照上面介绍从1号开始数数到5的那名战士去执行任务那么排长是第几个去执行任务的输入格式:输入包括多组数据每组一行包含一个整数M0M10000)敢死队人数若M0输入结束不做处理。输出格式:输出一个整数n代表排长是第n个去执行任务。输入样例:962230输出样例:在这里给出相应的输出。例如26132#includestdio.h #includestdlib.h typedef struct mon{ int num; struct node *next; }mon; mon *creat(int n); int sel(mon *head); int main(){ int n; mon *headcreat(n); while(scanf(%d,n)n!0){ headcreat(n); printf(%d\n,sel(head)); } return 0; } mon *creat(int n){ mon *head,*tail,*p; p(mon *)malloc(sizeof(mon)); p-num1; p-nextNULL; headp; tailp; for(int i2;in;i){ p(mon *)malloc(sizeof(mon)); p-numi; p-nextNULL; tail-nextp; tailp; } tail-nexthead; return (head); } int sel(mon *head){ mon *p,*q; int num0,c0; qhead; while(q-next!head) qq-next; while(1){ pq-next; num; if(num%50){ c; if(p-num1) break; q-nextp-next; free(p); } else qp; } return c; }