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
#include
#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
#include
#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
#include
#include
#defineElemTypeint
typedefstructNode
{
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;inext){
pindex=pi;
for(pj=pi->next,j=i+1;jnext)
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{
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("输入参加约瑟夫环的人数:
");
scanf("%d",&n);
printf("输入初始密码:
");
scanf("%d",&m);
printf("用尾插法建立约瑟夫环,请输入链表数据!
\n");
CreateFromTail(l,n);
p=l->next;
printf("约瑟夫环的人数以及对应密码分别是:
\n");
for(i=1;i<=n;i++)
{
printf("第%d个人,密码%d\n",p->index,p->data);
p=p->next;
}
GetJoseph(l,n,m);
}
本次实验小结: