#include<stdio.h>
#include<stdlib.h>
/*******************************************************************************
* data structure and macro definition
*******************************************************************************/
#define MAX 5
typedef enum{
OK =1,
ERROR = -1
}STATUS_EN;
typedef enum{
TRUE = 1,
FALSE = 0
}BOOL;
typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
struct LNode *next;
}LNode,*LinkList;
/******************************************************************************
* function implement
******************************************************************************/
/******************************************************************************
* function : destroy_list
* description : destroy link list
* input : struct LNode **ppHead(a pointer to the link head pointer)
* output : struct LNode **pphead
* return value : void
* AUthor : HanyoungXue
* Date : 2018-4-14
******************************************************************************/
// a link list with a head node
void destroy_list(LinkList *ppHead){
LNode *p = *ppHead;//head pointer
LNode *q = p->next;
while(p && p->next){
q = p->next;
p = q->next;
free(q);
q = NULL;
}
free(*ppHead);
*ppHead = NULL;
}
/******************************************************************************
* function : init_list
* description : init list
* input : struct LNode **ppHead
* output : struct Londe **ppHead
* return value : STATUS_EN(OK/ERROR)
* author : HanyoungXue
* date : 2018-4-14
******************************************************************************/
STATUS_EN init_list(LinkList *ppHead){
if (*ppHead){
destroy_list(ppHead);
}
LNode *p = (LNode*)malloc(sizeof(LNode));
p->next = NULL;
p->data = 0;
*ppHead = p;
return OK;
}
/*****************************************************************************
* function : insert_elem
* description : insert element at index == i
* input : struct LNode **pphead;
const int pos
const Elemtype elem
* output : struct LNode **pphead
* return value : STATUS_EN(OK/ERROR)
* Author : HanyoungXue
* Date : 2018-4-14
****************************************************************************/
STATUS_EN insert_elem(LinkList *ppHead,const int pos,Elemtype elem){
LNode *p = *ppHead;
LNode *s = NULL;
// finds the last node front the node with index = pos
int i = 0;
while(p && i< pos){
p = p->next;
i++;
}
// if doesn't find the last node, then return error
if (!p || i > pos)
{
return ERROR;
}
// new a Node
s = (LNode*)malloc(sizeof(LNode));
if (!s)
{
return ERROR;
}
// insert the node
s->data = elem;
s->next = p->next;
p->next = s;
return OK;
}
/* ***************************************************************************
* function : remove_elem
* description : remove the elem at index=pos,and return elem's data
* input : struct Lnode **pphead
const int pos
Elemtype *pElem
* output : struct LNode **ppHead
ElemType *pElem
* return value : STATUS_EN(OK/ERROR)
* Author : HanyoungXue
* Date : 2018-4-14
*****************************************************************************/
STATUS_EN remove_elem(LinkList *ppHead,const int pos,Elemtype *pElem){
LNode *p = *ppHead;
LNode *q = NULL;
int i=0;
while(p && p->next &&i<pos){
p = p->next;
i++;
}
// the postion of delete is unvalidable
if (!(p->next)||i>pos)
{
return ERROR;
}
// delete and release the node
q = p->next;
*pElem = q->data;
p->next = q->next;
free(q);
return OK;
}
/**********************************************************************************
* function : create_list
* description : create a single linkList bases on a array
* input : struct LNode **ppHead,
const ElemType elems[],
const int n
* output : struct LNode **ppHead
* return value : STATUS_EN(OK/ERROR)
* Author : HanyoungXUe
* date : 2018-4-14
*********************************************************************************/
STATUS_EN create_list(LinkList *ppHead,const Elemtype elems[],const int n){
int i = 0;
STATUS_EN status = OK;
for (int i = 0; i < n; i++)
{
status = insert_elem(ppHead,i,elems[i]);
if (status!=OK)
{
return status;
}
}
return OK;
}
/* *****************************************************************************
* function : is_empty_list
* description : to judge whether a list is null
* input : struct LNode **ppHead
* output : N/A
* return value : BOOL
* Author : HanyoungXue
* date : 2018-4-14
*******************************************************************************/
BOOL is_empty_list(LinkList pHead){
if (!pHead ||!(pHead->next)){
return TRUE;
}else{
return FALSE;
}
}
/* *****************************************************************************
* function : get_elem
* description : get an elem from single LinkList where index = pos
* input : struct LNode *pHead,
* Elemtype *pElem,
* const int pos
* output : Elemtype *pElem
* return value : STATUS_EN(OK/ERROR)
* author : HanyoungXue
* date : 2018-4-14
*******************************************************************************/
STATUS_EN get_elem(LinkList pHead,Elemtype *pElem,const int pos){
int i=0;
LNode *p = pHead -> next;
while(p && i<= pos){
if (i==pos){
*pElem = p->data;
return OK;
}else{
p = p->next;
i++;
}
}
return ERROR;
}
/* ******************************************************************************
* function : locate_elem
* description : gets the position which the elem be firstly found on LinkList.
* if doesn't find it, then return -1
* input : struct LNode *pHead
* const Elemtype elem
* output : N/A
* return value : int
* author : HanyoungXue
* date : 2018-4-14
********************************************************************************/
int locate_elem(LinkList pHead,const Elemtype elem){
LNode *p = pHead ->next;
int pos = 0;
while(p){
if (p->data==elem){
return pos;
}else{
pos ++;
p = p->next;
}
}
return -1;
}
/********************************************************************************
* function : get_length
* description : get the length of single LinkList
* input : struct LNode *pHead
* output : N/A
* return value : int
* author : HanyoungXue
* date : 2018-4-14
********************************************************************************/
int get_length(LinkList pHead){
if (!pHead ||!(pHead->next)){
return 0;
}
int length = 0;
LNode *p = pHead->next;
while(p){
p = p->next;
length ++;
}
return length;
}
/*********************************************************************************
* function : print_list
* description : print the all list
* input : struct LNode *pHead
* output : N/A
* return value : N/A
* author : HanyougXue
* date : 2018-4-14
*********************************************************************************/
void print_list(LinkList pHead){
if (is_empty_list(pHead)){
printf("link is empty!\n");
return;
}
LNode *p = pHead->next;
printf("linkList:\n");
while(p){
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
/*********************************************************************************
* function : reverse_list
* description : reverse single LinkList
* input : struct LNode **ppHead
* output : struct LNode **ppHead
* return value : N/A
* author : HanyoungXue
* date : 2018-4-14
*********************************************************************************/
void reverse_list(LinkList *ppHead){
if (!(*ppHead)||!((*ppHead)->next)){
return;
}
LNode *prev = NULL;
LNode *cur = (*ppHead)->next;
LNode *nex = NULL;
while(cur){
nex = cur->next;
cur->next = prev;
prev = cur;
cur = nex;
}
(*ppHead)->next = prev;
}
int main(int argc, char const *argv[]){
Elemtype A[MAX] = {4,5,2,1,3};
LinkList list = NULL;
init_list(&list);
create_list(&list,A,MAX);
print_list(list);
reverse_list(&list);
print_list(list);
insert_elem(&list,5,6);
print_list(list);
return 0;
}
网友评论