双链表插入元素

可以很肯定的告诉你：q->prev=p->next->prev是可以换成q->prev=p的！

p是一个指针，它里面存放的是该结点的地址；假设s是原来链表的中P的下一个结点，则s也是一个指针，里面存放的是该结点的地址，可知：s==p->next，则

s->prev==p->next->prev，因s->prev存放的是p结点的地址，也就是s->prev==p，所以p->next->prev==p。

其实道理很简单的，可以通过具体的程序来检验是否可换：

#include <iostream>

using namespace std

/*双向链表类型定义*/

typedef struct duNode

{

char data

struct duNode *prior

struct duNode *next

}duNode

typedef duNode *duLinklist//指针类型，故访问它的成员用“->”。

/*初始化双向链表*/

void initLinklist_Du(duLinklist &L)//此处叫做引用调用，即实参和形参共用一个地址。

{

L=new duNode

L->next=L

L->prior=L

}

/*取某个结点的位置*/

duNode *getElemP_D(duLinklist L,int i)

{

duNode *p

int count

p=L->next

count=1

while(p!=L&&count<i-1)

{

p=p->next

count++

}

if(p==L||count>i-1)

return NULL

else

return p->next

}

/*求双向链表的长度*/

int lengthLinklist_Du(duLinklist &L)

{

duNode *p

int count

p=L->next

count=0

while(p!=L)

{

p=p->next

count++

}

return count

}

/*在i之后插入元素*/

void insertList_Du(duLinklist &L,int i,char x)

{

duNode *p

duNode *q

p=getElemP_D(L,i)

if(p==NULL)

cout<<"Poision Error!"

q=new duNode

q->data=x

q->prior=p//在这里换成q->prior=p->next->prior，也是一样的。

q->next=p->next

p->next->prior=q

p->next=q

}

/*创建一个双向链表*/

void creatLinklist_Du(duLinklist &L,int n)

{

duNode *p

duNode *s

initLinklist_Du(L)

p=L

int i

for(i=0i<ni++)

{

s=new duNode

cin>>s->data

s->next=L

s->prior=p

p->next=s

L->prior=s

p=s

}

}

/*输出双向链表中的元素*/

void outputLinklist_Du(duLinklist &L)

{

duNode *p

p=L->next

int i

for(i=0i<lengthLinklist_Du(L)i++)

{

cout<<p->data<<" "

p=p->next

}

cout<<endl

}

void main()

{

duLinklist L

creatLinklist_Du(L,10)

insertList_Du(L,2,'a')

outputLinklist_Du(L)

}

呵呵，献丑了！

对于插入元素来说，最重要的是不要插入后丢了以前链表中的元素。只要保证插入后不丢元素，顺序你可以改的：

上面的题中，你找到了插入点并用指针P指向它，也就是到现在你只知道头指针和插入点的指针P，要在P所指向的结点之前插入元素，以前以前元素的信息都靠P来传达，所以要先修改新增结点中的信息，以使P以前的元素的信息不丢失，再来修改P的信息，可以：

1.s->next = p

2.s->prior = p->prior

3.p->prior->next = s

4.p->prior = s

可以用LinkedList代替你的AdditiveList

LinkedList<String>linklist=new LinkedList<String>()

String [] strs={"1","2","3","4"}

for (String string : strs) {

linklist.add(string)

}

System.out.println("链表的第一个元素是 : " + linklist.getFirst())

System.out.println("链表最后一个元素是 : " + linklist.getLast())

System.out.println("链表的长度 : " + linklist.size())

//然后你需要动态改变链表中的元素这时可以用ListIterator<E>迭代器来 *** 作链表

ListIterator<String>itr=linklist.listIterator()

while (itr.hasNext()) {

itr.next()//先正序将游标调至结尾

}

while (itr.hasPrevious()) {

String string = (String) itr.previous()//逆序遍历链表

System.out.println(string)

if("2".equals(string)){//在指定位置前插入元素

itr.add("0")//这里就是你需要插入的元素

itr.add("1")

}

}

System.out.println(linklist.toString())

---