数据结构实验指导书2010.doc

数据结构实验指导书实验一、线性表（2学时）1.设计实验设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入10个整数，产生顺序表，并输入结点值。（2）从键盘输入1个整数，在顺序表中查找该结点的位置11。若找到，输出结点的位置；若找不到，则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。2.实验报告完成实验一实验报告。格式统一按“实验报告格式”，注意内容部分有页眉页脚。报告中实验原理部分需包括程序设计的基本思想，原理；实验过程部分需包括源程序及注释和调试、运行程序过程中产生的问题及采取的措施；实验结果部分需包括运行输出结果及对算法的程序的讨论、分析，改进设想，其它经验教训。另还可就实验方式、组织、设备、题目提出意见和建议。提示：可参考以下思路进行设计：#include #include /顺序表的定义：#define ListSize 100/表空间大小可根据实际需要而定，这里假设为100typedef int DataType;/DataType可以是任何相应的数据类型如int, float或chartypedef structDataType dataListSize;/向量data用于存放表结点int length;/当前的表长度SeqList;void main()SeqList L;int i,x;int n=10;/欲建立的顺序表长度L.length=0;void CreateList(SeqList *L,int n);void PrintList(SeqList L,int n);int LocateList(SeqList L,DataType x);void InsertList(SeqList *L,DataType x,int i);void DeleteList(SeqList *L,int i);CreateList(&L,n);/建立顺序表PrintList(L,n);/打印顺序表printf(输入要查找的值：);scanf(%d,&x);i=LocateList(L,x);/顺序表查找printf(输入要插入的位置：);scanf(%d,&i);printf(输入要插入的元素：);scanf(%d,&x);InsertList(&L,x,i);/顺序表插入PrintList(L,n);/打印顺序表printf(输入要删除的位置：);scanf(%d,&i);DeleteList(&L,i);/顺序表删除PrintList(L,n);/打印顺序表/顺序表的建立：void CreateList(SeqList *L,int n)/在此插入必要的语句/顺序表的打印：void PrintList(SeqList L,int n)/在此插入必要的语句/顺序表的查找：int LocateList(SeqList L,DataType x)/在此插入必要的语句/顺序表的插入：void InsertList(SeqList *L,DataType x,int i)/在此插入必要的语句/顺序表的删除：void DeleteList(SeqList *L,int i)/在此插入必要的语句实验二、单链表（2学时）1.验证实验打开教材自带教学辅助光盘，进入光盘中的“DSDemoC”目录，运行DSDemo.EXE，进入数据结构算法演示系统（C语言描述）V3.1C中文版。具体操作请按照界面上的提示进行。选择主菜单中链表下的各算法。首先仔细阅读算法，再输入数据，分步运行算法，检验自己对算法的理解是否正确。在实验报告中写出自己在演示算法过程中理解和实际运算的不同之处，并总结原因。2.设计实验设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入20个整数，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。（5）将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。（6）删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。（7）把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。（8）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。3.实验报告完成实验二实验报告。要求同实验一。提示：可参考以下思路进行设计：#include #include /单链表的定义：typedef int DataType;/DataType可以是任何相应的数据类型如int, float或chartypedef struct node/结点类型定义DataType data;/结点的数据域struct node *next;/结点的指针域ListNode;typedef ListNode *LinkList;void main()int i;DataType key,x;LinkList head;ListNode *p;LinkList CreateList(void);void PrintList(LinkList head);LinkList LocateNode(LinkList head,DataType key);LinkList GetNode(LinkList head,int i);void InsertList(LinkList head,DataType x,int i);void DeleteList(LinkList head,int i);void DeleteManyList(LinkList head);void DeleteEvenList(LinkList head);void ChangeCircList(LinkList head);void PrintCircList(LinkList head);head=CreateList();/建立单链表PrintList(head);/打印单链表printf(输入要查找的值：);scanf(%d,&key);p=LocateNode(head,key);/单链表查找printf(请输入欲插入元素的位置：);scanf(%d,&i);printf(请输入欲插入的元素：);scanf(%d,&x);InsertList(head,x,i);/单链表插入PrintList(head);/打印单链表printf(请输入欲删除结点的位置：);scanf(%d,&i);DeleteList(head,i);/单链表删除PrintList(head);/打印单链表DeleteManyList(head);/删除重复值PrintList(head);/打印单链表DeleteEvenList(head);/删除偶数值PrintList(head);/打印单链表ChangeCircList(head);/修改为循环单链表PrintCircList(head);/打印循环单链表/*void DivideList(LinkList head,LinkList *A,LinkList *B); /分割成两个单链表DivideList(head, &A, &B);PrintList(A);PrintList(B);*/单链表的建立：LinkList CreateList(void)/在此插入必要的语句/单链表的打印：void PrintList(LinkList head)/在此插入必要的语句/单链表的查找1：LinkList LocateNode(LinkList head,DataType key)/在此插入必要的语句/单链表的查找2：LinkList GetNode(LinkList head,int i)/在此插入必要的语句/单链表的插入：void InsertList(LinkList head,DataType x,int i)/在此插入必要的语句/单链表的删除：void DeleteList(LinkList head,int i)/在此插入必要的语句/删除单链表中重复值：void DeleteManyList(LinkList head)/在此插入必要的语句/删除单链表中偶数值：void DeleteEvenList(LinkList head)/在此插入必要的语句/修改为循环单链表：void ChangeCircList(LinkList head)/在此插入必要的语句/循环单链表的打印：void PrintCircList(LinkList head)/在此插入必要的语句/*/分割成两个单链表void DivideList(LinkList head,LinkList *A,LinkList *B);/在此插入必要的语句*/实验三、栈和队列（4学时）1. 验证实验打开教材自带教学辅助光盘，进入光盘中的“DSDemoC”目录，运行DSDemo.EXE，进入数据结构算法演示系统（C语言描述）V3.1C中文版。具体操作请按照界面上的提示进行。分别选择主菜单中栈子菜单下的前三个算法和队列子菜单下的各算法。首先仔细阅读算法，再输入数据，分步运行算法，检验自己对算法的理解是否正确。在实验报告中写出自己在演示算法过程中理解和实际运算的不同之处，并总结原因。2. 应用实验阅读所给的源程序，在实验报告中写出算法的功能和运行结果。程序如下：#define MAXNUM 100/* 栈中最大元素个数 */#define N 11 /*地图的第一维长度*/#include #include typedef struct int x;/* 行下标 */ int y;/* 列下标 */ int d;/* 运动方向 */ DataType;struct SeqStack /* 顺序栈类型定义 */ int t; /* 指示栈顶位置 */ DataType sMAXNUM;typedef struct SeqStack *PSeqStack;/* 顺序栈类型的指针类型 */PSeqStack pastack;/* pastack是指向顺序栈的一个指针变量 */PSeqStack createEmptyStack_seq( void ) PSeqStack pastack; pastack = (PSeqStack)malloc(sizeof(struct SeqStack); if (pastack = NULL) printf(Out of space! n); else pastack-t = -1; return pastack;int isEmptyStack_seq( PSeqStack pastack ) return pastack-t = -1;/* 在栈中压入一元素x */void push_seq( PSeqStack pastack, DataType x ) if( pastack-t = MAXNUM - 1 ) printf( Overflow! n ); else pastack-t+; pastack-spastack-t = x; /* 删除栈顶元素 */void pop_seq( PSeqStack pastack ) if (pastack-t = -1 ) printf( Underflow!n ); else pastack-t-;/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */DataType top_seq( PSeqStack pastack ) return (pastack-spastack-t);void pushtostack(PSeqStack st, int x, int y, int d) DataType element; element.x = x; element.y = y; element.d = d; push_seq(st, element);void printpath(PSeqStack st) DataType element; printf(The revers path is:n); /* 打印路径上的每一点 */ while(!isEmptyStack_seq(st) element = top_seq(st); pop_seq(st); printf(the node is: %d %d n, element.x, element.y); /* 迷宫mazeMN中求从入口mazex1y1到出口mazex2y2的一条路径 */* 其中 1=x1,x2=M-2 , 1=y1,y2=N-2 */void mazePath(int mazeN, int direction2, int x1, int y1, int x2, int y2) int i, j, k, g, h; PSeqStack st; DataType element; st = createEmptyStack_seq( ); mazex1y1 = 2; /* 从入口开始进入,作标记 */ pushtostack(st, x1, y1, -1); /* 入口点进栈 */ while ( !isEmptyStack_seq(st) /* 走不通时,一步步回退 */ element = top_seq(st); pop_seq(st); i = element.x; j = element.y; for (k = element.d + 1; k base=(Car *)malloc(STACK_INIT_SIZE*sizeof(Car); if(!(S-base) return ERROR; S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK;int StackEmpty(SqStack S) if(S.top=S.base) return OK; else return ERROR;int StackFull(SqStack S) if(S.top-S.base=STACK_INIT_SIZE) return OK; else return ERROR;int Push(SqStack *S,Car e) if(S-top-S-base=STACK_INIT_SIZE) return OVERFLOW; else *(S-top+)=e; return OK; int Pop(SqStack *S,Car *e) if(S-top=S-base) return ERROR; *e=*(-(S-top);typedef struct Car2 *top2; Car2 *base2; int stacksize2;SqStack2;int InitStack2(SqStack2 *S2) S2-base2=(Car2 *)malloc(STACK_INIT_SIZE*sizeof(Car2); if(!(S2-top2) return ERROR; S2-top2=S2-base2; S2-stacksize2=STACK_INIT_SIZE; return OK;int Push2(SqStack2 *S2,Car2 e2) if(S2-top2-S2-base2=STACK_INIT_SIZE) return OVERFLOW; *(S2-top2+)=e2; return OK;int Pop2(SqStack2 *S2,Car2 *e2) if(S2-top2=S2-base2) exit(OVERFLOW); *e2=*(-(S2-top2); return OK;int StackEmpty2(SqStack2 S2) if(S2.top2=S2.base2) return OK; else return ERROR;typedef struct QNode Car data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;int InitQueue(LinkQueue *Q) Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode); if(!(Q-front) return ERROR; Q-front-next=NULL; return OK;int EnQueue(LinkQueue *Q,Car e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) return ERROR; p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; return OK;int QueueEmpty(LinkQueue Q) if(Q.front=Q.rear) return OK; else return ERROR;int DeQueue(LinkQueue *Q,Car *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;main() int i,position_s=1,position_q=1; int ch=1,status; float time,money; LinkQueue Q; Car car_I,car_D,car_M; SqStack S; SqStack2 S2; clrscr(); InitStack(&S); InitStack2(&S2); InitQueue(&Q); while(ch=1) clrscr(); for(i=0;i80;i+)printf(*); printf(n); for(i=0;i24;i+) printf(-); printf(tSOOSKY CAR POSITIONt); for(i=0;i24;i+) printf(-); printf(nttt); for(i=0;i10;i+) printf(-); printf(Information); for(i=0;i10;i+) printf(-); printf(nn); do printf(nttt1-arrival 0-departure 1/0 ?b); scanf(%d,&status); while(status!=1&status!=0); if(status=1) printf(ntttCar Number :); scanf(%d,&car_I.label); printf(ntttTime : ?b); scanf(%f,&(car_I.time); if(!StackFull(S) Push(&S,car_I); printf(nn); for(i=0;i80;i+) printf(-); printf(n); printf(tCAR NUMBER :); printf( %d,car_I.label); printf(tARRIVE TIME :); printf( %5.2f,car_I.time); printf(nn); for(i=0;i80;i+) printf(-); printf(nn); printf(nWelcome to our SOOSKY CAR POSITION ! nnThe position of your car is %d,position_s); position_s+; printf(n); printf(Do you want to continue 1-continue/0-quit ?b); scanf(%d,&ch); else EnQueue(&Q,car_I); printf(Welcome to our SOOSKY CAR POSITION ,We are sorry that nnOur position is full, but you are free to place your car nnon our road.The position of your car is %d,position_q); position_q+; printf(nDo you want to continue 1-continue/0-quit ?b); scanf(%d,&ch); if(status=0) clrscr(); for(i=0;i80;i+)printf(*); printf(n); for(i=0;i24;i+) printf(-); printf(tSOOSKY CAR POSITIONt); for(i=0;i24;i+) printf(-); printf(nttt); for(i=0;i10;i+) printf(-); printf(Information); for(i=0;i10;i+) printf(-); printf(nn); printf(tYour are going to drive your car away ,nttPlease fill of the form !n); printf(nttYour car Number :); scanf(%d,&car_D.label); printf(ntttTime : ?b); scanf(%f,&(car_D.time); do Pop(&S,&car_M); if(car_D.label!=car_M.label) Push2(&S2,car_M); else car_I.time=car_M.time; while(car_D.label!=car_M.label); while(!StackEmpty2(S2) Pop2(&S2,&car_M); Push(&S,car_M); while(!QueueEmpty(Q)&!StackFull(S) if(!StackFull(S) DeQueue(&Q,&car_M); Push(&S,car_M); printf(The car %d just drived away ,nntthe car%d has entered the SOOSKY CAR POSITION .n,car_D.label,car_M.label); time=car_D.time-car_I.time; if(time0.00001&time3.0) money=time*2.0; else money=time*3.0; printf(nn); for(i=0;i80;i+) printf(-); printf(nt); printf(Your car number %d :tThe fee is :%5.2f,car_D.label,money); printf(nn); for(i=0;i80;i+) printf(-); printf(nn); printf(Welcome to back ! Do you want to continue 1-contine/0-quit ?b); scanf(%d,&ch); 4. 选做题（此题有时间的同学可以选择其中一题完成）（1）设计栈的9个基本操作函数；（2）设计队列的9个基本操作函数； 实验四、树和二叉树（4学时）1. 验证实验打开教材自带教学辅助光盘，进入光盘中的“DSDemoC”目录，运行DSDemo.EXE，进入数据结构算法演示系统（C语言描述）V3.1C中文版。具体操作请按照界面上的提示进行。分别选择主菜单中树子菜单下的各算法。首先仔细阅读算法，再输入数据，分步运行算法，检验自己对算法的理解是否正确。在实验报告中写出自己在演示算法过程中理解和实际运算的不同之处，并总结原因。2.设计实验（1）设计程序。要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：a.基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。b.用广义表表示所建二叉树。c.用凹入表表示所建二叉树。d.分别利用前序遍历、中序遍历、后序遍历所建二叉树。e.求二叉树结点总数，观察输出结果。f.求二叉树叶子总数，观察输出结果。g.交换各结点的左右子树，用广义表表示法显示新的二叉树。h.二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）。此二叉树需满足如下要求：叶结点的值为3；只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值；左、右孩子均有的结点，则其值等于左、右孩子结点的值之和；最后用广义表表示法显示所建二叉树。提示：可参考以下思路设计#include #include /二叉树的链式存储表示typedef char DataType;/应由用户定义DataType的实际类型typedef struct nodeDataType data;struct node *lchild, *rchild;/左右孩子指针 BinTNode;/结点类型typedef BinTNode *BinTree;void main()void ListBinTree(BinTree T);/用广义表表示二叉树void DisplayBinTree(BinTree T);/用凹入表表示二叉树void CreateBinTree(BinTree *T);/构造二叉链表void Preorder(BinTree T);/前序遍历二叉树void Inorder(BinTree T);/中序遍历二叉树void Postorder(BinTree T);/后序遍历二叉树int nodes(BinTree T);/计算总结点数int leafs(BinTree T);/计算总叶子数BinTree swap(BinTree T);/交换左右子树BinTree T;printf(请输入先序序列（虚结点用空格表示）：n);CreateBinTree(&T);ListBinTree(T);printf(n);DisplayBinTree(T);printf(前序遍历：n);Preorder(T);printf(n);printf(中序遍历：n);Inorder(T);printf(n);printf(后序遍历：n);Postorder(T);printf(n);printf(二叉树的总结点数为%dn,nodes(T);printf(二叉树的总叶子结点数为%dn,leafs(T);T=swap(T);ListBinTree(T);printf(n);/构造二叉链表void CreateBinTree(BinTree *T)/在此插入必要的语句/用广义表表示二叉树void ListBinTree(BinTree T)/在此插入必要的语句/用凹入表表示二叉树void DisplayBinTree(BinTree T)/在此插入必要的语句/前序遍历二叉树void Preorder(BinTree T)/在此插入必要的语句/中序遍历二叉树void Inorder(BinTree T)/在此插入必要的语句/后序遍历二叉树void Postorder(BinTree T)/在此插入必要的语句/计算总结点数int nodes(BinTree T)/在此插入必要的语句/计算总叶子数int leafs(BinTree T)/在此插入必要的语句/交换左右子树BinTree swap(BinTree T)/在此插入必要的语句实验五 图的应用（2学时）1 演示图的相关算法打开教材自带教学辅助光盘，进入光盘中的“DSDemoC”目录，运行DSDemo.EXE，进入数据结构算法演示系统（C语言描述）V3.1C中文版。具体操作请按照界面上的提示进行。选择主菜单中“图”下的各算法。首先仔细阅读算法，再输入数据，分步运行算法，检验自己对算法的理解是否正确。在实验报告中写出自己在演示算法过程中理解和实际运算的不同之处，并总结原因。2. 图的遍历应用阅读所给的源程序，在实验报告中写出该程序的功能和运行结果。（最好能写出每个子函数功能，以及重要语句的注释）程序如下：#include #define MAXQUEUE 70 struct node int vertex; struct node *nextnode; ;typedef struct node *graph; struct node head61; int visited61; int queueMAXQUEUE; int front = -1; int rear = -1; void creategraph(int *node,int num) gr