Data structure (C language) experiment-singly linked list

Singly linked list without head node

Inverted linked list

Assume that the linear table (a1, a2, a3,…an) is stored in a singly linked list without a head node,
Please design the algorithm function linklist reverse1(linklist head) and
void reverse2(linklist *head) inverts the head of a singly linked list without a head node in place,
Make the table become (an,an-1,…a3.a2,a1). And construct test cases for testing.

linklist reverse1(linklist head)
{
    linklist p;
    linklist new_list;
    new_list = NULL;
    p = NULL;
    while (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL) {
        p = head;
        head = head->next;
        p->next = new_list;//The p node is inserted into the head of the linked list
        new_list = p; // Update the new_list pointer at the head of the linked list
    }
    return new_list;
}

Insert node

Assuming that the head of a singly linked list without a head node is arranged in ascending order, design the algorithm function linklist insert(linklist head,datatype x),
Insert the node with value x into the head of the linked list and maintain the order of the linked list.
Construct test cases for inserting into the header, middle and tail of the table for testing.

linklist insert(linklist head,datatype x)
{
    linklist p = head;
    if(p->info > x) { //Judge table header
        linklist dummy = (linklist*)malloc(sizeof(linklist));
        dummy->info = x;
        dummy->next = head;
        return dummy;
    }
    while(p->next) {
        if (p->next->info > x) {
            linklist dummy = (linklist*)malloc(sizeof(linklist));
            dummy->info = x;
            dummy->next = p->next;
            p->next = dummy;
            return head;
        } else {
            p = p->next;
        }
    }
    linklist dummy = (linklist*)malloc(sizeof(linklist));
    dummy->info = x;
    dummy->next = NULL;
    p->next = dummy;
    return head;
}

Appendix

#include <stdio.h>
#include <stdlib.h>
/******************************************/
/* Header file for linked list implementation, file name slnklist.h */
/******************************************/
 typedef int datatype;
 typedef struct link_node{
   datatype info;
   struct link_node *next;
 }node;
typedef node *linklist;

/************************************/
/*Function name: creatbystack() */
/*Function: Head interpolation method to create a singly linked list */
/************************************/
linklistcreatbystack()
{ linklist head,s;
    datatype x;
    head=NULL;
    printf("Please enter some integer sequences:\
");
    scanf("%d", & amp;x);
    while (x!=0) /*End input with 0*/
    { s=(linklist)malloc(sizeof(node)); /*Generate the node to be inserted*/
        s->info=x;
        s->next=head; /*Insert the new node to the front of the linked list*/
        head=s;
        scanf("%d", & amp;x);
    }
    return head; /*Return the created singly linked list*/
}
/************************************/
/*Function name: creatbyqueue() */
/*Function: Create a singly linked list using tail insertion method */
/************************************/
linklistcreatbyqueue()
{
    linklist head,r,s;
    datatype x;
    head=r=NULL;
    printf("Please enter some integer sequences:\
");
    scanf("%d", & amp;x);
    while (x!=0) /*End input with 0*/
    { s=(linklist)malloc(sizeof(node));
         s->info=x;
         if (head==NULL) /*Insert the new node into the end of the linked list*/
            head=s;
         else
            r->next=s;
        r=s;
        scanf("%d", & amp;x);
   }
    if (r) r->next=NULL;
    return head; /*Return the created singly linked list*/
}
/************************************/
/*Function name: print() */
/*Function: Output a singly linked list without a head node */
/************************************/
void print(linklist head)
{ linklist p;
    int i=0;
    p=head;
    printf("List is:\
");
    while(p)
    {
        printf("]",p->info);
        p=p->next;
         i + + ;
if (i ==0) printf("\
");
    }
    printf("\
");
}
/************************************/
/*Function name: delList() */
/*Function: Release a singly linked list without a head node */
/************************************/
void delList(linklist head)
{ linklist p=head;
  while (p)
  { head=p->next;
    free(p);
    p=head;
  }
}

Singly linked list with head node

Inverted linked list

Assuming that the linear list (a1, a2, a3,…an) is stored in a single linked list with the head node, please design the algorithm function void reverse (linklist head),
Invert the singly linked list head of the head node in place, so that the list becomes (an, an-1,…a3.a2,a1). And construct test cases for testing.

//For example, h->1->2->3,h->1 2->3,h->2->1 3,h->3->2->1
void reverse(linklist head)
{
    //There is no element or an element returns directly
    if (head->next == NULL || head->next->next == NULL) {
        return;
    }
    linklist pre,cur;
    cur = head->next;
    pre = NULL;
    //Disconnect the head node
    head->next = NULL;
    while(cur != NULL) {
        //Update pre and cur pointers
        pre = cur;
        cur = cur->next;
        //Header insertion method inserts nodes
        pre->next = head->next;
        head->next = pre;
    }
}

