实验一 线性表基本操作.doc

《实验一 线性表基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验一线性表基本操作（4课时）一、实验目的掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求1.格式正确，语句采用缩进格式；2.设计子函数实现题目要求的功能；3.编译、连接通过，熟练使用命令键；4.运行结果正确，输入输出有提示，格式美观。5.输入数据至少三组，分别代表不同的情况，以测试程序的正确性。6.将运行结果截图，并粘在文档的相应位置。三、实验环境1.turboc2,win-tc,VC++四、实验内容和步骤1.编程实现在顺序存储的有序表中插入一个元素。2.编程实现把顺序表中从i个元素开始

2、的k个元素删除。3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成(an,…..a2,a1)。4．约瑟夫环问题。约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印

3、出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。五、根据实验过程填写下面内容1．写出第1题的程序并写出运行结果和分析。#include"stdio.h"#include"malloc.h"#defineOK1#defineERROR0#defineElemTypeint#defineMAXSIZE100typedefstruct//顺序表申明{ElemTypeelem[MAXSIZE];intlast;}SeqList;SeqList*InitLis

4、t(intr)//初始化顺序表输入顺序表的元素{SeqList*l;inti,j,temp;l=(SeqList*)malloc(sizeof(SeqList));l->last=r-1;printf("请输入线性表的各元素值:");for(i=0;i<=l->last;i++){scanf("%d",&l->elem[i]);}for(i=0;ilast;i++)//排序{for(j=0;jlast-i;j++){if(l->elem[j]>l->elem[j+1]){temp=l->elem[j];l->e

5、lem[j]=l->elem[j+1];l->elem[j+1]=temp;}}}return(l);}SeqList*InsList(SeqList*L,ElemTypee)//插入元素{intK,i,j;if(L->last>=MAXSIZE-1){printf("表已满无法插入");return(ERROR);}for(K=0;Klast;K++){if(e<=L->elem[K]){i=K;break;}}for(j=L->last;j>=i;j--){L->elem[j+1]=L->elem[j];}L->ele

6、m[i]=e;L->last++;return(L);}voidshow(SeqList*L)//显示顺序表{inti;for(i=0;i<=L->last;i++){printf("%d",L->elem[i]);}}voidmain()//主函数{inte,r;SeqList*p,*p1;printf("请输入线性表的长度:");scanf("%d",&r);p=InitList(r);printf("请输入插入的元素：");scanf("%d",&e);p1=InsList(p,e);show(p1);}运行结果：分析：该程

7、序一共有三个子函数：InitList(intr)初始化顺序表、InsList(SeqList*L,ElemTypee)插入元素、show(SeqList*L)显示顺序表。主函数先得到数序表的长度r，把r传给初始化函数，经输入和排序得到一个顺序表，返回表的收地址L。输入一个待插入数e，再调用插入函数把它插入到该顺序表中（先用for循环通过比较找到该插入的位置，在用for循环把后面的元素都向后移一位，再把e插入，最后last++），返回首地址L。最后在调用显示函数，输出插入后的顺序表2．写出第2题的程序并写出运行结果和分析。#incl

8、ude"stdio.h"#include"malloc.h"#defineERROR0#defineMAXSIZE100#defineElemTypeinttypedefstruct{ElemTypeelem[MAXSIZE];intlast;}S