【数据结构】-线性表-双向循环链表-1328:链表的基本操作【好题
算法2-18~2-19:双向循环链表题目描述双向链表是在结点中既保存了后一个结点指针又保存了前一个结点指针的链表。这种链表较单向链表而言能够快速查找某一结点的前后结点。下面给出双向链表的定义、插入以及删除算法描述。 输入输入数据只有一组,包含很多行。每行有1~3个整数。第一个整数如果是0,则表示输出双向链表中的所有元素;第一个整数如果是1,表示插入1个整数,其后跟2个整数i、e代表在第i个位置插入e;第一个整数如果是2,表示删除1个整数,其后跟1个整数i,表示删除的位置为i。 输出当需要输出双向链表中的所有元素时输出,每次输出一行。整数间用一个空格隔开。 样例输入1 1 2 样例输出2 提示:1、如果使用switch,注意每个case后面使用break。 2、结构体定义时,因为定义里面有用到这个类型的指针,所以需要在开始struct后面写上结构体名。 3、注意循环链表全部遍历结束的条件是遍历的指针是否又指向了头结点。 总结: 1、双向链表的重要之处在于插入和删除时的操作顺序,切勿弄乱顺序而丢失数据。 2、循环链表全部遍历的结束条件需要注意,不是非空,而是判断是否到头结点了。 本题考查的是双向循环链表,所以上述都需要注意。 #include<stdio.h>
#include<stdlib.h>
typedef struct DLNode
{
int data;
struct DLNode *next;
struct DLNode *prior;
} DNLode;
void createDLNode(DLNode *&L)
{
L = (DLNode *)malloc(sizeof(DLNode));
L->prior = L;
L->next = L;
}
void printDLNode(DLNode *L)
{
DLNode *q;
q=L->next;
int i=0;
while(q!=L)// 如果q=L 则是循环完一遍链表了
{
if(i++)//good idea!
{
putchar(' ');
}
printf("%d",q->data);
q=q->next;
}
printf("n");
}
void insertDLNode(DLNode *&L,int i,int e)
{
DLNode *q,*qlen;
q=L;
qlen=L->next;
int num=0;
while(qlen!=L)//求出长度
{
num++;
qlen=qlen->next;
}
int j=1;
while(j<i)///不是j<i-1 :查找
{
j++;
q=q->next;
}
if(i>num+1||i<1)//越界
return ;
DLNode *s;
s=(DLNode *)malloc (sizeof(DLNode));
s->data = e;
s->next = q->next;
s->prior = q;
q->next = s;
q->next->prior = s;
return ;
}
void deleteDLNode (DLNode *&L,int i)
{
DLNode *q,*qlen;
qlen=L->next;
q=L;
int num=0;
while(qlen!=L)
{
qlen=qlen->next;
num++;
}
if(i<1||i>num)//越界
{
return ;
}
int j=0;
while(j<i-1)
{
q=q->next;
j++;
}
DLNode *qfree;
qfree= q->next;
q->next=qfree->next;
qfree->next->prior=q;
free(qfree);
}
int main (void)
{
int n;
DNLode *L;
createDLNode(L);
while(~scanf("%d",&n))
{
switch(n)
{
case 0:
{
printDLNode(L);
break;
}
case 1:
{
int i,e;
scanf("%d%d",&i,&e);
insertDLNode(L,i,e);
// printDLNode(L);
break;
}
case 2:
{
int i;
scanf("%d",&i);
deleteDLNode(L,i);
// printDLNode(L);
break;
}
default:
break;
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |