1．编写头文件
#include<stdio.h>
#include<stdlib.h>
#define datatype int
struct node
{
int num; //编号
datatype data; //存储的数据
struct node *pNext;
};
typedef struct node Node; //简写
//函数设计的思想
//改变一个变量需要变量的地址，改变指针需要指针的地址
//不用二级指针，必须要用返回值赋值
//增加，删除，查询，修改，排序，逆转
void backaddnode(Node **ppnode, int num, datatype data);//增加节点
Node * backaddnodeA(Node *pnode, int num, datatype data);//
void showallnode(Node *pnode);//显示所有的节点
Node * searchfirst(Node *pnode, int num);//查询
int change(Node *pnode, int oldnum, int newnum);//修改失败返回0，成功返回1
Node * rev(Node *pnode);//链表的逆转
Node * delete(Node *pnode, int num);//删除
Node * insert(Node *pnode, int findnum, int newnum, datatype data);//实现插入，前面插入
void sort(Node *pnode, char ch);//ch==> ch==<
2．编写链表的实现代码
#include "linknode.h"
//增加节点
void backaddnode(Node **ppnode, int num, datatype data)
{
//添加节点，需要先增加节点
Node *pNewNode = (Node *)malloc(sizeof(Node));
pNewNode->num = num; //赋值
pNewNode->data = data; //赋值
pNewNode->pNext = NULL;//尾部
//如果链表为NULL
if (*ppnode == NULL)
{
//存储新建节点的地址
*ppnode = pNewNode;
}
else
{
Node *p = *ppnode;//等于头结点
while (p->pNext != NULL)
{
//一直循环到最后一个节点的地址
p = p->pNext;
}
//表示尾部插入
p->pNext = pNewNode;
}
}
Node * backaddnodeA(Node *pnode, int num, datatype data)
{
//定义新节点
Node *pNewNode = (Node *)malloc(sizeof(Node));
pNewNode->num = num;
pNewNode->data = data;
pNewNode->pNext = NULL;
if (pnode == NULL)
{
//存储新建节点的地址
pnode = pNewNode;
}
else
{
//等于头结点
Node *p = pnode;
while (p->pNext != NULL)
{
//一直循环到最后一个节点的地址
p = p->pNext;
}
//尾部插入
p->pNext = pNewNode;
}
return pnode;
}
//显示所有的节点
void showallnode(Node *pnode)
{
printf("打印链表:\n");
Node *p = pnode;
while(p != NULL)
{
printf("%p,%p,%d,%d\n", p, p->pNext, p->num, p->data);
p = p->pNext;
}
}
//查询
Node * searchfirst(Node *pnode, int num)
{
Node *p = NULL;
//for循环
for (p = pnode; p != NULL;p=p->pNext)
{
if (num == p->num)
{
// 返回找到的地址
return p;
break;
}
}
return NULL;
}
//修改失败返回0，成功返回1
int change(Node *pnode, int oldnum, int newnum)
{
AAA:if (pnode != NULL)
{
//查找
if (oldnum == pnode->num)
{
pnode->num = newnum;
return 1;
}
pnode = pnode->pNext;
goto AAA;
}
return 0;
}
//链表的逆转
Node * rev(Node *pnode)
{
Node *p1, *p2, *p3;
p1 = p2 = p3 = NULL;//避免野指针
//表示为空链表或者只有一个节点的情况下，直接返回
if (pnode == NULL || pnode->pNext == NULL)
{
//返回头结点
return pnode;
}
else
{
p1 = pnode;
p2 = pnode->pNext;
//p2 == NULL时表示p1是最后一个节点了。
while (p2!=NULL)
{
//这里p3相当于中间变量，用于保存p2最开始的指向
p3 = p2->pNext;//布局第三个点
//将指针地址转向
p2->pNext = p1;
//循环向后移动
p1 = p2;
p2 = p3;
}
//将最开始的头节点的Next变成NULL
pnode->pNext = NULL;
//改变头节点位置，由最开始的位置变成最后节点
pnode = p1;
return pnode;
}
}
/************************************************************************/
/* 删除含有num的节点，删除节点的时候需要使用两个节点，其中一个节点要保存*/
/* 要删除节点的上一个节点的位置 */
/************************************************************************/
Node * delete(Node *pnode, int num)
{
Node *p1 = NULL, *p2 = NULL;
p1 = pnode;
//如果p1==NULL说明p2已经是最后节点
while (p1 != NULL)
{
if (p1->num == num)
{
//p1保存了要删除节点的地址，实际上p1就是要删除的那个节点
break;
}
else
{
//p2保存p1上一个节点的位置
p2 = p1;
p1 = p1->pNext;
}
}
//如果要删除的节点恰好是首节点
if (p1 == pnode)
{
//断开与p1的关系，跳过了这个节点
pnode = p1->pNext;
//删除节点
free(p1);
}
//中间和末尾删除的情况
else
{
//这时候把p2代表的那个节点地址指向p1的下一个节点
p2->pNext = p1->pNext;
//删除节点
free(p1);
}
//因为首地址改变了，所以要返回首地址的值
return pnode;
}
/************************************************************************/
/* 实现插入，前面插入 */
/* 同样要借助两个节点，一个节点存储查找到的目标节点，另外一个节点存储 */
/* 目标节点前的一个节点 */
/************************************************************************/
Node * insert(Node *pnode, int findnum, int newnum, datatype data)
{
Node *p1, *p2;
p1 = p2 = NULL;
p1 = pnode;
while (p1 != NULL)
{
if (p1->num == findnum)
{
//p1保存了要插入节点的地址
break;
}
else
{
//p1是查找到的目标节点，p2保存其上一个节点的地址
p2 = p1;
p1 = p1->pNext; //先前循环
}
}
//生成节点
Node *pnewnode = (Node *)malloc(sizeof(Node));
pnewnode->num = newnum;
pnewnode->data = data;
//表示找到的恰好是首节点
if (pnode == p1)
{
//新节点的下一个节点是头节点，这里下面也可以换成p1
pnewnode->pNext = pnode;
//这种方式表示的是头节点
pnode = pnewnode;
}
else
{
//将新节点的目标地址指向目标节点
pnewnode->pNext = p1;
//将p1的上一个节点的下一个的地址赋值成新节点的位置
p2->pNext = pnewnode;
}
return pnode;
}
/************************************************************************/
/* 当传递'>'的时候表示的是降序排列 */
/* 当传递'<'的时候表示的是升序排列 */
/************************************************************************/
void sort(Node *pnode, char ch)
{
if (ch == '<')
{
for (Node *p1 = pnode; p1 != NULL;p1=p1->pNext)
{
for (Node *p2 = pnode; p2 != NULL;p2=p2->pNext)
{
if (p1->num > p2->num)
{
//这里的Node作为中间变量
Node tnode;
tnode.num = p1->num;
p1->num = p2->num;
//交换数据
p2->num = tnode.num;
//交换data数据
tnode.data = p1->data;
p1->data = p2->data;
p2->data = tnode.data;
}
}
}
}
else
{
for (Node *p1 = pnode; p1 != NULL; p1=p1->pNext)
{
for (Node *p2 = pnode; p2 != NULL;p2 = p2->pNext)
{
if (p1->num < p2->num)
{
//作为中间变量
Node tnode;
tnode.num = p1->num;
p1->num = p2->num;
p2->num = tnode.num; //交换数据
//交换data
tnode.data = p1->data;
p1->data = p2->data;
p2->data = tnode.data;
}
}
}
}
}
3.编写main.c测试编写的链表
#include "linknode.h"
int main(int argc,char *argv[])
{
//定义一个头结点(这是最开始要做的)
Node *pnode = NULL;
//backaddnode(&pnode, 1, 1);
//backaddnode(&pnode, 2, 12);
//backaddnode(&pnode, 3, 14);
//showallnode(pnode);
pnode = backaddnodeA(pnode, 1, 1);
//pnode = backaddnodeA(pnode, 12, 11);
pnode = backaddnodeA(pnode, 3, 111);
pnode = backaddnodeA(pnode, 14, 1111);
pnode = backaddnodeA(pnode, 5, 11111);
//pnode = backaddnodeA(pnode, 16, 111111);
showallnode(pnode);
printf("改变参数\n");
change(pnode, 14, 141414);
showallnode(pnode);
//反转
printf("反转\n");
pnode = rev(pnode);
showallnode(pnode);
//删除
pnode = delete(pnode,1);
pnode = delete(pnode, 3);
showallnode(pnode);
//插入
pnode = insert(pnode, 3, 3, 333);
pnode = insert(pnode, 1, 13, 1333);
showallnode(pnode);
//排序
sort(pnode, '<');
showallnode(pnode);
sort(pnode, '>');
showallnode(pnode);
Node *pfind = searchfirst(pnode, 5);
if (pfind == NULL)
{
printf("没有找到");
}
else
{
printf("%p,%d,%d,%p\n", pfind, pfind->num, pfind->data, pfind->pNext);
}
getchar();
return 0;
}