Insert node

Assuming that the head of the singly linked list with the head node is arranged in ascending order, design the algorithm function linklist insert(linklist head,datatype x),
Insert the node with value x into the head of the linked list and maintain the order of the linked list.
Construct test cases for inserting into the header, middle and tail of the table for testing.

void insert(linklist head,datatype x)
{
    linklist pre,cur,dummy;
    //Create the inserted node dummy
    dummy = (linklist*)malloc(sizeof(linklist));
    dummy->info = x;
    pre = head;
    cur = head->next;
    //Find the position where x is inserted
    while (cur & amp; & amp; cur->info < x) {
        pre = cur;
        cur = cur->next;
    }
    //Insert dummy node
    pre->next = dummy;
    dummy->next = cur;
    return head;
}

Find the address of the k-th node from the bottom

Write a program to return the address of the k-th node from the last in the singly linked list of the leading node as quickly as possible. If it does not exist, return NULL.

linklist search(linklist head,int k)
{
    /*linklist p,x;
    p = head->next;
    x = p;
    int cnt = 0;
    //Calculate the length of the linked list
    while (x) {
        cnt + + ;
        x = x->next;
    }
    //Cannot find node
    if (k > cnt) {
        return NULL;
    }
    //Find the kth node from the bottom
    for (int i = 0; i < cnt - k; i + + ) {
        p = p->next;
    }
    return p;*/
    linklist fast = head;
    linklist slow = head;
    //flag is used to record whether k is not within the range
    int flag = 0;
    //The fast pointer moves k steps
    for(int i = 0; i < k & amp; & amp; fast; i + + ) {
        fast = fast->next;
    }
    //Slow pointer and fast pointer move together
    while(fast) {
        fast = fast->next;
        slow = slow->next;
        flag = 1;
    }
    return flag == 1 ? slow : NULL;
}

Polynomial addition

#include <stdlib.h>
#include <stdio.h>

typedef struct node
{ int coef; /*Coefficient*/
        int expn; /*exponent*/
        struct node *next;
}listnode; //Polynomial storage structure

typedef listnode *linklist;
void delList(linklist head);

 /*
 Function name: creat()
 Function: Establish a polynomial storage structure, and store polynomials in the table according to the exponent of the item in which they are located.
 */
linklist creat() //Create a polynomial storage structure,
{
      linklist head,s,p,pre,r;
      int coef;
      int expn;
      head=(linklist)malloc(sizeof(listnode)); /*Generate head node*/
      head->next=NULL;
      printf("Please enter the polynomial. Each term only needs to enter the coefficient and exponent (end the input when the entered coefficient is 0):\
");
      scanf("%d", & amp;coef); //Input coefficient
      scanf("%d", & amp;expn); //Input exponent
      p = head;
      while (coef!=0) //Please fill in the appropriate code here
      {
         s = (linklist)malloc(sizeof(listnode)); //Insert new node
         s->coef = coef;
         s->expn = expn;
         s->next = NULL;
         head->next = s; //Move head pointer backward
         head = s;
         scanf("%d", & amp;coef); //Input coefficient
         scanf("%d", & amp;expn); //Input exponent
         //printf("while");
      }
     return p;
}

void print(linklist head) //Output polynomial
  {
        linklist p;
        p=head->next;
        while (p)
        { printf("%d(X)",p->coef);
            printf("%d ",p->expn);
            p=p->next;
        }
        printf("\
");
 }

 /*
 Function name: add()
 Function function: polynomial addition
 Entry parameters: a and b are single-linked lists of leading nodes that store polynomials, and polynomials are stored in the list according to the exponent of the item in which they are located.
 */
