数据结构习题集与实验指导

.

i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){ DLR(root);

printf(\ return(0); }

else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return(0);} 执行结果：

若一开始运行就输入-9999，则无叶子输出，sum=0。

实验六 图的应用

[实验目的]：掌握图的定义和存储结构；

掌握图的遍历算法，比较和树的遍历的区别。 掌握图的最小生成树问题。 [实验题目]：

1.编写程序依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 参考算法：

Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {

InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) {

t=getchar();h=getchar(); //t为弧尾,h为弧头

.

.

if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList

实验 七 [实验目的]：掌握顺序表和有序表的查找方法； 掌握二叉排序树的构造和查找方法； [实验题目]：

1．顺序查找和折半查找示例： #include

typedef int KeyType; typedef struct{ KeyType key; int maths; int english; }ElemType;

#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)< (b)) #define LQ(a,b) ((a)<=(b)) typedef struct { ElemType *elem; int length; }SSTable;

int Search_Seq(SSTable ST,KeyType key) {

int i;

ST.elem[0].key=key;

for(i=ST.length; !EQ(ST.elem[i].key,key); --i); return i; }

int Search_Bin(SSTable ST,KeyType key) {

int low,mid,high;

low=1;high=ST.length; while(low<=high){

.

查找

.

mid=(low+high)/2;

if EQ(key,ST.elem[mid].key) return mid;

else if LT(key,ST.elem[mid].key) high=mid -1; else low=mid +1; } }

getdata(SSTable * t) {

FILE *fp; int i=1;

fp=fopen(\

fscanf(fp,\ while(i<=t->length) {

fscanf(fp,\ &(t->elem[i].maths),&(t->elem[i].english) ); i++; }

fclose(fp); }

main() {

ElemType stu[50]; SSTable class; int i,j,k; long time;

class.elem=stu; getdata(&class);

printf(\ printf(\ scanf(\

i=Search_Seq(class,k); j=Search_Bin(class,k);

printf(\ English\\n\

printf(\ %d\\n\ printf(\ %d\\n\ for(i=1;i<=4;i++)

{j=stu[i].maths+stu[i].english; printf(\ }

}

二叉排序树示例： #include

#define ERROR 0; #define FALSE 0; #define TRUE 1;

.

.

#define OK 1;

typedef int ElemType; typedef int Status; typedef int KeyType;

#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)< (b)) #define LQ(a,b) ((a)<=(b)) typedef struct BinaryTree {

ElemType data; struct BinaryTree *l; struct BinaryTree *r; }*BiTree,BiNode; BiNode * new() {

return( (BiNode *)malloc(sizeof(BiNode)) ); }

CreateSubTree(BiTree *T,ElemType *all,int i) {

if ((all[i]==0)||i>16) {

*T=NULL; return OK; }

*T=new();

if(*T==NULL) return ERROR; (*T)->data=all[i];

CreateSubTree(&((*T)->l),all,2*i); CreateSubTree(&((*T)->r),all,2*i+1); }

CreateBiTree(BiTree *T) {

ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,}; CreateSubTree(T,all,1); }

printelem(ElemType d) {

printf(\}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d)) {

if(T){

if(Visit(T->data))

if(PreOrderTraverse(T->l,Visit)) if(PreOrderTraverse(T->r,Visit)) return OK; return ERROR;

.