当前位置：网站首页>DHU programming exercise
DHU programming exercise
2022-06-30 02:10:00 【qq_ forty-three million four hundred and three thousand six hun】
4 Find sequence elements （ Linked list ）
1. Problem description
Input A、B、C、D Four sets （ There are no duplicate elements in the collection , And the element values are greater than 0）, They are stored in the linked list of non leading nodes .
This program first performs the following operations on the four sets ：
Yes A、B、C、D Sort in ascending order ;（ This function has been implemented , See function sort）.
do A=A+B operation ： First, execute two ordered linked lists A and B The merger of , And remain orderly , The results are stored in A in , Then delete the duplicate elements ;（ This function has been implemented , See function merge and purge）.
do A=A-C operation ： take C The elements appearing in are from A Delete in ;（ This function has been implemented , See function subtract）.
Yes D The elements that appear in , One by one A Query in ：
If in A in , From A Delete in
If in A Does not exist in the , Then add the element to A in , And keep the linked list A Orderly .
Please write a function fun This function is realized by the function body of .
- Output set A The elements in .（ This function has been implemented , See function displayLink）.
The prototype of the function to be written is as follows ：
struct student* fun(struct student* L1, struct student* L2)
Shape parameter ：
L1： The first collection passed in , Will be passed into the program A Set's chain header pointer
L2： The second collection passed in , Will be passed into the program D Set's chain header pointer
Return value ：
Returns the header pointer of the linked list of the first set
Part of the program code is as follows （ Or download attachments LinkSet.zip）：
#include <stdio.h>
#include <stdlib.h>
struct student
{
int num;
struct student *next;
};
struct student *createByTail()
{
struct student *head;
struct student *p1,*p2;
int n;
n=0;
p1=p2=(struct student*)malloc(sizeof(struct student));
scanf("%d",&p1->num);
head=NULL; // First set the linked list as an empty linked list
while(p1->num!=-1) //num by -1, It means that the user input ends
{
n=n+1;
if(n==1) // Create the first node
head=p1;
else
p2->next=p1;
p2=p1; //p2 Always point to the last node （ Tail pointer ）
p1=(struct student*)malloc(sizeof(struct student)); //p1 Point to the new node
scanf("%d",&p1->num);
}
p2->next=NULL; // Bear in mind ： Of the last node next The assignment is NULL
return head;
}
// Output the information in the linked list （num）
void displayLink(struct student *head)
{
struct student *p;
p=head;
printf("head-->");
while(p!= NULL)
{
printf("%d-->",p->num);
p=p->next;
}
printf("tail\n");
}
struct student *insertNodeInOrder(struct student *head,struct student *stu)
{
struct student *p0,*p1,*p2;
p1=head;
p0=stu;
if(head== NULL) // It's still an empty list
{
p0->next=head;
head=p0;
}
else
{
while((p0->num>p1->num)&&(p1->next!= NULL))
{// Find insertion location ,p2 Point to p1 The precursor of
p2=p1;
p1=p1->next;
}
//while The end condition of the loop has two , Next, you need to determine which condition exits the loop
if(p0->num<=p1->num)
{// from while The first condition of the loop condition exits the loop , So it can be inserted in p1 Before node
if(head==p1) head=p0;
else p2->next=p0;
p0->next=p1;
}
else
{// from while The second condition of the loop condition exits the loop , therefore p0->num Maximum , To be inserted last
p1->next=p0;
p0->next= NULL;
}
}
return head;
}
struct student *sort(struct student *head)
{
struct student *p,*s;
p=head;
head= NULL;
while(p)
{
s=p;
p=p->next;
head=insertNodeInOrder(head, s);
}
return head;
}
struct student * merge(struct student *LA, struct student *LB)
{
struct student *p,*s;
p=LB;
while(p)
{
s=p;
p=p->next;
LA=insertNodeInOrder(LA, s);
}
return LA;
}
struct student* subtract(struct student* LA, struct student* LB)
{
struct student *q, * p=LB;
struct student *pre=NULL;//pre Point to q The precursor of , So at first, it was assigned as NULL
while(p!=NULL) // Yes LB List traversal
{
q=LA;
while (q!=NULL && q->num!=p->num)
{
pre=q;
q=q->next; // stay LA Find out whether there are elements and p->num identical
}
if (q!=NULL) // Found the same element , Delete q The point is
{
if (q==LA) // If you delete the first node
{
LA = LA -> next;
free(q);
}
else
{
pre->next=q->next;
free(q);
}
}
p=p->next;
}
return LA;
}
void purge(struct student * head)
{
struct student *p,*q;
if(head== NULL || head->next == NULL)
return;
p=head;
while(p->next!= NULL)
{
if(p->num == p->next->num)
{
q=p->next;
p->next=q->next;
free(q);
}
else
{
p=p->next;
}
}
}
struct student* fun(struct student* L1, struct student* L2)
{
/ Write this function *****/
}
int main()
{
struct student *headA, *headB, *headC, *headD;
int i,n;
while(scanf("%d", &n)!= EOF)
{
i=0;
while( i<n)
{
headA=createByTail();// Create a linked list A
headB=createByTail();// Create a linked list B
headC=createByTail();// Create a linked list C
headD=createByTail();// Create a linked list D
headA = sort(headA);// Linked list A Sort
headB = sort(headB);// Linked list B Sort
headC = sort(headC);// Linked list C Sort
headD = sort(headD);// Linked list D Sort
headA = merge(headA, headB);// Link list B Merge to linked list A in
purge(headA);// Delete linked list A Repeat elements in
headA = subtract(headA, headC);// From the list A Subtract the linked list from C Medium element
headA=fun(headA, headD);// Linked list A And the list D call fun function
displayLink(headA);// Output list A The elements in
i++;
}
}
return 0;
}
2. Enter description
First enter a line , Contains an integer N, Indicates a total of tests N Group data .
Then enter 4*N That's ok , Each row is an element of a collection .
The... Of each group of data 1 Behavior set A The elements of , The first 2 Behavior set B The elements of , The first 3 Behavior set C The elements of , The first 4 Behavior set D The elements of .
The element value of each set is greater than 0 The integer of , When the input ,-1 End of the said .
3. The output shows that
Output information in head start , With tail ending , With “–>” Separate . If it's an empty list , Direct output “head–>tail”. See the output example for details .
4. Example
Input
2
3 5 8 10 15 9 -1
2 5 8 11 14 -1
2 5 10 -1
3 1 9 -1
3 5 8 10 15 9 -1
2 5 8 11 14 -1
2 5 10 -1
2 3 8 -1
Output
head–>1–>8–>11–>14–>15–>tail
head–>2–>9–>11–>14–>15–>tail
5. Code implementation （ Complete struct student* fun(struct student* L1, struct student* L2) function ）
#include <stdio.h>
#include <stdlib.h>
struct student
{
int num;
struct student *next;
};
struct student *createByTail()
{
struct student *head;
struct student *p1, *p2;
int n;
n = 0;
p1 = p2 = (struct student*)malloc(sizeof(struct student));
scanf("%d", &p1->num);
head = NULL; // First set the linked list as an empty linked list
while (p1->num != -1) //num by -1, It means that the user input ends
{
n = n + 1;
if (n == 1) // Create the first node
head = p1;
else
p2->next = p1;
p2 = p1; //p2 Always point to the last node （ Tail pointer ）
p1 = (struct student*)malloc(sizeof(struct student)); //p1 Point to the new node
scanf("%d", &p1->num);
}
p2->next = NULL; // Bear in mind ： Of the last node next The assignment is NULL
return head;
}
// Output the information in the linked list （num）
void displayLink(struct student *head)
{
struct student *p;
p = head;
printf("head-->");
while (p != NULL)
{
printf("%d-->", p->num);
p = p->next;
}
printf("tail\n");
}
struct student *insertNodeInOrder(struct student *head, struct student *stu)
{
struct student *p0, *p1, *p2 = NULL;
p1 = head;
p0 = stu;
if (head == NULL) // It's still an empty list
{
p0->next = head;
head = p0;
}
else
{
while ((p0->num > p1->num) && (p1->next != NULL))
{
// Find insertion location ,p2 Point to p1 The precursor of
p2 = p1;
p1 = p1->next;
}
//while The end condition of the loop has two , Next, you need to determine which condition exits the loop
if (p0->num <= p1->num)
{
// from while The first condition of the loop condition exits the loop , So it can be inserted in p1 Before node
if (head == p1) head = p0;
else p2->next = p0;
p0->next = p1;
}
else
{
// from while The second condition of the loop condition exits the loop , therefore p0->num Maximum , To be inserted last
p1->next = p0;
p0->next = NULL;
}
}
return head;
}
struct student *sort(struct student *head)
{
struct student *p, *s;
p = head;
head = NULL;
while (p)
{
s = p;
p = p->next;
head = insertNodeInOrder(head, s);
}
return head;
}
struct student * merge(struct student *LA, struct student *LB)
{
struct student *p, *s;
p = LB;
while (p)
{
s = p;
p = p->next;
LA = insertNodeInOrder(LA, s);
}
return LA;
}
struct student* subtract(struct student* LA, struct student* LB)
{
struct student *q, *p = LB;
struct student *pre = NULL;//pre Point to q The precursor of , So at first, it was assigned as NULL
while (p != NULL) // Yes LB List traversal
{
q = LA;
while (q != NULL && q->num != p->num)
{
pre = q;
q = q->next; // stay LA Find out whether there are elements and p->num identical
}
if (q != NULL) // Found the same element , Delete q The point is
{
if (q == LA) // If you delete the first node
{
LA = LA->next;
free(q);
}
else
{
pre->next = q->next;
free(q);
}
}
p = p->next;
}
return LA;
}
void purge(struct student * head)
{
struct student *p, *q;
if (head == NULL || head->next == NULL)
return;
p = head;
while (p->next != NULL)
{
if (p->num == p->next->num)
{
q = p->next;
p->next = q->next;
free(q);
}
else
{
p = p->next;
}
}
}
/* Yes D The elements that appear in , One by one A Query in ： If in A in , From A Delete in If in A Does not exist in the , Then add the element to A in , And keep the linked list A Orderly . */
/* Shape parameter ： L1： The first collection passed in , Will be passed into the program A Set's chain header pointer L2： The second collection passed in , Will be passed into the program D Set's chain header pointer Return value ： Returns the header pointer of the linked list of the first set */
/* Be careful ： The linked list does not take the lead node */
struct student* fun(struct student* L1, struct student* L2)
{
/* In this way, there will be a timeout , The time limit : 1S struct student *p, *q = L2, *pre, *s, *tmp; // Yes D The elements that appear in , One by one A Query in ： If in A in , From A Delete in while (q != NULL)// One by one L2 The elements in { p = L1; pre = NULL; while (p != NULL && p->num < q->num) { p = p->next; pre = p; } // stay L1 The element cannot be found in , The insert q Pointed node , And keep the linked list A Orderly . if (!p || p->num != q->num)//L1 Has been traversed or L1 No matching element found in { tmp = (struct student*)malloc(sizeof(struct student));// New node tmp->num = q->num; // Insert node into L1 And keep it in order L1 = insertNodeInOrder(L1, tmp); } else// stay L1 Remove duplicate elements from the table { // Delete header node if (p == L1) { s = p; p = p->next; free(s); } else { s = p; pre->next = s->next; free(s); } } q = q->next; } */
struct student *p1, *p2 = L2;
struct student *pre = NULL; //pre by p1 The precursor of
while (p2) {
p1 = L1;// Every time from L1 The header node begins to compare
while (p1 != NULL && p1->num != p2->num) {
pre = p1;
p1 = p1->next;
}
if (p1 == NULL) {
//L1 There's no element in it
student *node = new student;
node->num = p2->num;
L1 = insertNodeInOrder(L1, node);
}
else {
if (p1 == L1) {
// The element to be deleted is L1 The head node of
L1 = L1->next;
}
else {
pre->next = p1->next;
}
free(p1);
}
p2 = p2->next;
}
return L1;
}
int main()
{
struct student *headA, *headB, *headC, *headD;
int i, n;
while (scanf("%d", &n) != EOF)
{
i = 0;
while (i < n)
{
headA = createByTail();// Create a linked list A
headB = createByTail();// Create a linked list B
headC = createByTail();// Create a linked list C
headD = createByTail();// Create a linked list D
headA = sort(headA);// Linked list A Sort
headB = sort(headB);// Linked list B Sort
headC = sort(headC);// Linked list C Sort
headD = sort(headD);// Linked list D Sort
headA = merge(headA, headB);// Link list B Merge to linked list A in
purge(headA);// Delete linked list A Repeat elements in
headA = subtract(headA, headC);// From the list A Subtract the linked list from C Medium element
headA = fun(headA, headD);// Linked list A And the list D call fun function
displayLink(headA);// Output list A The elements in
i++;
}
}
return 0;
}
边栏推荐
- Copy entire directory to output folder maintain folder structure- Copy entire directory to output folder maintaining the folder structure?
- How does payment splitting help B2B bulk commodity transactions?
- 9 — 正则校验集合
- The national industrial information security development research center issued the report on industrial information security situation in 2021
- 一次 Keepalived 高可用的事故，让我重学了一遍它！
- 【自然语言处理】【多模态】OFA：通过简单的sequence-to-sequence学习框架统一架构、任务和模态
- 【MySQL 04】使用MySQL Workbench 8.0 CE 备份及恢复Linux中的MySQL数据库
- Let‘sPlayCurling
- dhu编程练习
- After the blueprint node of ue5 is copied to UE4, all connections and attribute values are lost
猜你喜欢
C language I want to pass
云存储架构能解决 DevOps 的什么问题？
C language score ranking
33Mysql
8 — router
Share the source code of the website of graduation student record
![[MySQL 04] use MySQL workbench 8.0 CE to back up and restore MySQL databases in Linux](/img/e7/fc2925a10ac5fb370dd221c3f4a46a.png)
[MySQL 04] use MySQL workbench 8.0 CE to back up and restore MySQL databases in Linux
018_ rate
Unity2d-- add keys to animation and bind events
Matlab 2012a drawing line segment with arrow
随机推荐
谁再用Redis过期监听实现关闭订单，立马滚蛋！
Blitzkrieg companies with DDoS attacks exceeding 100gbps in 2014
004_ icon
C language output integer in another format
005_ button
DTW学习（dynamic time warping）——思想、代码实现
The largest DDoS attack ever peaked at 400 Gbps
dhu编程练习
Yyds dry inventory consistent and smooth zoom type and spacing
Looking for thesaurus data [closed]
If mybaits cannot query the data, it can query how to change it in the database
Que se passe - t - il si un faux divorce devient un vrai divorce?
The national industrial information security development research center issued the report on industrial information security situation in 2021
Simple implementation of unity object pool
If mybaits cannot query the data, it can query how to change it in the database
想转行，但不知道自己要做什么工作比较好？
Want to change careers, but don't know what you want to do?
记录生产的一次OOM异常
Openlayers 3 built in interaction
As VoIP became the target, DDoS attacks surged by 35% in the third quarter