Sungyou_Yu 发表于 2013-7-7 22:45:55

带头结点单链表的创建,插入,删除等问题【程序中断】

#include<iostream>
using namespace std;

class List;
class ListNode
{
friend class List;
private:
        int data;
        ListNode *link;
public:
        ListNode():link(NULL){}
        ListNode(int d):data(d),link(NULL){}
};

class List
{
private:
        ListNode *first,*last;
public:
        List()
        {
        first=last=new ListNode();
        }
        ~List();
        int insert(int i,int d);
        int remove(int temp);
        ListNode * findData(int temp);
        ListNode * find(int i);
        int length();
        void makeEmpty();
};

List::~List()
{
        makeEmpty();
        delete first;
}

void List:: makeEmpty()
{//删除头结点之外的所有其他结点
    ListNode* q;
        while(first->link!=NULL)
        {
                q=first->link;
                first->link=q->link;
                delete q;
        }
        last=first;//last由wild pointer指向first
}

ListNode* List::findData(int temp)//找到数据值为temp的结点,并返回其地址
{
        ListNode *p=first->link;
        while(p!=NULL&&p->data!=temp)
        {
                p=p->link;
        }
        if(p==NULL)return NULL;
        return p;
}

ListNode* List::find(int i)//找到第i个结点【-1,0,1,2,,,】,并返回其地址
{
        ListNode* p=first->link;
        int k=0;
        if(i<-1){
                cout<<"位置无效,i需大于等于-1."<<endl;
                return NULL;
        }
        if(i=-1) {return first;}
        while(p!=NULL&&k<i)
        {
                p=p->link;
                k++;
        }
        if(p==NULL){
        cout<<"未找到该结点"<<endl;
        return NULL;
        }
        return p;
}

int List::insert(int i,int d)//将值为value的结点插入到第i个位置【0,1,2,,,】
{
        ListNode *p=find(i-1);
        if(p=NULL)return 0;
        ListNode* newnode=new ListNode(d);
        newnode->link=p->link;
        if(p->link=NULL)last=newnode;
        p->link=newnode;
        return 1;
}

int List::remove(int i)//将第i个元素删除【0,1,2,,,】
{
        ListNode *p=first->link,*q;
        int k=0;
        while(p!=NULL&&k<i-1)//确定第i-1个元素位置
        {
                p=p->link;
                k++;
        }
        if(i<0||p==NULL||p->link!=NULL)//p已经遍历到最后一个结点【p->link!=NULL】
        {                                                 //或最后一个结点之后或p没有遍历还在第0个结点【p==NULL】
        cerr<<"位置无效!"<<endl;
        return 0;
        }
        q=p->link;
        p->link=q->link;
        if(q->link==NULL)last=p;
        delete q;
        return 1;
}

int List::length()
{
        int k=0;
        ListNode *p=first->link;
        while(p!=NULL)
        {
                k++;
                p=p->link;
        }
        return k;
}

void main()
{
List *list=new List();
list->find(-1);
list->insert(0,35);
list->insert(1,10);
//....................
}
页: [1]
查看完整版本: 带头结点单链表的创建,插入,删除等问题【程序中断】