冬天¤不回来
海风轻轻吹过我的脸庞 阳光温柔的洒在我身上 海鸥自由的飞在天空中像 快乐的徘徊在游乐场 白云在偷看彩虹的模样 海洋总为那船长指方向 海浪抚摸著沙滩的衣裳 我也每天都为他换上新装 找到方向 揭开迷茫 学着坚强 努力去闯!
posts - 20,  comments - 90,  trackbacks - 0

//////////////////////下面给出链表LINKEDLIST 的完整申明 LINKEDLIST.H,假设结点的申明在头文件node.h中//////////
//////////////////////    掌握链表的必备知识点   //////////////////////
////////////////////本人仓促整理 应该有不少错误,node.h会马上给出//////////
#include<iostream.h>
#include<stdlib.h>               //exit(1) 退出函数。
#include"node.h"
template<class t>
enum boolean{false,true}         //将FALSE 和 TRUE 固定为0和1。
class linkedlist
{
   private:
    node<t> *front,*rear;        //指向表头和表尾的指针。
    node<t> *prevptr,*currtr;    //用于访问数据,插入和删除结点的指针。
    int size;
    int position;
       node<t> *getnode(const t& item, node<t> *ptr==null);   //申请及释放结点空间的函数。
    node<t> freenode(node<t> *p);
   public:
    linkedlist(void);
    ~linkedlist(void);
    linkedlist<t> & operator = (const linkedlist<t> &orglist);       //重载赋值运算赋。
       int size<void> const;
       boolean isempty(void) const;
    int nextnode(void);                            // 重新定位结点
    int setposition(int pos);
    int getposition(void)const;        
    void insertat(const t& item);                  //插入结点.
    void insertafter(const t& item);
    void deleteat(void);                           //删除结点.
    void deleteafter(void);
    t getdata(void) const;                         //修改和访问数据的函数。
    void setdata(const t& item);
       void clear(void);
};


template <class t>
node<t> *linkedlist<t>::getnode(const t&item ,node<t> *ptr);
{
 node<t> *newnode = new node<t>(item ptr);
 if(!newnode)
 {
  cerr<<"faied"<<e<endl;
  return null'
 }
 return newnode;                                   // 返回指向新生成接点的指针
}


template <class t>
void *linkedlist<t>::freenode(node<t> *ptr)
{
 if(!ptr)
 {
  cerr<<"invalid node pointer!"<<endl;
  return 0;
 }
 delete ptr;
}


template <class t>                                    //构造函数 建立一个空链表。
linkedlist<t>::linkedlist<void>:front(null),rear(null),prevter(null),currptr(null),size(0),position(-1)
{}

template <class t>
linkedlist::~linkedlist()
{
 clear();
}


