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

第一篇：线性表的链式存储结构实验报告

实验报告

课程名称：数据结构与算法分析 实验名称：链表的实现与应用

实验日期：2015.01.30 班级： 数媒1401 姓名： 范业嘉 学号 1030514108

一、实验目的

掌握线性表的链式存储结构设计与基本操作的实现。

二、实验内容与要求

⑴定义线性表的链式存储表示；

⑵基于所设计的存储结构实现线性表的基本操作；

⑶编写一个主程序对所实现的线性表进行测试；

⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用

线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。

⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。

三、数据结构设计

1.按所用指针的类型、个数、方法等的不同，又可分为：

线性链表（单链表）

静态链表

循环链表

双向链表

双向循环链表

2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。

四、算法设计

1.定义一个链表

void creatlist(Linklist &L,int n){ int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;i

s=(Linklist)malloc(sizeof(Lnode));

scanf(“%d”,&s->data);

s->next=NULL;

p->next=s;

p=s;

/ 8

} } 2.（1）两个链表的合并

void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc){ Linklist pa,pb,pc;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;free(Lb);}（2）两个链表的并集

Linklist unionlist(Linklist &La,Linklist &Lb){ Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){

flag=0;

p2=Lb->next;

while(p2)

{

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

{

flag=1;

break;

}

p2=p2->next;

}

if(flag==0)

{

s=(Linklist)malloc(sizeof(Lnode));

s->data=p1->data;

q->next=s;

q=s;

}

p1=p1->next;/ 8

}

q->next=Lb->next;return head;

}

3.（1）一元多项式的加法

List addpoly(List pa,List pb)

//一元多项式的加法 { int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){

if(pa->expn>pb->expn)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=pa->coef;

s->next=NULL;

p->next=s;

p=s;

pa=pa->next;

}

else if(pa->expn

expn)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;

}

else

{

n=pa->coef+pb->coef;

if(n!=0)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;/ 8

s->coef=n;

s->next=NULL;

p->next=s;

p=s;

}

pb=pb->next;

pa=pa->next;

} } while(pa!=NULL){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=pa->coef;

s->next=NULL;

p->next=s;

p=s;

pa=pa->next;} while(pb!=NULL){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;} return pc;}

（2）一元多项式的减法

List subpoly(List pa,List pb)

//一元多项式的减法 { int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){

if(pa->expn>pb->expn)

/ 8

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=pa->coef;

s->next=NULL;

p->next=s;

p=s;

pa=pa->next;} else if(pa->expn

expn){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=-pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;} else {

n=pa->coef-pb->coef;

if(n!=0)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=n;

s->next=NULL;

p->next=s;

p=s;

}

pb=pb->next;

pa=pa->next;} } while(pa!=NULL){ s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;} / 8

while(pb!=NULL){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=-pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;} return pc;}（3）一元多项式的乘法

void mulpolyn(polynomail pa,polynomail pb,polynomail &pc){

LNode *p,*q,*s,*hc;p=pa->next;q=pb->next;hc=pc;while(p!=NULL){

while(q!=NULL)

{

s=(polynomail)malloc(sizeof(LNode));

hc->next=s;

hc=hc->next;

hc->coef=q->coef*p->coef;

hc->expn=q->expn+p->expn;

q=q->next;

}

p=p->next;

q=pb->next;} hc->next=NULL;}

/ 8

五、测试结果

2.3.7 / 8

六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）

1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。

2.当写一元多项式的加减时，前提是弄清楚各种情况，系数相同时就相加减，系数不同就保留原有多项式；当系数相加减为0时，就free这个节点。在做减法时，我考虑到了减数与被减数之间的关系。

3.在做多项式时，我准备按照书上的算法一个一个写小函数，结果到最后发现写不下去了，就去问问同学和上网看看，结果感觉写这个数据结构的程序其实不必想麻烦了，只是指针，数组的高级运用。

/ 8

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

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

班级： 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页双向链表的存储结构定义及算法，编程实现双向链表的插入算法和删除算法。

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

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

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

班级： 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<

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

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

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

实验报告

课程名：数据结构

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

撰写时间：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：实验结果截图

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

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

数据结构原理实验报告

学号：

姓名：

线性表

一、问题描述 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;}

四、运行结果