Data structure exercise set assignment code (Chapter 2)

LauJiYeoung 2022-05-22 12:06:28 阅读数:704

datastructureexercisesetassignment

2.11- Sequence table insert elements

Description

Set the order table va The data in the is incrementally ordered . Write an algorithm , take x Insert into the appropriate place in the sequence table , To ensure order .

Input
The input is divided into two lines , The first line is va The order sheet , Separate each element by space , The second line is x Value .

The maximum number of elements in the sequence table is 100 individual , All elements have values greater than 0, The element is an integer .

Output
Output insert x after ,va Result

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct PolyNode{

int sum;
struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,int sum){

if(head==NULL){

return init(sum);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
pre=head;
if(head->sum>sum){

now->next=head;
return now;
}
else{

while(pre->next!=NULL&&pre->next->sum<now->sum){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
return head;
}
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
do{

printf("%d ",pre->sum);
pre=pre->next;
}while(pre!=NULL);
}
char c;
int x;
int main(){

struct PolyNode * head=NULL;
while((c=getchar())!='\n'){

int x=0;
int f=1;
while(c<'0'||c>'9'){

if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){

x=x*10+c-'0';
c=getchar();
}
x*=f;
int sum=x;
head=ins(head,sum);
if(c=='\n'||c==EOF)break;
}
scanf("%d",&x);
head=ins(head,x);
Print(head);
return 0;
}

2.12- Sequence table comparison

Description

set up A = ( a 1 , . . . , a m ) A=(a_1,...,a_m) A=(a1,...,am) and B = ( b 1 , . . . , b n ) B=(b_1,...,b_n) B=(b1,...,bn) All are sequential tables ,A ′ and B’ , respectively, A and B The sub tables after removing the maximum common prefix in are A and B The sub table after removing the maximum common prefix from the ( for example ,A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z), Then the biggest common prefix between the two is (x,y,y,z), The sub tables after removing the maximum common prefix in the two tables are
 Insert picture description here
Input
Enter in two lines , Represent the A and B The elements in , Separated by commas . Each sequential table has a maximum of 100 Elements .
Output
Output A and B The comparison of ,0 representative A=B,1 representative A<B,2 representative A>B

#include<string.h>
#include<stdio.h>
char A[1000],B[1000];
int main(){

scanf("%s%s",A,B);
int cmp=strcmp(A,B);
if(cmp<0)printf("1");
if(cmp==0)printf("0");
if(cmp>0)printf("2");
return 0;
}

2.15- List merge

Description

Known pointer ha and hb The two nodes of the chain point to the single head of the table respectively , And it is known that the length of the two linked lists is m and n. Try to write an algorithm to connect the two linked lists ( That is, the first element node of one table is connected after the last node of the other table ), Hypothetical pointer hc Point to the head node of the linked list after connection , The algorithm is required to complete the link operation in the shortest possible time .
Input
The input consists of three lines , The first row is the length of the two linked lists m and n, The second and third rows are linked lists ha and hb The elements in , Space off .

Output
Output the merged linked list hc, Elements are separated by spaces

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct PolyNode{

int sum;
struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,int sum){

if(head==NULL){

return init(sum);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
pre=head;
while(pre->next!=NULL){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
return head;
}
struct PolyNode * Merge(struct PolyNode *ha,struct PolyNode *hb){

struct PolyNode *a=ha, *b=hb;
while(a->next!=NULL&&b->next!=NULL){

a=a->next;
b=b->next;
}
if(a->next==NULL){

a->next=hb;
return ha;
}
else{

b->next=ha;
return hb;
}
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
if(head==NULL){

printf("NULL");
return;
}
do{

printf("%d ",pre->sum);
pre=pre->next;
}while(pre!=NULL);
}
char c;
int n,m,x,i;
int main(){

struct PolyNode * ha=NULL, * hb=NULL, *hc=NULL;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i){

scanf("%d",&x);
ha=ins(ha,x);
}
for(i=1;i<=m;++i){

scanf("%d",&x);
hb=ins(hb,x);
}
hc=Merge(ha,hb);
Print(hc);
return 0;
}

2.18- List delete elements

Description
Try to write an algorithm , The linear table operation is realized on the dynamic single linked list without head node DELETE(L,i).
Input
The input contains two lines , The first row is the elements in the linked list , The second line indicates the second line that needs to be deleted i Elements ,i from 0 Start counting
If deleted , The linked list does not contain elements , The output “NULL”.
Output
Output the deleted linked list elements

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct PolyNode{

int sum;
struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,int sum){

if(head==NULL){

return init(sum);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
pre=head;
while(pre->next!=NULL){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
return head;
}
struct PolyNode * del(struct PolyNode *head,int idx){

struct PolyNode *ret, *pre, *suc;
if(idx==0){

ret=head->next;
free(head);
return ret;
}
pre=head;
idx--;
while(idx){

pre=pre->next;
idx--;
}
if(pre->next!=NULL)
suc=pre->next->next;
else suc=NULL;
if(pre->next!=NULL)
free(pre->next);
pre->next=suc;
return head;
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
if(head==NULL){

printf("NULL");
return;
}
do{

printf("%d ",pre->sum);
pre=pre->next;
}while(pre!=NULL);
}
char c;
int x;
int main(){

struct PolyNode * head=NULL;
while((c=getchar())!='\n'){

int x=0;
int f=1;
while(c<'0'||c>'9'){

if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){

x=x*10+c-'0';
c=getchar();
}
x*=f;
int sum=x;
head=ins(head,sum);
if(c=='\n'||c==EOF)break;
}
scanf("%d",&x);
head=del(head,x);
Print(head);
return 0;
}

2.19- The linked list deletes the elements in the specified range

Description
It is known that the elements in a linear table are arranged in increasing order , And take the single linked list as the storage structure . Try to write an efficient algorithm , Delete all values greater than in the table mink And less than maxk The elements of ( If such an element exists in the table ), At the same time, the space of deleted nodes is released .
Be careful :mink and maxk Are given two parameter variables , Their values can be the same as the elements in the table , It can be different .
Input
The input contains two lines , The first row is the elements in the linked list , Space off .
The second line is mink and maxk Two elements , Space off .
Output
Output the elements in the last linked list

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char c;
int x,L,R;
typedef struct PolyNode{

int sum;
struct PolyNode *next;
}PolyNode;
struct PolyNode * init(int sum){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,int sum){

if(head==NULL){

return init(sum);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
pre=head;
while(pre->next!=NULL){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
return head;
}
struct PolyNode * del(struct PolyNode *head){

struct PolyNode *now=head,*ha=head,*pre;
while(now!=NULL){

if(now->sum>L&&now->sum<R){

if(now==ha){

ha=now->next;
free(now);
now=ha;
}
else{

pre=ha;
while(pre->next!=now){

pre=pre->next;
}
pre->next=now->next;
free(now);
now=pre;
}
}
else
now=now->next;
}
return ha;
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
if(head==NULL){

printf("NULL");
return;
}
do{

printf("%d ",pre->sum);
pre=pre->next;
}while(pre!=NULL);
}
int main(){

struct PolyNode * head=NULL;
while((c=getchar())!='\n'){

int x=0;
int f=1;
while(c<'0'||c>'9'){

if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){

x=x*10+c-'0';
c=getchar();
}
x*=f;
int sum=x;
head=ins(head,sum);
if(c=='\n'||c==EOF)break;
}
scanf("%d %d",&L,&R);
head=del(head);
Print(head);
return 0;
}

2.22- The linked list is reversed in place

Description
Try to write an algorithm , Realize the local inversion of single linked list
Input
Enter all the elements of the given linked list , Separated by commas
Output
The output is the result of reverse linked list , Separated by commas

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char c;
typedef struct PolyNode{

char sum;
struct PolyNode *next;
}PolyNode;
struct PolyNode * init(char sum){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,char sum){

if(head==NULL){

return init(sum);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
pre=head;
while(pre->next!=NULL){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
return head;
}
struct PolyNode * Reverse(struct PolyNode *head){

struct PolyNode *now=head->next,*pre=head,*tmp;
while(now!=NULL){

tmp=now->next;
now->next=pre;
pre=now;
now=tmp;
}
head->next=NULL;
return pre;
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
if(head==NULL){

printf("NULL");
return;
}
printf("%c",pre->sum);
pre=pre->next;
do{

printf(",%c",pre->sum);
pre=pre->next;
}while(pre!=NULL);
}
int main(){

struct PolyNode * head=NULL;
while((c=getchar())!='\n'&&c!=EOF){

if(c==',')continue;
else head=ins(head,c);
}
head=Reverse(head);
Print(head);
return 0;
}

2.29- Modify linked list

Description

It is known that A,B and C For three linear tables with increasing order , Now it is required to A The table does the following : Delete those existing B It appears in the table again C Elements appearing in the table . Try to write the algorithm to realize the above operation for the sequence table .

Input
The input contains three lines , Respectively ABC Elements in three linear tables , Separated by commas

Output
After the output operation A Elements in table

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char c;
int i;
typedef struct PolyNode{

char sum;
struct PolyNode *next;
}PolyNode;
struct PolyNode * init(char sum){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,char sum){

if(head==NULL){

return init(sum);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
pre=head;
while(pre->next!=NULL){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
return head;
}
struct PolyNode * del(struct PolyNode *head,char idx){

struct PolyNode *ret, *pre, *suc;
if(idx==head->sum){

ret=head->next;
free(head);
return ret;
}
pre=head;
while(pre->next!=NULL&&pre->next->sum!=idx){

pre=pre->next;
}
if(pre->next!=NULL)
suc=pre->next->next;
else suc=NULL;
if(pre->next!=NULL)
free(pre->next);
pre->next=suc;
return head;
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
if(head==NULL){

printf("NULL");
return;
}
printf("%c",pre->sum);
pre=pre->next;
if(pre==NULL)return;
do{

printf(",%c",pre->sum);
pre=pre->next;
}while(pre!=NULL);
}
struct PolyNode * operate(struct PolyNode *ha,struct PolyNode *hb,struct PolyNode *hc){

struct PolyNode *a=ha,*b=hb,*c=hc,*now,*ret=ha;
while(a!=NULL){

while(b!=NULL&&b->sum<a->sum){

b=b->next;
}
while(c!=NULL&&c->sum<a->sum){

c=c->next;
}
if(b!=NULL&&c!=NULL){

if(a->sum==b->sum&&a->sum==c->sum){

now=a->next;
ret=del(ret,a->sum);
a=now;
}
else{

a=a->next;
}
}
else a=a->next;
}
return ret;
}
char s[1000+10];
int main(){

struct PolyNode * ha=NULL,* hb=NULL,* hc=NULL;
scanf("%s",s);
for(i=0;i<strlen(s);++i){

if(s[i]!=',')ha=ins(ha,s[i]);
}
scanf("%s",s);
for(i=0;i<strlen(s);++i){

if(s[i]!=',')hb=ins(hb,s[i]);
}
scanf("%s",s);
for(i=0;i<strlen(s);++i){

if(s[i]!=',')hc=ins(hc,s[i]);
}
ha=operate(ha,hb,hc);
Print(ha);
return 0;
}

2.38- Two way circular linked list access

Description
There is a two-way circular linked list , In each node except prior,data and next Three extraterritorial , An access frequency domain is also added freq. Before the linked list is enabled , Frequency domain freq The values of are initialized to 0, And every time the linked list is checked LOCATE(L,x) After operation , Visited node ( That is, the element value is equal to x The node of ) Frequency domain in freq The value of increases 1, At the same time, adjust the order of nodes in the linked list , Arrange them in non increasing order of access frequency , In order to always keep the frequently accessed node close to the header node . Prepare a report that meets the above requirements LOCATE Operation algorithm .
Input
The input contains three lines , The first row is the number of elements in the linked list , The second row is the elements in the linked list , The third line contains all the accessed elements
Output
Sequentially output the elements in the linked list starting from the header node .
Be careful : If multiple elements are accessed the same number of times , It needs to be accessed in order , Put the first accessed element in front

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int i,n;
typedef struct PolyNode{

int sum,freq,Tim;
struct PolyNode *next, *pre;
}PolyNode;
struct PolyNode * init(int sum,int freq){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->freq=freq;
now->Tim=0;
now->next=NULL;
now->pre=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,int sum,int freq){

if(head==NULL){

return init(sum,freq);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->sum=sum;
now->freq=freq;
now->Tim=0;
pre=head;
while(pre->next!=NULL){

pre=pre->next;
}
now->next=pre->next;
pre->next=now;
now->pre=pre;
return head;
}
struct PolyNode * Convert(struct PolyNode *head){

struct PolyNode *now=head;
while(now->next!=NULL){

now=now->next;
}
now->next=head;
head->pre=now;
return head;
}
struct PolyNode * Modify(struct PolyNode *head,int sum,int Tim){

struct PolyNode * now=head,*pre;
// printf("%d\n",sum);
do{

// printf("%d ",now->sum);
if(now->sum==sum){

if(now->Tim==0)now->Tim=Tim;
now->freq++;
now->pre->next=now->next;
now->next->pre=now->pre;
if(now==head)head=now->next;
pre=head;
while((pre->freq>now->freq||(pre->freq==now->freq&&pre->Tim<now->Tim))&&pre->next!=head)
pre=pre->next;
if(pre->next==head&&(pre->freq>now->freq||(pre->freq==now->freq&&pre->Tim<now->Tim))){

pre=pre->next;
now->pre=pre->pre;
now->pre->next=now;
now->next=pre;
pre->pre=now;
return head;
}
// printf("sum=%d freq=%d\n",pre->sum,pre->freq);
now->pre=pre->pre;
now->pre->next=now;
now->next=pre;
pre->pre=now;
// printf("%p %p\n",head,pre);
if(pre==head)return now;
else return head;
break;
}
now=now->next;
// printf("%p %p\n",head,now);
}while(now!=head);
return head;
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
if(head==NULL){

printf("NULL");
return;
}
do{

printf("%d ",pre->sum);
pre=pre->next;
}while(pre!=head);
}
struct PolyNode * operate(struct PolyNode *head){

return ;
}
int main(){

struct PolyNode * head=NULL;
scanf("%d",&n);
for(i=1;i<=n;++i){

int x;
scanf("%d",&x);
head=ins(head,x,0);
if(n==1){

printf("%d",x);
return 0;
}
}
head=Convert(head);
int Tim=0;
char c;
c=getchar();
while((c=getchar())!='\n'){

int x=0;
int f=1;
while(c<'0'||c>'9'){

if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){

x=x*10+c-'0';
c=getchar();
}
x*=f;
int sum=x;
head=Modify(head,sum,++Tim);
if(c=='\n'||c==EOF)break;
// Print(head);
}
Print(head);
return 0;
}

2.41- Sparse polynomial derivation
Description

Try to use the circular linked list as the storage structure of sparse polynomials , Write an algorithm to find its derivative function , It is required to use the node space in the original polynomial to store its derivative function ( polynomial ), Release all useless at the same time ( Deleted ) node .

The circular linked list storage structure used in sparse polynomials LinkedPoly Defined as

typedef struct PolyNode{

PolyTerm data;
Struct PolyNode *next;
} PolyNode, *PolyLink;
typedef PolyLink LinkedPoly;

Input
The input is a given polynomial

Output
The output is the result after derivation , Rank from high to low according to the power of each term in the polynomial

If the derivative is 0, The output 0

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct PolyTerm{

int sum,power;
}PolyTerm;
typedef struct PolyNode{

struct PolyTerm data;
struct PolyNode *next;
}PolyNode, *PolyLink;
struct PolyNode * init(int sum,int power){

struct PolyNode *now=malloc(sizeof(struct PolyNode));
memset(now,0,sizeof(struct PolyNode));
now->data.sum=sum;
now->data.power=power;
now->next=NULL;
return now;
}
struct PolyNode * ins(struct PolyNode *head,int sum,int power){

// printf("%d %d\n",sum,power);
if(head==NULL){

return init(sum,power);
}
struct PolyNode *now=malloc(sizeof(struct PolyNode)),*pre;
memset(now,0,sizeof(struct PolyNode));
now->data.sum=sum;
now->data.power=power;
pre=head;
if(head->data.power<now->data.power){

now->next=head;
return now;
}
else{

if(head->data.power==power){

head->data.sum+=sum;
return head;
}
while(pre->next!=NULL&&pre->next->data.power>now->data.power){

pre=pre->next;
}
if(pre->next!=NULL&&pre->next->data.power==now->data.power){

pre->next->data.sum+=sum;
return head;
}
now->next=pre->next;
pre->next=now;
return head;
}
}
struct PolyNode * del(struct PolyNode *now){

struct PolyNode * pre=now;
// printf("%p\n%p\n",now,now->next);
if(now->next==now){

free(now);
return NULL;
}
while(pre->next!=now){

pre=pre->next;
}
pre->next=now->next;
free(now);
return pre;
}
void convert(struct PolyNode *head){

struct PolyNode * pre=head;
if(head==NULL)return;
while(pre->next!=NULL){

pre=pre->next;
}
pre->next=head;
}
struct PolyNode * derivation(struct PolyNode * head){

if(head==NULL)return NULL;
struct PolyNode * now=head;
do{

now->data.sum*=now->data.power;
now->data.power-=(now->data.power!=0);
now=now->next;
}while(now!=head);
do{

if(now->data.sum==0){

now=del(now);
}
if(now==NULL)break;
now=now->next;
}while(now!=head&&now!=NULL);
if(now==NULL)return NULL;
else return head;
}
void Print(struct PolyNode * head){

struct PolyNode * pre=head;
do{

struct PolyTerm now=pre->data;
if(now.sum<0){

printf("- ");
now.sum=-now.sum;
}
else{

if(pre!=head)
printf("+ ");
}
printf("%d",now.sum);
if(now.power!=0){

printf("x");
if(now.power>1){

printf("^");
printf("%d",now.power);
}
}
if(pre->next!=head)
printf(" ");
pre=pre->next;
}while(pre!=head);
}
char c;
int stack[10000];
int main(){

struct PolyNode * head=NULL;
int current=1;
while((c=getchar())!=EOF&&c!='\n'){

int x=0;
int f=1;
while(c<'0'||c>'9'){

if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){

x=x*10+c-'0';
c=getchar();
}
x*=f;
stack[++stack[0]]=x;
if(current==2){

int power=stack[stack[0]--];
int sum=stack[stack[0]--];
head=ins(head,sum,power);
current=1;
}
else{

if(c=='x'){

c=getchar();
if(c=='^'){

current=2;
}
else{

int sum=stack[stack[0]--];
head=ins(head,sum,1);
}
if(c=='\n'||c==EOF)break;
}
else{

int sum=stack[stack[0]--];
head=ins(head,sum,0);
}
}
// printf("%c\n",c);
if(c=='\n'||c==EOF)break;
// puts("in");
}
convert(head);
head=derivation(head);
if(head==NULL){

printf("0");
}
else{

Print(head);
}
return 0;
}
copyright:author[LauJiYeoung],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/142/202205211805585396.html