数据结构与算法D实验指导书.doc

《数据结构与算法D》实验指导书 武汉理工大学教材中心 2009年7月 实验一 线形链表的运算 一、实验目的 掌握线性表在顺序分配下的插入与删除运算。 二、实验原理 线性表是数据元素的有限序列，在日常生活中有很多相关的例子，如 1、人民币面值构成线性表 2、一年由4个季节构成 3、一个n维向量x=(x1,x2,x3,……,xn)。 线性表的结构特点是：数据元素之间是线性关系，即在线性表中必存在唯一的一个“第 一个”元素，必存在唯一的一个“最后一个”元素；除第一个元素外，每一个元素有且只有一个前趋元素；除最后一个元素外，每个元素有且只有一个后续元素。 若线性表中的数据元素之间可比较，则称该线性表为有序表，否则称为无序表。 三、实验内容 编写程序完成单链表的下列基本操作： (1) 建立一个长度为n的单链表。 (2) 插入新结点。 (3) 删除某一个结点。 (4) 打印输出La中的结点元素值。 四、实验方法 1、数据产生 通过随机数函数获得数据，或通过赋值方法确定数据。 2、线性表的插入与删除 线性表在本次实验中是动态变化，插入、删除元素，为使线性表任保持有序性，必须要找到元素插入或删除的位置。 插入算法： Insert_Link(LinkList * L,int i,datatype e) { LinkList *p,*s; int j; s=(LinkList *)malloc(sizeof(Lnode)); s-data=e; s-next=NULL; p=L; j=0; while(p!=NULL ji-1) { p=p-next; ++j;/*寻找第i-1个结点*/ } if(!p||ji-1) return ERROR; s-next=p-next; p-next=s; return OK; } 删除算法 Delete_Link(LinkList *L,int i,datatype e) { LinkList *p,*q; int j; p=L; j=0; while(p-next ji-1) { p=p-next; ++j; } if(!p-next||ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK; } 五、实验步骤和要求 1、确定构成线性表的数据； 2、根据给出算法编制程序，调试通过； 3、运行程序，检查程序是否完成实验内容中的要求。 六、实验报告要求 1、原理说明； 2、算法说明； 3、程序清单。 七、思考题 比较指针和数组实现线性表的插入、删除的异同。 实验二 堆栈/队列结构及运算 一、实验目的 用循环队列的链式结构求解约瑟夫问题。 二、实验原理 队是一种特殊的线性表，它只允许在一端进行插入，在另一端进行删除，允许插入的一端称为队尾，通常用一个队尾指示器指向队尾元素；允许删除的一端称为排头，用一个排头指示器指向排头元素。在队列中，最先插入的元素将最先删除，因此又称队为先进先出线性表。 从存储结构看，队分为顺序队与链队两种。 顺序队用一维数组连续存放队列元素，容量固定；链队的容量无法预先估计，可动态变化。在链队中我们设一个头结点，头指针始终指向头结点，尾指针指向队尾元素。 三、实验内容： n个人围坐在圆桌周围，从某个人开始编号为1，2，3，4,…,n，编号为1的位置上的人从1开始报数，数到m的人出列，从下一个人又从1开始报数，数到m的人便是第二个出列的人。如此重复下去，直到最后一个人出列为止。 四、实验方法： 1、初始化循环单链表 void init_linklist(LinkList *L)/*循环单链表进行初始化*/ { (*L)=(POINTER)malloc(sizeof(struct LNode)); (*L)-data=-1; (*L)-next=(*L); } 2、 入队操作算法 Inert_sque(LinkList * L) {int num; /*插入队列的结点值*/ LinkList p; while(num!=XX)