831数据结构与C语言考研试题2012-2014真题。

特别说明：把c1.h,C2-1.H,Bo2-1.cpp,Func2-2.cpp,Main2-1.cpp它们分别单独存为文件，然后把他们放在一个文件夹中，最后双击Main2-1.cpp。//c1.h(文件名)#include//字符串函数头文件#include//字符函数头文件#include//malloc()等#include//INT_MAX等#include//标准输入输出头文件，包括EOF(=^Z或F6)，NULL等#include//atoi()，exit()#include//eof()#include//数学函数头文件，包括floor()，ceil()，abs()等#include//ftime()#include//提供宏va_start，va_arg和va_end，用于存取变长参数表//函数结果状态代码。#defineTRUE1#defineFALSE0#defineOK1#defineERROR0//#defineINFEASIBLE-1没使用//#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3，故去掉此行typedefintStatus;//Status是函数的类型，其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型，其值是TRUE或FALSE，//c2-1.h线性表的动态分配顺序存储结构。#defineLIST_INIT_SIZE10//线性表存储空间的初始分配量#defineLIST_INCREMENT2//线性表存储空间的分配增量structSqList{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)};//bo2-1.cpp顺序存储的线性表(存储结构由c2-1.h定义)的基本操作(12个)，包括算法2.3～2.6voidInitList(SqList&L)//算法2.3{//操作结果：构造一个空的顺序线性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)//存储分配失败exit(OVERFLOW);L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量}voidDestroyList(SqList&L){//初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表Lfree(L.elem);//释放L.elem所指的存储空间L.elem=NULL;//L.elem不再指向任何存储单元L.length=0;L.listsize=0;}voidClearList(SqList&L){//初始条件：顺序线性表L已存在。操作结果：将L重置为空表L.length=0;}StatusListEmpty(SqListL){//初始条件：顺序线性表L已存在。//操作结果：若L为空表，则返回TRUE；否则返回FALSEif(L.length==0)returnTRUE;elsereturnFALSE;}intListLength(SqListL){//初始条件：顺序线性表L已存在。操作结果：返回L中数据元素的个数returnL.length;}StatusGetElem(SqListL,inti,ElemType&e){//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)//操作结果：用e返回L中第i个数据元素的值if(iL.length)//i不在表L的范围之内returnERROR;e=*(L.elem+i-1);//将表L的第i个元素的值赋给ereturnOK;}intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)//操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。//若这样的数据元素不存在，则返回值为0。算法2.6inti=1;//i的初值为第1个元素的位序ElemType*p=L.elem;//p的初值为第1个元素的存储位置while(iL.length)//到表结束处还未找到值为cur_e的元素returnERROR;//操作失败else//找到值为cur_e的元素，并由p指向其{pre_e=*--p;//p指向前一个元素(cur_e的前驱)，将所指元素的值赋给pre_ereturnOK;//操作成功}}StatusNextElem(SqListL,ElemTypecur_e,ElemType&next_e){//初始条件：顺序线性表L已存在//操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，//否则操作失败，next_e无定义inti=1;//从第1个元素开始ElemType*p=L.elem;//p指向第1个元素while(iL.length+1)//i值不合法returnERROR;if(L.length==L.listsize)//当前存储空间已满，增加分配，修改{newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType));if(!newbase)//存储分配失败exit(OVERFLOW);L.elem=newbase;//新基址赋给L.elemL.listsize+=LIST_INCREMENT;//增加存储容量}q=L.elem+i-1;//q为插入位置for(p=L.elem+L.length-1;p>=q;--p)//插入位置及之后的元素右移(由表尾元素开始移)*(p+1)=*p;*q=e;//插入e++L.length;//表长增1returnOK;}StatusListDelete(SqList&L,inti,ElemType&e)//算法2.5{//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1ElemType*p,*q;if(iL.length)//i值不合法returnERROR;p=L.elem+i-1;//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//q为表尾元素的位置for(++p;pb，分别返回-1、0或1if(a==b)return0;elsereturn(a-b)/abs(a-b);}voidprint(ElemTypec){//以十进制整型的格式输出元素的值printf("%d",c);}voidprint1(ElemType&c){//以十进制整型的格式输出元素的值(设c为引用类型)printf("%d",c);}voidprint2(ElemTypec){//以字符型的格式输出元素的值printf("%c",c);}//main2-1.cpp检验bo2-1.cpp的主程序#include"c1.h"typedefintElemType;//定义ElemType为整型#include"c2-1.h"//线性表的顺序存储结构#include"bo2-1.cpp"//线性表顺序存储结构的基本操作#include"func2-2.cpp"//包括equal()、comp()、print()、print1()和print2()函数Statussq(ElemTypec1,ElemTypec2){//数据元素判定函数(平方关系)，LocateElem()调用的函数if(c1==c2*c2)returnTRUE;elsereturnFALSE;}voiddbl(ElemType&c){//ListTraverse()调用的另一函数(元素值加倍)c*=2;}voidmain(){SqListL;ElemTypee,e0;Statusi;intj,k;InitList(L);//初始化线性表Lprintf("初始化L后，L.length=%d，L.listsize=%d，L.elem=%u\n",L.length,L.listsize,L.elem);for(j=1;j=k;j--){i=ListDelete(L,j,e);//删除第j个数据if(i==ERROR)//表中不存在第j个数据printf("删除第%d个元素失败。",j);else//表中存在第j个数据，删除成功，其值赋给eprintf("删除第%d个元素成功，其值为%d",j,e);}ListTraverse(L,dbl);//依次对元素调用dbl()，元素值乘2printf("L的元素值加倍后，L=");ListTraverse(L,print1);//依次输出表L中的元素DestroyList(L);//销毁表Lprintf("销毁L后，L.length=%d，L.listsize=%d，L.elem=%u\n",L.length,L.listsize,L.elem);}