C++双向循环链表问题,表示很奇怪,不能理解!求助!

java_hh 发布于 2011/08/03 19:25
阅读 1K+
收藏 0

 

// Chain.cpp : 定义控制台应用程序的入口点。 
// 

#include "stdafx.h" 
#include "iostream" 
using namespace std; 
template <class T> 
class ChainNode 
{ 

public: 
    ChainNode(){} 
    ChainNode(T &t,ChainNode <T> * p,ChainNode <T> * n) 
    { 
        data=t; 
        prior=p; 
        next=n; 
    } 
//private: 
    T data; 
    ChainNode <T> * next;            //指向后结点的指针 
    ChainNode <T> * prior;            //指向前结点的指针 
}; 
template <class T> 
class Chain 
{ 
public: 
    Chain(){head=0;size=0;} 
    void creat()                                                                            //初始化链表
     {; 
        cout<<"请输入您要创建几个结点的链表: "; cin>>size; 
        ChainNode <T> * p; 
        for(int i=0;i<size;i++) 
        { 
            tail=new ChainNode <T> ; 
            cout<<"请输入第"<<i+1<<"个结点的数 "; cin>>tail->data; 
            if(head==0) 
            { 
                head=tail; 
                
            } 
            else 
            { 
                p->next=tail; 
                tail->prior=p; 
            } 
            p=tail; 
            tail->next=head; 
            
        } 
        head->prior=tail; 
    } 
    
    void print()                                //打印链表 
    { 
        ChainNode <T> *p=head->next; 
        int i=1; 
        cout<<" "<<i<<":     "<<head->data<<endl; 
        i++; 
        while(p!=head) 
        { 
            cout<<" "<<i<<":     "<<p->data<<endl; 
            p=p->next; 
            i++; 
        } 
    } 
    void insert()                                    //插入链表 
    { 
        T num; 
        int wh; 
        cout<<"请输入你要插入的数: ";cin>>num; 
        cout<<"请输入你要插入的位置: ";cin>>wh; 
        ChainNode <T> * p=new ChainNode<T>; 
        p->data=num; 
        if(wh<0 || wh>size)                        //判断插入的位置是否合法 
        { 
            cout<<"out of bound"<<endl; 
            exit(1); 
        } 
        if(wh==1 ||wh==size)                    //插入链表头跟尾 
        { 
            tail->next=p; 
            head->prior=p;; 
            p->next=head; 
            p->prior=tail; 
            if(wh==1) 
                head=p; 
            else 
                tail=p; 
        } 
        if(wh>1 && wh<size)                    //插中间 
        { 
            ChainNode <T> * h; 
            int i; 
            if(wh<=size/2)                        //判断插入的数位置是否为链表的前半段,是则从首结点向后遍历
             {   
                i=1; 
                h=head; 
                while(i<wh) 
                { 
                    h=h->next; 
                    i++; 
                } 
            } 
            else                            //否则从尾结点向前遍历 
            { 
                h=tail; 
                i=size; 
                while(i>wh) 
                { 
                    h=h->prior; 
                    i--; 
                } 
            
            } 
            h->prior->next=p;                //假如我删除有4个数以上的链表中的一个数,就会出错. 
            h->prior=p; 
            p->next=h; 
            p->prior=h->prior; 
            /*h->prior->next=p;            //将上面4行注释起来,用这四行就没有问题,但其实这两段 
            p->prior=h->prior;                //也只是调换顺序而已,表示很疑惑啊,因为我习惯插入用 
            p->next=h;                            //上面那段.....这到底是为什么啊~~~ 很奇怪. 
            h->prior=p;*/ 
            
            
        } 
        size++;                        //增加一个后链表长度加1 
            
    } 
    void del()                                //删除链表 
    { 
        int wh; 
        ChainNode <T> * p; 
        cout<<"请输入你要删除数的位置: ";cin>>wh; 
        if(wh<0 || wh>size)                            //判断删除的是否合法 
        { 
            cout<<"out of bound"<<endl; 
            exit(1); 
        } 
        if(wh==1)                        //删头 
        { 
            p=head; 
            tail->next=head->next; 
            head->next->prior=tail; 
            head=head->next; 
            delete p; 
        } 
        if(wh==size)                //删尾 
        { 
            p=tail; 
            tail->prior->next=head; 
            head->prior=tail->prior; 
            tail=tail->prior; 
            delete p; 
        } 
        if(wh>1 && wh<size)                    //删中间 
        { 
            ChainNode <T> * h; 
            int i; 
            if(wh<=size/2)                    //判断删除的是否为链表的前半段,是则从首结点向后遍历 
            {   
                i=1; 
                h=head; 
                while(i<wh) 
                { 
                    h=h->next; 
                    i++; 
                } 
            } 
            else                        //否则从尾结点向前遍历 
            { 
                h=tail; 
                i=size; 
                while(i>wh) 
                { 
                    h=h->prior; 
                    i--; 
                } 
            
            } 
            h->prior->next=h->next; 
            h->next->prior=h->prior; 
            delete h; 

        } 
        size--;                    //删除一个后链表长度减1 
    } 
private: 
    ChainNode <T> * head;        //首结点的指针 
    ChainNode <T> * tail;        //尾结点的指针 
    int size;                    //链表长度 
}; 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    Chain<int> li; 
    li.creat(); 
    cout<<"该链表为:"<<endl; 
    li.print(); 
    li.insert(); 
    cout<<"插入后为:"<<endl; 
    li.print(); 
    li.del(); 
    cout<<"删除后为:"<<endl; 
    li.print(); 
    return 0; 
} 
加载中
0
骠骑将军
骠骑将军

