The experiment purpose : Deeply understand the establishment and operation of single linked list

Experimental content :

1. Create a single linked list A And B

2. Implement the main function , lookup 、 Insert 、 Delete etc.

3. Implement operations A-B

step 1: Contains the necessary function libraries , For the structure LNode Abstract data types in ElemType Make a specific definition

 #include <stdio.h>

 #include <stdlib.h>

 typedef int ElemType;

step 2: Defining structure LNode

 typedef struct LNode

 {

      ElemType data;

      struct LNode *next;

 }LNode, *LinkList;

F Tips :LNode Used to declare a data node in a single linked list ,LinkList Used to declare a pointer to a data node in a single linked list

step 3: Define basic functions InitList_L()、ListInsert_L()、GetElem_L ()、ListSize_L(), Used to build a single linked list A and B

step 3.1: Implementation function InitList_L().( This function is used to initialize the single linked list , That is to create the head node )

F Tips 1: Parameters L To point to “ Single chain header pointer ” The pointer to , namely

LinkList *L;

Equivalent to

LNode **L;

F Tips 2: Because it needs to be modified in the function L The content of the pointer to the header ( That is to call InitList_L() Before , The header pointer is empty , call InitList_L() after , The header pointer points to the newly created header node ), So you need to L Before to add “*” Number .

F Tips 3: because *L Represents the content of the header pointer , So in modifying the next Domain time , It can be executed :

(*L)->next=NULL

Because in a Is a pointer to a structure , operation a->b Equivalent to (*a).b, So the statement is equivalent to :

(*(*L)).next=NULL;

 void InitList_L(LinkList *L)

 {

      *L=(LinkList)malloc(sizeof(LNode));

      if (*L==NULL)

          exit(-);

      (*L)->next=NULL;

      // Equivalent to (*(*L)).next=NULL;                                              

 }

step 3.2: Implementation function ListInsert_L ().( Insert a new element at the specified location )

 int ListInsert_L(LinkList L,int i,ElemType e)

 {
LNode *p,*s;
int j;
p=L;
j=;
while(p&&j<i-)
{
p=p->next;++j;
}
if(!p||j>i-)
return ;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return ;
}

step 3.3:GetElem_L().( Returns the element at the specified position in the order table )

 int GetElem_L(LinkList L, int i, ElemType *e)
{
LinkList p;
int j=;
p=L->next;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return ;
*e=p->data;
return ;
}

step 3.4:ListSize_L().( Returns the length of a single linked list )

 int ListSize_L(LinkList L)
{
LNode *p;
int count=;
p=L;
while(p->next!=NULL)
{
p=p->next;
count++;
}
return count;
}

step 4: Build a linear table A And B, And output the elements

F Tips : Create... Statically A=(3,5,8,11),B=(2,6,8,9,11,15,20).

 int main()
{
int i,flag,e;
// Define two head pointers
LinkList A,B;
// Test functions GetElemPointer_L()
LNode *p;
/* Initialize single chain table A, Put the head pointer A The address of ( Point to A The pointer to ) Pass in */
InitList_L(&A);
/* Initialize single chain table B, Put the head pointer B The address of ( Point to B The pointer to ) Pass in */
InitList_L(&B);
/* It's a single linked list A Fill in the data */
ListInsert_L(A,,);

ListInsert_L(A,,);
/* It's a single linked list B Fill in the data */
ListInsert_L(B,,);

ListInsert_L(B,,);
/* Output single chain table A*/
printf(" Single chain list A The element in is :\n");
for(i=;i<=ListSize_L(A);i++)
{
flag=GetElem_L(A,i,&e);
if(flag)
printf("%4d",e);
}
printf("\n");
/* Output single chain table B*/
printf(" Single chain list B The element in is :\n");
for(i=;i<=ListSize_L(B);i++)
{
flag=GetElem_L(B,i,&e);
if(flag)
printf("%4d",e);
}
printf("\n");
}

step 4 Output result of

step 5: Implementation function ListDelete_L().( Used to delete an element at a specified location )

F Tips : The declaration of this function is :

 int ListDelete_L(LinkList *L,int i, ElemType *e)

step 6: Test functions ListDelete_L()

     flag=ListDelete_L(&B,,&e);
if(flag)
printf(" The deleted element is :%4d",e);
printf("\n");
printf(" Single chain list B The remaining elements in are :\n");
for(i=;i<=ListSize_L(B);i++)
{
flag=GetElem_L(B,i,&e);
if(flag)
printf("%4d",e);
}
printf("\n");


step 6 Output result of

step 7: Implementation function LocateElem_L
()

LocateElem_L(): Returns the position of a given element in a single linked list ( Serial number ). Be careful : The serial number of the head node is 0.

F Tips : First , Make p Point to the header node of the single linked list , namely L->next. If the list is empty , namely L->next==NULL, Then return to 0. otherwise , Traverse the single linked list , And return the location of the matching node . Last , If it doesn't turn up , Then return to 0.

The function is declared as :

 int LocateElem_L(LinkList L, ElemType e);

step 8: Test functions LocateElem_L()

 flag=LocateElem_L(B,);
printf(" Elements 15 In a single linked list B The position in is :%4d\n",flag);


step 8 Output result of

step 9: Implementation function GetElemPointer_L().( Return to the first... In the single linked list i Pointers to elements )

F Tips : First , If the list is empty , namely L->next==NULL, Return null pointer . Next , If parameter i illegal , Return null pointer . then , Traverse the single linked list , And returns a pointer to the matching node . Last , If it doesn't turn up , Return null pointer .

The function is declared as :

 LNode *GetElemPointer_L(LinkList L,int i);

step 10: Test functions GetElemPointer_L()

 p=GetElemPointer_L(A,);
printf(" Single chain list A No 3 Elements are :%4d\n",p->data);

step 10 Output result of

step 11: Implementation function DelElem_L()( Realization A-B).

F Tips : Loop through the order table B. In each cycle , Let's start with functions GetElemPointer_L() Get the point B Pointer to the current node in ( Suppose that the node pointer is stored in p in ), Reuse functions LocateElem_L() Under inspection A Whether there is a data field is equal to p->data The node of , If it exists, it returns the location of the matching node pos. Last , Utilization function ListDelete_L() Delete the matching node ( namely A No pos Nodes ).

function DelElem_L() The statement of :

 void DelElem_L(LinkList A,LinkList B);

step 12: Test functions DelElem_L() The function of

     DelElem_L(A,B);// perform A-B
printf(" Single chain list A The remaining elements in are :\n");
for(i=;i<=ListSize_L(A);i++)
{
flag=GetElem_L(A,i,&e);
if(flag)
printf("%4d",e);
}
printf("\n");


step 12 Output result of

Thinking questions

1. Organize all the basic functions of a single linked list into a separate file “LinkList.h”, And then use it include Command to call the file .

 /* Delete the element at the specified position */
int ListDelete_L(LinkList *L,int i, ElemType *e) {
LNode *p,*q;
p=*L;
int j=;
while(p->next&&j<i-) {
p=p->next;
++j;
}
if(!(p->next)||j>i-) return ;
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
return ;
} /* Returns the position of a given element in a single linked list */
int LocateElem_L(LinkList L, ElemType e) {
LNode *p;
int i;
if(L->next==NULL)
return ;
p=L->next;
i=;
while(p) { if(p->data==e)
return i;
else {
p=p->next;
i++;
}
if(!p) return ;
}
} /* Return to the first... In the single linked list i Pointers to elements */
/* If you find the second i Nodes , Returns a pointer to the node ; otherwise , Return null pointer */
LNode *GetElemPointer_L(LinkList L,int i) {
LNode *p;
int j;
// If the list is empty
if(L->next==NULL)
return NULL;
// If the parameter is illegal
if(i<)
return NULL;
p=L;
j=;
while(p->next!=NULL&&j<i) {
p=p->next;
j++;
}
if(j==i)
return p;
else
return NULL;
} void DelElem_L(LinkList A,LinkList B) {
int i,pos,flag;
ElemType e;
LNode *p;
for(i=; i<=ListSize_L(B); i++) {
p=GetElemPointer_L(B,i);//p Point to a single linked list B There is a second i Nodes
if(p) { // If a single list B There is a second i Nodes
pos=LocateElem_L(A,p->data);// if A There are the same nodes in , Then use to return it in A Position in
if(pos>)// If exist , It's in A Delete the element in the
ListDelete_L(&A,pos,&e);
/*
{flag=ListDelete_L(&A,pos,&e);
if(flag)
printf(" The deleted element is :%4d\n",e);
}
*/
}
}
}

