数据结构考试题.doc

数据结构
线性表
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#include<process.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int Boolean;
typedef int ElemType;
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2
typedef struct
{
int *elem;
int length;
int listsize;
}SqList;
Status InitList(SqList *L)
{ L->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L->elem)
exit(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
Status ListInsert(SqList *L,int i,int e)
{ int *newbase,*q,*p;
if(i<1||i>L->length+1)
return ERROR;
if(L->length>=L->listsize)
{
if(!(newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType))))
exit(OVERFLOW);
L->elem=newbase;
L->listsize+=LISTINCREMENT;
}
q=L->elem+i-1;
for(p=L->elem+L->length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++L->length;
return OK;
}
Status ListPrint(SqList *L)
{ int *q;
int i;
q=L->elem;
for(i=1;i<=L->length;i++)
printf("%d ",*q++);
printf("\n");
return OK; }
Status ListDelete(SqList *L,int i,ElemType *e)
{ ElemType *p,*q;
if(i<1||i>L->length) // i值不合法
return ERROR;
p=L->elem+i-1;
*e=*p;
q=L->elem+L->length-1;
for(++p;p<=q;++p)移
*(p-1)=*p;
L->length--;
return OK; }
Status GetElem(SqList *L,int i,ElemType *e)
{ if(i<1||i>L->length)
exit(ERROR);
*e=*(L->elem+i-1);
return OK; }
int menu()
{int n;
printf("put number");
scanf("%d",&n);return n; }
void main()
{ SqList l,La,Lb,Lc;
int i;
int e;
printf ("1 InitList\n 2 listinsert\n 3 listprint\n 4 ListDelete\n 5 GetElem\n 6 MergeList\n 6 exit\n");
do
{ switch(menu())
{ case 1:InitList(&l);printf("初始化!!!!!\n");break;
case 2:printf("i,e");scanf("%d%d",&i,&e);
ListInsert(&l,i,e);break;
case 3:ListPrint(&l);break;
case 4:printf("i,e");scanf("%d",&i);
ListDelete(&l,i,&e);break;
case 5:printf("i");scanf("%d",&i);
GetElem(&l,i,&e);printf("%d\n",e);break;
case 6:exit(0); }}
while(1); }
======================================================================
单链表

#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#define OK 1
#define ERROR 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;

