福州大学数据结构实验报告-线性表

第一篇：福州大学数据结构实验报告-线性表

数据结构原理实验报告

学号：

姓名：

线性表

一、问题描述 1.实现ADT表

2.设表的Reverse运算将表中元素的次序反转。扩充用数组实现表的结构List，增加函数Reverse(L)，将表L中元素的次序反转，并要求就地实现Reverse运算。

二、算法描述

从i=0开始，将表中第N个元素与N-i-1个元素调换即可

三、核心代码

void ReverseList(List L){

ListItem tmp;int i;for(i=0;in/2;i++){

} tmp = L->table[i];L->table[i] = L->table[L->n-1-i];L->table[L->n-1-i] = tmp;}

四、运行结果

第二篇：数据结构线性表实验报告

实验报告

课程名：数据结构

实验名：线性表及其操作 姓名： 班级： 学号：

撰写时间：2014.09.24

一 实验目的与要求

1.掌握线性表的实现

2.掌握线性表的基本操作的实现

二 实验内容

• 分别完成线性表的顺序表示及链式表示

• 在两种表示上, 分别实现一些线性表的操作, 至少应该包括 – 在第i个位置插入一个元素 – 删除第i个元素 – 返回线性表长

– 返回第i个元素的值

三 实验结果与分析

#include #include //---------线性表链式表示-----------struct V//声明一个结构体类型struct V { int value;struct V * next;//定义结构体变量 };void PrintLink(struct V*p)//定义一个结构体指针 { while(p!=NULL)//只要指针指向的变量不为NULL；就会一直循环链表指向下一个结构体

{

printf(“%d, ”,(*p).value);

p=(*p).next;//指针指向下一个结构体

} printf(“n”);} void Link(){

struct V*head;head=(struct V*)malloc(sizeof(struct V));//开辟一个长度为size的内存

(*head).value=-100;//表头为-100(*head).next=NULL;printf(“------------线性表链式表示------------n”);

int i,n=10;struct V*p=head;printf(“10个数据:n”);for(i=0;i

(*p).next=(struct V*)malloc(sizeof(struct V));

p=(*p).next;

(*p).value=2*i;

(*p).next=NULL;} PrintLink(head);//调用PrintLink函数

printf(“删除第四个数据:n”);int k=4;p=head;for(i=1;i

p=(*p).next;} struct V*temp=(*p).next;//k表示插入和删除的位置

(*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十个数据:n”);

k=10;p=head;for(i=1;i

p=(*p).next;} temp=(*p).next;(*p).next=(struct V*)malloc(sizeof(struct V));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);}

//---------线性表顺序表示-----------void seq1(){ int i,n=10,k=4;int a[10];//---------输出数组元素------------printf(“-------------线性表顺序表示---------n”);for(i=0;i

a[i]=i;} printf(“数组元素为:n”);for(i=0;i

printf(“%3d”,a[i]);} printf(“n”);//--------插入一个数组元素---------int m=n+1,j=12;//插入元素12 int b[20];for(i=0;i

if(i

{

b[i]=a[i];

}

else if(i==k)

{b[i]=j;}

else

{b[i]=a[i-1];} } printf(“输出插入一个元素的数组:n”);for(i=0;i

{

if(i

{c[i]=a[i];}

else

{c[i]=a[i+1];} } printf(“输出删除一个元素的数组:n”);for(i=0;i

printf(“数组元素为:n”);for(i=1;i<=a[0];i++){a[i]=i;} for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-----在k位置插入一个元素------------for(i=a[0];i>=k;i--){a[i+1]=a[i];} a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-------在k---------------for(i=0;i>k;i++){a[i]=a[i+1];} a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);

} int main(int argc,char *argv[]){ seq1();seq2();Link();return 0;}

图1：实验结果截图

实验分析：已在程序中按规定格式标注。

第三篇：数据结构--实验报告 线性表的基本操作

}(一)单链表的基本操作

#include using namespace std;#define true 1 #define false 0 #define ok 1 #define error 0 #define overflow-2 typedef int Status;typedef int ElemType;typedef struct LNode //存储结构 { ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n)//尾插法创建单链表 { LinkList p;L=new LNode;L->next=NULL;//建立一个带头结点的单链表

