“link.h”
#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <malloc.h>
typedef int DataType;
typedef struct LinkNode
{
DataType data;
struct LinkNode *next;
}LinkNode,*pLinkNode,*pList;
void InitLinkList(pList* pHead);
//void Destroy(pList *pHead);
void PushBack(pList* pHead, DataType x);
void PrintList(pList list);
pLinkNode Find(pList head, DataType x);
void EraseNotTail(pLinkNode pos);//删除无头单链表的非尾节点
void ReverseList(pList* pHead);//反转（逆序）链表--2
void BubbleSort(pList * pHead);//排序链表（冒泡）--3
void InsertFrontNode(pLinkNode pos, DataType x);// 在当前节点前插入一个数据x-----5
pLinkNode Merge(pList l1, pList l2);//合并两个有序列表-----6
pLinkNode FindMidNode(pList head);//查找链表的中间节点---7
void InitLinkList(pList* pHead)//初始化
{
assert(pHead);
*pHead = NULL;
}
pLinkNode buyNode(DataType x)//构造节点
{
pLinkNode newNode = (pLinkNode)malloc(sizeof(LinkNode));
newNode->data = x;
newNode->next = NULL;
return newNode;
}
void PushBack(pList* pHead, DataType x)//尾插
{
pLinkNode newNode;
pLinkNode cur = *pHead;
assert(pHead);
newNode = buyNode(x);
if(*pHead == NULL)
{
*pHead = newNode;
return;
}
else
{
while(cur->next)
{
cur = cur->next;
}
cur->next = newNode;
}
}
pLinkNode Find(pList head, DataType x)//查找某一节点
{
pLinkNode cur = head;
if(head == NULL)
{
printf("链表中无节点\n");
}
else
{
while(cur)
{
if(cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
}
void PrintList(pList list)//打印
{
pList cur = list;
while(cur)
{
printf("%d ",cur->data);
cur = cur->next;
}
printf("over");
}
void EraseNotTail(pLinkNode pos)
{
DataType x;
pLinkNode del = NULL;
x = pos->data;
pos->data = pos->next->data;
pos->next->data = x;
del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void ReverseList(pList* pHead)//逆序
{
pLinkNode cur = *pHead;
pLinkNode prev = NULL;
pLinkNode newHead = NULL;
if(cur == NULL)
return;
if(cur->next == NULL)
return;
while(cur)
{
prev = cur;
cur = cur->next;
prev->next = newHead;
newHead = prev;
}
*pHead = newHead;
}
void BubbleSort(pList * pHead)//排序链表（冒泡）--3
{
pLinkNode cur = *pHead;
pLinkNode end = NULL;
DataType x;
assert(pHead);
while(cur != end)
{
while(cur&&cur->next!=end)
{
if(cur->data > cur->next->data)
{
x = cur->data;
cur->data = cur->next->data;
cur->next->data = x;
}
cur = cur->next;
}
end = cur;
cur = *pHead;
}
}
void InsertFrontNode(pLinkNode pos, DataType x)// 在当前节点前插入一个数据x-----5
{
pLinkNode newNode = buyNode(x);
DataType tmp;
assert(pos);
newNode->next = pos->next;
pos->next = newNode;
tmp = pos->data;
pos->data = newNode->data;
newNode->data = tmp;
}
pLinkNode Merge(pList l1, pList l2)//合并两个有序列表-----6
{
pList newHead = NULL;
pLinkNode cur = newHead;
if(l1 == l2)
{
return l1;
}
if(l1 == NULL && l2 != NULL)
{
return l2;
}
if(l1 !=NULL && l2 == NULL)
{
return l1;
}
if(l1->data < l2->data)
{
newHead = l1;
l1 = l1->next;
}
else
{
newHead = l2;
l2 = l2->next;
}
cur = newHead;
while(l1&&l2)
{
if(l1->data<l2->data)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if(l1)
{
cur->next = l1;
}
else
{
cur->next = l2;
}
return newHead;
}
pLinkNode FindMidNode(pList head)//查找链表的中间节点---7
{
pLinkNode cur = head;
pLinkNode mid = head;
if(cur == NULL)
{
return NULL;
}
while(cur->next)
{
cur = cur->next->next;
mid = mid->next;
}
return mid;
}
#endif //__LINK_LIST_H__
“test.c”
#include "link.h"
void Test1()
{
pList mylist;
pLinkNode ret = NULL;
InitLinkList(&mylist);
PushBack(&mylist,1);
PushBack(&mylist,2);
PushBack(&mylist,3);
PushBack(&mylist,4);
PushBack(&mylist,5);
ret = Find(mylist,2);
EraseNotTail(ret);
PrintList(mylist);
}
void Test2()
{
pList mylist;
InitLinkList(&mylist);
PushBack(&mylist,1);
PushBack(&mylist,4);
PushBack(&mylist,2);
PushBack(&mylist,5);
PushBack(&mylist,3);
BubbleSort(&mylist);
PrintList(mylist);
}
void Test3()
{
pList mylist;
pLinkNode ret = NULL;
InitLinkList(&mylist);
PushBack(&mylist,1);
PushBack(&mylist,2);
PushBack(&mylist,3);
PushBack(&mylist,4);
PushBack(&mylist,5);
ret = Find(mylist,4);
InsertFrontNode(ret,6);
PrintList(mylist);
}
void Test4()
{
pList mylist;
pLinkNode ret = NULL;
InitLinkList(&mylist);
PushBack(&mylist,1);
PushBack(&mylist,2);
PushBack(&mylist,3);
PushBack(&mylist,4);
PushBack(&mylist,5);
ret = FindMidNode(mylist);
if(ret != NULL)
{
printf("%d ",ret->data);
}
}
void Test5()
{
pList l1;
pList l2;
pList ret = NULL;
InitLinkList(&l1);
InitLinkList(&l2);
PushBack(&l1,1);
PushBack(&l1,3);
PushBack(&l1,5);
PushBack(&l2,2);
PushBack(&l2,4);
PushBack(&l2,6);
ret = Merge(l1,l2);
PrintList(ret);
}
void Test6()
{
pList mylist;
InitLinkList(&mylist);
PushBack(&mylist,1);
PushBack(&mylist,2);
PushBack(&mylist,3);
PushBack(&mylist,4);
PushBack(&mylist,5);
//PrintList(mylist);
ReverseList(&mylist);
PrintList(mylist);
}
int main()
{
Test6();
return 0;
}