北邮数据结构实验报告 单链表.doc

北京邮电大学数据结构试验报告实验名称:实验一线性表学生姓名:班级:班内序号:学号:日期:2014年1月3日1实验目的?熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法?学习指针、模板类、异常处理的使用?掌握线性表的操作的实现方法?,选择下面任一种链式结构实现线性表,并完成线性表的基本功能。线性表存储结构(五选一):1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能:1、构造:使用头插法、尾插法两种方法2、插入:要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他:可自行定义编写测试main()函数测试线性表的正确性。:、:[i],将新结点加入链表中代码描述:template<classT>LinkList<T>::LinkList(Ta[],intn)//头插法建立{front=newNode<T>;front->next=NULL;for(inti=n-1;i>=0;i--){Node<T>*s=newNode<T>;s->data=a[i];s->next=front->next;front->next=s;}}时间复杂度:O(n):[i]:template<classT>LinkList<T>::LinkList(Ta[],intn)//尾插法建立{front=newNode<T>;front->next=NULL;Node<T>*r=front;for(inti=0;i<n;i++){Node<T>*s=newNode<T>;s->data=a[i];s->next=r->next;r->next=s;r=s;}}时间复杂度:O(n):,:template<classT>LinkList<T>::~LinkList()//析构函数,销毁链表{Node<T>*p=front;while(p){front=p;p=p->next;deletefront;}}:,p指向第一个结点,j=,直到p为空或者j等于1b1:p指向下一个结点b2:,说明第i个元素不存在,,说明p指向的元素就是所查找的元素,返回元素地址代码描述:template<classT>Node<T>*LinkList<T>::Get(inti)//按位查找{Node<T>*p=front;intj=0;while(p){if(j<i){p=p->next;j++;}elsebreak;}if(!p)throw"查找位置非法";elsereturnp;}时间复杂度:O(n):,p指向第一个结点,j=,,如果是,返回j;,,返回查找失败信息代码描述:template<classT>intLinkList<T>::Locate(Tx)//按值查找{Node<T>*p=front->next;intj=1;while(p){if(p->data==x)returnj;else{p=p->next;j++;}}return-1;}时间复杂度:O(n):,使其指向新插入的结点的位置代码描述:template<classT>voidLinkList<T>::Insert(inti,Tx)//插入函数{Node<T>*p=Get(i-1);if(p){Node<T>*s=newNode<T>;s->data=x;s->next=p->next;p->next=s;}elsethrow"插入位置非法";}时间复杂度:O(n):,查找要删除的位数i前一个位置i-