数据结构实验一 线性表基本操作

实验一线性表基本操作一、实验目的掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求包含有头文件和main函数；格式正确，语句采用缩进格式；设计子函数实现题目要求的功能；编译、连接通过，熟练使用命令键；运行结果正确，输入输出有提示，格式美观。三、实验设备、材料和工具奔腾2计算机或以上机型turboc2,win-tc四、实验内容和步骤实验内容：分析程序。用头插入法建立带头结点的单链表用尾插入法建立带头结点的单链表单链表就地逆置约瑟夫问题步骤：确定数据的结构；利用main函数调用各子函数；调试、分析运行结果。五、实验报告要求根据实验内容初步设计好程序，并从理论上排除错误；针对程序的健壮性准备好测试数据；结果分析中如实填写运行后的结果，记录调试过程中产生的重要问题和解决方法。六、根据实验过程填写下面内容基础部分1．请认真阅读理解，上机运行并分析结果。#include"seqlist.h"#include<stdio.h>main(){SeqLista;inti,m,x;printf("请输入顺序表元素，从小到大排列，元素为整型量，用空格分开，-99为结束标志：\n");a.last=0;i=0;scanf("%d",&i);while(i!=-99){a.elem[a.last]=i;a.last++;scanf("%d",&i);}a.last--;scanf("%d",&x);for(i=0;i<=a.last;i++)printf("%4d",a.elem[i]);printf("\n");i=a.last;while((i>=0)&&(x<a.elem[i]))i--;for(m=a.last;m>=i+1;m--)a.elem[m+1]=a.elem[m];a.elem[i+1]=x;a.last++;for(i=0;i<=a.last;i++)printf("%4d",a.elem[i]);printf("\n");}结果：以上程序的功能是什么？功能是在顺序表中顺序插入一个数。（已修改无法插入于第一个数之前的错误）2．下面的程序实现用头插法建立带头结点的单链表，请补充完整程序。#include<stdio.h>#include<stdlib.h>#defineElemTypechar#defineLENsizeof(structNode)typedefstructNode/*结点类型定义*/{ ElemTypedata; structNode*next;}Node,*LinkList;/*LinkList为结构指针类型*/voidCreateFromHead(LinkListL){ intc; Node*pnew; printf("请输入char类型数据，（以*结束）"); while(1) { pnew=(Node*)malloc(LEN); scanf("%c",&pnew->data); if(pnew->data=='*') break; pnew->next=L->next; L->next=pnew; } pnew->next=NULL; returnL;}voidmain(){ LinkListl; Node*p; printf("用头插法建立单链表,请输入链表数据,以*结束!\n"); l=(LinkList)malloc(sizeof(Node)); l->next=NULL; CreateFromHead(l); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; }}思考：建立循环单链表修改头插法建表算法的那些语句可以完成？思考结果： pnew->next=NULL;修改这句就可以了。改成pnew->next=L;3．下面的程序实现用尾插法建立带头结点的单链表，请补充完整程序。#include<stdio.h>#include<stdlib.h>#defineElemTypechar#defineLENsizeof(structNode)typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;voidinit_linklist(LinkList*l);voidCreateFromTail(LinkListL);voidinit_linklist(LinkList*l)/*对单链表进行初始化*/{ *l=(LinkList)malloc(LEN); (*l)->next=NULL;}voidCreateFromTail(LinkListL){ Node*pnew,*ptail; ptail=L; printf("请输入char类型数据，（以*结束）"); pnew=(Node*)malloc(LEN); scanf("%c",&pnew->data); for(;pnew->data!='*';) { ptail->next=pnew; ptail=pnew; pnew=(Node*)malloc(LEN); scanf("%c",&pnew->data); } ptail->next=NULL; returnL;}voidmain(){ LinkListl; Node*p; init_linklist(&l); printf("用尾插法建立单链表,请输入链表数据,以*结束!\n"); CreateFromTail(l); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; }}思考：建立循环单链表修改尾插法建表算法的那些语句可以完成？思考结果： ptail->next=NULL;ptail->next不赋值NULL，改赋值为头节点地址提高部分4.已知一个带头结点的单链表L，设计算法实现：以表中第一个元素作为标准，将单链表中所有值小于第一个元素的结点均放在第一个元素结点之前，所有值大于第一个元素的结点均放在第一个元素结点之后（排除后续结点和第一个元素结点值相等的情况），补充完整程序并调试运行#include<stdio.h>#include<stdlib.h>#include<MEMORY.H>#defineElemTypeinttypedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;intn;LinkListCreateFromTail(){ LinkListL; Node*r,*s; intc; intflag=1; L=(Node*)malloc(sizeof(Node)); L->next=NULL; r=L; n=0; while(flag) { scanf("%d",&c); if(c!=-1) { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; n++; } else { flag=0; r->next=NULL; } } n++; returnL;}voidReverseList(LinkListL)//排除后续结点和首结点相等情况{ Node*pi,*pj,*pindex; Node*temp; intlen=sizeof(Node)-sizeof(Node*); inti,j; for(pi=L,i=0;i<n-1;i++,pi=pi->next){ pindex=pi; for(pj=pi->next,j=i+1;j<n;j++,pj=pj->next) if(pindex->data>pj->data) pindex=pj; memcpy(&temp,pi,len); memcpy(pi,pindex,len); memcpy(pindex,&temp,len); }}voidmain(){ LinkListl; Node*p; printf("请输入数据(-1结束):"); l=CreateFromTail(); printf("输入的单链表为:\n"); p=l->next; while(p!=NULL) { printf("%d\n",p->data); p=p->next; } ReverseList(l); printf("所有值小于第一个元素的结点均放在第一个元素结点之前\n所有值大于第一个元素的结点均放在第一个元素结点之后\n"); printf("得到的单链表为:\n"); p=l->next; while(p!=NULL) { printf("%d\n",p->data); p=p->next; }}5.P54实习题2，补充程序，完成调试和运行#include"common.h"#include"stdio.h"typedefstructJoseph/*结点类型定义*/{ intindex; intdata; structJoseph*next;}Joseph,*JosephList;voidinit_JosephList(JosephList*l)/*对单链表进行初始化*/{ *l=(JosephList)malloc(sizeof(Joseph)); (*l)->next=NULL;}voidCreateFromTail(JosephListL,intn){ Joseph*r,*s; intc; inti; r=L; for(i=1;i<=n;i++) { printf("第%d人,输入密码:\n",i); s=(Joseph*)malloc(sizeof(Joseph)); s->index=i; scanf("%d",&c); s->data=c; r->next=s; r=s; } r->next=L->next;//构成约瑟夫环，注意不是L}voidGetJoseph(JosephListl,intn,intm){ JosephListp,q;inti; p=l; for(;;) { for(i=0;i<m;i++) { q=p; p=p->next; } printf("出列的人是第%d个人，密码是%d\n",p->index,p->data); m=p->data; q->next=p->next; n--; if(n==0)break; }}voidmain(){ JosephListl; Joseph*p; intn,m,i; init_JosephList(&l); printf("输入参加约瑟夫环的人数