template <class t>                                   //重载赋值运算符的函数.
linkedlist<t> &linkedlist<t>::operator = (const linkedlist<t> *orglist)
{
 node<t> *p = orglist.front;
 clear();                                         //这里清空链表是为了给复制做好准备么?
 while(p)  //                                    这里想不明白,大家帮我详细解释下? 
 {
  insertafter(p->data);
  p=p->nextnode();
 }        //                                     ENDL;
setposition(orglist.position);                       //这又是什么意思?要去复习重载了。
return *this;                                       


template <class t>
int linkedlist<t>::size(void) const
{
 return size;
}


template <class t>
boolean linkedlist<t>::isempty(void) const
{
 return size?false:ture;
}


template <class t>
int linkedlist<t>::nextnode(void)
{
 if(position>=0 && position<size)
 {
  position++;                                   //将当前结点往后移了一位。
        prevptr = currptr;
  currptr = currptr->nextnode();
 }
 else
 {
  position = size;                                //否则将此结点设置为最后结点。
        return position;
 }
}


template <class t>                                   //链表中重置当前结点位置的函数。
int linkedlist<t>::setpostion(int pos)
{
 if(!size)
  return -1;
 if(pos<0||pos>size-1)
 {
  cerr<<"error position"<<endl;
  return -1;
 }
 prevptr = null;
 currptr = front;
 position = 0;
 for(int k=0;k<pos;k++)
 {
  position++;
  prevptr = currptr;
  currptr = currptr->nextnode();
 }
 return position;
}


template <class t>
int linkedlist::getposition(void)const
{
 return position;
}

 

template <class t>                       //重要:链表中在当前结点处插入新结点的函数;
void linkedlist<t>::insertat(const t& item)
{
 node<t> *newnode;
 if(!size)                            //空表中插入。
 {
  newnode = getnode(item, front);
  front = rear = newnode;
  position = 0;
 }
 else if(!prevptr)                   //在表头插入                 
 {
  newnode = getnode(item , front);
        front = newnode;
 }
 else                                //在链表中间插入插入
 { 
  newnode = getnode(item , front);
  prevptr = insertafter(newnode);
 }
 size++;
 currptr = newnode;                  //新插入的结点为当前结点
}

 

template <class t>                       //重要:链表中在当前结点后插入新结点的函数;
void linkedlist<t>::insertafter(const t& item)
{
 node<t> *newnode;
 if(!size)                            //空表中插入。
 {
  newnode = getnode(item);
  front = rear = newnode;
  position = 0;
 }
 else if(currptr == rear||!currptr)   //在链表尾插入
 {
  newnode = getnode(item);
  rear->insertafter(newnode);
  prevptr=newnode;
  rear = newnode;
  position = size;
 }
 else
 {
  newnode = getnode(item ,currptr->nextnode());    //  在表的中间插入
  currptr->insertafter(newnode);
  prevptr = currptr;
  position++
 }
  size++;
  currptr = newnode;
}


template <class t>
void linkedlist<t>::deleteat(void)                  //重要:删除当前结点的函数
{
 node<t> *oldnode;
 if(!currptr)                                     //若表为空或者已到表尾,则给出错误提示并返回
 {
  cerr<<"currptr position is invalid!"<<endl;
  return;
 }
 if(!prevtr)                                       //删除表头结点。
 {
  oldnode = front;
  front = currptr->nextnode();
 }
 else
 {
  oldnode = prevptr->deleteafter();            //删除的是表中结点;
 }
 if(oldnode == rear)
 {
  rear = prevptr;                              //删除的是表尾结点,则修改表尾指针和当前位置结点值
  position--;
 }
 currptr = oldnode->nextnode();                  //后续结点作为新的当前结点
 freenode(oldnode);                              //释放原当前结点
 size--;                                         //链表大小减1;
}

 

template <class t>
void linkedlist<t>::deleteafter(void)
{
 node<t> *oldnode;
 if(!currptr||currptr==rear)
 {
  cerr<<"current position is invalid!"<<endl;
  return;
 }
 oldnode = currptr->deleteafter();                //保存被删除结点的指针并从链表中删除该结点。
 if(oldnode == rear)
 {
  rear == currptr;                              //删除的是表尾结点。
 }
 freenode(oldnode);
 size--;
}

 

template <class t>                                  //获取当前结点的函数
T linkedlist<t>::getdata(void) const
{
 if(!size || !currptr)                              //若表为空或已经到达表尾之后,则出错。
 {
  cerr<<"currptr node not exit!"<<endl;           //给出错误信息并退出。
  exit(1);
 }
 return currptr->data;
}


 
template <class t>                                //链表中修改当前结点数据的函数
void linkedlist<t>::setdata(const T& item)
{
 if(!size||!currptr)
 {
  cerr<<"data:current node not exit!"<<endl;
  exit(1);
 }
 currptr->data = item;
}


template <class t>
void linkedlist<t>::clear(void)
{
 node<t> *currptr=front,*nextnode;
 while(currnode)
 {
  nextnode = currnode->nextnode();
  freenode(currnode);
  currnode = nextnode;
 }
 front = rear = prevptr = currptr = null;                //修改空链表数据
    size = 0;
 position = -1;
}

posted on 2006-09-25 22:47 冬天¤不回来 阅读(1079) 评论(4)  编辑 收藏 引用

FeedBack:
# re: ///// 掌握链表的必备知识点 //////
2006-09-25 23:34 | warrior
我只有这个水平!请高手指点撒  回复  更多评论
  
# re: ///// 掌握链表的必备知识点 //////
2006-10-07 16:25 | 冬天¤不回来
主要是一些基本的插入 删除 运算  回复  更多评论
  
# re: ///// 掌握链表的必备知识点 //////
2006-10-24 23:43 | Asp
华为的一道笔试题:
只遍历一次链表,找到倒数第n个节点……
嘿嘿…… 可以想想…… 结果很容易……  回复  更多评论
  
# re: ///// 掌握链表的必备知识点 //////
2007-03-26 14:45 | zkkpkk
判断两链表是否相交,时间复杂度控制在O(n),据说是M$的试题  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


QQ:41696402

<2006年9月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(3)

随笔档案

文章档案

Programming

最新随笔

搜索

  •  

积分与排名

  • 积分 - 37440
  • 排名 - 532

最新评论

阅读排行榜

评论排行榜