数据结构实验.doc

数据结构与算法（C语言描述）实验指导书 谢颂华 编武汉理工大学物理科学与技术系光电专业教研室二一年四月前 言数据结构与算法是电子信息科学与技术专业的一门学科基础课，也是一门本科生必修课。在计算机科学的各领域中，都会或多或少的用到数据结构的相关知识，学好数据结构这门课程，对从事计算机技术、电子技术及相关领域的工作人员来说是非常重要。数据结构与算法主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。数据结构与算法是一门理论和实践相结合的课程，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。目 录实验一 线性表的基本操作1实验二 栈和队列及其应用3实验三 二叉树的基本操作5实验四 内部排序的基本操作7附录：数据结构与算法实验报告格式9 参考答案 10 3实验一 线性表的基本操作【实验目的】1. 熟悉C语言的上机环境，进一步掌握C语言的结构特点。2. 掌握线性表（顺序表和链表）的顺序和链式存储结构的定义及C语言的实现。3. 掌握线性表（顺序表和链表）的建立、插入、删除、查找等基本操作。【实验内容】1. 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：(1) 从键盘输入10个整数，产生顺序表，并输入结点值。(2) 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。(3) 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。(4) 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。2. 报数问题：编号为1，2，n的n个人围坐在一圆桌旁，每人持有一个正整数的编号。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，则退席的人的编号依次为6，1，7，5，3，2，4。【实验安排】由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。建议课时安排如下：课外 6学时 ，课内2学时【实验提示】1. 采用C语言的数组类型实现线性表的顺序存储，用C语言的结构体类型定义顺序表结点：、#define ListSize 100/表空间大小可根据实际需要而定，假设为100typedef int DataType;/DataType可以是任何相应的数据类型如int, float或chartypedef structDataType dataListSize;/向量data用于存放表结点int length;/当前的表长度SeqList;2. 为了方便调试及编程，可以分析题目，将整个实验分解成若干个小的函数，最后由主函数分别调用子函数即可，建议编写下列子函数： CreateList / 建立顺序表函数 PrintList / 输出顺序表函数 GetLenList / 顺序表长度函数 LocateList /顺序表的查找 InsertList / 在顺序表中插入结点函数 DeleteList / 在顺序表删除结点函数 如：/顺序表的建立：void CreateList(SeqList *L,int n)int i;for (i=0;idata=ch;CreateBinTree(&(*T)-lchild );/*构造左子树 */CreateBinTree(&(*T)-rchild );/*构造右子树 */3. huffman树的构造方法(1) 给定w1,w2,.,wn, 构成F=T1,T2,.,Tn, 每个树只有一个根结点;(2) 选择两个根结点最小的二叉树,作为lchild和rchild, 构成一新的二叉树;, 直至一棵树止。4. huffman树的存储结构 typedef struct int weight;int parent, lchild, rchild; HTNode ,*HuffmanTree; / 动态分配数组存储huffman树实验四 内部排序的基本操作【实验目的】1. 掌握排序的有关概念和特点。2. 熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。3. 关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。4. 了解各种排序方法的优缺点和适用范围。【实验内容】1. 从键盘输入上述8个整数，存放在数组quick8中，并输出值。2. 输出各种排序算法每一趟排序的结果，观察关键字次序的变化。3. 如果上述8个整数按照升序输入，即k1= 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 ，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。4. 如果上述8个整数按照降序输入，即k2= 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。5. 测试各排序算法的执行时间，比较执行效率。6. 随机产生3万个数，对其进行排序，观察其结果。【实验安排】建议课时安排如下：课外 2学时 ，课内2学时【实验提示】1. 采用C语言的定义记录类型的存储结构：typedef int InfoType;#define n 10/假设的文件长度，即待排序的记录数目typedef int KeyType;/假设的关键字类型typedef struct /记录类型KeyType key;/关键字项InfoType otherinfo;/其它数据项，类型InfoType依赖于具体应用而定义 RecType;typedef RecType SeqListn+1;/SeqList为顺序表类型，表中第0个单元一般用作哨兵 2. 注意哨兵的作用。附录：数据结构与算法实验报告格式1 实验目的2 实验内容3 实验对应算法的描述（解题思路）4 源程序5 程序运行结果6 调试和运行程序过程中产生的问题及采取的措施7 实验心得体会/*第一次试验*/第一个实验#include#define size 12#define OK 1#define OVERFLOW 0 struct Listint datasize;/向量data用于存放表结点int length;/当前的表长度list; /*输入函数*/int input()int i;for(i=0;i10;i+)printf(List.data%d=:,i+1);scanf(%d,&list.datai);list.length+;return OK;/*输出函数*/int output()int i;if(list.length=0) exit(0);for(i=0;ilist.length;i+)printf(%d,i+1);printf(n);for(i=0;ilist.length;i+)printf(%d,list.datai);return OK;/*查找函数*/int search()int tt,flag=0,i;printf(please input a num to be found:);scanf(%d,&tt);for(i=0;iaa;i-)/printf(%d,list.datai);list.datai-1=list.datai-2;list.datai-1=bb;return OK;/*删除函数*/int delete_fun()int aa,i;if(list.length=0) return 0;printf(please input the location to be deleted:);scanf(%d,&aa);/printf(%dn,list.length);/printf(%dn,list.data0);for(i=aa;ilist.length;i+)list.datai-1=list.datai;list.length-;return OK;void main()/int i;/list.length=10;/for(i=0;i10;i+) list.datai=i+1;input();output();search();insert();output();delete_fun();output();第二个实验#include#define size 100 /* 输入人数的上限 */void main() int personsize; int i, j; /* 循环修正变量 */ int arrayLen; /* 数组长度 */ int start, overNum; /* 开始位置各跨过位置 */ int deleNum; /* 出列人所在数组中的下标 */ int name, total; /* 输入时,人的信息以及人的总数 */ printf( 请输入圆桌上人的总数: ); scanf( %d, &arrayLen ); printf( n ); if( ( arrayLen size ) | ( arrayLen 0 ) ) printf( 超出范围,请重新输入: ); scanf( %d, &arrayLen ); printf( n ); for( i = 0; i arrayLen; i+ ) personi = i+1; printf(请输入开始号: ); scanf( %d, &start ); start = start - 1; printf( 请输入间隔: ); scanf( %d, &overNum ); total = arrayLen; printf( 出列人的顺序为:n ); for( i = 0; i , persondeleNum ); for ( j = deleNum; j arrayLen; j+ ) personj = personj+1; start = deleNum; arrayLen = arrayLen - 1; printf( nn );/*第二次试验*/2.1#include#include#includewindows.h#include #define MAX 200typedef struct int base; int top; int stMAX; SqStack;InitStack(SqStack *s,int aa)int i;(*s).base=0;(*s).top=0;for(i=1;i=aa;i+)(*s).st(*s).top=i;(*s).top+;printf(initiate succeeded!n);Push(SqStack *s,int i)if(*s).top200)(*s).st(*s).top=i;(*s).top+;elseprintf(full already!);Pop(SqStack *s,int *p)if(!(*s).top)printf(stack is empty!);else*p=(*s).st(*s).top-1; (*s).top-;printf(%dn,*p);Traverse(SqStack *s)int i;if(!(*s).top)printf(stack is empty!);elsefor(i=0;i(*s).top;i+)printf(%d,(*s).sti);Getlen(SqStack *s)printf(length of stack is %dn,(*s).top);main()int x;int num1,num2;int nn;SqStack l;printf(*options*n);printf(1.initiate2.push3.pop n);printf(4.getlen5.traverse6.exit n);printf(choose :);scanf(%d,&nn);while(1)printf(choose :);scanf(%d,&nn);switch(nn)case 1:printf(input num:);scanf(%d,&num1);InitStack(&l,num1);system(pause);break;case 2:printf(input element:);scanf(%d,&num2);Push(&l,num2);system(pause);break;case 3:printf(pop a num:);Pop(&l,&x);printf(the num is:%d,x);system(pause);break;case 4:Getlen(&l);/printf(the length is:%d,)system(pause);break;case 5:printf(traverse stack:);Traverse(&l);system(pause);break;case 6: exit(0);2.2#include#include#includewindows.h#include #define MAX 30typedef struct int baseMAX; int front; int rear; SqQueue;InitQueue(SqQueue *Q)(*Q).front=0;(*Q).rear=0;printf(initiate succeed!n);EnQueue(SqQueue *Q,int i)if(Q-rear+1)%MAX=Q-front)printf(full !);elseQ-baseQ-rear=i;Q-rear=(Q-rear+1)%MAX;DeQueue(SqQueue *Q,int *x)if(Q-front=Q-rear)printf(empty !);else*x=Q-baseQ-front; /临时存放在x中Q-front=(Q-front+1)%MAX; /将下一个元素给front作为首元素/printf(Delete element :%dn,*x);Traverse(SqQueue *Q)int i,j,k;if(Q-front=Q-rear)printf(empty !);elsej=(Q-rear-Q-front+MAX)%MAX; /避免出现问题i=Q-front;for(k=0;kbasei);/遍历元素i=(i+1)%MAX; /i指向下一个元素printf(n);Getlen(SqQueue *Q)printf(length of queue is %dn,(Q-rear-Q-front+MAX)%MAX);main()int i,x;int num1;SqQueue q;printf(input the num in the cycle:n);scanf(%d,&num1);InitQueue(&q);for(i=1;i=num1;i+)EnQueue(&q,i);Traverse(&q); Getlen(&q);printf(delete the first element:n);DeQueue(&q,&x); Getlen(&q); Traverse(&q);2.3#include#include/*链队列的基本操作*/typedef struct QNodeint data; /数据struct QNode *next; /下一地址Qnode,*QueuePtr;typedef struct QueuePtr front;/队首指针QueuePtr rear;/队尾指针 LinkQueue;/*chushihua*/InitQueue(LinkQueue *q)q-front=(QueuePtr)malloc(sizeof(Qnode);q-rear=q-front;if(!q-front)printf(error!n);elseprintf(initiate succeed!n);q-front-next=NULL;/*c插入e元素为队尾*/EnQueue(LinkQueue *q,int e)QueuePtr p;p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(0);(*p).data=e; /存到开发的内存p中(*p).next=NULL; q-rear-next=p;q-rear=p; /建立连接到队尾DeQueue(LinkQueue *q,int *e)QueuePtr p;if(q-front=q-rear)printf(empty !n);p=q-front-next; /将第二个给p*e=p-data;/保留p中的数据q-front-next=p-next;if(q-rear=p)q-rear=q-front;free(p);printf(Deleted element is %d,*e);/*遍历*/Traverse(LinkQueue *q)QueuePtr p;if(q-front=q-rear)printf(empty !n);elsep=q-front-next;for(p;p!=q-rear;p=p-next)printf(%d ,p-data);printf(%d n,q-rear-data);Getlen(LinkQueue *q) QueuePtr p;int i=0;if(q-front=q-rear)printf(empty ！n);elsep=q-front-next;for(p;p!=q-rear;p=p-next)i+; i=i+1; /保证最后一个可以算进来printf(the length of queue is %dn,i);main()int i,x;int num1,nn,num2;LinkQueue Q;printf(*options*n);printf(1.initiate2.add3.delete n);printf(4.getlen5.traverse6.exit n);printf(choose :);scanf(%d,&nn);while(1)printf(choose :);scanf(%d,&nn);switch(nn)case 1:/printf(input num:);/scanf(%d,&num1);InitQueue(&Q);system(pause);break;case 2:printf(input element:);scanf(%d,&num2);EnQueue(&Q,num2);system(pause);break;case 3:/printf(delete the 1st num:);DeQueue(&Q,&x);/printf(the num is:%d,x);system(pause);break;case 4:Getlen(&Q);/printf(the length is:%d,)system(pause);break;case 5:printf(traverse stack:);Traverse(&Q);system(pause);break;case 6: exit(0);/*windows(cls);*/*第三次试验*/3.1/*/ * Description:先序创建二叉树,遍历等操作#include stdio.h#includeint count3=0,count4=0;typedef int DataType;/应由用户定义DataType的实际类型typedef struct nodeDataType data;struct node *lchild, *rchild;/左右孩子指针 BiTNode,*BiTree;/结点类型/typedef BiTNode ;/BiTree T;int nn=0;/全局变量nnBiTree CreateBiTree()/char cc;BiTree T;printf(input node:);scanf(%c,&cc);getchar(); /必须加上这句话!if(cc= ) T=NULL;else/flag+;if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0);/if(flag=1)treep=T;T-data=cc;nn+;/p