《实验一 线性表基本操作》由会员分享，可在线阅读，更多相关《实验一 线性表基本操作（11页珍藏版）》请在金锄头文库上搜索。
1、实验一 线性表基本操作 （4课时）一、实验目的掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求1. 格式正确，语句采用缩进格式； 2. 设计子函数实现题目要求的功能；3. 编译、连接通过，熟练使用命令键；4. 运行结果正确，输入输出有提示，格式美观。5. 输入数据至少三组，分别代表不同的情况，以测试程序的正确性。6. 将运行结果截图，并粘在文档的相应位置。三、实验环境1. turboc2,win-tc,VC+四、实验内容和步骤1. 编程实现在顺序存储的有序表中插入一个元素。2. 编程实现把顺序表中从i个元素开始的k个元素删除。3. 编程序实现将单链表的
2、数据逆置，即将原表的数据（a1,a2.an）变成(an,.a2,a1)。4约瑟夫环问题。约瑟夫问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。 利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，
3、7，2，3，5。五、根据实验过程填写下面内容1写出第1题的程序并写出运行结果和分析。#include stdio.h#include malloc.h#define OK 1#define ERROR 0 #define ElemType int#define MAXSIZE 100typedef struct/顺序表申明ElemType elemMAXSIZE;int last;SeqList;SeqList * InitList(int r)/初始化顺序表 输入顺序表的元素SeqList *l;int i,j,temp;l=(SeqList*)malloc(sizeof(SeqList);
4、l-last = r-1;printf(请输入线性表的各元素值:n);for(i=0; ilast; i+)scanf(%d,&l-elemi);for(i=0;ilast;i+)/排序for(j=0;jlast-i;j+)if(l-elemjl-elemj+1)temp=l-elemj;l-elemj=l-elemj+1;l-elemj+1=temp;return(l);SeqList * InsList (SeqList *L,ElemType e)/插入元素int K,i,j;if(L-last=MAXSIZE-1)printf(表已满无法插入);return(ERROR);for(K=
5、0;Klast;K+)if(eelemK)i=K;break;for(j=L-last;j=i;j-)L-elemj+1=L-elemj;L-elemi=e;L-last+;return (L);void show(SeqList *L)/显示顺序表int i;for(i=0;ilast;i+)printf(%d ,L-elemi);void main()/主函数int e,r;SeqList *p,*p1;printf(请输入线性表的长度:);scanf(%d,&r);p=InitList(r);printf(请输入插入的元素：);scanf(%d,&e);p1=InsList(p,e);s
6、how(p1);运行结果：分析：该程序一共有三个子函数：InitList(int r)初始化顺序表、InsList (SeqList *L,ElemType e)插入元素、show(SeqList *L)显示顺序表。主函数先得到数序表的长度r，把r传给初始化函数，经输入和排序得到一个顺序表，返回表的收地址L。输入一个待插入数e，再调用插入函数把它插入到该顺序表中（先用for循环通过比较找到该插入的位置，在用for循环把后面的元素都向后移一位，再把e插入，最后last+），返回首地址L。最后在调用显示函数，输出插入后的顺序表2写出第2题的程序并写出运行结果和分析。#include stdio.h
7、#include malloc.h#define ERROR 0#define MAXSIZE 100#define ElemType inttypedef structElemType elemMAXSIZE;int last;SeqList;SeqList * InitList(int r)/初始化顺序表 输入顺序表的元素SeqList *l;int i,j,temp;l=(SeqList*)malloc(sizeof(SeqList);l-last = r-1;printf(请输入线性表的各元素值:n);for(i=0; ilast; i+)scanf(%d,&l-elemi);for(
8、i=0;ilast;i+)/排序for(j=0;jlast-i;j+)if(l-elemjl-elemj+1)temp=l-elemj;l-elemj=l-elemj+1;l-elemj+1=temp;return(l);SeqList * DelList(SeqList *l,int i,ElemType a,int k)/删除int j,p;if(il-last+1)printf(删除位置不合法);return (ERROR);for(j=i,p=0;ji+k,pelemj-1;for(j=i;jlast;j+)l-elemj-1=l-elemj+k-1;l-last=l-last-k;r
9、eturn (l);void show(SeqList *L)/显示顺序表int i;for(i=0;ilast;i+)printf(%d ,L-elemi);void main()/主函数int a100,r,i,k;SeqList *p,*p1;printf(请输入线性表的长度:);scanf(%d,&r);p=InitList(r);printf(请输入从哪开始删除：);scanf(%d,&i);printf(请输入删除的位数：);scanf(%d,&k);p1= DelList(p,i,a,k);show(p1);运行结果：分析：该函数有三个子函数：InitList(int r)初始化
10、顺序表、DelList (SeqList *L,int i,ElemType a,int k)删除元素、show(SeqList *L)显示顺序表。主函数先得到数序表的长度r，把r传给初始化函数，经输入和排序得到一个顺序表，返回表的收地址L。输入要删除的首位置i和删除的位数k，再调用删除函数把该顺序表中的相应元素删掉（先用for循环删除这k个元素，在用for循环把后面的元素向前移，最后last-k），返回首地址L。最后在调用显示函数，输出插入后的顺序表3写出第3题的程序并写出运行结果和分析。#includestdio.h#includemalloc.htypedef struct nodein
11、t data;struct node *next;link;link *creat(int n)/创建link *head,*p,*s;int i;p=head=(link*)malloc(sizeof(link);for(i=1;idata);p-next=s;p=s;p-next=NULL;return(head);void reverse(link *head )/置换link *p,*s,*t;p=head;s=p-next;t=s-next;while(s-next!=NULL)t=s-next;s-next=p;p=s;s=t;s-next=p;p=s;head-next-next
12、=NULL;head-next=p;void display(link *head)/显示link *p;p=head-next;while(p!=NULL)printf(%d,p-data);p=p-next;printf(n);void main()link *head;int r;printf(请输入链表的长度：);scanf(%d,&r);head=creat(r);printf(原链表：n);display(head);reverse(head);printf(置换后的链表：n);display(head);运行结果：分析：该函数有三个子函数：creat(int n)创建链表、reverse(link *head )逆置链表、display(link *head)显示链表。主函数先得到链表的长度r，把r传给创建函数，经输入得到一个链表，返回表的首地址head。再调用逆置函数实现链表逆置（用三个指针完成操作，把后一个的指针域指向前一个结点，到最后一个时，把头结点head指向最后一个结点），返回首地址head。最后在调用显示函
