单链表的基本功能实现

#include<stdio.h>
#include<assert.h>
#include<malloc.h>

#define ElemType int

typedef struct Node
{
ElemType data;
struct Node *next;
}Note,*PNode;

typedef struct List
{
PNode first;
PNode last;
size_t size;
}List;

typedef Node* It;

It begin(List *list)
{
return list->first->next;
}
It end(List *list)
{
return list->last->next;
}

Node* _buynode(ElemType x)
{
It s = (Node *)malloc(sizeof(Node));
assert(s != NULL);
s->data = x;
s->next = NULL;
return s;
}

void insert(List *list, It pos, ElemType x)
{
It p = list->first;
while(p->next != pos)
{
p = p->next;
}

It s = _buynode(x);
s->next = p->next;
p->next = s;
if(pos == NULL)
list->last = s;
list->size++;
}
void InitList(List *list)
{
list->first = list->last =(Node*)malloc(sizeof(Node));
assert(list->first != NULL);
list->first->next = NULL;
list->size = 0;
}

void push_back(List *list,ElemType x)
{
insert(list,end(list),x);
}

void show_list(List *list)
{
PNode p = list->first->next;
while(p != NULL)
{
printf("%d->",p->data);
p = p->next;
}
printf("Null\n");
}
void push_front(List *list,ElemType x)
{
insert(list,begin(list),x);
}

void pop_back(List *list)
{
if(list->size = 0)
{
printf("该链表为空，无法删除！");
return;
}
Node *p = list->first;
while(p->next != list->last)
p = p->next;

free(list->last);
list->last = p;
list->last->next = NULL;
list->size--;

}

void pop_front(List *list)
{
if(list->size = 0)
{
printf("该链表为空，无法删除！");
return;
}
Node *p = list->first->next;
list->first->next = p->next;
free(p);
if(list->size == 1)
{
list->last = list->first;
}
list->size--;
}

void insert_val(List *list,ElemType x)
{
It s = _buynode(x);
Node *p = list->first;
while(p->next!=NULL && p->next->data<x)
p = p->next;

if(p->next == NULL)
{
list->last = s;
}

s->next = p->next;
p->next = s;
list->size++;
}

Node* find(List *list,ElemType key)
{
Node *p = list->first->next;
while(p!=NULL && p->data!=key)
p = p->next;
return p;
}

int length(List *list)
{
return list->size;
}

void delete_val(List *list,ElemType key)
{
if(list->size == 0)
return;
Node *p = find(list,key);
if(p == NULL)
{
printf("要删除的数据不存在。\n");
return;
}
if(p == list->last)
{
pop_back(list);
}
else
{
Node *q =p->next;
p->data = q->data;
p->next = q->next;
free(q);
list->size--;
}
}

void sort(List *list)
{
if(list->size == 0 || list->size == 1)
return;
Node *s = list->first->next;
Node *q = s->next;
list->last = s;
list->last->next =NULL;
while(q != NULL)
{
s = q;
q = q->next;

Node *p = list->first;
while(p->next!=NULL && p->next->data<s->data)
p = p->next;

if(p->next == NULL)
{
list->last = s;
}

s->next = p->next;
p->next = s;

}
}

void resver(List *list)
{
if(list->size == 0 || list->size == 1)
{
return;
}
Node *p = list->first->next;
Node *q = p->next;

list->last = p;
list->last->next = NULL;

while(q != NULL)
{
p = q;
q = p->next;
p->next = list->first->next;
list->first->next = p;
}
}

void clear(List *list)
{
if(list->size == 0)
return;

Node *p = list->first->next;
while(p != NULL)
{
list->first->next = p->next;
free(p);
p = list->first->next;
}
list->last =list->first;
list->size = 0;
}

void destroy(List *list)
{
clear(list);
free(list->first);
list->first = list->last = NULL;
list->size = 0;
}

 

int main()
{
List mylist;
InitList(&mylist);
Node *p = NULL;
int select = 1;
ElemType Item;
while(select)
{
printf("*******************************************\n");
printf("*<<<<<<<<<<<<<链表功能列表>>>>>>>>>>>>>>>>*\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_val *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_val [10] sort *\n");
printf("* [11] resver [12] clear *\n");
printf("* [13] destory [0] quit_system *\n");
printf("*******************************************\n");
printf("请选择：>");
scanf("%d",&select);
if(select == 0)
break;

switch(select)
{
case 1:
printf("请输入要插入的数据(以-1结束)：>\n");
while(scanf("%d",&Item),Item != -1)
{
push_back(&mylist,Item);
}
break;
case 2:
printf("请输入要插入的数据(以-1结束)：>\n");
while(scanf("%d",&Item),Item != -1)
{
push_front(&mylist,Item);
}
break;
case 3:
show_list(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("请输入要插入的数据：>");
scanf("%d",&Item);
insert_val(&mylist,Item);
break;
case 7:
printf("请输入要查找的数据：>");
scanf("%d",&Item);
p = find(&mylist,Item);
if(p == NULL)
{
printf("要查看的数据在链表中不存在。\n");
}
else printf("要查找的数据存在。\n");
break;
case 8:
printf("单链表的长度为>%d",length(&mylist));
break;
case 9:
printf("请输入要删除的值：>");
scanf("%d",&Item);
delete_val(&mylist,Item);
break;
case 10:
sort(&mylist);
break;
case 11:
resver(&mylist);
break;
case 12:
clear(&mylist);
break;
// case 13:
// destroy(&mylist);
default:
printf("输入的命令错误，请重新输入。\n");
break;
}
}
destroy(&mylist);
}