Linked list operation experiment

content

1. Experiment name and nature

2. The purpose of the experiment

3. Experimental content

4. Knowledge preparation

5. Experimental requirements

6. Code

1. Experiment name and nature

Course

data structure

Experiment name

Operations on linked lists

experimental hours

2

Experimental nature

□ Verification □ Synthesis √ Design

Required/Optional

√Required □Optional

2. The purpose of the experiment

1. Master the linked storage structure of linear table - the definition of singly linked list and its implementation in C language.

2. Master the various basic operations of linear table in linked storage structure - singly linked list.

3. Experimental content

1. Create a singly linked list with a head node, and the value range of the node is integer data. It is required to insert the data entered by the user by tail insertion method to establish the corresponding singly linked list.

2. Design a function to find the position of element x in the linked list and return 0 if x is not in the linked list.

3. Design a function to insert element x after the ith element. If i is greater than the length of the list, insert x at the end of the list; if i is less than or equal to 0, insert x directly after the head.

4. Counts the number of nodes in a known singly linked list whose data field value is a specified value x.

4. Knowledge preparation

In the early stage, it is required to be proficient in the programming rules and methods of C language, and the basic operation algorithms of singly linked list and doubly linked list.

5. Experimental requirements

The programming implements the following functions:

(1) According to a series of input integers, ending with a 0 mark, use the tail interpolation method to establish a singly linked list, and output the value of each element in the singly linked list, and observe whether the input content is consistent with the output content.

(2) Find the position of element x in the singly linked list, if it exists, return the serial number of the element, otherwise return 0.

(3) Insert an element whose value is x after the i-th element of the singly linked list. If i is greater than the length of the linked list, insert x at the end of the linked list; if i is less than or equal to 0, insert x directly after the header . And output the value of each element in the inserted singly linked list.

(4) Input x, count the number of nodes in the singly linked list with the same value as x, and return the number, if not, return 0.

6. Code

#include <bits/stdc++.h>
using namespace std;
#define OK 1 //Success ID
#define ERROR 0 //failure flag

typedef int status;	//Status is the type of the function, and its value is the function result status code, such as OK, etc.
typedef struct node{
	int data;		  //data field 
	struct node *next;//pointer field 
}Lnode,*List;

void creat(List &L,int n)//tail insertion 
{
	L=new node;
	L->next=NULL;//Create a new linked list with only one empty node
	List t=new node;
	t=L;
	cout<<"please enter n elements:"; 
	for(int i=0;i<n;i++)
	{
		List p=new node;//generate a new node 
		
		cin>>p->data ;//assign value to new node 
		p->next =NULL ; 
		t->next =p;//Insert this node after the tail node
		t=p;//Displacement so that t is always the last node 
	}
}

status find(List L,int e)
{
	List p=new node; 
	int j=0;
	p=L;//Mobile node p finds the node whose data field is e 
	while(p&&p->data !=e)//find 
	{
		p=p->next ;
		j++;
	}
	if(!p&&p->data !=e)
		return ERROR;
	return j;
}

status Insert(List &L,int i,int e)
{
	List p=new node;//Set p to move the node to assist in finding the i-th element 
	List t=new node;//Open new nodes for easy insertion 
	p=L;
	int j=0;//(Why is j=1 when looking up above, but it is equal to 0 here) Think about it! ! 
	if(i<=0)//After plugging into the head node 
	{
		t->data =e;//assign value to new node 
		t->next =p->next ;//points to the i-th node 
		p->next=t;//replace the position of the i-th node 
		return OK;
	}
	while(p&&j<i)//find the i-1 th node 
	{
		p=p->next ;
		j++;
	}
	if(!p||j>i)//error is return insert failed 
		return ERROR;
	t->data =e;//assign value to new node 
	t->next =p->next ;//points to the i-th node 
	p->next=t;//replace the position of the i-th node 
	return OK;
} 

status find1(List L,int e)//Find the specified number of elements 
{
	List p=new node; 
	int j=0;
	p=L;//Mobile node p finds the node whose data field is e 
	while(p)//find 
	{
		if(p->data ==e)
			j++;
		p=p->next ;
	}
	return j;
}

void Put(List L)
{
	cout<<"Current element in the table:"; 
	List p=new node;
	p=L->next ;
	while(p)
	{
		cout<<p->data<<' ' ;
		p=p->next ;
	}
	cout<<endl;
}

int main()
{
	int n;
	List L=new node;
	cout<<"Please enter the elements to create a linked list:";
	cin>>n; 
	creat(L,n);
	Put(L);
	cout<<"Enter the element to find:";
	int x,i;
	cin>>x;
	i=find(L,x); 
	cout<<"The element position:"<<i<<endl;
	cout<<"Enter the element to insert:";
	cin>>x;
	cout<<"Enter the element position to insert:";
	cin>>i;
	Insert(L,i,x);
	cout<<"Enter the element to find:";
	cin>>x;
	i=find1(L,x);
	cout<<"value is x the number of elements:"<<i;
	return 0;	
	
}

Tags: data structure linked list

Posted by kodlcan on Fri, 13 May 2022 01:17:59 +0300