C language to achieve a single linked list of operations of two
- 2020-04-02 00:48:47
- OfStack
Last post
<
(link: #)
>
Mainly is the single linked list of some of the most basic operations, below, mainly some other typical algorithms and test procedures.
The following is mainly a single linked list of test procedures.
Here are some of the results running under Linux:
struct LNode *sort(struct LNode *head)
{
LinkList *p;
int n,i,j;
int temp;
n = ListLength(head);
if(head == NULL || head->next == NULL)
return head;
p = head->next;
for(j =1;j<n;++j)
{
p = head->next;
for( i =0;i<n-j;++i)
{
if(p->data > p->next->data)
{
temp = p->data;
p->data = p->next->data;
p->next->data = temp;
}
p = p->next;
}
}
return head;
}
LinkList *reverse(LinkList *head)
{
LinkList *p1,*p2 = NULL,*p3 = NULL;
if(head == NULL || head->next == NULL)
return head;
p1 = head->next;
while(p1!=NULL)
{
p3 = p1->next;
p1->next = p2;
p2 = p1;
p1 = p3;
}
head->next = p2;
// head = p2;
return head;
}
Status equal(ElemType c1,ElemType c2)
{
if(c1== c2)
return TRUE;
else
return FALSE;
}
void Union(LinkList *La,LinkList *Lb)
{
ElemType *e;
int La_len,Lb_len;
int i;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
for(i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,e); //Assign e to the ith element in Lb
if(!LocateElem(La,*e,equal))//If there is no element in La that is the same as e, insert
ListInsert(La,++La_len,*e);
}
}
void print(ElemType c)
{
printf("%4d",c);
}
void MergeList(LinkList *La,LinkList *Lb,LinkList **Lc)
{
int i =1,j=1,k=0;
int La_len,Lb_len;
ElemType *ai,*bj;
ai = (ElemType *)malloc(sizeof(ElemType));
bj = (ElemType *)malloc(sizeof(ElemType));
InitList(Lc);
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while(i<=La_len && j<=Lb_len)
{
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if(*ai<*bj)
{
ListInsert(*Lc,++k,*ai);
++i;
}
else
{
ListInsert(*Lc,++k,*bj);
++j;
}
}
while(i<=La_len)
{
GetElem(La,i++,ai);
ListInsert(*Lc,++k,*ai);
}
while(j<=Lb_len)
{
GetElem(Lb,j++,bj);
ListInsert(*Lc,++k,*bj);
}
}
LinkList *Searchmid(LinkList * head)
{
if(NULL == head)
return NULL;
if(head->next == NULL)
return head;
if(head->next->next == NULL)
return head;
LinkList *mid= head;
LinkList *p = mid->next;
while((p != NULL) && (NULL !=p->next))
{
mid = mid->next;
p = p->next->next;
}
return mid;
}
The following is mainly a single linked list of test procedures.
Status comp(ElemType c1,ElemType c2)
{
if(c1==c2)
return TRUE;
else
return FALSE;
}
void visit(ElemType c)
{
printf("%4d",c);
}
void main()
{
LinkList *L;
LinkList *mid;
mid = (struct LNode *)malloc(sizeof(struct LNode));
ElemType *e,e0,*e1;
Status i;
int j,k;
e = (ElemType *)malloc(sizeof(ElemType));
e1 = (ElemType *)malloc(sizeof(ElemType));
i = InitList(&L);
for(j=1;j<=6;j++)
{
i = ListInsert(L,1,j);
}
printf(" in L Is inserted in turn 1 ~ 6 After: L=");
ListTraverse(L,visit);
printf("L The value of the intermediate node is mid= : ");
mid = Searchmid(L);
printf("%dn",mid->data);
printf("L Output after inverse: L=");
ListTraverse(reverse(L),visit);
printf("L In order: L=");
ListTraverse(sort(L),visit);
i = ListEmpty(L);
printf("L Null or not: i=%d(1: Is that, 0: no )n",i);
i = ClearList(L);
printf(" empty L After: L=");
ListTraverse(L,visit);
i = ListEmpty(L);
printf("L Null or not: i=%dn",i);
for(j=1;j<=10;j++)
{
ListInsert(L,j,j);
}
printf(" in L Is inserted in turn 1~10 After: L=");
ListTraverse(L,visit);
GetElem(L,5,e);
printf(" The first 5 The value of element is: %dn",*e);
for(j=0;j<=1;j++)
{
k = LocateElem(L,j,comp);
if(k)
printf(" The first %d The value of each element is zero %dn",k,j);
else
printf(" No value for %d The elements of the n",j);
}
for(j=1;j<=2;j++)
{
GetElem(L,j,e1);
i = PriorElem(L,*e1,e);
if(i== INFEASIBLE)
printf(" The element %d No precursor n",*e1);
else
printf(" The element %d The precursor is: %dn",*e1,*e);
}
for(j=ListLength(L) -1;j<=ListLength(L);j++)
{
GetElem(L,j,e1);
i = NextElem(L,*e1,e);
if(i==INFEASIBLE)
printf(" The element %d No subsequent n",*e1);
else
printf(" The element %d The successor is: %dn",*e1,*e);
}
k = ListLength(L);
for(j=k+1;j>=k;j--)
{
i = ListDelete(L,j,e);
if(i==ERROR)
printf(" Delete the first %d Data failure n",j);
else
printf(" The deleted elements are: %dn",*e);
}
printf(" In turn, the output L The elements: ");
ListTraverse(L,visit);
DestroyList(L);
printf(" The destruction L After: L=%un",L);
printf("*************************************************n");
LinkList *La,*Lb;
i = InitList(&La);
if(i==1)
for(j=1;j<=5;j++)
i= ListInsert(La,j,j);
printf("La=");
ListTraverse(La,print);
InitList(&Lb);
for(j=1;j<=5;j++)
i = ListInsert(Lb,j,2*j);
printf("Lb = ");
ListTraverse(Lb,print);
Union(La,Lb);
printf("new La=");
ListTraverse(La,print);
printf("*************************************************n");
LinkList *La_1,*Lb_1,*Lc_1;
int a[4]={3,5,8,11},b[7]= {2,6,8,9,11,15,20};
InitList(&La_1);
for(j=1;j<=4;j++)
ListInsert(La_1,j,a[j-1]);
printf("La_1=");
ListTraverse(La_1,print);
InitList(&Lb_1);
for(j=1;j<=7;j++)
ListInsert(Lb_1,j,b[j-1]);
printf("Lb_1=");
ListTraverse(Lb_1,print);
MergeList(La_1,Lb_1,&Lc_1);
printf("Lc_1=");
ListTraverse(Lc_1,print);
}
Here are some of the results running under Linux:
in L Is inserted in turn 1 ~ 6 After: L= 6 5 4 3 2 1
L The value of the intermediate node is mid= : 4
L Output after inverse: L= 1 2 3 4 5 6
L In order: L= 1 2 3 4 5 6
L Null or not: i=0(1: Is that, 0: no )
empty L After: L=
L Null or not: i=1
in L Is inserted in turn 1~10 After: L= 1 2 3 4 5 6 7 8 9 10
The first 5 The value of element is: 5
No value for 0 The elements of the
The first 1 The value of each element is zero 1
The element 1 No precursor
The element 2 The precursor is: 1
The element 9 The successor is: 10
The element 10 No subsequent
Delete the first 11 Data failure
The deleted elements are: 10
In turn, the output L The elements: 1 2 3 4 5 6 7 8 9
The destruction L After: L=7954544
*************************************************
La= 1 2 3 4 5
Lb = 2 4 6 8 10
new La= 1 2 3 4 5 6 8 10
*************************************************
La_1= 3 5 8 11
Lb_1= 2 6 8 9 11 15 20
Lc_1= 2 3 5 6 8 8 9 11 11 15 20