University experiments 3 To guide the : Using single linked list to realize A-B More articles about

  1. VLAN experiment 4: Using single arm routing to achieve VLAN Routing between

    Single arm routing : Experimental environment : Experimental Topology : Experiment address : The experimental steps :1. establish VLAN And configuration Access.Trunk Interface . We are S2 To create a VLAN10 and VLAN20, And link PC1 Of E0/0/1 And link PC2 ...

  2. 148. Sort List (java Sort single linked lists )

    subject :Sort a linked list in O(n log n) time using constant space complexity. analysis : Sort single linked lists , The required time complexity is O(nlogn) ...

  3. Python And data structure [0] -&gt; Linked list /LinkedList[0] -&gt; Single linked list and single linked list with header Python Realization

    Single chain list / Linked List Catalog Single chain list Single linked list with header Linked list is a basic linear data structure , stay C In language , This data structure is implemented through pointers , Because storage space does not require continuity , So the insert and delete operations will be very fast . The following will benefit ...

  4. Using single arm routing to achieve VLAN Routing between nodes

    experiment 4: Using single arm routing to achieve VLAN Routing between nodes . Experimental principle :   Experimental content : This experiment simulates the company's network scene , Router R1 It's the company's export gateway , staff PC Through the access layer switch ( Such as S2 and S3) Access to corporate networks , The access layer switches are connected through convergence ...

  5. SDUT OJ Linked list 7 of data structure experiment : Deletion of duplicate elements in single linked list

    Linked list 7 of data structure experiment : Deletion of duplicate elements in single linked list Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem ...

  6. SDUT OJ Linked list 5 of data structure experiment : Split single linked list

    Linked list 5 of data structure experiment : Split single linked list Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem Descr ...

  7. Data structure experiment 2:C++ Implementation of single linked list class

    Too simple. , Post the title directly and then code it . subject : experiment 2 2.1 The experiment purpose Master the chain storage structure of linear list . Master the algorithm design of single linked list . According to the needs of specific problems , Design a reasonable chain storage structure to represent data , And design relevant calculation ...

  8. SDUT-2120_ Linked list 5 of data structure experiment : Split single linked list

    Linked list 5 of data structure experiment : Split single linked list Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description Input N Create a single linked list in order of integers , Will be ...

  9. SDUT-2122_ Linked list 7 of data structure experiment : Deletion of duplicate elements in single linked list

    Linked list 7 of data structure experiment : Deletion of duplicate elements in single linked list Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description In the reverse order of data entry ( The inverse ...

Random recommendation

  1. ( turn )Java Detailed explanation JVM How it works and how it works

    As a Java Users , master JVM The architecture of is also necessary . Speaking of Java, The first thing people think about is Java programing language , But in fact ,Java It's a technology , It consists of four parts :Java programing language .Java Class file format .Java virtual ...

  2. linux Under the various software installation process

    ////// Knowledge reserve //////////////////////////////////////////////////////////////////// /var  There are services and constantly changing documents in the database / ...

  3. About iterators IEnumerable And IEnumerator The difference between

    First of all IEnumerable And IEnumerator The definition of : 1.IEnumerable Interface allows the use of foreach loop , contain GetEnumerator() Method , You can iterate over items in the collection . 2.IEnumer ...

  4. ubuntu Reset root password

    from: http://mmicky.blog.163.com/blog/static/150290154201398113034698/ Use ubuntu When I forget root How to reset the password ? I use ...

  5. TaoBao Yinfeng UDF

    http://blog.csdn.net/zhaiwx1987/article/details/6902623

  6. c Language time base function #include&lt;time.h&gt;

    Date and time functions <time.h> The header file <time.h> Some types and functions for dealing with dates and times are described in . Some of these functions deal with local time , Because of time zones and other reasons , Local time and calendar time may not be the same ...

  7. Struts Learning custom interceptor

    * All interceptors need to be implemented Interceptor Interface or inheritance Interceptor Interface extension implementation class     * To rewrite init().intercept().destroy() Method         * in ...

  8. PHP Methods that reference operations and external operations on local static variables of functions

    Operate static variables inside functions or member methods externally by reference Here is a simple example , Explain three questions about citation : 1. Type conversion within a function after a parameter reference is also an address operation 2. When you pass a parameter reference to another function, you need to add a reference again ...

  9. d3.js Draw a polar graph (polar plot)

    0. introduction In polar coordinates , Any position can be made up of an angle and a relative origin ( pole ) The distance between the two represents . in other words , We can use  (angle,r)  To represent a point in a polar coordinate system . 1. data Suppose we have the following data set [ [10, 0.2], ...

  10. [mysql Use (2)] mysql Some grammar and grammar of Oracle The difference between

    One . Table space mysql There are shared table space and exclusive table space , Exclusive tablespace , It's actually a table, a table space , In fact, it is a table and a data file , Shared table spaces seem a little bit like oracle Table space , Different tables can be saved in the same data file ...