Sequential storage structure and chain storage structure of linear table and their simple operation (mixed use of C and C + +)
1, Preface:
In the first computer experiment when learning data structure, the teacher asked us to realize the sequential storage structure and chain storage structure of linear table and their simple operation. It was painful to watch. The codes in the book are all pseudo codes, which are typed out and n many errors are reported (we use the data structure and application algorithm program (Revised Version) compiled by Yan Weimin and Chen Wenbo of Tsinghua University Press) , the book is very good, but some places don't take care of beginners. Anyway, it's buzzing with brain melon seeds, but after understanding, it's full of a sense of achievement, which makes people love and hate. Interested partners can have a look); Search the results of predecessors on the Internet, and report 70 or 80 mistakes without exception (it may be my own reason, no other meaning).
In a rage, I stayed up for two nights and finally realized it (in the process of implementation, I also deeply realized how much a good compiler can help coders. When I wrote the sequence table, I used VC++6.0. I was bald when I found the wrong one. When I wrote the linked list, I changed VS2010, and there was a red wavy line at the wrong place. It was GA GA fast to correct the wrong one). I have always wanted to write a blog to record my efforts, but it always ended up for various reasons. Today I finally wrote this blog.
I won't introduce the concepts of sequence list and linked list. Once I search the Internet, there are many well written bloggers, so I won't repeat them; The following are the sequence list and its simple operations, and the linked list and its simple operations, which are implemented in c and c + +. Please find the specific operations in the header file comments (the comments inside may have some personal comments. I'm too lazy to delete them, so I'll make do with it)
2, Sequential storage structure of linear table and its simple operation (multi module):
First of all, we must create an empty project of WIN32 console application (when dividing multiple modules, we must pay attention to the introduction of header files for each source program file)
1. Create the header file Definition.h:
#include <stdio.h>
#Include < process. H > / / at least used in ErrorMessage
#Include < iostream. H > / / at least in ErrorMessage
const int LIST_INIT_SIZE=100;//Linear table (default) initial allocated maximum space
const int LISTINCREMENT=10;//Default amount of supplemental space
//Defines the SqList type of the linear table
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
int incrementsize;
}SqList;
//Initialization of sequence table
//C language has no default parameter usage, so it may be mixed with C and C + +
void InitList_Sq(SqList &L,int maxsize=LIST_INIT_SIZE,int incresize=LISTINCREMENT);
//Assign the first ten elements of the initialized sequence table to 1-10 respectively
void NatureList1_10_Sq(SqList &L);
//Sequential table lookup element
//Find the first element equal to e in L. if it can be found, return its bit order in L; otherwise, return 0
int LocateElem_Sq(SqList L,ElemType e);
/*The next three functions are to insert the sequence table*/
//Error message processing function
void ErrorMessage(char *s);
//Sequential table append space
void increment(SqList &L);
//Sequence table insert element
//Insert a new element E before the ith element of sequence table L, 1 < = i < = L.Length + 1. If the capacity is insufficient, expand the capacity according to the predefined increment
void ListInsert_Sq(SqList &L,int i,ElemType e);
//Sequence table delete element
//Delete the ith element in the sequence table L and return its value with e, 1 < = i < = L.Length
void ListDelete_Sq(SqList &L,int i,ElemType &e);//ErrorMessage is used
//Destruction of sequence table
//Free the storage space occupied by sequence table L
void DestroyList_Sq(SqList &L);
//Display of sequence table
//Because the order is reversed when looking for elements, in order to find out the reason, write a function to display the order table
void PrintList_Sq(SqList L);
2. Create the source program file InitList_Sq.cpp:
//Initialization of sequence table
//C language has no default constant usage, so it may be mixed with C and C + +
#include "Definition.h"
void InitList_Sq(SqList &L,int maxsize,int incresize)
{
L.elem=new ElemType[maxsize];//Allocate an array space with a maximum capacity of maxsize for the sequential table
L.length=0;
L.listsize=maxsize;
L.incrementsize=incresize;
}
3. Create the source program file NatureList1_10_Sq.cpp:
//Assign the first ten elements of the initialized sequence table to 1-10 respectively
#include "Definition.h"
void NatureList1_10_Sq(SqList &L)
{
for(int i=0;i<=9;i++)
{
L.elem[i]=i+1;
}
L.length=10;
}
4. Create the source program file LocateElem_Sq.cpp:
//Sequential table lookup element
//Find the first element equal to e in L. if it can be found, return its bit order in L; otherwise, return 0
#include "Definition.h"
int LocateElem_Sq(SqList L,ElemType e)
{
int i=1;
ElemType *p=L.elem;
while(i<=L.length && *(p++)!=e) i++;
if(i<=L.length) return i;
else return 0;
}//LocateElem_Sq5. Create the source program file ErrorMessage.cpp:
//Error message processing function
#include "Definition.h"
void ErrorMessage(char *s)
{
cout<<s<<endl;
exit(1);
}6. Create the source program file increment.cpp:
//Sequential table append space
#include "Definition.h"
void increment(SqList &L)
{
ElemType *a;//？？ Mark that there may be a problem here??
a=new ElemType [L.listsize+L.incrementsize];
for(int i=0;i<=L.length;i++)
a[i]=L.elem[i];
delete[] L.elem;
L.elem=a;
L.listsize=L.listsize+L.incrementsize;
}7. Create the source program file ListInsert_Sq.cpp:
//Sequence table insert element
//Insert a new element E before the ith element of sequence table L, 1 < = i < = L.Length + 1. If the capacity is insufficient, expand the capacity according to the predefined increment
#include "Definition.h"
void ListInsert_Sq(SqList &L,int i,ElemType e)
{
if(i<1||i>L.length+1)
ErrorMessage("i Illegal value");
if(L.length>=L.listsize)
increment(L);//'>' it should be OK
ElemType *q=&(L.elem[i-1]);
for(ElemType *p=&(L.elem[L.length-1]);p>=q;p--)
*(p+1)=*p;
*q=e;
L.length++;
}//ListInsert_Sq
8. Create source program file ListDelete_Sq.cpp:
//Sequence table delete element
//Delete the ith element in the sequence table L and return its value with e, 1 < = i < = L.Length
#include "Definition.h"
void ListDelete_Sq(SqList &L,int i,ElemType &e)
{
if((i<1)||(i>L.length))
ErrorMessage("i Illegal value");
ElemType *p=&(L.elem[i-1]);
e=*p;
ElemType *q=L.elem+L.length-1;
for(++p;p<=q;p++)
*(p-1)=*p;
L.length--;
}9. Create the source program file DestroyList_Sq.cpp:
//Destruction of sequence table
//Free the storage space occupied by sequence table L
#include "Definition.h"
void DestroyList_Sq(SqList &L)
{
delete[] L.elem;
L.listsize=0;
L.length=0;
}//DestroyList_Sq
10. Create source program file PrintList_Sq.cpp:
//Display of sequence table
//Because the time-finding order is reverse, in order to find out the reason, write a function to display the sequence table
#include "Definition.h"
void PrintList_Sq(SqList L)
{
printf("All elements of the current sequence table:");
for (int i=0;i<L.length; i++)
{
printf("%d ", L.elem[i]);
}
printf("\n");
}//PrintList_Sq11. Create (main function) source program file Main_Sq.cpp:
#include "Definition.h"
int main()
{
SqList A;
printf("\n\n");
int flag;
printf("******************************************************\n");
printf("*************choose the operation of List*************\n");
printf("*****************1-Initialization of sequence table*********************\n");
printf("*****************2-Get 1-10 Natural sequence table of***************\n");
printf("*****************3-Display of sequence table***********************\n");
printf("*****************4-Sequential table lookup element*********************\n");
printf("*****************5-Sequence table insert element*********************\n");
printf("*****************6-Sequence table delete element*********************\n");
printf("*****************7-Destruction of sequence table***********************\n");
printf("*****************0-sign out*******************************\n");
printf("******************************************************\n");
printf("\n\n");
while(1){
printf("Input the function you want to chose:\n");
scanf("%d",&flag);
if(flag==0||flag==1||flag==2||flag==3||flag==4||flag==5||flag==6||flag==7)
{
printf("The function is=%d\n",flag);
switch(flag)
{
case 1:
{
InitList_Sq(A);
printf("Sequence table initialization succeeded\n");
break;
}
case 2:
{
NatureList1_10_Sq(A);
printf("Got 1-10 Natural sequence table of\n");
break;
}
case 3:
{
printf("The current sequence table is:\n");
PrintList_Sq(A);
break;
}
case 4:
{
int a,pos;
printf("Please enter the element value you want to find\n");
scanf("%d",&a);
pos=LocateElem_Sq(A,a);
printf("The element value you want to find appears at the earliest%d position\n",pos);
printf("Note: if 0 is displayed, there is no such element in the sequence table\n");
break;
}
case 5:
{
int pos;
ElemType a;
printf("Please enter the position and value of the element you want to insert (before):\n");
scanf("%d%d",&pos,&a);
ListInsert_Sq(A,pos,a);
printf("Insert element succeeded\n");
break;
}
case 6:
{
int pos;
ElemType a;
printf("Please enter the location of the element you want to delete:\n");
scanf("%d",&pos);
ListDelete_Sq(A,pos,a);
printf("The element you deleted is%d\n",a);
break;
}
case 7:
{
DestroyList_Sq(A);
printf("Destroyed successfully\n");
break;
}
case 0:
printf("you choose to exit\nGoodbye!\n");
return 0;
}
}
else ErrorMessage("Please select the function in the menu");
}
return 0;
}
3, Sequential storage structure of sequential table and its simple operation (two modules):
1. Create the header file Definition.h:
#include <stdio.h>
#Include < process. H > / / at least used in ErrorMessage
#Include < iostream > / / at least in ErrorMessage
using namespace std;
const int LIST_INIT_SIZE=100;//Linear table (default) initial allocated maximum space
const int LISTINCREMENT=10;//Default amount of supplemental space
//Defines the SqList type of the linear table
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
int incrementsize;
}SqList;
//Initialization of sequence table
//C language has no default constant usage, so it may be mixed with C and C + +
void InitList_Sq(SqList &L,int maxsize=LIST_INIT_SIZE,int incresize=LISTINCREMENT);
//Assign the first ten elements of the initialized sequence table to 1-10 respectively
void NatureList1_10_Sq(SqList &L);
//Sequential table lookup element
//Find the first element equal to e in L. if it can be found, return its bit order in L; otherwise, return 0
int LocateElem_Sq(SqList L,ElemType e);
/*The next three functions are to insert the sequence table*/
//Error message processing function
void ErrorMessage(char *s);
//Sequential table append space
void increment(SqList &L);
//Sequence table insert element
//Insert a new element E before the ith element of sequence table L, 1 < = i < = L.Length + 1. If the capacity is insufficient, expand the capacity according to the predefined increment
void ListInsert_Sq(SqList &L,int i,ElemType e);
//Sequence table delete element
//Delete the ith element in the sequence table L and return its value with e, 1 < = i < = L.Length
void ListDelete_Sq(SqList &L,int i,ElemType &e);//ErrorMessage is used
//Destruction of sequence table
//Free the storage space occupied by sequence table L
void DestroyList_Sq(SqList &L);
//Display of sequence table
//Because the order is reversed when looking for elements, in order to find out the reason, write a function to display the order table
void PrintList_Sq(SqList L);
//Initialization of sequence table
//C language has no default constant usage, so it may be mixed with C and C + +
void InitList_Sq(SqList &L,int maxsize,int incresize)
{
L.elem=new ElemType[maxsize];//Allocate an array space with a maximum capacity of maxsize for the sequential table
L.length=0;
L.listsize=maxsize;
L.incrementsize=incresize;
}
//Assign the first ten elements of the initialized sequence table to 1-10 respectively
void NatureList1_10_Sq(SqList &L)
{
for(int i=0;i<=9;i++)
{
L.elem[i]=i+1;
}
L.length=10;
}
//Display of sequence table
//Because the order is reversed when looking for elements, in order to find out the reason, write a function to display the order table
void PrintList_Sq(SqList L)
{
printf("All elements of the current sequence table:");
for (int i=0;i<L.length; i++)
{
printf("%d ", L.elem[i]);
}
printf("\n");
}//PrintList_Sq
//Sequential table lookup element
//Find the first element equal to e in L. if it can be found, return its bit order in L; otherwise, return 0
int LocateElem_Sq(SqList L,ElemType e)
{
int i=1;
ElemType *p=L.elem;
while(i<=L.length && *(p++)!=e) i++;
if(i<=L.length) return i;
else return 0;
}//LocateElem_Sq
/*The next three functions are to insert the sequence table*/
//Error message processing function
void ErrorMessage(char *s)
{
cout<<s<<endl;
exit(1);
}
//Sequential table append space
void increment(SqList &L)
{
ElemType *a;//？？ Mark that there may be a problem here??
a=new ElemType [L.listsize+L.incrementsize];
for(int i=0;i<=L.length;i++)
a[i]=L.elem[i];
delete[] L.elem;
L.elem=a;
L.listsize=L.listsize+L.incrementsize;
}
//Sequence table insert element
//Insert a new element E before the ith element of sequence table L, 1 < = i < = L.Length + 1. If the capacity is insufficient, expand the capacity according to the predefined increment
void ListInsert_Sq(SqList &L,int i,ElemType e)
{
if(i<1||i>L.length+1)
ErrorMessage("i Illegal value");
if(L.length>=L.listsize)
increment(L);//'>' it should be OK
ElemType *q=&(L.elem[i-1]);
for(ElemType *p=&(L.elem[L.length-1]);p>=q;p--)
*(p+1)=*p;
*q=e;
L.length++;
}//ListInsert_Sq
//Sequence table delete element
//Delete the ith element in the sequence table L and return its value with e, 1 < = i < = L.Length
void ListDelete_Sq(SqList &L,int i,ElemType &e)
{
if((i<1)||(i>L.length))
ErrorMessage("i Illegal value");
ElemType *p=&(L.elem[i-1]);
e=*p;
ElemType *q=L.elem+L.length-1;
for(++p;p<=q;p++)
*(p-1)=*p;
L.length--;
}
//Destruction of sequence table
//Free the storage space occupied by sequence table L
void DestroyList_Sq(SqList &L)
{
delete[] L.elem;
L.listsize=0;
L.length=0;
}//DestroyList_Sq
2. Create (main function) source program file Main_Lk.cpp:
#include "Definition.h"
int main()
{
SqList A;
printf("\n\n");
int flag;
printf("******************************************************\n");
printf("*************choose the operation of List*************\n");
printf("*****************1-Initialization of sequence table*********************\n");
printf("*****************2-Get 1-10 Natural sequence table of***************\n");
printf("*****************3-Display of sequence table***********************\n");
printf("*****************4-Sequential table lookup element*********************\n");
printf("*****************5-Sequence table insert element*********************\n");
printf("*****************6-Sequence table delete element*********************\n");
printf("*****************7-Destruction of sequence table***********************\n");
printf("*****************0-sign out*******************************\n");
printf("******************************************************\n");
printf("\n\n");
while(1){
printf("Input the function you want to chose:\n");
scanf("%d",&flag);
if(flag==0||flag==1||flag==2||flag==3||flag==4||flag==5||flag==6||flag==7)
{
printf("The function is=%d\n",flag);
switch(flag)
{
case 1:
{
InitList_Sq(A);
printf("Sequence table initialization succeeded\n");
break;
}
case 2:
{
NatureList1_10_Sq(A);
printf("Got 1-10 Natural sequence table of\n");
break;
}
case 3:
{
printf("The current sequence table is:\n");
PrintList_Sq(A);
break;
}
case 4:
{
int a,pos;
printf("Please enter the element value you want to find\n");
scanf("%d",&a);
pos=LocateElem_Sq(A,a);
printf("The element value you want to find appears at the earliest%d position\n",pos);
printf("Note: if 0 is displayed, there is no such element in the sequence table\n");
break;
}
case 5:
{
int pos;
ElemType a;
printf("Please enter the position and value of the element you want to insert (before):\n");
scanf("%d%d",&pos,&a);
ListInsert_Sq(A,pos,a);
printf("Insert element succeeded\n");
break;
}
case 6:
{
int pos;
ElemType a;
printf("Please enter the location of the element you want to delete:\n");
scanf("%d",&pos);
ListDelete_Sq(A,pos,a);
printf("The element you deleted is%d\n",a);
break;
}
case 7:
{
DestroyList_Sq(A);
printf("Destroyed successfully\n");
break;
}
case 0:
printf("you choose to exit\nGoodbye!\n");
return 0;
}
}
else ErrorMessage("Please select the function in the menu");
}
return 0;
}4, Sequential storage structure of linked list and its simple operation (multi module):
1. Create the header file division. H:
#include <stdio.h>
#Include < process. H > / / at least used in ErrorMessage
#Include < iostream > / / at least in ErrorMessage
using namespace std;
const int LIST_INIT_SIZE=5;//The default length of the linked list is 5
typedef int ElemType;//Declare ElemType
//Storage and presentation of (single) linked list
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;//?? There may be a problem. Mark it??
//Initialize a linked list with length n, and the default length is LIST_INIT_SIZE
void ListCreat_Lk(LinkList *&head,int n=LIST_INIT_SIZE);//Pay special attention to * & head
//Traverse the linked list (output item by item)
void TravelList_Lk(LinkList *head);
//Find the length of the linked list
int ListLength_Lk(LinkList *head);
//Find the elements in the linked list and display their node bit order
void LocateElem_Lk(LinkList *head,ElemType e);
//Error message processing function
void ErrorMessage(char *s);
//Linked list node insertion (front insertion)
//Insert an element e before the i th element
void InsertElem_Lk(LinkList *&head,int i,ElemType e);//Pay special attention to * & head
//Delete the ith element of the linked list and return its value with e
void DeleteElem_Lk(LinkList *&head,int i,ElemType &e);//Pay special attention to * & head
//Destruction of linked list
//Delete one by one, starting with the first element
void DestroyList_Lk(LinkList *&head);//Pay special attention to * & head
2. Create the source program file ListCreat_Lk.cpp:
//Initialize a linked list with length n, and the default length is LIST_INIT_SIZE
#Include "division. H" / / definition is the wrong number, so make do with it
void ListCreat_Lk(LinkList *&head,int n)
{
LinkList *node,*end;//Define head node, common node and tail node;
head=new LinkList;//Assign address
end=head;//If it is an empty linked list, the head and tail nodes are the same
for(int i=0;i<n;i++)
{
node=new LinkList;
scanf("%d",&node->data);
end->next=node;
end=node;
}
end->next=NULL;//End creation
}//LinkCreat_Lk
3. Create the source program file TravelList_Lk.cpp:
//Traverse the linked list (output item by item)
#Include "division. H" / / definition is the wrong number, so make do with it
void TravelList_Lk(LinkList *head)
{
LinkList *p=head->next;
while(p!=NULL)
{
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}//TravelList_Lk4. Create the source program file ListLength_Lk.cpp:
//Find the length of the linked list
#Include "division. H" / / definition is the wrong number, so make do with it
int ListLength_Lk(LinkList *head)
{
LinkList *p=head->next;
int k=0;
while(p)
{
p=p->next;
k++;
}
return k;
}//ListLength_Lk
5. Create the source program file locaterelem_ Lk.cpp:
//Find the elements in the linked list and display their node bit order
#Include "division. H" / / definition is the wrong number, so make do with it
void LocateElem_Lk(LinkList *head,ElemType e)
{
int k=0;
LinkList *p=head;
while(p&&p->data!=e)
{
p=p->next;
k++;
}
if(p==NULL) k=0;
printf("The first bit order of the element you are looking for is:%d\n",k);
printf("Note: if 0 is displayed, the linked list has no checked elements\n");
}//LocateList_Lk
6. Create the source program file ErrorMessage.cpp:
//Error message processing function
#Include "division. H" / / definition is the wrong number, so make do with it
void ErrorMessage(char *s)
{
cout<<s<<endl;
exit(1);
}//ErrorMessage
7. Create the source program file InsertElem_Lk.cpp:
//Linked list node insertion (front insertion)
//Insert an element e before the i th element
#Include "division. H" / / definition is the wrong number, so make do with it
void InsertElem_Lk(LinkList *&head,int i,ElemType e)//Pay special attention to * & head
{
int k=ListLength_Lk(head);
if(i<1||i>k) ErrorMessage("i Illegal value");
else if(i==1)
{
LinkList *p=new LinkList;
p->data=e;
p->next=head->next;
head->next=p;
}
else
{
LinkList *q=head;
for(i=i-1;i>0;i--)
{
q=q->next;
}
LinkList *p=new LinkList;
p->data=e;
p->next=q->next;
q->next=p;
}
}//InsertElem_Lk
8. Create the source program file DeleteElem_Lk.cpp:
//Delete the ith element of the linked list and return its value with e
#Include "division. H" / / definition is the wrong number, so make do with it
void DeleteElem_Lk(LinkList *&head,int i,ElemType &e)//Pay special attention to * & head
{
int k=ListLength_Lk(head);
if(i<1||i>k) ErrorMessage("i Illegal value");
else if(i==1)
{
LinkList *p=head->next;
head->next=p->next;
e=p->data;
delete p;
}
else
{
LinkList *q=head;
for(i=i-1;i>0;i--)
{
q=q->next;
}
LinkList *p=q->next;
e=p->data;
q->next=p->next;
delete p;
}
}//DeleteElem_Lk
9. Create the source program file DestroyList_Lk.cpp:
//Destruction of linked list
//Delete one by one, starting with the first element
#Include "division. H" / / definition is the wrong number, so make do with it
void DestroyList_Lk(LinkList *&head)//Pay special attention to * & head
{
LinkList *p;
while(head->next!=NULL)
{
p=head->next;
head->next=p->next;
delete p;
}
}//DestroyLink_Lk
10. Create source program file Main_Lk.cpp:
#Include "division. H" / / definition is the wrong number, so make do with it
int main()
{
LinkList *head1;//LinkList *head1=new LinkList; Warnings can also be removed
head1=NULL;
printf("\n\n");
int flag;
printf("**************************************************************\n");
printf("*****************choose the operation of List*****************\n");
printf("*********************1-Initialization of linked list***************************\n");
printf("*********************2-Traversal of linked list (output item by item)*****************\n");
printf("*********************3-Find the length of the linked list***************************\n");
printf("*********************4-Find elements of linked list*************************\n");
printf("*********************5-Element insertion of linked list*************************\n");
printf("*********************6-Element deletion of linked list*************************\n");
printf("*********************7-Destruction of linked list*****************************\n");
printf("*********************0-sign out***********************************\n");
printf("**************************************************************\n");
printf("****Note: This program involves the leading node of the linked list, but does not participate in the calculation of length and bit order****\n");
printf("\n\n");
while(1){
printf("Input the function you want to chose:\n");
scanf("%d",&flag);
if(flag==0||flag==1||flag==2||flag==3||flag==4||flag==5||flag==6||flag==7)
{
printf("The function is=%d\n",flag);
switch(flag)
{
case 1:
{
printf("Please enter the five values of the linked list one by one:\n");
ListCreat_Lk(head1);
printf("The linked list was initialized successfully(Length 5)\n");
break;
}
case 2:
{
printf("The current linked list is:\n");
TravelList_Lk(head1);
break;
}
case 3:
{
int len=ListLength_Lk(head1);
printf("The current linked list length is:%d\n",len);
break;
}
case 4:
{
int a;
printf("Please enter the element value you want to find\n");
scanf("%d",&a);
LocateElem_Lk(head1,a);
break;
}
case 5:
{
int pos;
ElemType a;
printf("Please enter the position and value of the element you want to insert (before):\n");
scanf("%d%d",&pos,&a);
InsertElem_Lk(head1,pos,a);
printf("Insert element succeeded\n");
break;
}
case 6:
{
int pos;
ElemType a;
printf("Please enter the location of the element you want to delete:\n");
scanf("%d",&pos);
DeleteElem_Lk(head1,pos,a);
printf("The element you deleted is%d\n",a);
break;
}
case 7:
{
DestroyList_Lk(head1);
printf("Destroyed successfully\n");
break;
}
case 0:
printf("you choose to exit\nGoodbye!\n");
return 0;
}
}
else ErrorMessage("Please select the function in the menu");
}
return 0;
}
/*"."Generally understood as "yes"
"->"Generally understood as "pointing to the structure"
That is, reference the elements in the structure variable. If the variable is a general structure variable, use "." and if it is a pointer, use "-" >
Pay attention to the difference between header node and header pointer*/
5, Sequential storage structure of linked list and its simple operation (two modules):
1. Create the header file Definition.h:
#include <stdio.h>
#Include < process. H > / / at least used in ErrorMessage
#Include < iostream > / / at least in ErrorMessage
using namespace std;
const int LIST_INIT_SIZE=5;//The default length of the linked list is 5
typedef int ElemType;//Declare ElemType
//Storage and presentation of (single) linked list
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;//There may be a problem. Mark it??
//Initialize a linked list with a length of n. the default length is LIST_INIT_SIZE
void ListCreat_Lk(LinkList *&head,int n=LIST_INIT_SIZE);//Pay special attention to * & head
//Traverse the linked list (output item by item)
void TravelList_Lk(LinkList *head);
//Find the length of the linked list
int ListLength_Lk(LinkList *head);
//Find the elements in the linked list and display their node bit order
void LocateElem_Lk(LinkList *head,ElemType e);
//Error message processing function
void ErrorMessage(char *s);
//Linked list node insertion (front insertion)
//Insert an element e before the i th element
void InsertElem_Lk(LinkList *&head,int i,ElemType e);//Pay special attention to * & head
//Delete the ith element of the linked list and return its value with e
void DeleteElem_Lk(LinkList *&head,int i,ElemType &e);//Pay special attention to * & head
//Destruction of linked list
//Delete one by one, starting with the first element
void DestroyList_Lk(LinkList *&head);//Pay special attention to * & head
//Initialize a linked list with a length of n. the default length is LIST_INIT_SIZE
void ListCreat_Lk(LinkList *&head,int n)
{
LinkList *node,*end;//Define head node, common node and tail node;
head=new LinkList;//Assign address
end=head;//If it is an empty linked list, the head and tail nodes are the same
for(int i=0;i<n;i++)
{
node=new LinkList;
scanf("%d",&node->data);
end->next=node;
end=node;
}
end->next=NULL;//End creation
}//LinkCreat_Lk
//Traverse the linked list (output item by item)
void TravelList_Lk(LinkList *head)
{
LinkList *p=head->next;
while(p!=NULL)
{
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}//TravelList_Lk
//Find the length of the linked list
int ListLength_Lk(LinkList *head)
{
LinkList *p=head->next;
int k=0;
while(p)
{
p=p->next;
k++;
}
return k;
}//ListLength_Lk
//Find the elements in the linked list and display their node bit order
void LocateElem_Lk(LinkList *head,ElemType e)
{
int k=0;
LinkList *p=head;
while(p&&p->data!=e)
{
p=p->next;
k++;
}
if(p==NULL) k=0;
printf("The first bit order of the element you are looking for is:%d\n",k);
printf("Note: if 0 is displayed, the linked list has no checked elements\n");
}//LocateList_Lk
//Error message processing function
void ErrorMessage(char *s)
{
cout<<s<<endl;
exit(1);
}//ErrorMessage
//Linked list node insertion (front insertion)
//Insert an element e before the i th element
void InsertElem_Lk(LinkList *&head,int i,ElemType e)//Pay special attention to * & head
{
int k=ListLength_Lk(head);
if(i<1||i>k) ErrorMessage("i Illegal value");
else if(i==1)
{
LinkList *p=new LinkList;
p->data=e;
p->next=head->next;
head->next=p;
}
else
{
LinkList *q=head;
for(i=i-1;i>0;i--)
{
q=q->next;
}
LinkList *p=new LinkList;
p->data=e;
p->next=q->next;
q->next=p;
}
}//InsertElem_Lk
//Delete the ith element of the linked list and return its value with e
void DeleteElem_Lk(LinkList *&head,int i,ElemType &e)//Pay special attention to * & head
{
int k=ListLength_Lk(head);
if(i<1||i>k) ErrorMessage("i Illegal value");
else if(i==1)
{
LinkList *p=head->next;
head->next=p->next;
e=p->data;
delete p;
}
else
{
LinkList *q=head;
for(i=i-1;i>0;i--)
{
q=q->next;
}
LinkList *p=q->next;
e=p->data;
q->next=p->next;
delete p;
}
}//DeleteElem_Lk
//Destruction of linked list
//Delete one by one, starting with the first element
void DestroyList_Lk(LinkList *&head)//Pay special attention to * & head
{
LinkList *p;
while(head->next!=NULL)
{
p=head->next;
head->next=p->next;
delete p;
}
}//DestroyLink_Lk
2. Create (main function) source program file Main_Lk.cpp:
#Include "division. H" / / definition is the wrong number, so make do with it
int main()
{
LinkList *head1;//LinkList *head1=new LinkList; Warnings can also be removed
head1=NULL;
printf("\n\n");
int flag;
printf("**************************************************************\n");
printf("*****************choose the operation of List*****************\n");
printf("*********************1-Initialization of linked list***************************\n");
printf("*********************2-Traversal of linked list (output item by item)*****************\n");
printf("*********************3-Find the length of the linked list***************************\n");
printf("*********************4-Find elements of linked list*************************\n");
printf("*********************5-Element insertion of linked list*************************\n");
printf("*********************6-Element deletion of linked list*************************\n");
printf("*********************7-Destruction of linked list*****************************\n");
printf("*********************0-sign out***********************************\n");
printf("**************************************************************\n");
printf("****Note: This program involves the leading node of the linked list, but does not participate in the calculation of length and bit order****\n");
printf("\n\n");
while(1){
printf("Input the function you want to chose:\n");
scanf("%d",&flag);
if(flag==0||flag==1||flag==2||flag==3||flag==4||flag==5||flag==6||flag==7)
{
printf("The function is=%d\n",flag);
switch(flag)
{
case 1:
{
printf("Please enter the five values of the linked list one by one:\n");
ListCreat_Lk(head1);
printf("The linked list was initialized successfully(Length 5)\n");
break;
}
case 2:
{
printf("The current linked list is:\n");
TravelList_Lk(head1);
break;
}
case 3:
{
int len=ListLength_Lk(head1);
printf("The current linked list length is:%d\n",len);
break;
}
case 4:
{
int a;
printf("Please enter the element value you want to find\n");
scanf("%d",&a);
LocateElem_Lk(head1,a);
break;
}
case 5:
{
int pos;
ElemType a;
printf("Please enter the position and value of the element you want to insert (before):\n");
scanf("%d%d",&pos,&a);
InsertElem_Lk(head1,pos,a);
printf("Insert element succeeded\n");
break;
}
case 6:
{
int pos;
ElemType a;
printf("Please enter the location of the element you want to delete:\n");
scanf("%d",&pos);
DeleteElem_Lk(head1,pos,a);
printf("The element you deleted is%d\n",a);
break;
}
case 7:
{
DestroyList_Lk(head1);
printf("Destroyed successfully\n");
break;
}
case 0:
printf("you choose to exit\nGoodbye!\n");
return 0;
}
}
else ErrorMessage("Please select the function in the menu");
}
return 0;
}
/*"."Generally understood as "yes"
"->"Generally understood as "pointing to the structure"
That is, reference the elements in the structure variable. If the variable is a general structure variable, use "." and if it is a pointer, use "-" >
Pay attention to the difference between header node and header pointer*/6, Postscript:
Now that I'm almost finished writing my first blog, I feel I'm about to sublimate. To get down to business, if you want to implement it in pure c language, change cout to printf, const to #dfine, modify the default parameters slightly, and new to malloc... On the contrary, if you want to implement it in pure c + + (because c + + is fully compatible with c, I'm not sure if this statement is right, ha, just understand what it means). Just replace printf with cout...,...,... Because I'm lazy, I don't want to do it anymore, so I'll just make do with it (use it). As for the demonstration results, I don't know where to put the screenshot, so I'll omit it.
Again, there may be some miscellaneous personal notes in the notes during my writing / debugging. If I can't understand them, I'll just ignore them. If I look back, I may not understand them... Well, I'm too lazy to delete them.
The first blog is inevitably wrong. Welcome to correct it.