LinkList q=L;//使q指向表尾

} Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素 { LinkList p=L->next;int j=1;while(p&&jnext;++j;} for(int i=1;i<=n;i++){ p=new LNode;

cin>>p->data;p->next=NULL;q->next=p;q=p;} if(!p||j>i)return error;//第i个元素不存在

e=p->data;return ok;} Status LinkInsert(LinkList &L,int i,ElemType e)//插入 { LinkList p=L;int j=0;while(p&&jnext;++j;} //寻找第i-1个结点 if(!p||j>i-1)return error;//i小于1或者大于表长加1 LinkList s=new LNode;//生成新结点

s->data=e;s->next=p->next;//插入L中

p->next=s;return ok;}

Status ListDelete(LinkList &L,int i,ElemType &e)// 删除 { LinkList p=L;LinkList q;int j=0;while(p->next&&j

p=p->next;++j;} if(!(p->next)||j>i-1)return error;//删除位置不合理

q=p->next;p->next=q->next;//删除并释放结点

e=q->data;delete(q);return ok;

} void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){ //合并两个顺序链表

LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data)

{ pc->next=pa;

pc=pa;pa=pa->next;} else

{ pc->next=pb;

pc=pb;

pb=pb->next;} } pc->next=pa?pa:pb;delete(Lb);} void show(LinkList L)//{ LinkList p;p=L->next;while(p){ cout<

data<<“-->”;p=p->next;} cout<next;while(p){ ++i;

显示 表长 3

p=p->next;} return i;} void xiugai(LinkList L)//修改 { int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<“请输入要修改的元素位置(0>i;GetElem(L,i,e);cout<<“该位置的元素:”<>k;while(p&&jnext;++j;} m=p->data;p->data=k;cout<<“修改后的单链表显示如下:”<>a;cout<<“请输入第一个有序链表的元素共（”<>b;cout<<“请输入第二个有序链表的元素共（”<>select;switch(select){ case 1:cout<<“请输入单链表的长度:”<

cin>>x;

cout<<“请输入”<

CreateList(list,x);break;case 2: cout<<“单链表显示如下:”<

show(list);break;case 3: int s;cout<<“单链表的长度为:”<>x;while(x<0||x>Length(list,s)){ cout<<“输入有误，请重新输入”<>x;} GetElem(list,x,y);cout<<“该位置的元素为:”<>x;while(x<0||x>Length(list,s)){ cout<<“输入有误，请重新输入”<>x;} cout<<“要插入的元素值:”;cin>>y;LinkInsert(list,x,y);cout<<“插入后单链表显示如下:”<>x;while(x<0||x>Length(list,s)){ cout<<“输入有误，请重新输入”<>x;} cout<<“要删除的元素值:”<

ListDelete(list,x,y);

} break;case 8: hebing();break;case 9: exit(0);break;default : cout<<“输入有误，请重新输入”<

四、测试结果 1)顺序表 的测试结果

8 2)单链表的测试结果

五、心得体会

当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。记得去年学习C++时，学了一个学期，程序设计用了三周，才完成的，这个实验报告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良好。

通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C++是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C++语言，将各种操作描述出来构成算法。数据结构+算法=程序设计。

在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C++的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。

单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数……通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。

这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。

第四篇：数据结构实验报告二线性表的顺序存储

实验报告二 线性表的顺序存储

班级： 2010XXX 姓名： HoogLe 学号： 2010XXXX 专业： XXXX

2858505197@qq.com

一、实验目的：

（1）掌握顺序表的基本操作的实现方法。

（2）应用顺序表的基本算法实现集合A=AUB算法。

（3）应用顺序表的基本算法实现两有序顺序表的归并算法。

二、实验内容：

1、线性表顺序存储结构的基本操作算法实现（要求采用类模板实现）

[实现提示]（同时可参见教材p5822-p60页算法、ppt）函数、类名称等可自定义，部分变量请加上学号后3位。库函数载和常量定义：（代码）#include using namespace std;const int MaxSize=100;

（1）顺序表存储结构的定义(类的声明)：（代码）

template //定义模板类SeqList class SeqList { public: SeqList();//无参构造函数

SeqList(datatype a[ ], int n);//有参构造函数 ~SeqList(){};//析构函数为空 int Length();//求线性表的长度

datatype Get(int i);//按位查找，取线性表的第i个元素 int Locate(datatype item);//查找元素item void Insert(int i, datatype item);//在第i个位置插入元素item datatype Delete(int i);//删除线性表的第i个元素 void display();//遍历线性表，按序号依次输出各元素 private: datatype data[MaxSize];//存放数据元素的数组 int length;//线性表的长度 };

（2）初始化顺序表算法实现（不带参数的构造函数）/* *输 入：无

*前置条件：顺序表不存在 *功 能：构建一个顺序表 *输 出：无

*后置条件：表长为0 */ 实现代码：

template SeqList:: SeqList(){ length=0;}

（3）顺序表的建立算法（带参数的构造函数）

/* *输 入：顺序表信息的数组形式a[],顺序表长度n *前置条件：顺序表不存在

*功 能：将数组a[]中元素建为长度为n的顺序表 *输 出：无

*后置条件：构建一个顺序表 */ 实现代码：

template SeqList:: SeqList(datatype a[], int n){ if(n>MaxSize){

cout<<“数组元素个数不合法”<

data[i]=a[i];length=n;}（4）在顺序表的第i个位置前插入元素e算法 /* *输 入：插入元素e,插入位置i *前置条件：顺序表存在，i要合法

*功 能：将元素e插入到顺序表中位置i处 *输 出：无

*后置条件：顺序表插入新元素，表长加1 */ 实现代码：

template void SeqList::Insert(int i, datatype item){ int j;if(length>=MaxSize){

cout<<“溢出”<length+1){

cout<<“i不合法！”<=i;j--)

data[j]=data[j-1];data[i-1]=item;length++;}（5）删除线性表中第i个元素算法 /* *输 入：要删除元素位置i *前置条件：顺序表存在,i要合法

*功 能：删除顺序表中位置为i的元素 *输 出：无

*后置条件： 顺序表册除了一个元素，表长减1 */ 实现代码：

template datatype SeqList::Delete(int i){ int item,j;if(length==0){

cout<<“表为空,无法删除元素!”<length){

cout<<“i不合法!”<

for(j=i;j

data[j-1]=data[j];//注意数组下标从0记

length--;return item;}（6）遍历线性表元素算法 /* *输 入：无

*前置条件：顺序表存在 *功 能：顺序表遍历 *输 出：输出所有元素 *后置条件：无 */ 实现代码：

template void SeqList::display(){ if(length==0){

cout<<“表为空，无法输出!”<

cout<

（7）获得线性表长度算法 /* *输 入：无

*前置条件：顺序表存在 *功 能：输出顺序表长度 *输 出：顺序表长度 *后置条件：无 */ 实现代码：

template int SeqList::Length(){ return Length;}

（8）在顺序线性表中查找e值，返回该元素的位序算法 /* *输 入：查询元素值e *前置条件：顺序表存在

*功 能：按值查找值的元素并输出位置 *输 出：查询元素的位置 *后置条件：无 */ 实现代码：

template int SeqList::Locate(datatype item){ for(int i=0;i

//下标为i的元素等于item，返回其序号i+1

return 0;//查找失败 }

（9）获得顺序线性表第i个元素的值 /* *输 入：查询元素位置i *前置条件：顺序表存在，i要合法

*功 能：按位查找位置为i的元素并输出值 *输 出：查询元素的值 *后置条件：无 */ 实现代码：

template datatype SeqList::Get(int i){ if(i<0||i>length){

cout<<“i不合法!”<

（10）判表空算法 /* *输 入：无 *前置条件：无

*功 能：判表是否为空

*输 出：为空返回1，不为空返回0 *后置条件：无 */ 实现代码：

template bool SeqList::Empty(){ if(length==0){

return 1;} else {

return 0;} }

(11)求直接前驱结点算法 /* *输 入：要查找的元素e，待存放前驱结点值e1

*前置条件：无

*功 能：查找该元素的所在位置，获得其前驱所在位置。*输 出：返回其前驱结点的位序。*后置条件：e1值为前驱结点的值 */ 实现代码：

template int SeqList::Pre(datatype item){ int k=Locate(item)-1;if(k>0)

return k;else {

cout<<“无前驱结点！”<

return 0;} }(12)求直接后继结点算法 /* *输 入：要查找的元素e，待存放后继结点值e1 *前置条件：无

*功 能：查找该元素的所在位置，获得其后继所在位置。*输 出：返回其后继结点的位序。*后置条件：e1值为后继结点的值 */ 实现代码：

template int SeqList::Suc(datatype item){ int k=Locate(item)+1;if(k>length){

cout<<“无后继结点!”<

return k;} }

上机实现以上基本操作，写出main()程序： void main(){ SeqList Seq;//创建

if(Seq.Empty()){

cout<<“线性表为空!”<

} Seq.Insert(1,1);Seq.Insert(2,2);Seq.Insert(3,3);Seq.Insert(4,4);Seq.Insert(5,5);//插入元素操作

cout<<“输出插入的五个元素:”<

cout<

cout<<“2是第”<

cout<<“第五个元素是:”<

cout<<“线性表的长度为:”<

Seq.Delete(3);//删除元素

cout<<“删除第三个元素后的线性表为:”<

cout<

cout<<“元素2前驱结点的数值为：”<

cout<<“元素4后继结点的位置为：”<

cout<<“元素4后继结点的数值为：”<

要求对每个算法都加以测试，判断是否正确；并测试不同类型数据的操作。粘贴测试数据及运行结果：

2、用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）/* *输 入：集合A,集合B *前置条件：无

*功 能：实现A=AUB *输 出：无

*后置条件：A中添加了B中的元素。*/

实现代码：

template SeqList SeqList::Add(SeqList& item){ if(item.Empty())

return *this;else {

int k=item.Length();

int num=this->Length();

for(int i=1;i<=k;i++)

{

for(int j=0;j

if(data[j]==item.Get(i))

{

break;

}

else if(num-1==j&&data[num-1]!=item.Get(i))

{

this->Insert(++num,item.Get(i));

}

}

return *this;} } void main(){ SeqList A,B;cout<<“A∪B的结果是:”<

B.Insert(1,2);B.Insert(2,6);B.Insert(3,1);B.Insert(4,8);B.Insert(5,9);//插入集合B中元素

A.Add(B);A.display();cout<

3、对以上顺序表类中的基本操作算法适当加以补充，实现向一个有序的（非递减）的顺序表中插入数据元素e算法。/* *输 入：插入元素e *前置条件：顺序表已有序

*功 能：将元素e插入到顺序表中适当的位置，使顺序表依然有序 *输 出： 无

*后置条件：有序顺序表插入了新元素，且表长加1。*/ 实现代码：

template void SeqList::orderInsert(datatype item){ int num=this->Length();for(int i=0;i

if((data[i]item))

{

for(int k=num;k>i;k--)

data[k]=data[k-1];

data[i+1]=item;

length++;

break;

}

if(data[i]>item)

{

for(int k=num;k>i;k--)

data[k]=data[k-1];

data[i]=item;

length++;

break;

} } } void main(){ SeqList A,B;A.Insert(1,3);A.Insert(2,5);A.Insert(3,6);A.Insert(4,8);A.Insert(5,10);//插入顺序表

cout<<“原顺序表为:”<

cout<

cout<<“插入新元素后的顺序表为:”<

4、算法实现：La,Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）（利用函数类板实现）MergeList： /* *输 入：有序线性表La,有序线性表Lb *前置条件：顺序表已有序

*功 能：将两线性表归并，不去掉相同元素 *输 出： 返回一个新的有序线性表Lc *后置条件：无 */ 实现代码：

template SeqList SeqList::ElseAdd(SeqList Seq1,SeqList Seq2){ int num=Seq2.Length();for(int i=0;i<=num;i++){

Seq1.orderInsert(Seq2.Get(i));} return Seq1;} void main(){ SeqList La,Lb,Lc;La.Insert(1,2);La.Insert(2,4);La.Insert(3,6);La.Insert(4,8);//插入La cout<<“La中元素为:”<

cout<<“合并后的Lc为:”<

cout<

粘贴测试数据及运行结果：

三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）

第五篇：数据结构实验报告三线性表的链式存储

实验报告三 线性表的链式存储

班级： 2010XXX 姓名： HoogLe 学号： 2010XXXX 专业： XXXX

2858505197@qq.com

一、实验目的：

（1）掌握单链表的基本操作的实现方法。（2）掌握循环单链表的基本操作实现。（3）掌握两有序链表的归并操作算法。

二、实验内容：（请采用模板类及模板函数实现）

1、线性表链式存储结构及基本操作算法实现

[实现提示]（同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义： #include using namespace std;（1）单链表存储结构类的定义： template class LinkList{ public: LinkList();//初始化带头结点空单链表构造函数实现

LinkList(T a[],int n);//利用数组初始化带头结点的单链表构造函数实现

~LinkList();int length();//求单链表表长算法

T get(int i);//获得单链表中第i个结点的值算法

int locate(T temp);void insert(int i,T temp);//在带头结点单链表的第i个位置前插入元素e算法

T Delete(int i);//在带头结点单链表中删除第i个元素算法

void print();//遍历单链表元素算法

bool isEmpty();//判单链表表空算法

void deleleAll();//删除链表中所有结点算法（这里不是析构函数，但功能相同）private: Node *head;};（2）初始化带头结点空单链表构造函数实现 输入：无

前置条件：无

动作：初始化一个带头结点的空链表 输出：无

后置条件：头指针指向头结点。

//初始化带头结点空单链表构造函数实现 template LinkList::LinkList(){ head = new Node;head->next = NULL;}

（３）利用数组初始化带头结点的单链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无

动作：利用头插或尾插法创建带头结点的单链表 输出：无

后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。//利用数组初始化带头结点的单链表构造函数实现 template LinkList::LinkList(T a[],int n){ head=new Node;head->next=NULL;for(int i=0;i *s=new Node;s->data=a[i];s->next=head->next;head->next=s;} }（４）在带头结点单链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法

动作：在带头结点的单链表中第i个位置之前插入元素e 输出：无

后置条件：单链表中增加了一个结点

//在带头结点单链表的第i个位置前插入元素e算法 template void LinkList::insert(int i,T temp){ Node *p = head;int count = 0;while(p&&count

p=p->next;

count++;} if(p==NULL)cout<<“i不合法，越界!”;else{

Node *s = new Node;

s->data = temp;

s->next = p->next;

p->next = s;} }（５）在带头结点单链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单链表不空，i的值要合法

动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无

后置条件：单链表中减少了一个结点

//在带头结点单链表中删除第i个元素算法 template T LinkList::Delete(int i){ Node *p = head;int count = 0;while(p&&count

p=p->next;

count++;} if(p==NULL)cout<<“i不合法，越界!”;else{

Node *s = p->next;

T x= s->data;

p->next = s->next;

return x;} }（６）遍历单链表元素算法 输入：无

前置条件：单链表不空

动作：遍历输出单链表中的各元素。输出：无

后置条件：无

//遍历单链表元素算法 template void LinkList::print(){ Node *p = head->next;while(p){

cout<

data<<“ ”;

p=p->next;} cout<

（７）求单链表表长算法。输入：无

前置条件：无

动作：求单链表中元素个数。输出：返回元素个数 后置条件：无

//求单链表表长算法 template int LinkList::length(){ Node *p = head;int count = 0;while(p){

p=p->next;

count++;} return--count;}

（８）判单链表表空算法 输入：无

前置条件：无

动作：判表是否为空。

输出：为空时返回１，不为空时返回0 后置条件：无 //判断非空

template bool LinkList::isEmpty(){ Node *p = head->next;if(p)return true;else return false;}

（９）获得单链表中第i个结点的值算法 输入：无

前置条件：i不空，i合法 动作：找到第i个结点。

输出：返回第i个结点的元素值。后置条件：无

//获得单链表中第i个结点的值算法 template T LinkList::get(int i){ Node *p = head;int count = 0;while(p&&count

p=p->next;

count++;} if(p==NULL)cout<<“i不合法，越界!”;else{

return p->data;} }

(10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无

前置条件：单链表存在

动作：清除单链表中所有的结点。输出：无

后置条件：头指针指向空 //删除所有元素 template void LinkList::deleleAll(){ Node *p = head;while(p){

Node *t=p;

p=p->next;

t->next=NULL;} }

(11)上机实现以上基本操作，写出main()程序： 参考p72 void main(){ int a[10]={1,2,3,4,5,6,7,8,9,0};//测试带参数的构造函数（前端插入！）

LinkList list1(a,10);//测试插入

if(list1.isEmpty()){ cout<<“链表不为空!”<

cout<<“链表为空!”<

2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。template class LinkList{ public: LinkList(T a[],int n);//利用数组初始化带头结点的单循环链表构造函数实现

void insert(int i,T temp);//在带头结点单循环链表的第i个位置前插入元素e算法

T Delete(int i);//在带头结点单循环链表中删除第i个元素算法

void print();//遍历单循环链表元素算法 private: Node *head;int length;};（１）利用数组初始化带头结点的单循环链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无

动作：利用头插或尾插法创建带头结点的单循环链表 输出：无

后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。

//利用数组初始化带头结点的单循环链表构造函数实现 template LinkList::LinkList(T a[],int n){ head=new Node;head->next= head;length = 0;for(int i=0;i *s=new Node;s->data=a[i];

s->next = head->next;head->next=s;

length++;} }

（２）在带头结点单循环链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法

动作：在带头结点的单循环链表中第i个位置之前插入元素e 输出：无

后置条件：单循环链表中增加了一个结点

//在带头结点单循环链表的第i个位置前插入元素e算法 template void LinkList::insert(int i,T temp){ cout<length< *p = head;int count = 0;if(i>length)cout<<“i不合法，越界!”;else{

while(count

p=p->next;

count++;

}

Node *s = new Node;

s->data = temp;

s->next = p->next;

p->next = s;} }（３）在带头结点单循环链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单循环链表不空，i的值要合法

动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无

后置条件：单循环链表中减少了一个结点

//在带头结点单循环链表中删除第i个元素算法 template T LinkList::Delete(int i){ Node *p = head;int count = 0;

if(i>length)cout<<“i不合法，越界!”<

while(count

p=p->next;

count++;

}

Node *s = p->next;

T x= s->data;

p->next = s->next;

return x;} }

（４）遍历单循环链表元素算法 输入：无

前置条件：单循环链表不空

动作：遍历输出单循环链表中的各元素。输出：无

后置条件：无

//遍历单循环链表元素算法 template void LinkList::print(){ Node *p = head->next;while(p!=head){

cout<

data<<“ ”;

p=p->next;} cout<

