软件课程设计数据结构.pdfVIP

四．数据结构

第二题

1.题目

假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知p为指向链表

中某结点的指针，试编写算法在链表中删除结点p的前趋结点。

2.需求分析

设计一个循环链表，没有头结点也无头指针，然后就可以任意删除一个结点的前驱结

点。此程序能删除输入一个元素的前驱结点。循环链表中的元素全部都是整数，这里用到结

构体structqueue,数据域中包括数据、queue型的前驱指针prior后继指针next，用户开

始可以随心所欲的初始化一个循环链表。

依据题目要求输入测试数据：

【输入数据】

3

111213

12

【输出数据】

111213

1213

3.概要设计

【step1】建一个结构体structqueue，他包括数据域date、前驱指针prior、后继指针next。

【step2】编写主要操作函数：建空循环链表jianqueue(queues)、删除结点函数dele(queue

s,inte)、插入函数push(queues,inte,intn)、输出函数queueprior(queue

s)。

【step3】编写主函数实现对各个函数的调用。来完成题目所要求的结果。

4.详细设计与编码

（1）流程图

主函数

用户输入初始化链表的元素个数

调用queueprior(queues)输出链表元素

连续调用插入函数push(queues,inte,intn)初始化链表

用户输入要操作的元素

调用dele(queues,inte)执行删除操作

调用queueprior(queues)再次输出链表元素

（2）源程序

#includeiostream

usingnamespacestd;

structqueue

{

intdata;

queue*prior;

queue*next;

};

voidjianqueue(queues)//构造空队

{

s.data=NULL;//第一个元素恒为0

s.prior=s;

s.next=s;

}

voiddele(queues,inte)//删除e元素的前驱结点

{

queue*p;

p=s.next;

while(p-next-data!=e)

p=p-next;

p-prior-next=p-next;

p-next-prior=p-prior;

deletep;

}

voidpush(queues,inte,intn)//在第n个位置插入元素e

{

queue*p;

p=newqueue;

queue*q;

q=s.next;

for(inti=1;in;q=q-next,i++);

p-data=e;

p-prior=q-prior;

q-prior-next=p;

p-next=q;

q-prior=p;

}

voidqueueprior(queues)//输出链表中的元素

{

queue*p;

p=s.next;

while(p-next!=s){{

p=p-next;

}

coutp-dataendl;

}

intmain()

{

queuea;

intb,c,m,i,j;

jianqueue(a);jianqueue(a);

请输入要初始化循环链表元素的