linklist add(linklist a,linklist b) //Please complete this function
{
    linklist pa,pb,c,pc,r;
    pa = a;
    pb = b;
    c = (linklist)malloc(sizeof(listnode));
    c->next = NULL;
    pc = c;
    while (pa & amp; & amp; pb) {
        if (pa->expn == pb->expn) {
            r = (linklist)malloc(sizeof(listnode));
            //Add two polynomials
            r->expn = pa->expn;
            r->coef = pa->coef + pb->coef;
            r->next = NULL;
            //Insert into c linked list
            pc->next = r;
            pc = r;
            //Double pointers move backward
            pa = pa->next;
            pb = pb->next;
        } else if (pa->expn < pb->expn) {
            r = (linklist)malloc(sizeof(listnode));
            //Insert node a into c
            r->expn = pa->expn;
            r->coef = pa->coef;
            r->next = NULL;
            pc->next = r;
            pc = r;
            //pa moves back
            pa = pa->next;
        } else {
            r = (linklist)malloc(sizeof(listnode));
            //Insert node b into c
            r->expn = pb->expn;
            r->coef = pb->coef;
            r->next = NULL;
            pc->next = r;
            pc = r;
            //pb moves back
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    return c->next;
}

int main()
 {
           linklist a,b,c;
           a=creat();
           printf("Polynomial a is: ");
           print(a);

           b=creat();
           printf("Polynomial b is: ");
           print(b);

           c=add(a,b);
           printf("The sum of two polynomials is:\
");
           print(c);
           delList(c);
           return 0;
 }
 /******************************************/
/*Function name: delList() */
/*Function: Release the singly linked list of the leading node */
/******************************************/
void delList(linklist head)
{ linklist p=head;
  while (p)
  { head=p->next;
    free(p);
    p=head;
  }
}

appendix

#include <stdio.h>
#include <stdlib.h>
/****************************************/
/* Header file for linked list implementation, file name slnklist.h */
/****************************************/
 typedef int datatype;
 typedef struct link_node{
        datatype info;
        struct link_node *next;
 }node;
typedef node *linklist;
/**********************************************/
/*Function name: creatbystack() */
/*Function: Head insertion method to create a singly linked list with head node */
/**********************************************/
linklistcreatbystack()
{

    linklist head,s;
    datatype x;
    head=(linklist)malloc(sizeof(node));
    head->next=NULL;

    printf("Please enter a sequence of integers (separated by spaces, ending with 0):\
");
    scanf("%d", & amp;x);
    while (x!=0)
    {
        s=(linklist)malloc(sizeof(node));
        s->info=x;

        s->next=head->next;
        head->next=s;

        scanf("%d", & amp;x);
    }
    return head;
}
/******************************************/
/*Function name: creatbyqueue() */
/*Function: tail insertion method to create a singly linked list with head node */
/******************************************/
linklistcreatbyqueue()
{
    linklist head,r,s;
    datatype x;
    head=r=(linklist)malloc(sizeof(node));
    head->next=NULL;
    printf("Please enter a sequence of integers (separated by spaces, ending with 0):\
");
    scanf("%d", & amp;x);
    while (x!=0)
    {
         s=(linklist)malloc(sizeof(node));
         s->info=x;
         r->next=s;
         r=s;
         scanf("%d", & amp;x);
   }
    r->next=NULL;
    return head;
}
/************************************/
/*Function name: print() */
/*Function: Output the singly linked list of the leading node */
/************************************/
void print(linklist head)
{
    linklist p;
    int i=0;
    p=head->next;
    printf("List is:\
");
    while(p)
    {
        printf("}",p->info);
        i + + ;
        if (i ==0) printf("\
");
        p=p->next;
    }
    printf("\
");

}

/******************************************/
/*Function name: creatLink() */
/*Function: Read n data from the file to form a singly linked list */
/******************************************/
linklist creatLink(char *f, int n)
{
    FILE *fp;
    int i;
    linklist s,head,r;
    head=r=(linklist)malloc(sizeof(node));
    head->next=NULL;
    fp=fopen(f,"r");
    if (fp==NULL)
        return head;
    else
    {
         for (i=0;i<n;i + + )
            {
                s=(linklist)malloc(sizeof(node));
                fscanf(fp,"%d", & amp;(s->info));
                r->next=s;
                r=s;
            }
        r->next=NULL;
        fclose(fp);
        return head;
    }
}

/*
    Function name: writetofile
    Function: Store the contents of the linked list into file f
*/
void writetofile(linklist head, char *f)
{
    FILE *fp;
    linklist p;
    int i=0;
    fp=fopen(f,"w");
    if (fp!=NULL)
    {
        p=head->next;
        fprintf(fp,"%s","List is:\
");
        while(p)
        {
            fprintf(fp,"}",p->info);
            i + + ;
            if (i ==0) fprintf(fp,"%c",'\
');
            p=p->next;
        }
        fprintf(fp,"%c",'\
');
        fclose(fp);
    }
    else printf("Failed to create file!");

}


/************************************/
/*Function name: delList() */
/*Function: Release the singly linked list of the leading node */
/************************************/
void delList(linklist head)
{ linklist p=head;
  while (p)
  { head=p->next;
    free(p);
    p=head;
  }
}