#include <malloc.h>
#define Maxqsize 5
typedef char ElemType
typedef struct
{
ElemType elem[Maxqsize]
int front,rear
}SqQueue
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc (sizeof(SqQueue))
q->front=q->rear=0
}
void ClearQueue(SqQueue *&q)
{
free(q)
}
int QueueLength(SqQueue *q)
{
return (q->rear-q->front+Maxqsize)%Maxqsize
}
int QueueEmpty(SqQueue *q)
{
return(q->front==q->rear)
}
int enQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%Maxqsize==q->front)
return 0
q->rear=(q->rear+1)%Maxqsize
q->elem[q->rear]=e
return 1
}
int deQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear)
return 0
q->front=(q->front+1)%Maxqsize
e=q->elem[q->front]
return 1
}
void main()
{
ElemType e
SqQueue *q
printf("橘轿(1)初始化队列Q\n")
InitQueue(q)
printf("(2)依次进队列元素A,B,C\n")
if (enQueue(q,'A')==0) printf("队满,不能进队\n")
if (enQueue(q,'B')==0) printf("队满升竖,不能进队\n")
if (enQueue(q,'C')==0) printf("队满,不能进队\n")
printf("(3)队列为%s\n",(QueueEmpty(q)?"空":"非空"))
if (deQueue(q,e)==0)
printf("队空,不能出队\n")
else
printf("(4)出队一个元素%c\n",e)
printf("(5)队列Q的元素个数:%d\n",QueueLength(q))
printf("(6)依次进队列元素D,E,F\n")
if (enQueue(q,'D')==0) printf("队满,不能进队\n")
if (enQueue(q,'E')==0) printf("队满,不能进队\n")
if (enQueue(q,'F')==0) printf("队满,不能进队\n"吵伍大)
printf("(7)队列Q的元素个数:%d\n",QueueLength(q))
printf("(8)出队列序列:")
while (!QueueEmpty(q))
{ deQueue(q,e)
printf("%c ",e)
}
printf("\n")
printf("(9)释放队列\n")
ClearQueue(q)
}
#include<stdio.h>#include<stdbool.h>
#include<malloc.h>
typedef
int
typedata
struct
node
{
struct
node
*prev,
*next
typedata
data
}
typedef
struct
node
node
typedef
struct
node*
link
//
============init_head===============
//
//头节点的初始化
link
init_head(void)
{
link
head
=
(link)malloc(sizeof(node))
if(head
!=
NULL)
{
head->prev
=
head->next
=
head
}
return
head
}
//
============newnode
================
//
//创建新节点
link
newnode(typedata
data)
{
link
new
=
(link)malloc(sizeof(node))
if(new
!=
NULL)
{
//前趋指针和后趋指针都指向自己
new->prev
=
new->next
=
new
new->data
=
data
}
return
new
}
//
=================is_empty================
//
bool
is_empty(link
head)
{
//为空时，头节点的前趋指针和后趋指针都指向head（头节点）
if((head->next==head)
&&
(head->prev==head))
return
true
return
false
}
//
================insert_tail
==================
//
void
insert_tail(link
head,
link
new)
{
if(is_empty(head))
{
//第一个节点插入
head->next
=
head->prev
=
new
new->next
=
new->prev
=
head
return
}
//除了第一个节点插入
new->prev
=
head->prev
new->next
=
head
new->prev->next
=
new
new->next->prev
=
new
}
//
================show
====================
//
void
show(link
head)
{
//为空时，直接返回
if(is_empty(head))
return
//遍历整个链
link
tmp
=
head->next
while(tmp
!=
head)
{
printf("%d\t",
tmp->data)
tmp
=
tmp->next
}
printf("\n")
}
//
==============insert_opint
===============
//
void
insert_opint(link
end_node,
link
p)
{
p->prev
=
end_node
p->next
=
end_node->next
end_node->next->prev
=
p
end_node->next
=
p
}
//
================insertion_sort===========
//
//顺序排序
void
insertion_sort(link
head)
{
if(is_empty(head))
return
//把队列分拆，头节点和第一个节点为一个已排序的队列，
//其他的节点逐个比较已排序队列插
link
p
=
head->next->next
head->prev->next
=
NULL
head->next->next
=
head
head->next->prev
=
head
head->prev
=
head->next
while(p
!=
NULL)
{
link
end_node
=
head->prev
if(p->data
>
end_node->data)
{
link
tmp
=
p
p
=
p->next
insert_tail(head,
tmp)
}
else
{
while(end_node!=head
&&
p->data<end_node->data)
end_node
=
end_node->prev
link
tmp
=
p
p
=
p->next
insert_opint(end_node,
tmp)
}
}
}
int
main(void)
{
link
head
=
init_head()
if(head
==
NULL)
{
printf("falure\n")
return
0
}
typedata
data
while(1)
{
if(scanf("%d",
&data)
!=
1
)
break
link
new
=
newnode(data)
if(new
==
NULL)
{
printf("falure\n")
return
0
}
insert_tail(head,
new)
show(head)
}
printf("the
figure
is:\n")
show(head)
insertion_sort(head)
show(head)
return
0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）