#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
}
typedef struct _queue{
int head
int tail
int len
int capacity
int * arr
}QUEUE, *PQUEUE
int Queue_Create(QUEUE ** que, 渣亮int _len)
{
if (_len < 0 || _len > 10000)
{
printf("len is err !\n")
return -1
}
PQUEUE temp = (PQUEUE)malloc(sizeof(QUEUE))
if (NULL == temp)
{
printf("malloc err !\n")
return -2
}
memset(temp, 0, sizeof(QUEUE))
temp->arr = (int *)malloc(sizeof(int)* _len)
if (NULL == temp->arr)
{
printf("malloc err !\n")
return -3
}
memset(temp->arr, 0, sizeof(int)* _len)
temp->head = 0
temp->tail = 0
temp->len = 0
temp->capacity = _len
*que = temp
return 0
}
int Queue_En(PQUEUE que, int num)
{
if (NULL == que)
{
printf("que is NULL\n")
return -1
}
que->arr[que->tail] = num
que->len++
que->tail = (que->tail + 和梁纯1) % que->capacity
return 0
}
int Queue_IsFull(PQUEUE que)
{
if (NULL == que)
{
printf("que is NULL\n")
return 0
}
if ((que->tail + 1) % que->capacity == que->head)
{
return 1
}
return 0
}
int Queue_Empth(PQUEUE que)
{
if (NULL == que)
{
printf("que is NULL\n")
return 0
}
if (0 == que->len)
{
return 1
}
return 0
}
int Queue_Out(PQUEUE que, int * num)
{
if (Queue_Empth(que))
{
return -1
}
*num = que->arr[que->head]
que->len--
que->head = (que->head + 1) % que->capacity
return 0
}
int Queue_Free(PQUEUE * que)
{
if (NULL == que || NULL == *que)
{
return -1
}
PQUEUE temp = *que
if (temp->arr != NULL)
{
free(temp->arr)
}
free(temp)
*que = NULL
printf("free success 唤咐!\n")
return 0
}
void main()
{
PQUEUE queue = NULL
int ret = Queue_Create(&queue, 10)
if (0 == ret)
{
printf("create success !\n")
}
int num = 0
Queue_En(queue, 99)
Queue_En(queue, 88)
Queue_En(queue, 77)
Queue_En(queue, 9)
Queue_En(queue, 8)
Queue_En(queue, 7)
for (int i = 0 i < queue->len i++)
{
printf("%d\n", queue->arr[i])
}
Queue_Out(queue, &num)
printf("%d\n", num)
Queue_Free(&queue)
system("pause")
}
(1)编写一个程序,实现顺序环形队列的各种基本运算,并在此基础上设计一个主程序完成如下功能:(1)初始化尘山队列q;
(2)判断队列q是否非空;
(3)依次进队元素100、909、44、8;
(4)出队一个元素,输出该元素;
(5)派世中输出队列q的元素个数;
(6)依次进队元素-67、55、99、70;
(7)输出队列q的元素个数;
#include<stdio.h>
#include<malloc.h>
#define QUEUE_INIT_SIZE 100
#define QUEUEINCREMENT 10
#define OK 1
#define TURE 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status
typedef int QElemType
typedef struct
{
QElemType *base
int front
int rear
}SqQueue
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType *)malloc
(QUEUE_INIT_SIZE*sizeof(QElemType))
if(!Q.base)
exit(OVERFLOW)
Q.front=Q.rear=0
return OK
}
int QueueNumElem(SqQueue Q)
{
return (Q.rear-Q.front)%QUEUE_INIT_SIZE
}
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%QUEUE_INIT_SIZE==Q.front)
return ERROR
Q.base[Q.rear]=e
Q.rear=(Q.rear+1)%QUEUE_INIT_SIZE
return OK
}
SqQueue DeQueue(SqQueue Q,int e)
{
int i
if(Q.front==Q.rear)
printf("队为空!\n")
for(i=ei<Q.reari++)
Q.base[i]=Q.base[i+1]
Q.rear--
return Q
}
int main()
{
SqQueue Q,Q1
static int qele=0
int i,j=0,k=0,m=0
static int frontd=Q.front
i=InitQueue(Q)
if(i==1)
printf("队初始化成功!!\n")
else
printf("队初始化失败!!\n")
if(Q.front!=Q.rear)
printf("队不为空!!\n")
else
printf("队为空L!!\n")
printf("输入数据(END of '9999'):")
scanf("%d",&qele)
while(qele!=9999||Q.rear==Q.front)
{
EnQueue(Q,qele)
scanf("%d",&qele)
}
frontd=Q.front
while(Q.rear!=Q.front)
{
printf(" %d ",Q.base[Q.front])
Q.front++
j++
}
printf("\n")
Q.front=frontd
printf("返敬输入要出队的元素:")
scanf("%d",&j)
while(Q.front!=Q.rear)
{
if(Q.base[Q.front]==j)
{
printf("%d\n",Q.base[Q.front])
Q=DeQueue(Q,Q.front)
m++
break
}
Q.front++
}
Q.front=frontd
while(Q.front!=Q.rear)
{
printf(" %d ",Q.base[Q.front])
Q.front++
}
printf("\n")
Q.front=frontd
printf("队的长度:%d\n",Q.rear-Q.front)
printf("输入数据(END of '9999'):")
scanf("%d",&qele)
while(qele!=9999||Q.rear==Q.front)
{
EnQueue(Q,qele)
scanf("%d",&qele)
}
Q.front=frontd
printf("队的长度:%d\n",Q.rear-Q.front)
Q.front=frontd
printf("出队顺序:")
while(Q.rear!=Q.front)
{
printf(" %d ",Q.base[Q.front])
Q=DeQueue(Q,Q.front)
m++
}
printf("end\n")
Q.front=0
Q.rear=m
while(Q.rear!=Q.front)
{
free(Q.base)
//Q.base++
Q.front++
if(Q.rear-1==Q.front)
printf("队已经释放!\n")
}
return 0
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)