C language to achieve a single linked list of operations of one
- 2020-04-02 00:48:53
- OfStack
Recently, I have reviewed some important parts of the data structure, and now I have recorded my achievements, which are mainly adapted from the examples and exercises in yan weimin's data structure (C language version). First of all, is the realization of a variety of single linked list, which contains some commonly tested knowledge points. For example, the inverse of a single linked list, the merge of a single linked list, the algorithm to find the middle node of a single linked list and so on.
The following is the definition of the structure of a single linked list:
Below is the basic operation of single linked list: among them, there are some macros, without giving some definitions of them, which can be viewed through yan weimin's data structure (C language version).
The following is the definition of the structure of a single linked list:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
Below is the basic operation of single linked list: among them, there are some macros, without giving some definitions of them, which can be viewed through yan weimin's data structure (C language version).
Status InitList (struct LNode **L)
{
(*L) = (struct LNode *)malloc(sizeof(struct LNode)); //Generating head node
if(!*L)
exit(OVERFLOW);
(*L)->next = NULL;
return OK;
}
Status DestroyList(struct LNode *L)
{
struct LNode *q;
while(L)
{
q = L->next;
free(L);
L = q;
}
return OK;
}
Status ClearList(struct LNode *L)
{
LinkList *p,*q;
p = L->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
Status ListEmpty(LinkList *L)
{
if(L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}
int ListLength(struct LNode *L)
{
int i=0;
LinkList *p = L->next;
while(p)
{
i++;
p = p->next;
}
return i;
}
Status GetElem(struct LNode *L,int i,ElemType *e)
{
int j=1;
LinkList *p = L->next;
while(p && j<i)
{
p = p->next;
j++;
}
if(!p || j>i)
return ERROR;
*e = p->data;
return OK;
}
int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
int i =0;
LinkList *p = L->next;
while(p)
{
i++;
if(compare(p->data,e))
return i;
p=p->next;
}
return 0;
}
Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
LinkList *q,*p=L->next;
while(p->next)
{
q = p->next;//Q points to the successor of p
if(q->data == cur_e)
{
*pre_e = p->data;
return OK;
}
p = q;
}
return INFEASIBLE;
}
Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
LinkList *p;
p = L->next;
while(p->next)
{
if(p->data == cur_e)
{
* next_e = p->next->data;
return OK;
}
p = p->next;
}
return INFEASIBLE;
}
Status ListInsert(struct LNode *L,int i,ElemType e)
{
int j =0;
struct LNode *p=L,*s=NULL;
while(p && j<i-1)
{
p=p->next;
j++;
}
if(!p || j>i-1)
return ERROR;
s = (struct LNode *)malloc(sizeof(struct LNode));
if(!s)
printf("malloc error~n");
// p->next = s;
s->data = e;
// p->next = s;
s->next = p->next;
p->next = s;
//s->next = NULL;
// p = s;
return OK;
}
Status ListDelete(LinkList *L,int i,ElemType *e)
{
LinkList *p=L,*q;
int j=0;
while(p->next && j< i-1)
{
p = p->next;
j++;
}
if(!p->next || j>i-1)
return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
LinkList *p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("n");
return OK;
}