实验一 线性表基本操作

实验一线性表基本操作（4课时）一、实验目的掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求1.格式正确，语句采用缩进格式；2.设计子函数实现题目要求的功能；3.编译、连接通过，熟练使用命令键；4.运行结果正确，输入输出有提示，格式美观。5.输入数据至少三组，分别代表不同的情况，以测试程序的正确性。6.将运行结果截图，并粘在文档的相应位置。三、实验环境1.turboc2,win-tc,VC++四、实验内容和步骤1.编程实现在顺序存储的有序表中插入一个元素。2.编程实现把顺序表中从i个元素开始的k个元素删除。3.编程序实现将单链表的数据逆置，即将原表的数据（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，7，2，3，5。五、根据实验过程填写下面内容1．写出第1题的程序并写出运行结果和分析。#includestdio.h#includemalloc.h#defineOK1#defineERROR0#defineElemTypeint#defineMAXSIZE100typedefstruct//顺序表申明{ElemTypeelem[MAXSIZE];intlast;}SeqList;SeqList*InitList(intr)//初始化顺序表输入顺序表的元素{SeqList*l;inti,j,temp;l=(SeqList*)malloc(sizeof(SeqList));l-last=r-1;printf(请输入线性表的各元素值:\n);for(i=0;i=l-last;i++){scanf(%d,&l-elem[i]);}for(i=0;il-last;i++)//排序{for(j=0;jl-last-i;j++){if(l-elem[j]l-elem[j+1]){temp=l-elem[j];l-elem[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;KL-last;K++){if(e=L-elem[K]){i=K;break;}}for(j=L-last;j=i;j--){L-elem[j+1]=L-elem[j];}L-elem[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);}运行结果：分析：该程序一共有三个子函数：InitList(intr)初始化顺序表、InsList(SeqList*L,ElemTypee)插入元素、show(SeqList*L)显示顺序表。主函数先得到数序表的长度r，把r传给初始化函数，经输入和排序得到一个顺序表，返回表的收地址L。输入一个待插入数e，再调用插入函数把它插入到该顺序表中（先用for循环通过比较找到该插入的位置，在用for循环把后面的元素都向后移一位，再把e插入，最后last++），返回首地址L。最后在调用显示函数，输出插入后的顺序表2．写出第2题的程序并写出运行结果和分析。#includestdio.h#includemalloc.h#defineERROR0#defineMAXSIZE100#defineElemTypeinttypedefstruct{ElemTypeelem[MAXSIZE];intlast;}SeqList;SeqList*InitList(intr)//初始化顺序表输入顺序表的元素{SeqList*l;inti,j,temp;l=(SeqList*)malloc(sizeof(SeqList));l-last=r-1;printf(请输入线性表的各元素值:\n);for(i=0;i=l-last;i++){scanf(%d,&l-elem[i]);}for(i=0;il-last;i++)//排序{for(j=0;jl-last-i;j++){if(l-elem[j]l-elem[j+1]){temp=l-elem[j];l-elem[j]=l-elem[j+1];l-elem[j+1]=temp;}}}return(l);}SeqList*DelList(SeqList*l,inti,ElemTypea[],intk)//删除{intj,p;if((i1)||(il-last+1)){printf(删除位置不合法);return(ERROR);}for(j=i,p=0;ji+k,pk;j++,p++){a[p]=l-elem[j-1];}for(j=i;jl-last;j++){l-elem[j-1]=l-elem[j+k-1];}l-last=l-last-k;return(l);}voidshow(SeqList*L)//显示顺序表{inti;for(i=0;i=L-last;i++){printf(%d,L-elem[i]);}}voidmain()//主函数{inta[100],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(intr)初始化顺序表、DelList(SeqList*L,inti,ElemTypea[],intk)删除元素、show(SeqList*L)显示顺序表。主函数先得到数序表的长度r，把r传给初始化函数，经输入和排序得到一个顺序表，返回表的收地址L。输入要删除的首位置i和删除的位数k，再调用删除函数把该顺序表中的相应元素删掉（先用for循环删除这k个元素，在用for循环把后面的元素向前移，最后last-k），返回首地址L。最后在调用显示函数，输出插入后的顺序表3．写出第3题的程序并写出运行结果和分析。#includestdio.h#includemalloc.htypedefstructnode{intdata;structnode*next;}link;link*creat(intn)//创建{link*head,*p,*s;inti;p=head=(link*)malloc(sizeof(link));for(i=1;i=n;i++){printf(输入第%d个数据,i);s=(link*)malloc(sizeof(link));scanf(%d,&s-data);p-next=s;p=s;}p-next=NULL;return(head);}voidreverse(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=NULL;head-next=p;}voiddisplay(link*head)//显示{link*p;p=head-next;while(p!=NULL){printf(%d,p-data);p=p-next;}printf(\n);}voidmain(){link*head;intr;printf(请输入链表的长度：);scanf(%d,&r);head=creat(r);printf(原链表：\n);display(head);reverse(head);printf(置换后的链表：\n);display(head);}运行结果：分析：该函数有三个子函数：creat(intn)创建链表、reverse(link*head)逆置链表、display(link*head)显示链表。主函数先得到链表的长度r，把r传给创建函数，经输入得到一个链表，返回表的首地址head。再调用逆置函数实现链表逆置（用三个指针完成操作，把后一个的指针域指向前一个结点，到最后一个时，把头结点head指向最后一个结点），返回首地址head。最后在调用显示函数，输出逆置后的链表。4．写出实现题目要求的程序和运行结果，并分析正确性。#includestdio.h#includemalloc.h#defineOK1#defineERORR0typedefintElemType1;typedefintElemType2;typedefstructNode{ElemType1number;ElemType2password;structNode*next;}Node,*LinkList;intInitList(LinkListH,intn){Node*s,*t;inti;t=H;for(i=1;i=n;i++){s=(Node*)malloc(sizeof(Node));if(s==NULL){printf(申请空间失败);returnERORR;}s-number=i;printf(请输入第%d个人的密码：,i);scanf(%d,&s-password);t-next=s;t=s;}t-next=NULL;return(OK);}intJosephus(LinkListH,intm){intcount=0;Node*pre;//指向当前接点前一个接点Node*temp;//存放将要删除的接点pre=H;//p指向第一个接点while(H-next!=NULL)//表示已经没有接点了{count++;if(count==m){m=pre-next-password;printf(%4d,pre-next-number);/*将接点从连表里删除*/temp=pre-next;pre-next=temp-next;free(temp);count=0;if(pre-next==NULL)//如果m这个点刚好数到的是结尾那个接点的话{pre=H;}}else{if(pre-next-next==NULL){pre=H;}else{pre=pre-next;}}}printf(\n);returnOK;}voidmain(){intn,m;Node*H;H=(Node*)malloc(sizeof(Node));H-next=NULL;printf(请输入参加游戏的人数n和第一次的报数上限值m：);scanf(%d%d,&n,&m);if(!InitList(H,n)