第一次《数据结构》上机测试代码题目分配：本次测试一共三个大题目，包括A）顺序表的基本操作，B）单链表的基本操作及C）栈和队列的操作。
1、题目一有3个小题目，每位同学只需做其中一题即可，做题序号由学号后两位模3决定。
若模出来结果为1，则做第1道；结果为2，则做第2道；结果为0，做第3道。
2、题目二也有3个小题目，每位同学只需做其中一题即可，做题序号同题目一。
3、题目三所有同学都做。
该题目有2个测试用例，测试用例由学号后一位模2决定。
若模出来结果为1，则用第1个测试用例；结果为0，则用第2个测试用例。
注意事项：1、每个同学在D：盘下新建一个文件夹，以“班级+学号+姓名”形式命名，如：2班20120102张三。
该文件夹中应该包含三个子文件夹，包括了所有作业。
2、三个子文件夹分别对应三个试题，分别命名为：1）顺序表、2）链表、及3）栈和队列。
将相应题目的工程建于各文件夹下。
（也即，顺序表文件夹应该有顺序表的操作的工程文件）3、考试结束，请各位同学在座位上，等待监考老师确认你的考题之后方可签字离开。
第一部分线性表题目一：*************头文件sequential.h***********************#ifndef _FUNC_H#define _FUNC_H//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int Status;//Status是函数的类型，其值是函数结果状态代码typedef int ElemType;//数据元素的类型ElemType为inttypedef struct {ElemType * elem;int length;int listsize;}SqList;extern Status InitList_sq (SqList &L);//初始化一个空的顺序表Lextern Status BuildList_sq (SqList &L, int n);//构造由n个元素构成的顺序表Lextern Status ListInsert_sq (SqList &L, int i, ElemType e);//在顺序表L中第i个位置插入新元素e,插入成功，返回1(OK)，否则返回0(ERROR)extern Status ListDelete_sq (SqList &L, int i, ElemType &e);//在顺序线性表L中删除第i个元素,并用e 返回其值，删除成功，返回1(OK)，否则返回0(ERROR)extern Status LocateElem_sq (SqList &L,ElemType e); //定位元素e，定位成功，函数返回该元素在顺序表中的位置，否则返回0extern Status ClearList_sq(SqList &L); //清空顺序表extern Status ListTraverse_sq (SqList L);//遍历顺序表extern void menu();//选择菜单#endif************************************************************************************** *********************************************************************************************************功能函数function.cpp*********************#include <stdlib.h>#include "stdio.h"#include "sequential.h"Status InitList_sq (SqList &L){//初始化一个空的顺序表LL.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));if (! L.elem) return ERROR;L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;}//end of InitListStatus BuildList_sq(SqList &L, int n){//构造由n个元素构成的顺序表Lif (L.length >= L.listsize){ElemType * newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));if (!newbase) return ERROR;L.elem = newbase;L.listsize += LISTINCREMENT;}ElemType e;for (int i = 0; i<n; i++){printf("第%d个元素的值为:",i+1);scanf("%d", &e);L.elem[i]=e;}return OK;}//依次访问L中的每个数据元素并输出其值Status ListTraverse_sq (SqList L){int i = 0;if (! L.elem) return ERROR;while (i < L.length){printf("%d ", L.elem[i]);i++;}printf("\n");return OK;}Status ClearList_sq(SqList &L){//清空顺序表if (! L.elem) return ERROR;L.elem = NULL;L.length = 0;L.listsize = 0;return OK;}Status ListInsert_sq (SqList &L, int i, ElemType e){//在顺序表L中第i个位置插入新元素e,插入成功，返回1(OK)，否则返回0(ERROR)return OK;}//end of ListInsertStatus ListDelete_sq (SqList &L, int i, ElemType &e){//在顺序线性表L中删除第i个元素,并用e返回其值，删除成功，返回1(OK)，否则返回0(ERROR)return OK;}Status LocateElem_sq(SqList &L, ElemType e){ //定位元素e，定位成功，函数返回该元素在顺序表中的位置，否则返回0return 0;}//打印菜单void menu(){printf("\n请选择操所\n");printf("1.插入元素\n");printf("2.删除元素\n");printf("3.定位元素\n");printf("4.遍历顺序表\n");printf("0.清空线性表,并退出\n");}************************************************************************************** ************************************************************************************** *****************主函数sequential.cpp**************************#include <stdio.h>#include "sequential.h"void main(){SqList L;int i=0;ElemType e = 0;if (!InitList_sq(L)) printf("建立空线性表失败,请重启程序\n");else{printf("请输入需要建立的元素个数,输入0表示退出\n");scanf("%d", &L.length);printf("请逐个输入整数型元素:\n");if (!BuildList_sq(L, L.length)) printf("建立线性表失败,请重新输入\n");else{char choice = 1;while(choice){menu();scanf("%d", &choice);switch(choice){case 1:break;case 2:break;case 3:break;case 4:ListTraverse_sq(L);break;}//end of switch} //end of while}//end of buildlist}//end of initlist}题目二：******* 头文件linked .h****************************** #ifndef _FUNC_H#define _FUNC_H//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10//Status是函数的类型，其值是函数结果状态代码typedef int Status;typedef int ElemType;typedef struct LNode {ElemType data; // 数据域struct LNode *next; // 指针域} LNode, *LinkList;extern Status ListInsert_L(LinkList L, int i, ElemType e);//向链表的i位置中插入元素e,如果插入成功，函数返回1，否则返回0：extern Status ListDelete_L(LinkList L, int i, ElemType &e);//删除链表i位置元素，并用e返回,如果删除成功，函数返回1，否则返回0：extern Status LocateElem(LinkList L,ElemType e);//定位元素e在链表中的位置,存在返回该元素的位序，否则返回0；extern void ClearList(LinkList &L);//清空链表extern void CreateListe_L(LinkList &L,int n );//创建链表extern Status ListTravel_L(LinkList L);//遍历链表extern void menu();//菜单#endif************************************************************************************** ************************************************************************************* ********功能函数function.cpp***************************#include <stdlib.h>#include "stdio.h"#include "linked .h"void CreateListe_L(LinkList &L,int n ){//生成链表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;LinkList q=L;for (int i=1;i<=n;i++){LinkList p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);q->next=p;q=p;}q->next=NULL;}Status ListTravel_L(LinkList L){//遍历链表LinkList p;if (!L) return ERROR;printf("链表为:");p=L->next;while (p){printf("%d ",p->data);p=p->next;}return OK;}void ClearList(LinkList &L){//清除链表while ( L->next){LinkList p=L->next;L->next = p->next;free(p);}}Status ListInsert_L(LinkList L, int i, ElemType e){//向链表的i位置中插入元素e,如果插入成功，函数返回1，否则返回0return OK;}//end of ListInsertStatus ListDelete_L(LinkList L, int i, ElemType &e){//删除链表i位置元素，并用e返回,如果删除成功，函数返回1，否则返回0 return OK;}Status LocateElem(LinkList L,ElemType e){//定位元素e在链表中的位置,存在返回该元素的位序，否则返回0}void menu(){//菜单printf("\n**********************\n");printf("1.插入元素\n");printf("2.删除元素\n");printf("3.定位元素\n");printf("4.遍历链表\n");printf("0.清空链表,并退出\n");printf("\n**********************\n");}************************************************************************************** ************************************************************************************** *****************主函数linked .cpp*******************************#include <stdio.h>#include <stdlib.h>#include " linked.h"void main(){LinkList L=(LinkList)malloc(sizeof (LNode));L->next = NULL;int i;int n;ElemType e = 0;char choice = 1;printf("请输入要建立的链表元素个数:");scanf("%d", &n);CreateListe_L(L, n);while(choice){menu();scanf("%d", &choice);switch(choice){case 1:break;case 2:break;case 3:break;case 4:break;}//end of switch} //end of while}题目三：***********************头文件3.h*******************************#ifndef _FUNC_H#define _FUNC_H#define STACK_SIZE 3 //顺序栈的深度为3typedef char SElemType;//栈元素的类型为chartypedef struct {SElemType *base;SElemType *top;int stacksize;} SqStack;//顺序栈extern int InitStack (SqStack &s);//构造栈extern int POP (SqStack &s, SElemType &e);//S栈顶元素出栈，赋给变量e；extern int PUSH (SqStack &s, SElemType e);//元素e入S栈；extern int StackEmpty(SqStack s);//判S栈是否为空extern int EnQueue(SqStack &S1, SqStack &S2,SElemType x);//利用两量栈S1,S2实现元素x的入对列extern int QueueEmpty(SqStack S1,SqStack S2);//判队列是否为空算法extern int DeQueue(SqStack &S2,SqStack &S1,SElemType &x);//利用两量栈S1,S2实现元素x的出对列,成功返回1，否则返回0extern void menu();//菜单extern void TravelQueue(SqStack S1, SqStack S2);//遍历队列#endif************************************************************************************** ************************************************************************************** *****************功能函数function.h**************************************#include <stdio.h>#include <stdlib.h>#include "3.h"int InitStack (SqStack &s){//初始化顺序栈ss.base=(SElemType*)malloc(STACK_SIZE * sizeof (SElemType));if (!s.base) return 0; //存储分配失败s.top = s.base;s.stacksize = STACK_SIZE;return 1;}int POP (SqStack &s, SElemType &e) {// 出栈操作，并用e返回栈顶if (s.top == s.base) return 0; // 若栈空，返回ERRORe = *--s.top; //不空，用形参e返回其值return 1; //返回OK；}int PUSH (SqStack &s, SElemType e) {// 入栈操作if (s.top - s.base >= s.stacksize) return 0; //栈满，返回ERROR*s.top++ = e; //*S.top=e;S.top++;return 1;}int StackEmpty(SqStack s){//判断栈S是否为空，为空，返回OK，否则返回ERRORif (s.base == s.top) return 1;return 0;}void menu(){//菜单printf("\n**********************\n");printf("1:入队列\n");printf("2:出队列\n");printf("3:判空\n");printf("4:遍历\n");printf("0.退出\n");printf("\n**********************\n");}//遍历队列void TravelQueue(SqStack S1, SqStack S2){SElemType *p_S1, *p_S2;printf("队列中的元素为：\n");for( p_S2=S2.top-1; p_S2>=S2.base; p_S2--)printf("%c--",*p_S2);for(p_S1=S1.base ; p_S1<S1.top ; p_S1++)printf("%c--",*p_S1);}//利用两量栈S1,S2实现元素x的入对列int EnQueue(SqStack &S1, SqStack &S2,SElemType x){//将x入队列，若入队列成功返回1,否则返回0。