你注释起来的代码是正确的

错误注意看117和119行,

双向链表修改的关键是prior和next的赋值顺序

你117时候h的prior已经指定为插入元素p了

119右值h->prior=p,左值是p->prior,等于插入元素p的prior指向自身,双向链表从原来的h->prior后面断了

正确的顺序是:

// p挂在前面
h->prior->next = p;
p->prior = h->prior;

// p连到后面
p->next = h;
h->prior = p;
0
绿悠悠
绿悠悠
问题在哪?
0
java_hh
java_hh

引用来自“绿悠悠”的答案

问题在哪?
我在插入一个数的代码中有注明
0
java_hh
java_hh
怎么没人帮忙


0
周翼翼
周翼翼

你这样一堆乱代码,没几个会看你的.

画个图就行了.

而且,你这代码实在是....insert的位置和结点应该作为参数传入函数,哪有人进入函数后让人输入的.

0
ChenQi
ChenQi
同楼上。。。
0
java_hh
java_hh

引用来自“骠骑将军”的答案

你注释起来的代码是正确的

错误注意看117和119行,

双向链表修改的关键是prior和next的赋值顺序

你117时候h的prior已经指定为插入元素p了

119右值h->prior=p,左值是p->prior,等于插入元素p的prior指向自身,双向链表从原来的h->prior后面断了

正确的顺序是:

// p挂在前面
h->prior->next = p;
p->prior = h->prior;

// p连到后面
p->next = h;
h->prior = p;
就是不能断开再连上去是吧, 我就是奇怪这是插入的代码有问题,而且插入数的时候也没问题啊,就是会影响到删除.......  难道我删除的跟插入的要一致.........以后就不断开插入吧~
骠骑将军
骠骑将军
我说的断开是插入元素p->prior指向了自己. 你插入已经有问题了,但是由于输出时候从前到后遍历用的都是->next,所以"看起来"没问题而已,其实是不对的. 如果你要测试,可以在你觉得正确的插入操作后,从后往前用->prior遍历一次,就能发现问题了
0
java_hh
java_hh

引用来自“周翼翼”的答案

你这样一堆乱代码,没几个会看你的.

画个图就行了.

而且,你这代码实在是....insert的位置和结点应该作为参数传入函数,哪有人进入函数后让人输入的.

谢谢你啊,这么用心,还画图,     是啊,我之前都是习惯在函数内让人输入 的,不习惯传参数,以后会试着用的了......          现在学着数据结构,真是头大 啊!!~~
0
java_hh
java_hh

引用来自“java_hh”的答案

引用来自“骠骑将军”的答案

你注释起来的代码是正确的

错误注意看117和119行,

双向链表修改的关键是prior和next的赋值顺序

你117时候h的prior已经指定为插入元素p了

119右值h->prior=p,左值是p->prior,等于插入元素p的prior指向自身,双向链表从原来的h->prior后面断了

正确的顺序是:

// p挂在前面
h->prior->next = p;
p->prior = h->prior;

// p连到后面
p->next = h;
h->prior = p;
就是不能断开再连上去是吧, 我就是奇怪这是插入的代码有问题,而且插入数的时候也没问题啊,就是会影响到删除.......  难道我删除的跟插入的要一致.........以后就不断开插入吧~
对哦,我终于领悟我错在哪了,我把h->prior=p;放在前面,然后后面的p->prior=h->prior;实际上已经指向插入的元素p自己了。。。。。。。     晕啊,终于醒过来了
返回顶部
顶部