Ⅰ 用队列实现按层次创建二叉树的源代码，最好是C语言
队列？？你每输入一个节点将其存入队列中，再输入它的左孩子，它的左孩子也会入队，我们取的时候应先取该节点的左孩子，
LZ一定要用队列也行，但绝对不是正确的选择！
队列如下：
#include <iostream>
using namespace std;
typedef struct bitnode
{
char data;
struct bitnode *lchild,*rchild;
}*bitree,tree;
int number=0;
void createbitree(bitree &t)
{
char c;
int i=0,r=0,f=0;//r,f分别指向队首和队尾
bitree p=NULL,temp=NULL,pre=NULL,s[100];
s[0]=NULL;
int lflag[100]={0};
int rflag[100]={0};
printf("请输入根节点：");
t=new tree;
t->lchild=t->rchild=NULL;
scanf("%c",&t->data);
temp=pre=t->lchild;
s[++i]=t;
f=i;
p = t;
while(f!=r)
{
if(p->lchild==NULL&&lflag[i]==0)
{
printf("请输入%c的左孩子:",p->data);
fflush(stdin);
scanf("%c",&c);
if(c!='#')
{
p->lchild = new tree;
p = p->lchild;
p->lchild=p->rchild=NULL;
p->data = c;
s[++f]=p;
i = f;
lflag[i]=rflag[i]=0;
}
else
lflag[i]=1;
}
else if(p->rchild==NULL&&rflag[i]==0)
{
printf("请输入%c的右孩子:",p->data);
fflush(stdin);
scanf("%c",&c);
if(c!='#')
{
p->rchild = new tree;
p = p->rchild;
p->lchild=p->rchild=NULL;
p->data = c;
s[++f]=p;
i=f;
lflag[i]=rflag[i]=0;
}
else
{
rflag[i]=1;
p=s[++r];
i=r;
}
}
else
{
p=s[++r];
i=r;
}
}
}
void preorder(bitree &t)//遍历二叉树，输出函数
{
if (t!=0)
{
cout<<t->data<<",";
preorder(t->lchild);
preorder(t->rchild);
}
}
void main()
{
bitree t;
t=0;
createbitree(t);
cout<<"the value of the preorder value is:";
preorder(t);
}
在此，强烈建议LZ用栈，更符合树的输入层次：
#include <iostream>
using namespace std;
typedef struct bitnode
{
char data;
struct bitnode *lchild,*rchild;
}*bitree,tree;
int number=0;
void createbitree(bitree &t)
{
char c;
int i=0;
bitree p=NULL,temp=NULL,pre=NULL,s[100];
s[0]=NULL;
int lflag[100]={0};
int rflag[100]={0};
printf("请输入根节点：");
t=new tree;
t->lchild=t->rchild=NULL;
scanf("%c",&t->data);
temp=pre=t->lchild;
s[++i]=t;
p = t;
while(s[i]!=NULL)
{
if(p->lchild==NULL&&lflag[i]==0)
{
printf("请输入%c的左孩子:",p->data);
fflush(stdin);
scanf("%c",&c);
if(c!='#')
{
p->lchild = new tree;
p = p->lchild;
p->lchild=p->rchild=NULL;
p->data = c;
s[++i]=p;
lflag[i]=rflag[i]=0;
}
else
lflag[i]=1;
}
else if(p->rchild==NULL&&rflag[i]==0)
{
printf("请输入%c的右孩子:",p->data);
fflush(stdin);
scanf("%c",&c);
if(c!='#')
{
p->rchild = new tree;
p = p->rchild;
p->lchild=p->rchild=NULL;
p->data = c;
s[++i]=p;
lflag[i]=rflag[i]=0;
}
else
{
rflag[i]=1;
p=s[--i];
}
}
else
p=s[--i];
}
}
void preorder(bitree &t)//遍历二叉树，输出函数
{
if (t!=0)
{
cout<<t->data<<",";
preorder(t->lchild);
preorder(t->rchild);
}
}
void main()
{
bitree t;
t=0;
createbitree(t);
cout<<"the value of the preorder value is:";
preorder(t);
}
不懂追问！你的疑问往往是我要学习的地方！
Ⅱ 队列的源代码（c语言）
以前写的.你可以看看咯..
class Queue
{
struct Node
{
int a;
Node * next;
};
public:
Queue();
void pump(int b);
void pop();
int getlength();
virtual void print();
private:
Node * head;
Node * rear;
};
void Queue::pump(int b)
{
Node *p1=new Node;
p1->a=b;
p1->next=NULL;
rear->next=p1;
rear=p1;
head->a++;
cout<<setw(2)<<b<<setw(2)<<" 进入队列 "<<endl;
}
void Queue::pop()
{
Node *p;
p=head->next;
cout<<" "<<setw(2)<<p->a<<setw(2)<<"出队"<<endl;
head->next=p->next;
delete p;
head->a--;
}
int Queue::getlength()
{
return head->a;
}
void Queue::print()
{
Node *p;
p=head->next;
cout<<"队列中的元素是:"<<endl;
while(p)
{
cout<<p->a<<" -> ";
p=p->next;
}
cout<<"NULL"<<endl;
}
Queue::Queue()
{
rear=head;
};
Ⅲ 请大家帮忙用c语言编个队列的源程序
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
int data;
struct QNode *next;
} LinkNode;//每个结点的定义
typedef struct{
LinkNode *front, *rear;
}LinkQuene;//采用链表结构的队列
void InitQuene(LinkQuene &Q)//带有头结点的队列
{
Q.front=(LinkNode *)malloc(sizeof(QNode));
Q.rear=Q.front;
}
bool EmptyQuene(LinkQuene Q)
{
if(Q.front==Q.rear)
return true;
else
return false;
}
void QueneTraverse(LinkQuene Q)
{
if(EmptyQuene(Q)==false)
{
LinkNode *p=Q.front->next;
printf("\n当前队列的遍历序列为：");
while(p!=Q.rear)
{
printf("%d->",p->data);
p=p->next;
}
printf("%d\n",p->data);
}
}
void EnQuene(LinkQuene &Q, int e)
{
LinkNode *p=(LinkNode *)malloc(sizeof(QNode));
if(!p)
exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
void DeQuene(LinkQuene &Q, int &e)
{
LinkNode *p;
if(EmptyQuene(Q))
{ printf("队列为空！\n");
exit(0);
}
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
void menu()
{
printf("\n***************************\n");
printf("**[1]新建队列 **\n");
printf("**[2]入队列 **\n");
printf("**[3]出队列 **\n");
printf("**[4]遍历整个队列 **\n");
printf("**[0]退出 **\n");
printf("***************************\n");
printf("请输入命令：\n");
}
void main()
{
LinkQuene Q;
InitQuene(Q);
int a,order;
char ans,temp;
while(1)
{
menu();
ans='n';
scanf("%d",&order);
switch(order)
{
case 1:
do{
printf("请输入队列的元素：\n");
scanf("%d",&a);
fflush(stdin); //清空键盘缓冲区（过滤回车）
EnQuene(Q,a);
printf("是否继续添加元素？(Y/N)");
scanf("%c",&ans);
fflush(stdin);
}while(ans=='y' || ans =='Y');
QueneTraverse(Q);
break;
case 2:
if( EmptyQuene(Q))
{
printf("队列为空!\n");
break;
}
do{
printf("请输入添加到队列的元素：\n");
scanf("%d",&a);
fflush(stdin);
EnQuene(Q,a);
printf("是否继续添加元素?(Y/N)");
scanf("%c",&ans);
fflush(stdin);
}while(ans=='y' || ans =='y');
QueneTraverse(Q);
break;
case 3:
if(EmptyQuene(Q))
{
printf("队列为空!\n");
break;
}
else{
do{
DeQuene(Q,a);
fflush(stdin);
printf("元素%d已经出队列\n",a);
if(EmptyQuene(Q)==false)
{
printf("是否继续出队列?(Y/N)");
scanf("%c",&ans);
}
else
{
printf("队列已空!\n");
break;
}
}while(ans=='y' || ans =='y');
QueneTraverse(Q);
break;
}
case 4:
if(EmptyQuene(Q))
{
printf("队列为空!\n");
break;
}
QueneTraverse(Q);break;
case 0:
exit(0);
default:
printf("您输入的命令有误!\n");
}
}
}
Ⅳ 用c语言进行链式队列的创建，编译链接没错，但是运行的时候程序被终止。以下是源代码和注释
自行比对这两个函数吧
voidinsert_link(structlinkqueue*ps,intval)//完成队列的增加。
{
structnode*pnew=(structnode*)malloc(sizeof(structnode));//申请一个节点
pnew->data=val;//将要放入队列的值赋给节点的数据域
pnew->next=NULL;
//pnew=ps->rear->next;//将rear指向新的节点，并将新的节点的指针域置空。
ps->rear->next=pnew;
ps->rear=ps->rear->next;
//pnew->next=NULL;
}
voidtraverse_link(structlinkqueue*ps)//完成队列遍历
{
structnode*p=ps->front->next;//申请一个临时指针变量，以完成队列遍历。因为头节点没有存放数据所以让指针指向front下一个节点
while(/*p->next*/p!=NULL){//当指针指向的节点的指针域不为空时就继续下移，并且输出本节点的数据
printf("%d",p->data);
p=p->next;
}
}
Ⅳ 帮忙些一个C语言队列的程序, 要求只有一个文件"queue.c".
我在写，但是你的图片显然看不到。。。。
写好了，测试无误，代码如下。我不能看到你的图片，因而，无法知道你的person结构体里面到底有些什么，我示意地给出了名字、年龄、优先级，你可以自主往里面添加，就增加几个单词而已啦。MAX_HEAP_SIZE我不太明白用作何种意义，就当作最大不能超过MAX_HEAP_SIZE个人来处理了，不合适你可以很容易修改。（联系方式[email protected]）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHARACTERS 30
#define MAX_HEAP_SIZE 100
#define MAX_PRIORITY 100
#define MIN_PRIORITY 0
/* define struct of a person */
struct person{
char *name;
int age;
int priority;
struct person *Next;
};
typedef struct person Person;
typedef struct person * Element;
/* implement the queue data structure */
/* using an additional head to simplify logic */
Element Head = (Element)malloc(sizeof(Person));
Element Rear = Head;
int PersonCount = 0;
/* function declarations */
Element GetInput(); /* Obtain the user's input */
int Enqueue(Element);/* Enqueue a person */
void Dequeue();/* Dequeue the person at the top of heap */
void printPerson(Element);/* Print a person's information */
void freeElem(Element);/* Free an element */
void Dump();/* Dump all persons' information in the heap */
void Exit();/* Free heap and exit */
int main()
{
while(true)
{
printf("\nPlease select a menu option:\n"\
"1) Enqueue a person\n"\
"2) Dequeue the next person\n"\
"3) Dump the contents of the heap\n"\
"4) Quit the program\n"\
"Enter an option: ");
int choice;
scanf("%d", &choice);
switch(choice)
{
case 1:
Element elem;
if((elem = GetInput())!= NULL)
if(Enqueue(elem) == 0)
printf("Succeed!\n");
break;
case 2:
Dequeue();
break;
case 3:
Dump();
break;
case 4:
Exit();
break;
default:
fprintf(stderr, "Invalid choice!\n");
break;
}
}
}
Element GetInput()
{
/* if heap is full, not allow to enqueue */
if (PersonCount > MAX_HEAP_SIZE)
{
fprintf(stderr, "Heap is full!\n");
return NULL;
}
/* input like: Michael 20 90 */
printf("Input person's information in order of Name, Age and Priority :\n");
Element elem = (Element)malloc(sizeof(Person));
elem->name = (char*)malloc(MAX_CHARACTERS);
fflush(stdin);
scanf("%s%d%d", elem->name, &elem->age, &elem->priority);
/* check the validation of input */
if (elem->age <= 0 || elem->age > 130 || elem->priority > MAX_PRIORITY || elem->priority < MIN_PRIORITY)
{
fprintf(stderr, "Invalid personal information! Abort!\n");
freeElem(elem);
return NULL;
}
elem->Next = NULL;
return elem;
}
int Enqueue(Element elem)
{
/* if heap is null, deal with it */
if(Head == Rear)
{
Head->Next = Rear = elem;
return 0;
}
/* if heap contains more than one element */
Element tmp;
for (tmp = Head; tmp != Rear; tmp = tmp->Next)
{
/* implement the priority queue */
if(elem->priority >= tmp->Next->priority)
{
elem->Next = tmp->Next;
tmp->Next = elem;
return 0;
}
}
/* if the element being enqueued has the lowest priority */
if(tmp == Rear)
{
tmp->Next = Rear = elem;
return 0;
}
return 1;
}
void Dequeue()
{
/* if the queue is empty */
if (Head == Rear)
{
fprintf(stderr, "The queue is empty!\n");
return;
}
Element tmp = Head->Next;
/* print person's information */
printPerson(tmp);
Head->Next = tmp->Next;
/* free element */
freeElem(tmp);
}
void printPerson(Element elem)
{
if(NULL == elem)
{
fprintf(stderr, "Element is NULL!\n");
exit(EXIT_FAILURE);
}
printf("Name: %s\t Age: %d\t Priority: %d\n", elem->name, elem->age, elem->priority);
}
void freeElem(Element elem)
{
free(elem->name);
free(elem);
}
void Dump()
{
if (Head == Rear)
{
fprintf(stderr, "The queue is empty!\n");
return;
}
int index = 1;/* index starts from 1 */
Element tmp;
for (tmp = Head->Next; tmp != Rear; tmp = tmp->Next)
{
printf("Index: %d\tName: %s\t Age: %d\t Priority: %d\n", index, tmp->name, tmp->age, tmp->priority);
}
printf("Index: %d\tName: %s\t Age: %d\t Priority: %d\n", index++, tmp->name, tmp->age, tmp->priority);
}
void Exit()
{
/* if the queue if empty, free the head */
if (Head == Rear)
{
free(Head);
exit(0);
}
/* free all elements */
Element curr = Head->Next;
free(Head);
while (curr != Rear)
{
Head = curr->Next;
freeElem(curr);
curr = Head;
}
/* at last, free the rear element */
freeElem(Rear);
exit(0);
}
这个是数组优先级队列的实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* define debug */
#ifdef __DEBUG__
#include <stdarg.h>
void debug(const char *fmt, ...)
{
va_list ap;
va_start(ap, fmt);
vprintf(fmt, ap);
va_end(ap);
}
#else
void debug(const char *fmt, ...)
{
}
#endif
/* common constraints */
#define MAX_CHARACTERS 30
#define MAX_HEAP_SIZE 100
#define MAX_PRIORITY 100
#define MIN_PRIORITY 0
/* define struct of a person */
typedef struct person{
char name[MAX_CHARACTERS+1];/* better to use char *name */
int priority;
} Person, *Element;
/* function declarations */
int isFull(int, int);/* decide whether the queue is full */
Element GetInput(); /* Obtain the user's input */
int Enqueue(Element *, Element, int *, int *);/* Enqueue a person */
void Dequeue(Element *, int *);/* Dequeue the person at the top of heap */
void Dump(const Element *, int, int);/* Dump all persons' information in the heap */
void Exit(Element *, int, int);/* Free heap and exit */
int main()
{
/* define the queue and allocate memory. Local to main function. */
/* can store MAX_HEAP_SIZE-1 elements */
Element *queue = (Element *)malloc(MAX_HEAP_SIZE * sizeof(Element *));
/* pointers to the queue, initially they point to zero */
int front, rear;
front = rear = 0;
/* for user's choice */
while(true)
{
printf("\nPlease select a menu option:\n"\
"1) Enqueue a person\n"\
"2) Dequeue the next person\n"\
"3) Dump the contents of the heap\n"\
"4) Quit the program\n"\
"Enter an option: ");
int choice;
fflush(stdin);
scanf("%d", &choice);
switch(choice)
{
case 1:
/* if heap is full, not allow to enqueue */
if (isFull(front, rear))
{
fprintf(stderr, "Heap is full!\n");
break;
}
/* if not, process the enqueue operation */
Element elem;
if((elem = GetInput())!= NULL)
if(Enqueue(queue, elem, &front, &rear) == 0)
printf("Insertion Successful.\n");
break;
case 2:
/* if the queue is empty */
if(rear == front)
{
printf("The heap is empty. No removal has occurred.");
break;
}
Dequeue(queue, &front);
break;
case 3:
Dump(queue, front, rear);
break;
case 4:
Exit(queue, front, rear);
break;
default:
fprintf(stderr, "Invalid choice!\n");
}
}
}
int isFull(int front, int rear)
{
/* circular queue is used here */
return (rear+1) % MAX_HEAP_SIZE == front;
}
Element GetInput()
{
/* allocate memory for a person on the heap */
Element elem = (Element)malloc(sizeof(Person));
/* input like:
* Enter the name: Bill Smith
* Enter the priority: 77
*/
printf("\nEnter the name: ");
fflush(stdin);
fgets(elem->name, MAX_CHARACTERS, stdin);
elem->name[strlen(elem->name)-1] = '\0';/* deal with the '\n' in the string*/
printf("Enter the priority: ");
fflush(stdin);
scanf("%d", &elem->priority);
/* check the validation of input */
if (elem->priority > MAX_PRIORITY || elem->priority < MIN_PRIORITY)
{
fprintf(stderr, "Insertion failed because of an invalid priority.\n");
free(elem);
return NULL;
}
return elem;
}
/* calling function is responsible for queue check */
int Enqueue(Element *queue, Element elem, int *front, int *rear)
{
/* if queue if empty */
if (front == rear)
{
*rear = (*rear + 1) % MAX_HEAP_SIZE;/* has a circular meaning */
return 0;
}
/* queue is not empty, compare before insertion*/
/* first write to the rear of the queue */
*rear = (*rear + 1) % MAX_HEAP_SIZE;
queue[*rear] = elem;
int pointer = *rear;
/* exchange to proper position of the queue */
Element tmp;
int next;
while(true)
{
if(pointer == 0)
next = MAX_HEAP_SIZE;
else
next = pointer - 1;
if(queue[pointer] > queue[next])
{
/* exchange */
tmp = queue[pointer];
queue[pointer] = queue[next];
queue[next] = tmp;
}
else
return 0;/* done with enqueue */
}
return 1; /* something happened unexpectedly */
}
/* the calling function is responsible for queue check */
void Dequeue(Element *queue, int *front)
{
*front = (*front + 1) % MAX_HEAP_SIZE;
printf("%s (Priority %d) has been removed.\n",\
(*queue[*front]).name, (*queue[*front]).priority);
}
void Dump(const Element *queue, int front, int rear)
{
/* if the queue is empty */
if(rear == front)
{
printf("The heap is empty.\n");
return;
}
printf("Index\tPriority\t\tName\n-----\t---------\t----------------------\n");
rear = (rear+1)%MAX_HEAP_SIZE;
int index = 0;/* index starts from 0 */
while((front = (front+1)%MAX_HEAP_SIZE) != rear)
{
printf("%d\t%d\t\t%s\n", index, (*queue[front]).priority, (*queue[front]).name);
++index;
}
}
void Exit(Element *queue, int front, int rear)
{
printf("\nProgram terminating...");
if(rear == front)
{
free(queue);
exit(0);
}
/* free the elements */
rear = (rear+1)%MAX_HEAP_SIZE;
while((front = (front+1)%MAX_HEAP_SIZE) != rear)
{
free(queue[front]);
}
/* free the array of pointers to elements */
free(queue);
exit(0);
}
Ⅵ 求一段C语言的 队列 数据结构代码,能用的就加分啊!
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using std::cout;
using std::endl;
using std::ostream;
template <class Type>
class Queue {
friend ostream & operator<< (ostream &, const Queue<Type> &);
public:
static const int DefaultSize;
Queue(int = DefaultSize); //创建一个最大容量为MaxQueueSize的空队列
Queue(Type [], int, int = DefaultSize);
~Queue() {delete [] queue;}
bool IsFull(); //若元素个数等于队列的最大容量则返回true，否则返回false
void Add(const Type &); //若IsFull()为true，调用外处理函数QueueFull()，否则将item插入队尾
bool IsEmpty() const; //若队列中元素个数等于0，则返回true，否则返回false
Type * Delete(Type &); //若IsEmpty()为true，调用QueueEmpty()并返回0，否则删除队列前段元素并返回其指针
void Empty(); //清空队列
void QueueFull(); //扩充1倍的存储空间
void QueueEmpty(); //提示队列已空，元素不能出队
private:
int front, rear;
Type * queue;
int maxSize;
};
template <class Type>
const int Queue<Type>::DefaultSize = 10;
template <class Type>
Queue<Type>::Queue(int pMaxSize) {
queue = new Type [pMaxSize];
maxSize = pMaxSize;
front = rear = -1;
}
template <class Type>
Queue<Type>::Queue(Type pArray[], int pSize, int pMaxSize) {
queue = new Type [pMaxSize];
for (int i = 0; i < pSize; i++)
{
queue[i] = pArray[i];
}
front = -1; rear = pSize - 1;
maxSize = pMaxSize;
}
template <class Type>
bool Queue<Type>::IsFull() {
if ( rear == maxSize - 1 ) return true;
else return false;
}
template <class Type>
bool Queue<Type>::IsEmpty() const {
if ( rear == front ) return true;
else return false;
}
template <class Type>
void Queue<Type>::Add(const Type & pX) {
if (IsFull())
{
QueueFull();
queue[++rear] = pX;
}
else
{
queue[++rear] = pX;
}
}
template <class Type>
Type * Queue<Type>::Delete(Type & pX) {
if (IsEmpty())
{
QueueEmpty();
return 0;
}
else
{
pX = queue[++front];
return &pX;
}
}
template <class Type>
void Queue<Type>::QueueEmpty() {
cout << "队列为空，不能进行出队操作！" << endl;
}
template <class Type>
void Queue<Type>::QueueFull() {
Type * newQueue = new Type [maxSize * 2];
for ( int i = front + 1; i <= rear; i++ )
{
newQueue[i] = queue[i];
}
maxSize = maxSize * 2;
delete [] queue;
queue = newQueue;
cout << "队列已满，现已增加空间为原来的2倍 " << maxSize;
}
template <class Type>
void Queue<Type>::Empty() {
front = rear = -1;
}
template <class Type>
ostream & operator<< (ostream & pOutput, const Queue<Type> & pQ) {
if (pQ.IsEmpty())
{
cout << "空队列" << endl;
return pOutput;
}
for ( int i = pQ.front + 1; i <= pQ.rear; i++ )
{
pOutput << pQ.queue[i] << " ";
}
cout << endl;
return pOutput;
}
#endif