Question

单链表、单循环链表和双向链表

对于单链表、单循环链表和双向链表,如果仅仅知道一个指向链表中某结点的指针p,能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断,若可以,写出程序段;不可以，说明理由。

Answer 1

1.单链表不行，因为单链表没有办法得到其前驱；
2. 单循环链表可以，假设链表的元素大于等于2：
struct Node
{
Node * next;
int data;
};

循环链表 Node * list;
Node *pnode = p;

while(pnode->next != p)
{
pnode = pnode->next;
}

//找到其前驱了
int tmp = pnode->data;
pnode->data = p->data;
p->data->tmp;

3.双向链表可以，假设链表的元素大于等于2，且p不为链表头。
struct Node
{
Node * next;
Node * pre;
int data;
}

双向链表list;
Node *pnode = p;
if(p->pre != NULL)
{
int tmp = p->data;
p->data = p->pre->data;
p->pre->data = tmp;
}

Answer 2

#include "stdio.h"
#include "stdlib.h"
#define ERROR 0
#define OK 0
typedef int Elemtype;
typedef int status;
typedef struct LNode{
Elemtype date;
struct LNode *next;
}LNode,*LinkList;
//建立链表
void CreateList(LinkList &L){
LinkList p;int i,n;
printf("请输入要建立链表的长度\n");
scanf("%d",&n);
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
for(i=n;i>0;--i){
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->date);
p->next=L->next;L->next=p;
}
}
//输出链表
void PrintList(LinkList L){
LinkList p;
for(p=L->next;p;p=p->next)
printf("%5d",p->date);
}
//在i位置插入元素e
status ListInsert(LinkList &L,int i,Elemtype e){
LinkList p,s;int j;
p=L;j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1)return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->date=e;s->next=p->next;
p->next=s;
return OK;
}
//删除第i个元素
status ListDelete(LinkList &L,int i,Elemtype &e){
LinkList p,q;int j;
p=L;j=0;
while(p->next&&j<i-1){p=p->next;++j;}
if(!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->date;free(q);
return OK;
}
void main(){
LinkList L;Elemtype e;int i,n;
CreateList(L);
PrintList(L);
printf("\n输入1则插入元素，输入2则删除元素\n");
scanf("%d",&n);
switch(n){
case 1:
printf("请输入要插入元素的位置");scanf("%d",&i);
printf("请输入要插入的元素");scanf("%d",&e);
ListInsert(L,i,e);
PrintList(L);break;
case 2:
printf("请输入要删除元素的位置");scanf("%d",&i);
ListDelete(L,i,e);
PrintList(L);}
}