Data structure experiment II - Implementation of single linked list

1, [experiment purpose]
1. Master the basic method of establishing single linked list.

2. Master the idea and implementation of single linked list insertion and deletion algorithm

2, [experiment content]

Follow the example of the single linked list implementation in the textbook, and design an ordered single linked list. The data elements in the single linked list are integer and incrementally ordered. Definition of ordered single linked list:

Logical structure: ordered linear table, data elements increasing orderly

Storage structure: Chain

Operation set: initialize, insert, delete, undo

(1)ListInitiate(L) initializes the linear table and generates an empty table L.

(2)ListInsert(L,x) inserts the data element x into the ordered Table L, so that the new table is still ordered.

(3)ListDelete(L,x) deletes the data element X in the ordered table L. if the deletion is successful, 1 is returned; if unsuccessful, 0 is returned.

(4)Destroy(L) undo single linked list

Requirements:

1. the operation set of the ordered single linked list includes the following operations: initialization, insertion, deletion, and revocation. The code of the header file single linked list is used.

2. write the main function main() to verify whether the designed ordered single linked list can be inserted and deleted correctly.

Tip:

1. when inserting, start from the first data element node of the linked list, compare the data field value of each node and the value of X one by one. When data is less than or equal to x, compare the next node; Otherwise, the appropriate position of the insertion node is found. At this time, apply for a new node to store x, and then insert the new node; When the last node still has data less than or equal to x, insert the new node into the end of the single chain table.

2. when deleting, start from the first data element node in the linked list, and compare the data field value and x value of each node one by one. When data is not equal to x, compare the next node; Otherwise, the node to be deleted will be found. After deleting the node, release the node. If the node with value x is not found at the end of the table, there is no element to delete in the linked list.

source code

Header file
typedef struct SingleNode
{
	ElemType data;
	struct SingleNode *next;
}SingleLinkedList;

void ListInitiate(SingleLinkedList **head)
{
	if((*head = (SingleLinkedList*)malloc(sizeof(SingleLinkedList)))==NULL)
		exit(1);
		(*head)->next = NULL;
}

void ListInsert(SingleLinkedList *head,ElemType x)
{
	SingleLinkedList *p, *q,*h;
	p = head->next;
	q = head;
	while(p!=NULL&&p->data <=x)
	{
		q = p;
		p = p->next;
	}
	h = (SingleLinkedList*)malloc(sizeof(SingleLinkedList));
	h-> data = x;
	h->next = q->next;
	q->next = h; 
}

int ListDelete(SingleLinkedList *head,ElemType x)
{
	SingleLinkedList *p, *q;
	p = head;
	while(p->next!= NULL)
	{
		if(p->next->data == x)
		{
		break;
		}
		p=p->next;
		
	}
	if(p->next == NULL)
		return 0;
	else
	{
		q=p->next;
		p->next = p->next->next;
		free(q);
		return 1;
	}

		
}

void Destroy(SingleLinkedList **head)
{
	SingleLinkedList *p, *q;
	p = *head;
	while(p != NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}
	*head = NULL;
}

int listlength(SingleLinkedList *head)
{
	SingleLinkedList *p=head;
	int size = 0;
	while(p->next!=NULL)
	{
		p=p->next;
		size++;
		
	}
	return size;
}


source file
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
#include"LinkedList.h"

int main(void)
{
	SingleLinkedList *head,*p;
	ListInitiate(&head);
	int x,n,i,s,t,m;
	printf("Please select how many numbers to enter:");
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		printf("Section%d The first number is:",i+1);
		scanf("%d",&x);
		ListInsert(head,x);
				 
	}
	p=head;
	for(i = 0;i < n;i++)
	{
		printf("%5d",p->next->data);
		p=p->next;
	}
	
	printf("\n Enter the number you want to delete:");
	scanf("%d",&s);
	
	m=ListDelete(head,s);
	if(m=0)
	printf("Delete failed");
	
	p=head;
	t=listlength(head);

	for(i = 0;i < t;i++)
	{
		
		printf("%5d",p->next->data);
		p=p->next;
	}
	return 0;
}

Tags: C data structure

Posted by Distant_storm on Mon, 30 May 2022 02:01:19 +0530