(５)上机实现以上基本操作，写出main()程序： void main(){ int a[10]={1,2,3,4,5,6,7,8,9,0};//测试带参数的构造函数（前端插入！）

LinkList list1(a,10);list1.print();cout<<“测试插入”<

３、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。模板函数：

template void LinkList::addtwo(LinkList La,LinkList Lb){ Node *p1=La.head->next;Node *p2=Lb.head->next;int num=0;while(p1&&p2){

if(p1->data>p2->data)

{

this->insert(++num,p1->data);

p1=p1->next;

}

else{ this->insert(++num,p2->data);

p2=p2->next;

} } if(!p1){

p1=p2;} while(p1){

this->insert(++num,p1->data);

p1=p1->next;}

} void main(){ int a[5]={1,2,5,6,9};int b[5]={0,3,4,7,8};LinkList list1(a,5);LinkList list2(b,5);list1.print();list2.print();LinkList list3;list3.addtwo(list1,list2);list3.print();system(“pause”);} 粘贴测试数据及运行结果：

选做题：

１、按一元多项式ADT的定义，实现相关操作算法： ADT PNode is Data 系数(coef)指数(exp)指针域(next):指向下一个结点 Operation 暂无

end ADT PNode ADT Polynomial is Data PNode类型的头指针。Operation

Polynomail 初始化值：无

动作：申请头结点，由头指针指向该头结点，并输入m项的系数和指数，建立一元多项式。

DestroyPolyn 输入：无

前置条件： 多项式已存在 动作：消毁多项式。输出：无

后置条件：头指针指向空

PolyDisplay 输入：无

前置条件： 多项式已存在，不为空 动作：输出多项式各项系数与指数 输出：无

后置条件：无 AddPoly 输入：另一个待加的多项式

前置条件：一元多项式pa和pb已存在。动作及后置条件：完成多项式相加运算，（采用pa=pa+pb形式,并销毁一元多项式pb）输出：无

end ADT Polynomial

２、实现一元多项式的减法，操作描述如下： SubPoly 输入：待减的多项式pb 前置条件：一元多项式pa和pb已存在。

动作及后置条件：完成多项式减法运算，即：pa=pa-pb,并销毁一元多项式pb。输出：无

３、参考P74-P79页双向链表的存储结构定义及算法，编程实现双向链表的插入算法和删除算法。

三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）