关于单链表，是最熟悉不过的一种数据结构了。今天，花费了很长的时间写出了单链表，和大家分享一下，有问题大家可以提出来！！！
#define _CRT_SECURE_NO_WARNINGS 1
#ifndef __LINKLIST_H__
#define __LINKLIST_H__
#include<>
#include<>
#include<>
typedef int datatype;
typedef struct LinkNode
{
datatype data;
struct LinkNode *next;
}LinkNode,*pLinkNode;
typedef struct LinkList
{
LinkNode *pHead;
}LinkList,*pLinkList;
static enum A
{
EXIT,
INIT,
PUSHBACK,
POPBACK,
PUSHFRONT,
POPFRONT,
INSERT,
REMOVE,
REMOVEALL,
BUBBLESORT,
ERASE,
PRINTLIST
};
void InitLinkList(pLinkList pList);
void DestroyList(pLinkList pList);
void PushBack(pLinkList pList,datatype x);
void PopBack(pLinkList pList);
void PushFront(pLinkList pList, datatype x);
void PopFront(pLinkList pList);
void PrintList(pLinkList pList);
pLinkNode Find(pLinkList pList, datatype x);
void Insert(pLinkList pList, pLinkNode pos, datatype x);
void Remove(pLinkList pList,datatype x);
void RemoveAll(pLinkList pList, datatype x);
void Erase(pLinkList pList,pLinkNode pos);
void BubbleSort(pLinkList pList);
void meau();
#endif //!__LINKLIST_H__#define _CRT_SECURE_NO_WARNINGS 1
#include""
void meau()
{
printf("$$$$$$$$$$$$$$ SEQLIST $$$$$$$$$$$$$$$$\n");
printf("$$$$$$$$$$$$$$$$$$$$$$￥$$$$$$$$$$$$$$$$$$$$$\n");
printf("$$$ 2.push_back $$$\n");
printf("$$$ 3.pop_back 4.push_front $$$\n");
printf("$$$ 5.pop_front $$$\n");
printf("$$$ $$$\n");
printf("$$$ $$$\n");
printf("$$$ $$$\n");
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
}
void InitLinkList(pLinkList pList)
{
assert(pList);
pList->pHead = NULL;
}
void DestroyList(pLinkList pList)
{
assert(pList);
pLinkNode p = NULL;
pLinkNode cur = NULL;
cur = pList->pHead;
if (NULL == pList->pHead)
{
return;
}
while (cur != NULL)
{
p = cur;
cur = cur->next;
free(p);
}
pList->pHead = NULL;
}
void judgement(pLinkNode newnode)
{
if (NULL == newnode)
{
printf("out of memory");
exit(EXIT_FAILURE);
}
}
void PushBack(pLinkList pList, datatype x)
{
assert(pList);
pLinkNode cur= NULL;
pLinkNode prev = NULL;
pLinkNode newnode = (pLinkNode)malloc(sizeof(LinkNode));
newnode->data = x;
newnode->next = NULL;
judgement(newnode);
if (NULL == pList->pHead)
{
pList->pHead = newnode;
return;
}
else
{
cur = pList->pHead;
while (cur != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = newnode;
}
}
void PopBack(pLinkList pList)
{
pLinkNode cur = NULL;
pLinkNode del = NULL;
assert(pList);
cur = pList->pHead;
if (pList->pHead == NULL)
{
printf("此链表为空链表\n");
return;
}
else if (NULL==pList->pHead->next)
{
free(cur);
pList->pHead = NULL;
return;
}
else
{
while (cur->next != NULL)
{
del = cur;
cur = cur->next;
}
free(cur);
del->next = NULL;
}
}
void PushFront(pLinkList pList, datatype x)
{
assert(pList);
pLinkNode newnode = (pLinkNode)malloc(sizeof(LinkNode));
newnode->data = x;
newnode->next = NULL;
judgement(newnode);
newnode->next = pList->pHead;
pList->pHead = newnode;
}
void PopFront(pLinkList pList)
{
pLinkNode cur = NULL;
pLinkNode del = NULL;
assert(pList);
if (pList->pHead == NULL)
{
printf("此链表为空链表\n");
return;
}
else
{
cur = pList->pHead->next;
del = pList->pHead;
free(del);
pList->pHead = cur;
}
}
void PrintList(pLinkList pList)
{
pLinkNode cur = NULL;
assert(pList);
cur = pList->pHead;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
pLinkNode Find(pLinkList pList, datatype x)
{
pLinkNode cur = NULL;
pLinkNode find = NULL;
assert(pList);
cur = pList->pHead;
while (cur != NULL)
{
if (x == cur->data)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void Insert(pLinkList pList, pLinkNode pos, datatype x)
{
assert(pList);
pLinkNode cur = pList->pHead;
pLinkNode front =NULL;
pLinkNode newnode = (pLinkNode)malloc(sizeof(LinkNode));
judgement(newnode);
newnode->data = x;
newnode->next = NULL;
if (pos == NULL)
{
printf("没有这样一个元素，无法插入\n");
return;
}
while (cur != NULL)
{
if (cur == pos)
{
break;
}
front = cur;
cur = cur->next;
}
if (NULL == front)
{
pList->pHead = newnode;
newnode->next = cur;
}
else
{
front->next = newnode;
newnode->next = cur;
}
}
void Remove(pLinkList pList, datatype x)
{
pLinkNode cur = NULL;
pLinkNode del = NULL;
pLinkNode front = NULL;
assert(pList);
if (pList->pHead == NULL)
{
printf("此链表为空链表\n");
return;
}
cur = pList->pHead;
front = cur;
while (cur != NULL)
{
if (cur->data == x)
{
if (cur == pList->pHead) //考虑第一个节点的情况
{
del = cur;
pList->pHead = cur->next;
free(del);
}
else //删除非第一个节点
{
del = cur;
front->next = cur->next;
free(del);
}
return;
}
else
{
front = cur;
cur = cur->next;
}
}
printf("没有值为%d的节点\n", x);
}
void RemoveAll(pLinkList pList, datatype x)
{
pLinkNode cur = NULL;
pLinkNode del = NULL;
pLinkNode front = NULL;
assert(pList);
if (pList->pHead == NULL)
{
printf("此链表为空链表\n");
return;
}
cur = pList->pHead;
front = cur;
while (cur != NULL)
{
if (cur->data == x)
{
if (cur == pList->pHead) //考虑第一个节点的情况
{
del = cur;
front = cur->next; //记得要移动front
pList->pHead = cur->next;
free(del);
}
else //删除非第一个节点
{
del = cur;
front->next = cur->next;
free(del);
}
cur = front; //让cur移动到当前的front进行操作
}
else
{
front = cur;
cur = cur->next;
}
}
//printf("没有值为%d的节点\n", x);
}
void Erase(pLinkList pList, pLinkNode pos)
{
pLinkNode cur = NULL;
pLinkNode erase = NULL;
pLinkNode front =pList->pHead ;
assert(pList);
cur = pList->pHead;
if (pList->pHead == NULL)
{
printf("此链表为空链表");
return;
}
while (cur != NULL)
{
if (pos == cur)
{
if (pos == pList->pHead)
{
erase = pos;
pList->pHead = cur->next;
free(erase);
erase->next = NULL;
}
else
{
erase = pos;
front->next = cur->next;
free(erase);
erase->next = NULL;
}
return;
}
else
{
front = cur;
cur = cur->next;
}
}
}
void BubbleSort(pLinkList pList)
{
pLinkNode cur = NULL;
pLinkNode tail = NULL;
assert(pList);
cur = pList->pHead;
if ((pList->pHead == NULL)
||(pList->pHead->next==NULL)) //对于无节点和只有一个节点不进行排序
{
return;
}
while (cur != tail) //当尾指针不等于头指针时进行冒泡
{
while (cur->next != tail) //控制cur指针最后到的位置是倒数第二个节点
{
if (cur->data > cur->next->data)//进行冒泡
{
datatype tmp = cur->data;
cur->data = cur->next->data;
cur->next->data = tmp;
}
cur = cur->next; //让cur向后移动进行下一次冒泡
}
tail = cur; //让尾指针向前移动
cur = pList->pHead; //让当前的指针重置到头节点
}
}
#define _CRT_SECURE_NO_WARNINGS 1
#include""
void Test()
{
LinkList list;
int input = 1;
datatype x = 0;
InitLinkList(&list);
while (input)
{
meau();
printf("请选择操作：");
scanf("%d", &input);
fflush(stdin);
switch (input)
{
case INIT:
InitLinkList(&list);
break;
case PUSHBACK:
printf("请输入你要尾插节点的数据：\n");
scanf("%d", &x);
fflush(stdin);
PushBack(&list,x);
break;
case POPBACK:
PopBack(&list);
break;
case PUSHFRONT:
printf("请输入你要尾插节点的数据：\n");
scanf("%d", &x);
fflush(stdin);
PushFront(&list, x);
break;
case POPFRONT:
PopFront(&list);
break;
case INSERT:
printf("请输入你所插入位置的节点元素值");
scanf("%d", &x);
fflush(stdin);
pLinkNode pos = Find(&list, x);
printf("请输入你所插入节点元素值");
scanf("%d", &x);
fflush(stdin);
Insert(&list, pos, x);
break;
case REMOVE:
printf("请输入你需要删除单一节点的值：");
scanf("%d", &x);
fflush(stdin);
Remove(&list,x);
break;
case REMOVEALL:
printf("请输入你需要删除节点的值：");
scanf("%d", &x);
fflush(stdin);
RemoveAll(&list, x);
break;
case BUBBLESORT:
BubbleSort(&list);
break;
case ERASE:
printf("请输入你所要擦除的节点数据：");
scanf("%d", &x);
fflush(stdin);
pos = Find(&list, x);
Erase(&list, pos);
break;
case PRINTLIST:
PrintList(&list);
break;
case EXIT:
DestroyList(&list);
break;
default:
input = 1;
break;
}
}
}
int main()
{
Test();
system("pause");
return 0;
}