typedef int Status;
//-----------------------------------------------------------------------------
void CreateList(LinkList *L,int n)
{
int i;
LNode *p;
*L=(LinkList)malloc(sizeof(LNode));
(*L)->next=NULL;
for(i=n;i>0;--i)
{p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=(*L)->next;
(*L)->next=p;}
}
//----------------------------------------------------------------------------
Status ListInsert(LinkList *L,int i,int e)
{
int j;
LinkList p,s;
p=*L;j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
return OK;
}
//-----=---------------------------------------------------------------------
void ListPrint(LinkList *L)
{LinkList p;
p=(*L)->next;
printf("%d",p->data);
while(p->next)
{
p=p->next;
printf("%3d",p->data);
}
}
//----------------------------------------------------------------------------
Status ListDelete(LinkList *L,int i,int *e)
{LinkList p,q;
int j;
p=*L;j=0;
while(p->next&&j<i-1)
{p=p->next;++j;}
if(!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
*e=q->data; free(q);
return OK;
}
//-----------------------------------------------------------------------------
Status GetElem(LinkList *L,int i,int *e)
{
LinkList p;
int j;
p=(*L)->next;j=1;
while(p&&j<i)
{p=p->next;++j;}
if(!p||j>i) return ERROR;
*e=p->data;
return OK;
}
//---------------------------------------------------------------------------
int Menu()
{int a;
printf("******************************\n");
printf("* 1->CreateList *\n");
printf("* 2->ListInsert *\n");
printf("* 3->Listprint *\n");
printf("* 4->ListDelete *\n");
printf("* 5->GetElem *\n");
printf("* 6->exit *\n");
printf("******************************\n");

do
{printf("Enter You selelt:");
scanf("%d",&a);
}while(!(a>=1&&a<=7));
return(a);
}
main()
{
LinkList l,La,Lb,Lc;
int x,i,e,n,result,flag=0;
do
{
x=Menu();
switch(x)
{case 1: printf("Enter n :");
scanf("%d",&n);
CreateList(&l,n);
flag=1;
printf("success!print Enter continue...\n");
break;
case 2:if(flag==0)
{printf("please enter 1! zai shu 2!");
break;
}
printf("\n please input i and e:");
scanf("%d %d",&i,&e);
result=ListInsert(&l,i,e);
if(result==ERROR)
printf("Enter i is Erroe!please Enter contime...\n");
else
printf("Indent Success complered\n!");
break;
case 3:printf("ListPrint:");
ListPrint(&l);
printf("\n!please Entrer contime....");
break;
case 4:
printf("Enter i :");
scanf("%d",&i);
result=ListDelete(&l,i,&e);
if(result==ERROR)
printf("Enter i is Error! please Enter cintime...\n");
else
printf("Indent Succes complered: %d\n",e);
break;
case 5:
printf("Enter i :");
scanf("%d",&i);
GetElem(&l,i,&e);
printf("Succes is i :%d\n",e);
break;
case 6: printf("\n");x=0;break;
}
}while(x!=0);
}
======================================================================
栈
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<math.h> // floor(),ceil(),abs()
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int SElemType;

typedef struct
{ int *base;
int *top;
int stacksize;
}SqStack;
//----------------------------------------------------------
Status InitStack(SqStack *S)
{S->base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S->base) exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
//-----------------------------------------------------------
Status Push(SqStack *S,SElemType e)
{
if(S->top-S->base>=S->stacksize)
{S->base=(SElemType *) realloc(S->base,(S->stacksize+STACKINCREMENT) *sizeof(SElemType));
if(!S->base) exit(OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return OK;
}
//----------------------------------------------------------
int Menu()
{int x;
printf("enter your choice:");
scanf("%d",&x);
return x;
}
//---------------------------------------------------------
void StackPrint(SqStack S)
{SElemType *p;
p=S.top;
printf("打印---:");
while(p!=S.base)
{printf("%d\t",*--p);
}
}
//-----------------------------------------------------------
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==S->base) return ERROR;
*e=*--S->top;
return OK;

}
//----------------------------------------------------------
Status GetTop(SqStack S, SElemType *e)
{
if(S.top==S.base) return ERROR;
*e=*(S.top-1);
return OK;
}
//----------------------------------------------------------
main()
{int e,n=0;
SqStack s;
char kuohao[100];
printf("------------------------------------------------\n");
printf("\t\t1:InitStack\t\t\n");
printf("\t\t2:Push\t\t\t\n");
printf("\t\t3:Print\t\t\t\n");
printf("\t\t4:GetTop\t\t\n");
printf("\t\t5:Pop\t\t\t\n");
printf("\t\t6:Exit\t\t\t\n");
printf("-------------------------------------------------\n");
while(1)
{
switch(Menu())
{ case 1:printf("栈建立成功!!!!!");printf("\n");
InitStack(&s);printf("\n");break;
case 2:printf("输入压入栈顶的元素:");scanf("%d",&e);printf("\n");
Push(&s,e);printf("\n");break;
case 3:StackPrint(s);printf("\n");break;
case 4:printf("打印站顶元素------值为%d",GetTop(s,&n));
break;
case 5:Pop(&s,&n);
printf("弹出站顶元素------值为%d",n);
break;

case 6:exit(0); }
};
}
======================================================================
队列
#include<malloc.h> // malloc()等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#define OK 1
#define ERROR 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int SElemType;
typedef struct QNode
{ int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{ QueuePtr front;
QueuePtr rear;
}LinkQueue;
//----------------------------------------------------------------
Status InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front) exit (OVERFLOW);
Q->front->next=NULL;
return OK;
}
//---------------------------------------------------------------
Status DestroyQueue(LinkQueue *Q)
{while(Q->front)
{
Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
return OK;}
//-----------------------------------------------------------------
Status EnQueue(LinkQueue *Q, SElemType e)
{ QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit (OVERFLOW);
p->data=e;p->next=NULL;
Q->rear->next=p;
Q->rear=p;
return OK;
}
//----------------------------------------------------------------
void QueuePrint( LinkQueue *Q )
{
/*QueuePtr p;
if(Q.rear==Q.front) exit(0);
while(Q.rear!=Q.front)
{
p=Q.front->next;
printf("%d ",p->data);
Q.front=p;}*/
QueuePtr p;
p=Q->front;
while(Q->rear!=p)
{ p=p->next;
printf("%d ",p->data);} }
//----------------------------------------------------------------
Status DeQueue(LinkQueue *Q, SElemType *e)
{ QueuePtr p;
if(Q->front==Q->rear) return ERROR;
{p=Q->front->next;
*e=p->data;
Q->front->next=p->next;}
if(Q->rear==p) Q->rear=Q->front;
free(p);
return OK; }
//---------------------------------------------------------------
int menu()
{int n;
printf("put number");
scanf("%d",&n);return n; }
void main()
{
int n;
LinkQueue Q;
SElemType e;
printf (" 1 InitQueue\n 2 DestroyQueue\n 3 EnQueue\n 4 DeQueue\n 5 StackPrint\n 6 exit\n");
do{
n=menu();
switch(n)
{ case 1:if(InitQueue(&Q))printf("初始化！！！");else printf("ERROR");printf("\n");break;
case 2:if(DestroyQueue(&Q))printf("OK"); else printf("ERROR");printf("\n");break;
case 3:printf("enter e:");scanf("%d",&e);if(EnQueue(&Q, e))printf("OK");else printf("EROR");printf("\n");break;
case 4:if(DeQueue( &Q, &e))printf("%d",e);else printf("ERROR");printf("\n");break;
case 5:QueuePrint(&Q);printf("\n");break;
case 6:exit(0); } }
while(1); }