linklist.h
#ifndef __LINKLIST_H__
#define __LINKLIST_H__
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct LinkNode
{
DataType data;
struct LinkNode* next;
}LinkNode,*pLinkNode;
typedef struct LinkList
{
LinkNode* pHead;
}LinkList,*pLinkList;
void InitLinkList(pLinkList list);
void DestoryList(pLinkList list);
void PushBack(pLinkList list , DataType x);
void PopBack(pLinkList list);
void PushFront(pLinkList list , DataType x);
void PopFront(pLinkList list);
void PrintList(pLinkList list);
pLinkNode Find(pLinkList list,DataType x);
void Insert(pLinkList list, pLinkNode pos, DataType x);
void Remove(pLinkList list, DataType x);
void RemoveAll(pLinkList list, DataType x);
void Erase(pLinkList list,pLinkNode pos);
void BubbleSort(pLinkList list);
void SelectSort(pLinkList list);
void InsertSort(pLinkList list);
#endif //__LINKLIST_H__
linkllist.c
#include"linklist.h"
void CreateNode(pLinkNode *newNode, DataType x) //创建节点
{
*newNode = (pLinkNode)malloc(sizeof(LinkNode));
if (NULL == *newNode)
{
printf("out of memory\n");
exit(EXIT_FAILURE);
}
(*newNode)->data = x;
(*newNode)->next = NULL;
}
void InitLinkList(pLinkList list) //初始化
{
list->pHead = NULL;
assert(list);
}
void DestoryList(pLinkList list)
{
assert(list);
if (NULL==list->pHead) //链表为空直接返回
{
return;
}
else
{
pLinkNode cur = list->pHead; //cur指向第一个结点
while (cur != NULL)
{
list->pHead = cur->next; //pHead指向cur的下一个结点，当cur是最后一个结点时，pHead指向空
free(cur);
cur = list->pHead; //cur指向当前第一个结点,当链表为空时，cur指向空
}
}
}
void PushBack(pLinkList list, DataType x)
{
pLinkNode newNode = NULL;
assert(list);
CreateNode(&newNode,x);
if (NULL == (list->pHead)) //如果是空链表，直接插入头指针之后
{
list->pHead = newNode;
}
else
{
pLinkNode cur = list->pHead;
while (NULL != (cur->next)) //找到最后一个结点cur
{
cur = cur->next;
}
cur->next = newNode;
}
}
void PopBack(pLinkList list)
{
assert(list);
if (NULL == list->pHead)
{
return;
}
else
{
pLinkNode cur = list->pHead;
if (NULL == cur->next) //如果只有一个结点
{
free(cur);
list->pHead= NULL;
}
else
{
while (NULL != cur->next->next) //大于一个结点，先找到倒数第二个结点
{
cur = cur->next;
}
free(cur->next);
cur->next= NULL;
}
}
}
void PushFront(pLinkList list, DataType x)
{
pLinkNode newNode = NULL;
assert(list);
CreateNode(&newNode, x);
newNode->next =list->pHead; //newNode的指针域先指向第一个结点
list->pHead= newNode; //头指针指向newNode
}
void PopFront(pLinkList list)
{
pLinkNode cur = list->pHead; //cur指向第一个结点
assert(list);
if (NULL == list->pHead) //空链表
{
return;
}
list->pHead = cur->next; //指向第一个结点的指针域
free(cur);
cur = NULL;
}
void PrintList(pLinkList list)
{
pLinkNode cur = list->pHead;
assert(list);
while (NULL != cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("over\n");
}
pLinkNode Find(pLinkList list, DataType x)
{
pLinkNode cur = list->pHead;
assert(list);
while (NULL != cur)
{
if (cur->data == x)
{
break;
}
cur = cur->next;
}
return cur;
}
void Insert(pLinkList list, pLinkNode pos, DataType x) //在pos后面插入元素
{
pLinkNode cur = list->pHead;
pLinkNode newNode = NULL;
assert(list);
CreateNode(&newNode, x);
while (NULL != cur) //先找到这个位置
{
if (cur == pos)
{
break;
}
cur = cur->next;
}
if (NULL != cur)
{
newNode->next=cur->next;
cur->next = newNode;
}
else
{
printf("没有这个结点\n");
}
}
void Remove(pLinkList list, DataType x)
{
pLinkNode cur = list->pHead;
pLinkNode p = list->pHead;
assert(list);
if (NULL == list->pHead) //空链表直接返回
{
return;
}
if (NULL == cur->next) //如果只有一个结点
{
if (cur->data == x)
{
list->pHead = cur->next;
free(cur);
return;
}
}
else
{
if (cur->data == x) //先判断第一个结点是不是要删除的结点
{
list->pHead = cur->next;
free(cur);
return;
}
cur = cur->next;
while (NULL != cur)
{
if (cur->data == x)
{
p->next = cur->next; //p结点的指针域指向要删除结点的指针域
free(cur);
return;
}
p = cur;
cur = cur->next;
}
}
}
void RemoveAll(pLinkList list, DataType x)
{
pLinkNode cur = list->pHead;
pLinkNode p = NULL;
assert(list);
if (NULL == list->pHead)
{
return;
}
while (NULL != cur)
{
if (NULL == list->pHead->next) //如果要只有一个结点
{
if (cur->data == x) //如果是则删除
{
list->pHead = cur->next;
free(cur);
return;
}
}
else if (list->pHead->data == x) //判断是不是第一个结点，是则删除，继续判断
{
list->pHead = cur->next;
free(cur);
cur = list->pHead;
}
else
{
break;
}
}
//要删除的结点在第一个结点之后
cur = cur->next;
p = list->pHead ;
while (NULL != cur)
{
if (cur->data == x)
{
p->next = cur->next; //p结点的指针域指向要删除结点的指针域
free(cur);
cur = p;
}
p = cur;
cur = cur->next;
}
}
void Erase(pLinkList list, pLinkNode pos) //删除pos后面的结点
{
pLinkNode cur = list->pHead;
pLinkNode p = list->pHead;
assert(list);
if (NULL == cur)
{
return;
}
if (NULL == cur->next) //如果只有一个结点
{
if (cur == pos)
{
free(cur);
list->pHead = NULL;
}
}
else
{
if (cur == pos) //如果是第一个结点
{
list->pHead = cur->next;
free(cur);
return;
}
cur = cur->next;
while (NULL != cur)
{
if (cur == pos)
{
p->next = cur->next;
free(cur);
return;
}
p= cur;
cur = cur->next;
}
}
}
void BubbleSort(pLinkList list)
{
pLinkNode cur = list->pHead;
pLinkNode p1= list->pHead;
int flag = 0;
DataType tmp=0;
pLinkNode p2 = list->pHead->next;
assert(list);
if (NULL == list->pHead)
{
return;
}
if (NULL == cur->next)
{
return;
}
cur = cur->next;
while (NULL!=cur)
{
flag = 1;
while (NULL != p2)
{
if (p1->data > p2->data)
{
tmp = p1->data;
p1->data = p2->data;
p2->data = tmp;
flag = 0;
}
p2 = p2->next;
p1 = p1->next;
}
if (flag)
{
break;
}
p1 = list->pHead;
p2 = list->pHead->next;
cur = cur->next;
}
}
test.c
#include"linklist.h"
void Menu()
{
printf("**********************************\n");
printf("*0.Quit 1.InitLinkList *\n");
printf("*2.PushBack 3.PopBack *\n");
printf("*4.PushFront 5.PopFront *\n");
printf("*6.PrintList 7.Find *\n");
printf("*8.Insert 9.Remove *\n");
printf("*10.RemoveAll 11.Erase *\n");
printf("*12.BubbleSort \n");
printf("**********************************\n\n");
printf("请选择: ");
}
void test()
{
LinkList list;
DataType x = 0;
pLinkNode pos = NULL;
int n = -1;
while (1)
{
Menu();
scanf("%d", &n);
switch (n)
{
case 0:
DestoryList(&list);
exit(1);
break;
case 1:
InitLinkList(&list);
break;
case 2:
printf("请输入：");
scanf("%d",&x);
PushBack(&list,x);
break;
case 3:
PopBack(&list);
break;
case 4:
printf("请输入：");
scanf("%d", &x);
PushFront(&list,x);
break;
case 5:
PopFront(&list);
break;
case 6:
PrintList(&list);
break;
case 7:
printf("请输入：");
scanf("%d", &x);
pos=Find(&list,x);
printf("查找成功\n");
break;
case 8:
printf("请输入元素：");
scanf("%d", &x);
Insert(&list,pos,x);
break;
case 9:
printf("请输入：");
scanf("%d", &x);
Remove(&list,x);
break;
case 10:
printf("请输入：");
scanf("%d", &x);
RemoveAll(&list,x);
break;
case 11:
Erase(&list,pos);
break;
case 12:
BubbleSort(&list);
break;
default:
printf("选择无效,请重新选择\n");
break;
}
}
}
int main()
{
test();
system("pause");
return 0;
}
