《数据结构》第一次上机测试代码部分(最新版)

1、第一次数据结构上机测试代码题目分配： 本次测试一共三个大题目，包括A）顺序表的基本操作，B）单链表的基本操作及C）栈和队列的操作。1、 题目一有3个小题目，每位同学只需做其中一题即可，做题序号由学号后两位模3决定。若模出来结果为1，则做第1道；结果为2，则做第2道；结果为0，做第3道。2、题目二也有3个小题目，每位同学只需做其中一题即可，做题序号同题目一。3、题目三所有同学都做。该题目有2个测试用例，测试用例由学号后一位模2决定。若模出来结果为1，则用第1个测试用例；结果为0，则用第2个测试用例。注意事项：1、 每个同学在D：盘下新建一个文件夹，以“班级+学号+姓名”形式命名，如：2班2012

2、0102张三。该文件夹中应该包含三个子文件夹，包括了所有作业。2、 三个子文件夹分别对应三个试题，分别命名为：1）顺序表、2）链表、及3）栈和队列。将相应题目的工程建于各文件夹下。（也即，顺序表文件夹应该有顺序表的操作的工程文件）3、 考试结束，请各位同学在座位上，等待监考老师确认你的考题之后方可签字离开。第一部分 线性表题目一：*头文件sequential.h*#ifndef _FUNC_H#define _FUNC_H/函数结果状态代码#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#defin

3、e 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 &

4、amp;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,Ele

5、mType 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

6、 &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 *)reall

7、oc(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.elemi=e;return OK;/依次访问L中的每个数据元素并输出其值Status ListTraverse_sq (SqLi

8、st L)int i = 0;if (! L.elem) return ERROR;while (i < L.length)printf("%d ", L.elemi);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, Elem

9、Type 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

10、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;

11、if (!InitList_sq(L) printf("建立空线性表失败,请重启程序n");elseprintf("请输入需要建立的元素个数,输入0表示退出n");scanf("%d", &L.length);printf("请逐个输入整数型元素:n");if (!BuildList_sq(L, L.length) printf("建立线性表失败,请重新输入n");elsechar choice = 1;while(choice) menu();scanf("%d",

12、 &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 TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define O

13、VERFLOW -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，否则返

14、回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 ListTr

15、avel_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+) LinkLis

16、t 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(L

17、inkList &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，否则返回0 return OK;/end of ListInsertStatus ListDelete_L(LinkList L, int i, ElemType &e) /删除链表i位置元素，并用e返回,如果删除成功，函数返回1，否则

18、返回0 return OK; Status LocateElem(LinkList L,ElemType e)/定位元素e在链表中的位置,存在返回该元素的位序，否则返回0 return OK;void menu()/菜单printf("n*n");printf("1.插入元素n");printf("2.删除元素n");printf("3.定位元素n");printf("4.遍历链表n");printf("0.清空链表,并退出n");printf("n*n"

19、);*主函数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);whi

20、le(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

21、; 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);/利用

22、两量栈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>#inclu

23、de <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) retur

24、n 0;/ 若栈空，返回ERROR e = *-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 m

25、enu()/菜单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=

26、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。SElemType x1;if(S1.top - S1.base >= S1.stacksize && !StackEmpty(S2) /S1满S2非空