数据结构课程设计实验1-4(C语言).doc

《数据结构课程设计实验1-4(C语言).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一顺序表的操作1、实验目的和要求：1）了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并)。2)通过在visualC++实现以上操作的C语言代码。3）提前了解实验相关的知识（尤其是C语言）。2、实验内容：1)顺序表的插入算法,删除算法,顺序表的合并算法2)顺序表应用的实例（二选一）a)利用顺序表的基本运行，实现如果在顺序表A中出现的元素，在顺序表B中也出现，则在顺序表A中将该元素删除。及实现A-B。b)顺序表A和B的元素都是非递减排列，将他们合并成一个顺序表C，要求C也是非递减排列。3、部分参考实验代码：⑴顺序表结构的定义：

2、#include#defineListSize100typedefintDataType;typedefstruct{DataTypelist[ListSize];intlength;}SeqList;⑵顺序表插入（在第i号元素前插入一个新的元素）intInsertList(SeqList*L,inti,DataTypee)/*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/{intj;if(i<1

3、

4、i>L->length+1)/*在插入元素前，判断插入位置是否合法*/{printf("插入位置i不合法！

5、");return-1;}elseif(L->length>=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入元素*/{printf("顺序表已满，不能插入元素。");return0;}else{for(j=L->length;j>=i;j--)/*将第i个位置以后的元素依次后移*/L->list[j]=L->list[j-1];L->list[i-1]=e;/*插入元素到第i个位置*/L->length=L->length+1;/*将顺序表长增1*/return1;}}⑶顺序表删除intDeleteList(SeqList*L,inti,Da

6、taType*e){intj;if(L->length<=0){printf("顺序表已空不能进行删除!");return0;}elseif(i<1

7、

8、i>L->length){printf("删除位置不合适!");return-1;}else{*e=L->list[i-1];for(j=i;j<=L->length-1;j++)L->list[j-1]=L->list[j];L->length=L->length-1;return1;}实验二单链表的操作1、实验目的1）掌握用VisualC++6.0上机调试单链表的基本方法2）理解链表的基本操作、了解链表的建立

9、和输出3）掌握链表的插入、删除、合并和归并等实现方法2、实现内容1、单链表基本操作的实现2、链表应用的实例（二选一）a)利用链表的基本运行，实现如果在链表A中出现的元素，在链表B中也出现，则在链表A中将该元素删除。b)、约瑟夫（Josephus）问题的求解（循环链表的使用，使用C和C++语言均可）。假设有编号为1，2，……，n的n个人围坐成一圈，约定从编号为k（n>=k>=1）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。1、给定一个8个人的圈（n=8），约定从第3个人

10、开始报数（k＝3），数到第4个人时的那个人出列（m＝4），使用循环链表，产生一个出队编号的序列。2、参考的出队序列为：<62743518>。3、部分参考实验代码：1、结点定义typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}ListNode,*LinkList;2、单链表初始化voidInitList(LinkList*head)/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/{if((*head=(LinkList)malloc(sizeof(ListNode

11、)))==NULL)/*为头结点分配一个存储空间*/exit(-1);(*head)->next=NULL;/*将单链表的头结点指针域置为空*/}ListNode*Get(LinkListhead,inti)/*查找单链表中第i个结点。查找成功返回该结点的指针表示成功；否则返回NULL表示失败。*/{ListNode*p;intj;if(ListEmpty(head))/*在查找第i个元素之前，判断链表是否为空*/returnNULL;if(i<1)/*在查找第i个元素之前，判断该序号是否合法*/returnNULL;j=0;p=head