數據結構課程設計題目
『壹』 大二數據結構課設，要求用C語言！拜託啦！必採納，題目在下面
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#definelen(x)((int)log10(x)+1)
/*Nodeofthehuffmantree*/
structnode{
intvalue;
charletter;
structnode*left,*right;
};
typedefstructnodeNode;
/*81=8.1%,128=12.8%andsoon.The27thfrequencyisthespace.SourceisWikipedia*/
intenglishLetterFrequencies[27]={81,15,28,43,128,23,20,61,71,2,1,40,24,69,76,20,1,61,64,91,28,10,24,1,20,1,130};
/*findsandreturnsthesmallsub-treeintheforrest*/
intfindSmaller(Node*array[],intdifferentFrom){
intsmaller;
inti=0;
while(array[i]->value==-1)
i++;
smaller=i;
if(i==differentFrom){
i++;
while(array[i]->value==-1)
i++;
smaller=i;
}
for(i=1;i<27;i++){
if(array[i]->value==-1)
continue;
if(i==differentFrom)
continue;
if(array[i]->value<array[smaller]->value)
smaller=i;
}
returnsmaller;
}
/**/
voidbuildHuffmanTree(Node**tree){
Node*temp;
Node*array[27];
inti,subTrees=27;
intsmallOne,smallTwo;
for(i=0;i<27;i++){
array[i]=malloc(sizeof(Node));
array[i]->value=englishLetterFrequencies[i];
array[i]->letter=i;
array[i]->left=NULL;
array[i]->right=NULL;
}
while(subTrees>1){
smallOne=findSmaller(array,-1);
smallTwo=findSmaller(array,smallOne);
temp=array[smallOne];
array[smallOne]=malloc(sizeof(Node));
array[smallOne]->value=temp->value+array[smallTwo]->value;
array[smallOne]->letter=127;
array[smallOne]->left=array[smallTwo];
array[smallOne]->right=temp;
array[smallTwo]->value=-1;
subTrees--;
}
*tree=array[smallOne];
return;
}
/*.(usedtofacilitatearithmetic)*/
voidfillTable(intcodeTable[],Node*tree,intCode){
if(tree->letter<27)
codeTable[(int)tree->letter]=Code;
else{
fillTable(codeTable,tree->left,Code*10+1);
fillTable(codeTable,tree->right,Code*10+2);
}
return;
}
/*functiontocompresstheinput*/
voidcompressFile(FILE*input,FILE*output,intcodeTable[]){
charbit,c,x=0;
intn,length,bitsLeft=8;
intoriginalBits=0,compressedBits=0;
while((c=fgetc(input))!=10){
originalBits++;
if(c==32){
length=len(codeTable[26]);
n=codeTable[26];
}
else{
length=len(codeTable[c-97]);
n=codeTable[c-97];
}
while(length>0){
compressedBits++;
bit=n%10-1;
n/=10;
x=x|bit;
bitsLeft--;
length--;
if(bitsLeft==0){
fputc(x,output);
x=0;
bitsLeft=8;
}
x=x<<1;
}
}
if(bitsLeft!=8){
x=x<<(bitsLeft-1);
fputc(x,output);
}
/**/
fprintf(stderr,"Originalbits=%dn",originalBits*8);
fprintf(stderr,"Compressedbits=%dn",compressedBits);
fprintf(stderr,"Saved%.2f%%ofmemoryn",((float)compressedBits/(originalBits*8))*100);
return;
}
/*functiontodecompresstheinput*/
voiddecompressFile(FILE*input,FILE*output,Node*tree){
Node*current=tree;
charc,bit;
charmask=1<<7;
inti;
while((c=fgetc(input))!=EOF){
for(i=0;i<8;i++){
bit=c&mask;
c=c<<1;
if(bit==0){
current=current->left;
if(current->letter!=127){
if(current->letter==26)
fputc(32,output);
else
fputc(current->letter+97,output);
current=tree;
}
}
else{
current=current->right;
if(current->letter!=127){
if(current->letter==26)
fputc(32,output);
else
fputc(current->letter+97,output);
current=tree;
}
}
}
}
return;
}
/*function*/
voidinvertCodes(intcodeTable[],intcodeTable2[]){
inti,n,;
for(i=0;i<27;i++){
n=codeTable[i];
=0;
while(n>0){
=*10+n%10;
n/=10;
}
codeTable2[i]=;
}
return;
}
intmain(){
Node*tree;
intcodeTable[27],codeTable2[27];
intcompress;
charfilename[20];
FILE*input,*output;
buildHuffmanTree(&tree);
fillTable(codeTable,tree,0);
invertCodes(codeTable,codeTable2);
/*getinputdetailsfromuser*/
printf("Typethenameofthefiletoprocess:n");
scanf("%s",filename);
printf(":n");
scanf("%d",&compress);
input=fopen(filename,"r");
output=fopen("output.txt","w");
if(compress==1)
compressFile(input,output,codeTable2);
else
decompressFile(input,output,tree);
return0;
}
『貳』 數據結構課程設計
#include <stdio.h>
#include <malloc.h>
#include <windows.h>
#include <time.h>
#define MAXSIZE 100
typedef struct Ttime{
int t_hour;
int t_min;
int t_sec;
}Ttime;
typedef struct Mcar{
int number;
Ttime t[2];
}Mcar;
typedef struct{
Mcar elements[MAXSIZE];
int top;
}CarStop;
typedef struct node{
Mcar date;
struct node *next;
}LinkQueue;
typedef struct{
LinkQueue *front;
LinkQueue *rear;
}Queue;
void InitQueue(Queue *Q){
Q -> front = (LinkQueue *) malloc(sizeof(LinkQueue));
Q -> front -> next = NULL;
Q -> rear = Q -> front;
}
int IsEmptyH(Queue Q){
if(Q.front == Q.rear)
return 1;
else
return 0;
}
void EeQueue(Queue *Q, Mcar x){
Q -> rear -> next = (LinkQueue *)malloc(sizeof(LinkQueue));
Q -> rear = Q -> rear -> next;
Q -> rear -> date = x;
Q -> rear -> next = NULL;
}
Mcar DeQueue(Queue *Q){
LinkQueue *p;
Mcar y;
if(!(*Q)){
p = Q -> front -> next;
Q -> front -> next = p -> next;
if(p -> next == NULL)
Q -> rear = Q -> front;
y = p -> date;
free(p);
return y;
}
}
int IsEmpty(CarStop S){
if(S.top == 0)
return 1;
else
return 0;
}
int IsFull(CarStop S){
if(S.top == MAXSIZE)
return 1;
else
return 0;
}
int Init(CarStop *S){
S -> top = 0;
}
void PutIn(CarStop *S, Mcar D){
if(!IsFull(*S)){
S -> elements[S -> top] = D;
S -> top++;
}
else
printf("IS FULL");
}
Mcar Pop(CarStop *S){
if(!IsEmpty(*S)){
S -> top--;
return S -> elements[S -> top];
}
else
printf("IS NULL");
}
Mcar TopNum(CarStop S){
if(!IsEmpty(S)){
return S.elements[S.top - 1];
}
}
int serachOneCar(CarStop S, Mcar num){
int i = 0;
if(!IsEmpty(S)){
while(i <= S.top){
if(num.number == S.elements[i].number)
return 1;
i++;
}
}
else
return 0;
}
void getInOneCar(CarStop *CarStack, Queue *Q, Mcar car){
time_t secnow;
struct tm * tmptr;
time(&secnow);
tmptr = localtime(&secnow);
car.t[0].t_hour= tmptr -> tm_hour;
car.t[0].t_min = tmptr -> tm_min;
car.t[0].t_sec = tmptr -> tm_sec;
printf("please put in you car number:\n");
scanf("%d", &car.number);
if(!IsFull(*CarStack))
PutIn(CarStack, car);
else{
printf("car stop is full, please stay in bian\n");
EeQueue(Q, car);
}
printf("you car's intime is :[%d]:[%d]:[%d]\n\n\n", car.t[0].t_hour, car.t[0].t_min, car.t[0].t_sec);
}
void getOutOneCar(CarStop *CarStack, CarStop *CarStackL, Queue *Q, Mcar car){
Mcar lin;
time_t secnow;
struct tm * tmptr;
time(&secnow);
tmptr = localtime(&secnow);
car.t[1].t_hour= tmptr -> tm_hour;
car.t[1].t_min = tmptr -> tm_min;
car.t[1].t_sec = tmptr -> tm_sec;
printf("please put in you car number:\n");
scanf("%d", &car.number);
if(IsEmpty(*CarStack) || !serachOneCar(*CarStack, car))
printf("soory, there is no the car\n");
else{
while(1){
lin = Pop(CarStack);
if(lin.number == car.number)
break;
else
PutIn(CarStackL, lin);
}
while(!IsEmpty(*CarStackL)){
PutIn(CarStack, Pop(CarStackL));
}
if(!IsEmptyH(*Q))
PutIn(CarStack, DeQueue(Q));
printf("\n\nyou car's intime is :[%d]:[%d]:[%d]\n", lin.t[0].t_hour, lin.t[0].t_min, lin.t[0].t_sec);
printf("you car's out time is :[%d]:[%d]:[%d]\n", car.t[1].t_hour, car.t[1].t_min, car.t[1].t_sec);
int alltime = (car.t[1].t_hour - lin.t[0].t_hour) * 3600 + (car.t[1].t_min - lin.t[0].t_min) * 60 + (car.t[1].t_sec - lin.t[0].t_sec);
printf("you car's all time is second:[%d]\n", alltime);
}
}
int main(){
CarStop CarStack, CarStackL;
Queue Q;
LinkQueue *pp;
InitQueue(&Q);
Init(&CarStack);
Init(&CarStackL);
Mcar car;
//String caozuo;
int caozuo, i, j;
while(1){
printf("\t**************the car stop menu*************\n");
printf("\t\t***** 1. get in a car\n\n");
printf("\t\t***** 2. get out a car\n\n");
printf("\t\t***** 0. out the car stop\n\n");
printf("\t\t*****put in the else you can see all the car in the carstop\n\n");
printf("\t*****************************************\n");
printf("please put in you caozuo: \n");
scanf("%d", &caozuo);
switch(caozuo){
case 1: getInOneCar(&CarStack, &Q, car);
break;
case 2: getOutOneCar(&CarStack, &CarStackL, &Q, car);
break;
case 0: return 0; break;
default : break;
}
if(!IsEmpty(CarStack)){
i = 0;
printf("the all car is:\n");
while(i < CarStack.top){
printf("the [%d] is %d\n",i + 1, CarStack.elements[i].number);
i++;
}
}
else
printf("the car stop IS NULL\n");
printf("****************************\n");
if(!IsEmptyH(Q)){
j = 1;
pp=Q.front;
printf("the bian's car is:\n");
while(pp!=Q.rear){
printf("the [%d] wait car is %d\n", j, pp -> next -> date.number);
pp = pp -> next;
j++;
}
}
else
printf("the bian is NULL\n");
printf("****************************\n");
system("pause");
system("cls");
}
}
C語言編譯通過
『叄』 數據結構課程設計
這個是程序：
#include "string.h"
#define NULL 0
unsigned int key;
unsigned int key2;
int *p;
struct node
{
char name[20],address[20];
char num[11];
struct node *next;
}
**phone;
**nam;
**address;
typedef struct node *pnode;
typedef struct node *mingzi;
void hash(char num[11])
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
key=key%17;
}
void hash2(char name[8])
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
Key2=key2%17;
}
struct node* input()
{
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp = new node;
temp->next=NULL;
printf("qing shu ru xing ming(no more then 8 chars) :\n");
scanf("%s",&temp->name);
printf"qing shu ru dian hua hao ma(no more then 11 numbers):\n");
scanf("%s",&temp->num);
printf("qing shu ru di (no more then 20 chars):\n");
scanf("%s",&temp->address);
return temp;
}
int add()
{
struct node *newphone;
struct node *newname;
newphone=input();
printf("ni de ji lu shi");
if(find(newphone->num))
{
printf("hao ma yi jing cun zai bu nene zai tian jia.\n");
return 0;
}
if(find2(newphone->name))
{
printf("xing ming yi jing cun zai bu neng zai tian jia.\n");
return 0;
}
printf("%s_%s_%s\n",newphone->name,newphone->address,newphone->num);
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next = phone[key]->next;
phone[key]->next=newphone;
newname->next = nam[key2]->next;
nam[key2]->next=newname;
return 0;
}
int find(char num[11])
{
int isfind=0;
struct node *q;
hash(num);
node *q=phone[key]->next;
while(q!= NULL)
{
if(strcmp(num,q->num) ==0)
{
isfind=1;
break;
}
q=q->next;
}
if(isfind)
printf("%s_%s_%s\n",q->name,q->address,q->num);
return isfind;
}
int find2(char name[8])
{
int isfind=0;
hash2(name);
struct node *q=nam[key2]->next;
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
{
isfind=1;
break;
}
q=q->next;
}
if(isfind)
printf("%s_%s_%s\n",q->name,q->address,q->num);
return isfind;
}
void create()
{
int i;
phone = (pnode*)malloc(13*sizeof(pnode));
for(i=0;i<13;i++)
{
phone[i]=(struct node*)malloc(sizeof(struct node));
phone[i]->next=NULL;
}
}
void create2()
{
int i;
nam = (mingzi*)malloc(13*sizeof(mingzi));
for(i=0;i<13;i++)
{
nam[i]=(struct node*)malloc(sizeof(struct node));
nam[i]->next=NULL;
}
}
void list()
{
int i;
struct node *p;
for(i=0;i<13;i++)
{
p=phone[i]->next;
while(p)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next;
}
}
}
void list2()
{
int i;
struct node *p;
for(i=0;i<13;i++)
{
p=nam[i]->next;
while(p!=NULL)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next;
}
}
}
void menu()
{
printf("0.tian jia ji lv.\n");
printf("2.cha zhao ji lu.\n");
printf("3.xing ming lie biao.\n");
printf("4.hao ma lie biao.\n");
printf("5.qing chu suo you ji lu.\n");
printf("6.tui chu xi tong.\n");
}
int main()
{
char num[11];
char name[8];
int sel;
create();
create2();
while(1)
{
menu();
scanf("%d",&sel);
if(sel==3)
{
char b;
printf("Input 9 to search with number,8 to name.\n");
b=getch();
if(b=='9')
{
printf("Please input the number:\n");
scanf("%s",&num);
if(!find(num))
printf("Record not exist.\n");
}
else if(b=='8')
{
printf("Please input the name:\n");
scanf("%s",&name);
if(!find(name))
printf("Record not exist.\n");
}
else
{
printf("Wrong input!Please input again!\n");
continue;
}
}
else if(sel==2)
{
printf("All record with name:\n");
list2();
}
else if(sel==0)
{
printf("Please input the information:\n");
add();
}
else if(sel==4)
{
printf("All record with number:\n");
list();
}
else if(sel==5)
{
create();
create2();
printf("All records have been removed.\n");
}
else if(sel==6)
{printf("7");
break;
}
}
return 0;
}
『肆』 數據結構課程設計題目：猴子選大王問題
我使用了另一種方法，不需要構建環形鏈表也可以，只需要用一個數組標記已離開的猴子即可，相對比較簡單。這個程序輸出猴子離開的順序，最後輸出的即為大王。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
int main()
{
int m,n;
int *not_in;
int pos;
int i;
int j;
printf("m n = ");
scanf("%d%d", &m, &n);
assert(m > 0);
assert(n > 0);
not_in = (int *)malloc(sizeof(int)*(m + 1));
memset(not_in, 0, sizeof(int)*(m + 1));
pos = m;
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
do
{
pos++;
if (pos == m + 1)
pos = 1;
}
while (not_in[pos]);
}
printf("%d ", pos);
not_in[pos] = 1;
}
printf("\n");
return 0;
}
『伍』 有沒有誰做過數據結構課程設計,題目為:
題目1 馬踏棋盤問題
#include "stdio.h"
#define M 70
#define FALSE 0
#define TRUE 1
typedef struct node
{
int vec,x,y;
struct node *link;
}listnode;
#define MAXSIZE 70
typedef struct
{
int stack[MAXSIZE];
int top;
}seqstack;
seqstack *s;
void setnull(seqstack *s)
{
s->top=-1;
}
int push(seqstack *s,int x)
{
if(s->top>=MAXSIZE-1)
{
printf("stack overflow!\n");
return FALSE;
}
else
{
s->stack[++s->top]=x;/*棧頂指針上移，數據元素入棧*/
return TRUE;
}
}
int pop(seqstack *s)/*出當前棧s的棧頂元素*/
{ int p;
if(s->top<0)
{
printf("stack empty!\n");/* 棧空，返回空值*/
return NULL;
}
else
{
s->top--;
return(s->stack[s->top+1]);
}/*由於return語句的特點，必須先使 top減1，然後再執行return語句。而此時棧頂元素的表示應該為s->top+1*/
}
void creatlist(listnode ag[])
{
listnode *p;
int i,j,x,y,x1,x2,y1,y2,k;
k=1;
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
{
ag[k].x=i;
ag[k].y=j;
ag[k].vec=8*ag[k].x+ag[k].y-8;
ag[k].link=NULL;
printf("%d(%d,%d)",ag[k].vec,ag[k].x,ag[k].y);
k++;
}
printf("\n");
}
for(i=1;i<=64;i++)
{
/*printf("*%d*",i); */
setnull(s);
x1=ag[i].x;
y1=ag[i].y;
if((x1+1>0)&&(y1+2>0)&&(x1+1<=8)&&(y1+2<=8))
{
x2=x1+1;
y2=y1+2;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1+1>0)&&(y1-2>0)&&(x1+1<=8)&&(y1-2<=8))
{
x2=x1+1;
y2=y1-2;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1-1>0)&&(y1+2>0)&&(x1-1<=8)&&(y1+2<=8))
{
x2=x1-1;
y2=y1+2;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1-1>0)&&(y1-2>0)&&(x1-1<=8)&&(y1-2<=8))
{
x2=x1-1;
y2=y1-2;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1+2>0)&&(y1-1>0)&&(x1+2<=8)&&(y1-1<=8))
{
x2=x1+2;
y2=y1-1;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1+2>0)&&(y1+1>0)&&(x1+2<=8)&&(y1+1<=8))
{
x2=x1+2;
y2=y1+1;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1-2>0)&&(y1+1>0)&&(x1-2<=8)&&(y1+1<=8))
{
x2=x1-2;
y2=y1+1;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
if((x1-2>0)&&(y1-1>0)&&(x1-2<=8)&&(y1-1<=8))
{
x2=x1-2;
y2=y1-1;
j=8*x2+y2-8;
/*printf("%d ",j);*/
push(s,j);
}
do
{
j=pop(s);
x2=ag[j].x;
y2=ag[j].y;
p=(listnode *)malloc(sizeof(listnode));
p->vec=j;
p->x=x2;
p->y=y2;
p->link=ag[i].link;
ag[i].link=p;
/*printf(" %d(%d,%d) ",p->vec,p->x,p->y);*/
p=(listnode *)malloc(sizeof(listnode));
p->vec=i;
p->x=x1;
p->y=y1;
p->link=ag[j].link;
ag[j].link=p;
/*printf(" %d(%d,%d) ",p->vec,p->x,p->y);*/
} while(s->top>=0);
}
}
void dfs(listnode ag[],int v,int flag[])
{
listnode *p;
int i;
flag[v]=1;
printf("(%d,%d)",ag[v].x,ag[v].y);
p=ag[v].link;
while(p!=NULL)
{
i=p->vec;
if(flag[i]==0)
dfs(ag,i,flag);
p=p->link;
}
}
/*void blt(listnode ag[M],int n)
{
int i;
int flag[M];
for(i=1;i<=n;i++)
flag[i]=0;
for(i=1;i<=n;i++)
if(flag[i]==0)
dfs(ag,i,flag);
}*/
void main()
{
listnode ag[M];
int flag[M];
creatlist(ag);
dfs(ag,28,flag);
}
『陸』 數據結構課程設計
#include "stdio.h"
#include "time.h"
#define MAXNUM 5 //停車場車位數
#define PRICE 2.0 //每小時收費
typedef struct car //定義車的結構體
{
char num[10]; //車牌號(最多10個位元組)
struct tm intime; //進入時間
struct tm outtime; //離開時間
int expense; //費用
int length; //停車時長
int position; //停車位
}CAR;
typedef struct //棧結構
{
CAR car[MAXNUM]; //車輛信息
int top; //棧頂指針
} SeqStack;
void StackInit(SeqStack * s) //初始化棧
{
s->top = -1;
}
int StackIsEmpty(SeqStack * s) //判斷棧是否為空
{
if (s->top == -1)
return 1;
else
return 0;
}
int StackIsFull(SeqStack *s) //判斷棧是否為滿
{
if (s->top == MAXNUM - 1)
return 1;
else
return 0;
}
void StackPush(SeqStack *s, CAR car) // 進棧
{
if (!StackIsFull(s)) //若棧未滿
{
s->top++; //修改棧頂指針
s->car[s->top] = car; //將車輛信息入棧
}
}
CAR StackPop(SeqStack *s) //出棧
{
CAR car;
if (s->top != -1) //棧不為空
{
car = s->car[s->top];
s->top--;
return car;
}
}
CAR StackGetTop(SeqStack * s) //取棧頂元素
{
CAR car;
if (s->top != -1)
{
car = s->car[s->top];
return car;
}
}
//隊列鏈表
typedef struct carnode //定義鏈隊列的節點
{
CAR data;
struct carnode *next;
}CarNodeType;
typedef struct //鏈隊列
{
CarNodeType *head; //頭指針
CarNodeType *rear; //尾指針
}CarChainQueue;
void ChainQueueInit(CarChainQueue * q) //初始化鏈隊列接點性質
{
if(!(q->head = (CarNodeType *) malloc(sizeof(CarNodeType))))
{
printf("內存分配失敗!\n");
exit(0);
}
q->rear = q->head; //頭尾指針相同
q->head->next = NULL; //頭尾指針後下一個節點為空
q->rear->next = NULL;
}
void ChainQueueIn(CarChainQueue * q, CAR car) //入隊列
{
CarNodeType *p;
if(!(p = (CarNodeType *) malloc(sizeof(CarNodeType))))
{
printf("內存分配失敗!\n");
exit(0);
}
p->data = car;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
CAR ChainQueueOut(CarChainQueue * q) //出隊列
{
CarNodeType *p;
CAR car;
if (q->head != q->rear)
{
p = q->head->next;
if (p->next == NULL)
{
car = p->data;
q->rear = q->head;
free(p);
} else
{
q->head->next = p->next;
car = p->data;
free(p);
}
return car;
}
}
int ChainQueueIsEmpty(CarChainQueue * q) //判斷鏈隊列是否為空
{
if (q->rear == q->head) //若隊首等於列尾
return 1; //返回空
else
return 0; //返回非空
}
void separator(int n,char ch,char newline) //輸出多個字元
{
int i;
for(i=0;i<n;i++)
printf("%c",ch);
if(newline==1)
printf("\n");
}
void PrintDate(struct tm gm_date)
{
printf("%d/%d %02d:%02d:%02d\n", gm_date.tm_mon,gm_date.tm_mday,gm_date.tm_hour+8, gm_date.tm_min, gm_date.tm_sec);
}
void ShowPark(SeqStack *s) //查看車位狀態
{
int i;
struct tm gm_date;
printf("\n車位使用情況\n");
separator(40,'_',1);
if (StackIsEmpty(s)) //若棧是空
printf("停車場內已沒有車輛!\n");
else
{
printf("位置\t車牌號\t進站時間\n");
for (i = 0; i <= s->top; i++)
{
printf("%d\t", s->car[i].position);
printf("%s\t", s->car[i].num);
PrintDate(s->car[i].intime); //輸出日期
}
printf("\t\t\t共%d輛", s->top + 1);
if (s->top == MAXNUM - 1)
printf("(已滿)\n");
else
printf("(還可停放放%d輛)\n", MAXNUM - 1 - s->top);
printf("\n");
}
separator(40,'_',1);
}
void ShowAisle(CarChainQueue * q)//顯示過道上車輛的情況
{
if (!ChainQueueIsEmpty(q)) //若隊列不為空
{
CarNodeType *p;
p = q->head->next; //隊列中的第1輛車
printf("\n\n過道使用情況\n");
separator(30,'_',1);
printf("車牌\t進入時間\n");
while (p!= NULL) //隊列不為空
{
printf("%s\t", p->data.num);
PrintDate(p->data.intime);; //顯示該輛車的信息
p = p->next; //下一輛
}
} else
printf("\n過道上沒有車在等待\n");
separator(30,'_',1);
printf("\n\n");
}
void ShowAll(SeqStack *s, CarChainQueue *q) //查看車位和過道使用情況
{
ShowPark(s); //顯示車位使用情況
ShowAisle(q); //顯示過道使用情況
}
void InPark(SeqStack * s, CarChainQueue * q) //車輛進入停車場
{
CAR car;
struct tm *gm_date;
time_t seconds;
time(&seconds);
gm_date = gmtime(&seconds);;
printf("\n車牌號:");
scanf("%s",&car.num);
car.intime=*gm_date; //進入停車場的時間
if (!StackIsFull(s) && ChainQueueIsEmpty(q)) //如果車位未占完，且過道上沒有車
{
car.position = (s->top) + 2; //車位號
StackPush(s, car); //車輛直接進入車位
ShowPark(s); //輸出現在停車場的情況
}
else if (StackIsFull(s) || !ChainQueueIsEmpty(q)) //如果車位已滿，過道上還有車，則必須放在過道上
{
printf("提示：車位滿,只有先停放在過道中。\n");
car.position = MAXNUM;
ChainQueueIn(q, car); //停放在過道
ShowPark(s); //顯示車位的情況
ShowAisle(q); //輸出過道上的情況
}
}
void PrintRate(CAR *car) //離開時輸出費用等情況
{
printf("\n\n 賬單\n" );
separator(30,'_',1);
printf("車牌:%s\n", car->num);
printf("停車位置:%d\n", car->position);
printf("進入時間:");
PrintDate(car->intime);
printf("離開時間:");
PrintDate(car->outtime);
printf("停車時間(秒):%d\n", car->length);
printf("費用(元):%d\n", car->expense);
separator(30,'_',1);
printf("\n\n");
}
void OutPark(SeqStack *s, CarChainQueue *q) //車出站出當時過道上的情況放在過道上直接進入車站
{
struct tm *gm_date;
time_t seconds;
SeqStack p; //申請臨時放車的地方
StackInit(&p);
char nowtime[10];
int i, pos;
CAR car;
if (StackIsEmpty(s)) //如果車位中沒有車輛停放
{
printf("所有車位都為空，沒有車輛需要離開!\n");
}
else
{
printf("現在車位使用情況是:\n");
ShowPark(s); //輸出車位使用情況
printf("哪個車位的車輛要離開:");
scanf("%d", &pos);
if (pos > 0 && pos <= s->top + 1) //輸入車位號正確
{
for (i = s->top + 1; i > pos; i--) //在將pos車位之後停的車放入臨時棧，以使pos車位的車出來
{
car = StackPop(s); //出棧
car.position = car.position - 1;//修改車位號
StackPush(&p, car); //將車輛放入臨時棧
}
car = StackPop(s); //將位於pos車位的車輛出棧
time(&seconds);
gm_date = gmtime(&seconds); //獲取當前時間
car.outtime=*gm_date;//離開時間
car.length=mktime(&car.outtime)-mktime(&car.intime); //停車場中停放時間
car.expense=(car.length/3600+1)*PRICE; //費用
PrintRate(&car); //輸出車出站時的情況---進入時間，出站時間，原來位置，花的費用等
while (!StackIsEmpty(&p)) //將臨時棧中的車重新進入車位
{
car = StackPop(&p); //從臨時棧中取出一輛車
StackPush(s, car); //將車進入車位
}
while(!StackIsFull(s) && !ChainQueueIsEmpty(q)) //如果車位未滿, 且過道上還有車
{
car = ChainQueueOut(q); //將最先停在過道中的車輛進入車位
time(&seconds);
gm_date = gmtime(&seconds); //獲取當前時間
car.intime = *gm_date;//保存進入車位的時間
StackPush(s, car); //將車輛進入車位
}
}
else //車位號輸入錯誤
{
printf("車位號輸入錯誤，或該車位沒有車輛!\n");
}
}
}
int main()
{
SeqStack Park; //停車場棧
CarChainQueue Aisle; //過道鏈表
StackInit(&Park);
ChainQueueInit(&Aisle);
char choice;
do{
printf("\n\n");
separator(10,' ',0);
printf("停車場管理\n");
separator(30,'_',1);
printf("1.車輛進入\n");
printf("2.車輛離開\n");
printf("3.查看停車場情況\n");
printf("0.退出系統\n");
separator(56,'_',1);
printf("提示：本停車場有%d個車位，車位停滿後的車輛將停放在過道上。\n",MAXNUM);
printf("本停車場時計費，收費標准:%.2f元/小時,過道上不收費。\n\n",PRICE);
printf("\n選擇操作(0~3):");
fflush(stdin);
choice=getchar();
switch (choice)
{
case '1': //車輛進入
InPark(&Park,&Aisle);
break;
case '2': //車輛離開
OutPark(&Park,&Aisle);
break;
case '3':
ShowAll(&Park,&Aisle);
break;
}
}while(choice!='0');
return 0;
}
『柒』 數據結構課程設計題目，圖的建立以及遍歷。
//圖的遍歷演算法程序
//圖的遍歷是指按某條搜索路徑訪問圖中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法，程序如下：
#include <iostream>
//#include <malloc.h>
#define INFINITY 32767
#define MAX_VEX 20 //最大頂點個數
#define QUEUE_SIZE (MAX_VEX+1) //隊列長度
using namespace std;
bool *visited; //訪問標志數組
//圖的鄰接矩陣存儲結構
typedef struct{
char *vexs; //頂點向量
int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣
int vexnum,arcnum; //圖的當前頂點數和弧數
}Graph;
//隊列類
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base;
int front;
int rear;
};
//圖G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
//創建無向網
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("輸入頂點數和弧數:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回車
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點數目
printf("輸入%d個頂點.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化頂點
printf("輸入頂點%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回車
}
for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("輸入%d條弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("輸入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //輸入一條邊依附的頂點和權值
temp=getchar(); //接收回車
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//圖G中頂點k的第一個鄰接頂點
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//圖G中頂點i的第j個鄰接頂點的下一個鄰接頂點
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度優先遍歷
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次執行DFS時,k為-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //對尚未訪問的頂點調用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //訪問第k個頂點
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //對k的尚未訪問的鄰接頂點i遞歸調用DFS
}
}
//廣度優先遍歷
void BFS(Graph G){
int k;
Queue Q; //輔助隊列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i尚未訪問
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //隊頭元素出列並置為k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w為k的尚未訪問的鄰接頂點
visited[w]=true;
printf("%c ",G.vexs[w]);
Q.EnQueue(w);
}
}
}
}
//主函數
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n廣度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序結束.\n");
}
輸出結果為（紅色為鍵盤輸入的數據，權值都置為1）：
輸入頂點數和弧數:8 9
輸入8個頂點.
輸入頂點0:a
輸入頂點1:b
輸入頂點2:c
輸入頂點3:d
輸入頂點4:e
輸入頂點5:f
輸入頂點6:g
輸入頂點7:h
輸入9條弧.
輸入弧0:a b 1
輸入弧1:b d 1
輸入弧2:b e 1
輸入弧3:d h 1
輸入弧4:e h 1
輸入弧5:a c 1
輸入弧6:c f 1
輸入弧7:c g 1
輸入弧8:f g 1
廣度優先遍歷: a b d h e c f g
深度優先遍歷: a b c d e f g h
程序結束.