After the sequence list is the linked list , Linked list is the second structure of linear list .

( single ) Linked list according to 《 data structure 》 This book Write initialization is required , insert , lookup , delete , Length function .

The first is the definition of structure ：

Each node of the linked list consists of its own data , Address composition of the next node .

typedef It means alias . hold lei This nickname to int  The data type of linear table can be changed directly
typedef int lei; struct ss { lei data; ss *next; };
The first is the initialization function . Here is a list with a head pointer , So just need to new A head node , Let the head node next point NULL.
ss* chushihua() { ss*L=new ss; L->next=NULL; return L; }
The second is the length function . Just let a temporary pointer point to the head pointer , And just go through it all the time , Finally return the length of the linked list .
int size(ss* L) { int len=0; while(L->next !=NULL) { L=L->next; len++; }
return len; }
The third is the lookup function , According to the requirements of the book , There are two kinds of lookup functions , One is to search by number .

Can let L The pointer goes on and on , When L The next node of is an empty node or stops at the required number .

If this time L Not empty cut cnt== Sequence number required , This indicates that the node exists , Just go back ; Otherwise, a null pointer is returned to indicate that it does not exist .
ss* find_num(ss *L,int xuhao) { int cnt=0; while(L->next!=NULL && cnt<xuhao) {
L=L->next; cnt++; } if(cnt==xuhao && L) return L; return NULL; }
The second is to search by value , This is a little more brainless , Go through it all the time , Until you find or find the end , If it is found, it will return , If it is not found, it will automatically return a null pointer .
ss* find_data(ss* L,lei data) { L=L->next; while(L && L->data!=data) {
L=L->next; } return L; }
The fourth is the insertion function . First find out whether this location can be checked , If the previous one of the positions is empty , It returns an error .

otherwise new A new node , The next node of the new node points to now n-1 The next node of , Let's now n-1 The node of points to the new node , That's how the transfer is done , return true.
bool charu(ss* L,lei data,int weizhi) { ss *a; ss *b=L; int cnt=0; while(b &&
cnt < weizhi - 1 ) { b=b->next; cnt++; } if(b==NULL||cnt!=weizhi - 1) {
cout<<" Wrong insertion position "<<endl; return false; } a=new ss; a->data=data; a->next=b->next;
b->next=a; return true; }
The fifth is the delete function .

First find the previous location where you need to delete the node , If the node to be deleted does not exist , Return to false.

If it exists , Let delete the node's previous node's next Point to the next, Then release the nodes that need to be deleted .
bool shanchu(ss *L,int weizhi) { ss *a; ss *b=L; int cnt=0; while(b &&
cnt<weizhi-1) { b=b->next; cnt++; } if(b==NULL ||b->next == NULL|| cnt!=weizhi
- 1) { cout<<" Delete error "<<endl; return false; } a=b->next; b->next = a->next;
free(a); return true; }
Next is the full code ：
#include<iostream> #include<algorithm> #include<cstring> using namespace std;
typedef int lei; struct ss { lei data; ss *next; }; ss* chushihua() { ss*L=new
ss; L->next=NULL; return L; } int size(ss* L) { int len=0; while(L->next
!=NULL) { L=L->next; len++; } return len; } ss* find_num(ss *L,int xuhao) { int
cnt=0; while(L->next!=NULL && cnt<xuhao) { L=L->next; cnt++; } if(cnt==xuhao &&
L) return L; return NULL; } ss* find_data(ss* L,lei data) { L=L->next; while(L
&& L->data!=data) { L=L->next; } return L; } bool charu(ss* L,lei data,int
weizhi) { ss *a; ss *b=L; int cnt=0; while(b && cnt < weizhi - 1 ) { b=b->next;
cnt++; } if(b==NULL||cnt!=weizhi - 1) { cout<<" Wrong insertion position "<<endl; return false; }
a=new ss; a->data=data; a->next=b->next; b->next=a; return true; } bool
shanchu(ss *L,int weizhi) { ss *a; ss *b=L; int cnt=0; while(b && cnt<weizhi-1)
{ b=b->next; cnt++; } if(b==NULL ||b->next == NULL|| cnt!=weizhi - 1) {
cout<<" Delete error "<<endl; return false; } a=b->next; b->next = a->next; free(a);
return true; } int main() { ss *L=chushihua(); cout<<" The length of the list is ："<<size(L)<<endl;
charu(L,1,1); charu(L,3,2); charu(L,5,3); cout<<" The length of the list is ："<<size(L)<<endl;
cout<<" No 1 The address of the element of ："<<find_num(L,1)<<endl;
cout<<" No 2 The address of the element of ："<<find_num(L,2)<<endl; cout<<" The value is 3 The address of the element of
："<<find_data(L,3)<<endl; cout<<" The length of the list is ："<<size(L)<<endl; cout<<" Delete the last element
"<<endl; shanchu(L,3); cout<<" The length of the list is ："<<size(L)<<endl; return 0; }

Technology
Daily Recommendation
views 2