链式栈
// stacklinknode.h
#define datatype int
struct stacknode
{
int num;//编号
datatype data;//数据
struct stacknode *pNext;//指针域
};
typedef struct stacknode StackNode;//简化
StackNode * init(StackNode * phead);//初始化
StackNode * push(StackNode * phead, int num, datatype data);//进栈
StackNode * pop(StackNode * phead, StackNode * poutdata);//出栈
StackNode * freeall(StackNode * phead);//清空
StackNode * printfall(StackNode * phead);//打印
// stacklinknode.c
#include"stacklinknode.h"
#include<stdio.h>
#include<stdlib.h>
StackNode * init(StackNode * phead)//初始化
{
return NULL;
}
StackNode * push(StackNode * phead, int num, datatype data)//进栈
{
StackNode *pnewnode = (StackNode *)malloc(sizeof(StackNode));//创建节点
pnewnode->num = num;
pnewnode->data = data;
pnewnode->pNext = NULL;//开辟节点并赋值
if (phead == NULL)//空链表，直接连接上
{
phead = pnewnode;//连接一个节点
}
else
{
StackNode *p = phead;
while (p->pNext!=NULL)
{
p = p->pNext;//一直向前
}
p->pNext = pnewnode;//插入
}
return phead;//返回头结点
}
StackNode * printfall(StackNode * phead)
{
if (phead==NULL)
{
return NULL;
}
else
{
printf("%d,%d,%p,%p\n", phead->num, phead->data,phead,phead->pNext);
printfall(phead->pNext);//打印
}
}
StackNode * pop(StackNode * phead, StackNode * poutdata)
{
if (phead == NULL)
{
return NULL;//已经没有元素
}
else if (phead->pNext==NULL)
{
poutdata->num = phead->num;
poutdata->data = phead->data;//取出数据
free(phead);//释放内存
phead = NULL;//只有一个节点
return phead;
}
else
{
StackNode *p = phead;
while (p->pNext->pNext!=NULL)
{
p = p->pNext;//循环到倒数第二个节点
}
poutdata->num = p->pNext->num;
poutdata->data = p->pNext->data;//取出数据
free(p->pNext);//释放
p->pNext = NULL;
return phead;
}
}
//删除所有节点
StackNode * freeall(StackNode * phead)
{
if (phead == NULL)
{
return NULL;
}
else
{
StackNode *p1=NULL, *p2=NULL;
p1 = phead;//头结点
while (p1->pNext != NULL)
{
p2 = p1->pNext;//保存下一个节点
p1->pNext = p2->pNext;//跳过p2
free(p2);//释放节点
}
free(phead);
return NULL;
}
}
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"stacklinknode.h"
/*
利用链式栈，先进后出的原则。 实现10进制数字转化为2进制数字
*/
void main01()
{
int num;
scanf("%d", &num);
printf("num=%d\n", num);//打印数据
StackNode *phead = NULL;//创建一个链式栈的头结点
printf("\n\n");
while (num)
{
printf("%d\n", num % 2);
phead = push(phead, num%2, 0);
num /= 2;
}
while (phead != NULL)
{
StackNode *pout = (StackNode *)malloc(sizeof(StackNode));
phead = pop(phead, pout);
printf("%d", pout->num);//出栈
}
system("pause");
}
void main()
{
StackNode *phead=NULL;//创建一个链式栈的头结点
phead = init(phead);//设置栈为空
phead = push(phead, 1, 1);
phead = push(phead, 2, 11);
phead = push(phead, 3, 111);
phead = push(phead, 4, 1111);
phead = push(phead, 5, 11111);
printfall(phead);
phead = freeall(phead);
printf("\n释放以后");
printfall(phead);
//while (phead!=NULL)
//{
// //保存出栈的数据
// printf("出栈\n");
// StackNode *pout =(StackNode *) malloc(sizeof(StackNode));
// phead = pop(phead, pout);
// printf("出栈之后\n");
// printfall(phead);
// printf("\n出栈之后的数据%d,%d", pout->num, pout->data);
//}
system("pause");
}
链表队列以及优先队列
//queue.h
struct queue
{
int num;//代表数据
int high;//优先级1111
struct queue *pNext;//存储下一个节点的地址
};
typedef struct queue Queue;//简化队列
Queue * init(Queue *queueA);//初始化
Queue * EnQueue(Queue *queueA, int num, int high);//入队
Queue * DeQueue(Queue *queueA, Queue *pout);//出队
Queue * freeall(Queue *queueA);//清空
void sort(Queue *queueA);//优先级排队
void printfall(Queue *queueA);//打印所有数据，递归
Queue * insertEnQueue(Queue *queueA, int num, int high);
//queue.c
#include"Queue.h"
#include<stdio.h>
#include<stdlib.h>
Queue * init(Queue *queueA)//初始化
{
return NULL;
}
Queue * EnQueue(Queue *queueA, int num, int high)//顺序入队
{
Queue *pnewnode = (Queue *)malloc(sizeof(Queue));//分配内存
pnewnode->num = num;
pnewnode->high = high;
pnewnode->pNext = NULL;
if (queueA==NULL)//链表为空
{
queueA = pnewnode;
//sort(queueA);//排队
return queueA;//返回值
}
else
{
Queue *p = queueA;//头结点
while (p->pNext!=NULL)
{
p = p->pNext;
}
//确定要插入的位置
p->pNext = pnewnode;//插入
//sort(queueA);//排队
return queueA;//返回
}
}
Queue * DeQueue(Queue *queueA, Queue *pout)//顺序出队
{
if (queueA == NULL)
{
return NULL;
}
else
{
pout->num = queueA->num;
pout->high = queueA->high;//赋值
Queue *ptemp = queueA;//记录要删除的地址
queueA = queueA->pNext;//跳过queueA
free(ptemp);//释放节点
return queueA;
}
}
Queue * freeall(Queue *queueA)//清空
{
}
Queue * insertEnQueue(Queue *queueA, int num, int high) //队列插入
{
Queue *pnewnode = (Queue *)malloc(sizeof(Queue));//分配内存
pnewnode->num = num;
pnewnode->high = high;
if (queueA == NULL)//节点为空
{
pnewnode->pNext = NULL;
queueA = pnewnode;
return queueA;
}
else
{
if (pnewnode->high >queueA->high)
{
pnewnode->pNext = queueA;//头部插入
queueA = pnewnode;//指向这个节点
return queueA;
}
else
{
Queue *p = queueA;//头结点
while (p->pNext != NULL)
{
p = p->pNext;
}
//p循环到尾部
if (pnewnode->high <= p->high)
{
p->pNext = pnewnode;
pnewnode->pNext = NULL;
return queueA;
}
else
{
Queue *p1, *p2;
p1 = p2 = NULL;//避免也指针
p1 = queueA;//头结点
while (p1->pNext != NULL)
{
p2 = p1->pNext;
if (p1->high>=pnewnode->high && p2->high<pnewnode->high)
{
pnewnode->pNext = p2;
p1->pNext = pnewnode;//插入
break;
}
p1 = p1->pNext;
}
return queueA;
}
}
}
}
void sort(Queue *queueA)//优先级排队
{
if (queueA == NULL || queueA->pNext == NULL)
{
return;
}
//for (Queue * p1 = queueA; p1 != NULL;p1=p1->pNext)
//{
// for (Queue *p2 = queueA; p2 != NULL; p2 = p2->pNext)
// {
// if (p1->high >p2->high)
// {
// Queue temp;
// temp.num = p1->num;
// p1->num = p2->num;
// p2->num = temp.num;
// temp.high = p1->high;
// p1->high = p2->high;
// p2->high = temp.high;//交换就节点数据
// }
// }
//}
}
void printfall(Queue *queueA)//递归
{
if (queueA==NULL)
{
return;
}
else
{
printf("%d,%d,%p,%p\n", queueA->num, queueA->high, queueA, queueA->pNext);
printfall(queueA->pNext);//进入下一个节点
}
}
//main.c
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
void main()
{
Queue *phead = NULL;//创建头结点
phead = init(phead);//初始化
phead = insertEnQueue(phead, 1, 1);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 2, 12);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 3, 3);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 4, 14);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 5, 5);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 6, 16);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 6, 0);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 7, 0);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 8, 0);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 9, 1);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 10, 0);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 11, 16);
printf("\n");
printfall(phead);
phead = insertEnQueue(phead, 111, 19);
printf("\n");
printfall(phead);
//while (phead != NULL)//不为空就继续
//{
// //分配内存
// Queue * ptemp = (Queue *)malloc(sizeof(Queue));
// phead = DeQueue(phead, ptemp);
// printf("\n拉屎一次以后\n");
// printfall(phead);
// printf("\n拉出来的是%d,%d", ptemp->num, ptemp->high);
//}
system("pause");
}
封装链表库
//linknode.h
#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==<
//linknode.c
#include"linknode.h"
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 backaddnode(Node **ppnode, int num, datatype data)//增加节点
{
Node *pnewnode = (Node *)malloc(sizeof(Node));
pnewnode->num = num;//赋值
pnewnode->data = data;//赋值
pnewnode->pNext = NULL;//尾部
if (*ppnode == NULL)
{
*ppnode = pnewnode;//存储新建节点的地址
}
else
{
Node *p = *ppnode;//等于头结点
while (p->pNext != NULL)
{
p = p->pNext;//一直循环到最后一个节点的地址
}
p->pNext = pnewnode;//尾部插入
}
}
void showallnode(Node *pnode)//显示所有的节点
{
printf("\n打印链表\n");
while (pnode != NULL)
{
printf("%p,%p",pnode,pnode->pNext);
printf(" %d,%d\n", pnode->num, pnode->data);
pnode = pnode->pNext;
}
}
Node * searchfirst(Node *pnode, int num)
{
for (Node *p=pnode;p!=NULL;p=p->pNext)//for循环
{
if (num==p->num)
{
return p;//返回找到的地址
break;
}
}
return NULL;
}
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;
while (p2 != NULL)
{
p3 = p2->pNext;//布局第三个点
p2->pNext = p1;//地址转向
p1 = p2;//循环移动
p2 = p3;
}
pnode->pNext = NULL;
pnode = p1;//存储头结点地址
return pnode;
}
}
Node * delete(Node *pnode, int num)
{
Node *p1=NULL, *p2=NULL;
p1 = pnode;
while (p1 != NULL)
{
if (p1->num == num)
{
//p1保存了要删除节点的地址
break;
}
else
{
p2 = p1;//p2保存上一个节点
p1 = p1->pNext;//向前循环
}
}
if (p1 == pnode)
{
pnode = p1->pNext;//跳过这个节点
free(p1);//删除节点
}
else
{
p2->pNext = p1->pNext;//跳过p1
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
{
p2 = p1;//p2保存上一个节点
p1 = p1->pNext;//向前循环
}
}
Node * pnewnode = (Node *)malloc(sizeof(Node));
pnewnode->num = newnum;
pnewnode->data = data;//赋值
if (pnode == p1)
{
pnewnode->pNext = pnode;
pnode = pnewnode;//头部插入一个节点
}
else
{
pnewnode->pNext = 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)
{
struct node tnode;
tnode.num = p1->num;
p1->num = p2->num;
p2->num = tnode.num;//交换数据
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)
{
struct node tnode;
tnode.num = p1->num;
p1->num = p2->num;
p2->num = tnode.num;//交换数据
tnode.data = p1->data;
p1->data = p2->data;
p2->data = tnode.data;//交换数据
}
}
}
}
}
//main.c
#include<stdio.h>
#include<stdlib.h>
#include"linknode.h"
void main()
{
Node *pnode=NULL;//链表的头结点
//backaddnode(&pnode, 1, 11);
//backaddnode(&pnode, 2, 12);
//backaddnode(&pnode, 3, 13);
//backaddnode(&pnode, 4, 14);
//backaddnode(&pnode, 5, 15);
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);
//change(pnode, 15, 155);
//pnode = rev(pnode);
//pnode = delete(pnode, 1);
//pnode = delete(pnode, 3);
//pnode = delete(pnode, 6);
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", pfind, pfind->num, pfind->data, pfind->pNext);
}*/
system("pause");
}
