当前位置：网站首页>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;
}
边栏推荐
- 【自然语言处理】【多模态】OFA：通过简单的sequence-to-sequence学习框架统一架构、任务和模态
- C language I want to pass
- 208. implement trie (prefix tree) - attach detailed notes
- scp远程拷贝命令记录
- Jenkins continuous integration environment build 8 (configure mailbox server to send build results)
- 【MySQL 05】SUSE 12 SP5 安装MySQL后第一次修改mysql密码
- C language number prime
- Copy entire directory to output folder maintain folder structure- Copy entire directory to output folder maintaining the folder structure?
- Global communication infrastructure faces apt, robotics and DDoS; The weakest mobile network
- C language continues (3n+1) conjecture
猜你喜欢
Implementation of a simple camera based on pyqt5
【银河麒麟V10】【桌面】火狐浏览器设置主页不生效
![[graph neural network] overview of graph classification learning [2]: graph classification based on graph neural network](/img/5f/b23b64eed7f28ffd92c122b6859e2d.png)
[graph neural network] overview of graph classification learning [2]: graph classification based on graph neural network
What should I do when I feel confused after graduation from university?
DMX configuration
013_ slider
003_ color
UE5的蓝图节点拷贝到UE4后连线和属性值全部丢失了
Share the source code of the website of graduation student record
The (3n+1) conjecture that C language kills people without paying for their lives
随机推荐
A summary of the quantification of deep network model
8 — router
DDoS threat situation gets worse
[MySQL 06] backup and restore MySQL database in Linux + docker container environment
[MySQL 04] use MySQL workbench 8.0 CE to back up and restore MySQL databases in Linux
208. implement trie (prefix tree) - attach detailed notes
【银河麒麟V10】【桌面】火狐浏览器设置主页不生效
AI landing manufacturing: intelligent robots should have these four abilities
Internet Crime Complaint Center reports an increase in DDoS Attacks
If mybaits cannot query the data, it can query how to change it in the database
Openlayers 3 built in interaction
Tools and life services
Local page floating animation is realized with the help of scroll wheel
33Mysql
Share the source code of the website of graduation student record
Upload, use of Avatar
005_ button
scp远程拷贝命令记录
C language output integer in another format
widget使用setImageViewBitmap方法设置bug分析