数据结构线性表试验报告（最终定稿）

第一篇：数据结构线性表试验报告

线性表上机实习

1、实验目的

（1）熟悉将算法转换为程序代码的过程。

（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。

（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。

2、实验要求

（1）熟悉顺序表的插入、删除和查找。（2）熟悉单链表的插入、删除和查找。

3、实验内容: ① 顺序表

（1）抽象数据类型定义

typedef struct {

TypeData data[maxsize];

//容量为maxsize的静态顺手表

int n;

//顺序表中的实际元素个数

}SeqList;

//静态顺序表的定义

在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。

（2）存储结构定义及算法思想

在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下：

for(n=0;n

cout<<“请输入线性表数据”<

cin>>L.data[n];

//顺序将数据存入顺序表

}

//其他存储与此类似，都是直接赋值与数组的某一位

插入版块子函数：

void insert(SeqList &L)

//插入数据 {

int a,b,c,k;

cout<<“请输入插入的数及其插入的位置”<

cin>>a>>b;

if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”<

k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1;

while(c>b){

L.data[c]=L.data[c-1];c--;

//通过循环，实现插入位置后的数据挨个往后移动一位

}

L.data[b]=k;} 顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。显示操作是通过循环实现表中第一个元素到最后一个元素的输出，查找操作是直接取数组中的查找位输出。

（3）实验结果与分析

② 单链表

（1）抽象数据类型定义

typedef struct node{ DataType data;

//链表的数据类型

struct node *link;

//链表的结点指针

}linknode,*linklist;

//定义了结构体linklode和结构体指针linklist

在本次实验中，首先程序自己建立一个空的头结点，通过菜单的功能选择“添加链表数据”可自由添加链表的节点数及元素值。在菜单选择中，有“添加链数据”，“插入链表数据”，“删除链表数据”，“查找链表数据”和“显示链表数据”功能，选择不能的功能选择就能实现不同的操作。其中“添加链表数据”可反复批量输入链表数据。

（2）存储结构定义及算法思想

在单链表中，typedef int DataType;DataType data;定义链表存储数据位整型。存储结构如下：

while(p->link!=NULL){ p=p->link;

k++;

//首先找到单链表的最后结点（如果是只有头结点

} 的单链表则直接跳过），以便后面接着输入数据

for(int i=0;i

{ cout<<“请输入数据”<

//开辟新的结点空间并转化为linklist指针型

cin>>q->data;

q->link=p->link;

//将前面一个结点的指向(及NULL)赋给新开辟的结点的指向

p->link=q;

//将插入点前面一个结点指向新开辟的的结点

p=q;

//将指明的最后一个一个结点向后移1位到最后一位，以便后面接着输入

}

删除结点子函数：

void delate(linklist &l){

//删除单链表数据

linklist p;int m,n,i=0;

cout<<“请输入想要删除的结点位置”<

cin>>m;

p=l;

//将头结点赋给转移指针p

while(p&&i

//查找删除结点的位置

p=p->link;

//当在单链表中间已查到删除结点或p=NULL时跳出循环

i++;

} if(p==NULL){

//当p=NULL跳出循环时，表明链表中没有该结点

cout<<“该结点不存在，删除错误”<

}

n=p->link->data;//找到删除接结点将数据取出并显示出来（找结点时是找的前一个结点）

cout<<“被删除的结点元素为: ”<

p->link=p->link->link;

//将删除结点的前后结点链接起来

}

链表的删除，插入操作是类似的，要考虑到加入或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。

（4）实验结果与分析

③ 心得体会

本次数据结构实习我收获颇丰，以前学过c语言与c++也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。

附录：

顺序表源代码: #include using namespace std;#define maxsize 50 typedef int TypeData;typedef struct { TypeData data[maxsize];int n;}SeqList;

void makeSeq(SeqList &L)// 据 { int m,n,k;cout<<“请输入线性表长度”<>m;for(n=0;n>L.data[n];} L.n=m;cout<<“您输入的线性表为：”<

输入线性表数输出线性表数据

void insert(SeqList &L)//插入数据 { int a,b,c,k;cout<<“请输入插入的数及其插入的位置”<>a>>b;if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”<b){ L.data[c]=L.data[c-1];c--;} L.data[b]=k;} void delate(SeqList &L)//删除数据 { int wei;cout<<“请输入想要删除数据的位置”<>wei;if(wei<1||wei>L.n){ cout<<“不能在该位置删除”<>a;if(a<=0||a>(L.n)){cout<<“不能在该位置插入”<

cout<<“删除 2”<>xuanze;switch(xuanze){ case 1: insert(L);break;case 2: delate(L);break;case 3: find(L);break;case 4: showSeq(L);break;default :break;} } }

单链表源代码：

#include using namespace std;typedef int DataType;typedef struct node{ DataType data;struct node *link;}linknode,*linklist;

linklist chushihua(){ linklist L;L=(linklist)malloc(sizeof(linknode));L->link=NULL;cout<<“开辟空间成功，头结点建立”<>a;linklist p,q;

p=l;while(p->link!=NULL){ p=p->link;k++;} for(int i=0;i>q->data;q->link=p->link;p->link=q;p=q;} } void show(linklist l){ cout<<“链表数据为：”<link;while(p!=NULL){ cout<

data<<“ ”;p=p->link;} cout<>m;linklist p;p=l->link;while(p&&ilink;i++;} if(!p){ cout<<“链表没有这么长,查找错误”<data<

{ linklist p,q;int m,n,i=0;

cout<<“请输入您要插入的结点位置及插入的数据”<>m>>n;p=l;while(p&&ilink;i++;} if(p==NULL){ cout<<“不能在该位置插入，插入错误”<

q=(linklist)malloc(sizeof(linknode));q->data=n;q->link=p->link;p->link=q;}

void delate(linklist &l){ linklist p;int m,n,i=0;cout<<“请输入想要删除的结点位置”<>m;p=l;while(p&&ilink;i++;} if(p==NULL){ cout<<“该结点不存在，删除错误”<link->data;cout<<“被删除的结点元素为: ”<link=p->link->link;} void main(){ linklist L;int select;

L=chushihua();

while(1){ cout<<“请选择功能”<>select;switch(select){

case 1: shuru(L);break;case 2: insert(L);break;case 3: delate(L);break;case 4: find(L);break;case 5: show(L);break;default :break;} } }

第二篇：数据结构试验报告

实验一：ADT的类C描述向C程序的转换实验(2学时)

实验目的：

(1)复习C语言的基本用法；

(2)学会用类C的语言对算法进行描述的方法，将类C算法转换成C源程序的方法和过程；

(3)抽象数据类型的定义和表示、实现；

(4)加深对数据的逻辑结构和物理结构之间关系的理解；(5)初步建立起时间复杂度和空间复杂度的概念。实验内容：(类C算法的程序实现)(1)输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果； 实验准备：

1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：

1.安装TC并设置好环境，如果已安装好，可以跳过此步； 2.录入程序代码并进行调试和算法分析；

对实验内容(1)的操作步骤：1)用类C语言描述算法过程；2)用C语言环境实现该算法。

对实验内容(2)的操作步骤：1)完成算法的C实现；2)分析其时间复杂度和空间复杂度。

3.编写实验报告。

实验结果：// 动态分配数组空间 #include #include

int size,i;int *pArray;int *p;void malloc_size(){ pArray=(int *)malloc(size*(sizeof(int)));}

int input_size(){ printf(“please input the size:n”);printf(“size= ”);scanf(“%d”,&size);return 0;}

int input_data(){ printf(“please input the value:n”);for(i=0;i

printf(“pArray[%d]= ”,i);

scanf(“%d”,&pArray[i]);} return *pArray;}

int Compare(){ int x,y,i;x=y=p[0];for(i=0;i

if(x>=p[i])x=p[i];

if(y<=p[i])y=p[i];} printf(“min= %dt

max=%dn”,x,y);return 0;}

int Output_data(){ p=pArray;printf(“before ofpaixu :n”);for(i=0;i

printf(“%dt”,*pArray);

pArray++;} printf(“n”);return *pArray;}

void paixu(){ int x=0;int i,j;printf(“later of paixu:n”);for(i=0;i

for(j=i+1;j

{

if(p[i]>=p[j])

{

x=p[i];p[i]=p[j];p[j]=x;

}

}

printf(“%dt”,p[i]);} printf(“n”);}

void main(){ clrscr();input_size();malloc_size();input_data();Output_data();Compare();paixu();}

实验结果：

实验二

线性表及其基本操作实验(2学时)实验目的：

(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序；

(3)掌握线性表的顺序存储结构和动态存储结构之区分。

实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算； 实验准备：

1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：

1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//线性链表

#include #include #define M 6

typedef struct node { int data;struct node *next;}*Sqlist;

void Initlialize(Sqlist &L){ L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;}

int Getlength(Sqlist L){ int i=0;Sqlist p=L->next;while(p!=NULL){

i++;

p=p->next;}

return i;}

int Getelem(Sqlist L,int i){

int j=1,e;Sqlist p=L->next;while(j

p=p->next;

j++;}

e=p->data;printf(“第 %d 个元素是：%dn”,i,e);return 1;}

int Locatelem(Sqlist L,int x){

int i=0;Sqlist p=L->next;while(p!=NULL&&p->data!=x){

p=p->next;

i++;} if(p==NULL)

return 0;else

{

printf(“%d 是第 %d 个元素n”,x,i);return i;} }

void CreatlistF(Sqlist &L,int a[ ],int n){ Sqlist s;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;for(i=0;i

s=(Sqlist)malloc(sizeof(Sqlist));

} }

void CreatlistR(Sqlist &L,int a[],int n){

Sqlist s,r;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;r=L;for(i=0;i

s=(Sqlist)malloc(sizeof(Sqlist));

s->data =a[i];

s->next=NULL;

r->next =s;r =s;} }

int Inselem(Sqlist &L,int i,int x){ int j=1;Sqlist s,p=L->next;s=(Sqlist)malloc(sizeof(Sqlist));s->data =x;s->next =NULL;if(i<1||i>Getlength(L))

return 0;while(j

p=p->next;j++;} printf(“在第 %d 个位置插入数据：%dn”,i,x);s->next =p->next;

p->next =s;return 1;}

int Delelem(Sqlist &L,int i){

int j=1;

Sqlist p,q;

p=L;

if(i<1||i>Getlength(L))

return 0;s->data =a[i];

s->next =L->next;L->next =s;

while(j

{

p=p->next;

j++;

}

q=p->next;

p->next =q->next;

free(q);

return 1;}

void Displist(Sqlist L){ Sqlist p=L->next;

while(p!=NULL)

{

printf(“%dt”,p->data);

p=p->next;

}

printf(“n”);}

void input(int *pArray,int n){

printf(“请输入数组数据(共含 %d 个元):n”,n);

for(int i=0;i

Scanf(“%d”,&pArray[i]);

}

int main(int argc, char* argv[]){ Sqlist L;

int Array[M],Select;initlialize(L);do{

printf(“请输入选择方法（1表示头插法，2表示尾插法,0表示结束）：n”);

scanf(“%d”,&Select);

switch(Select)

{

case 1: printf(“按头插法建立线性表:n”);

input(Array,M);

creatlistF(L,Array,M);

break;case 2: printf(“按尾插法建立线性表:n”);

input(Array,M);

creatlistR(L,Array,M);

break;

}

printf(“原线性表数据为:n”);Displist(L);

Getelem(L,3);

Locatelem(L,2);

Inselem(L,5,5);

printf(“修改后的线性表数据为:n”);

Delelem(L,4);

Displist(L);}while(Select!=0);return 0;} 运行结果:

实验三

栈和队列实验(6学时)实验目的：

(1)熟练掌握栈和队列的抽象数据类型及其结构特点；(2)实现基本的栈和队列的基本操作算法程序。实验内容：(类C算法的程序实现，任选其一)(1)设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP等操作）(必做)；

(2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计与实现（选做）； 实验准备：

1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：

1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//队列存储 #include #define QueueSize 10 typedef int status;

typedef struct sqqueue { char data[QueueSize];int front,rear;}SqQueue;

void InitQueue(SqQueue &qu){ qu.front =qu.rear =0;}

status EnQueue(SqQueue &qu,char x){

if((qu.rear +1)%QueueSize==qu.front)

return 0;qu.rear =(qu.rear+1)%QueueSize;qu.data[qu.rear]=x;return 1;}

status DeQueue(SqQueue &qu,char &x){ if(qu.rear==qu.front)

return 0;qu.front =(qu.front +1)%QueueSize;x=qu.data[qu.front];return 1;}

status GetHead(SqQueue qu,char &x){ if(qu.rear ==qu.front)

return 0;x=qu.data[(qu.front+1)%QueueSize];return 1;}

status QueueEmpty(SqQueue qu){ if(qu.rear==qu.front)

return 1;else

return 0;}

void main(){ SqQueue qu;char e;InitQueue(qu);printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”));

printf(“inser an”);

EnQueue(qu,'a');

printf(“inser bn”);

EnQueue(qu,'b');

printf(“inser cn”);

EnQueue(qu,'c');

printf(“inser dn”);

EnQueue(qu,'d');

printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”));

GetHead(qu,e);

printf(“Queue of top elem is: %cn”,e);

printf(“show of Queue:n”);

while(!QueueEmpty(qu)){

DeQueue(qu,e);

printf(“%ct”,e);}

printf(“n”);} 实验结果：

（2）//用栈实现对表达式的求值运算

#include #include #include

#define TRUE 1 #define FALSE 0 #define OK #define ERROR 0 #define INFEASIBLE-1 #define OVERFLOW-2 #define STACK_INIT_SIZE

#define STACKINCREMENT 10

typedef int Status;typedef char ElemType;

typedef ElemType OperandType;

typedef char OperatorType;

typedef struct {

ElemType *base;

ElemType *top;

int stacksize;}SqStack;

Status InitStack(SqStack &S){

S.base =(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));

if(!S.base)exit(OVERFLOW);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;}

Status GetTop(SqStack S){

ElemType e;

if(S.top == S.base)return ERROR;

e = *(S.top-1);

return e;}

Status Push(SqStack &S,ElemType e)

{

if(S.top1 < n){

merge(r, r1, i, i+length-1, i + 2*length1 < n-1)

merge(r, r1, i, i+length-1, n-1);

else

for(j = i;j < n;j++)r1[j] = r[j];}

void MergeSort(SortObject * pvector){

RecordNode record[MAXNUM];

int length = 1;

while(length < pvector->n){

mergePass(pvector->record, record, pvector->n, length);

length *= 2;

mergePass(record, pvector->record, pvector->n, length);

length *= 2;

} }

SortObject vector = {8, 49,38,65,97,76,13,27,49};

int main(){

int i;printf(“排序前序列为：”);

for(i = 0;i < 8;i++)

printf(“%d ”, vector.record[i]);printf(“n”);

MergeSort(&vector);printf(“采用归并排序为：”);

for(i = 0;i < 8;i++)

printf(“%d ”, vector.record[i]);

getchar();

return 0;}

实验结果：

实验十

查找实验(2学时)* 实验目的：

(1)熟练掌握各种静态查找表方法(顺序查找、折半查找、索引顺序表等)；(2)熟练掌握二叉排序树的构造方法和查找算法；

(3)了解和掌握其它查找方法。

实验内容：(类C算法的程序实现，除顺序查找算法之外，任选一个)(1)顺序查找算法的实现(必做)；(2)折半查找算法的实现(选做)； 实验结果：//查找实验

1、顺序查找：

#include #define LENGTH 20

void SequenceSearch(int *fp,int Length){

int data;

printf(“开始使用顺序查询.请输入你想要查找的数据: ”);

scanf(“%d”,&data);

for(int i=0;i

if(fp[i]==data)

{

printf(“数据%d 是第 %d 个数据n”,data,i+1);

return;

}

printf(“未能查找到数据%d.n”,i,data);}

void main(){

int count;

int arr[LENGTH];

printf(“请输入你的数据的个数:”);

scanf(“%d”,&count);

printf(“请输入 %d 个数据:”,count);

for(int i=0;i

scanf(“%d”,&arr[i]);

SequenceSearch(arr,count);}

实验结果：

2、折半查找：

#include #include #define M 10

typedef struct { char *elem;

int length;

}SStable;

void Create(char **t)

{ int i;static char a[M+1];*t=a;for(i=1;i<=M;i++){

printf(“A[%d] is:”,i);

scanf(“%c”,&a[i]);

if(a[i]!= 'n')getchar();} }

int Searth(char *t,char k){ int i;for(i=M;i>=0 && t[i]!=k;i--);

Return i;}

void output(char *t){ int i;for(i=1;i<=M;i++)

printf(“n

A[%d] is %c”,i,t[i]);}

void px(char *t)

{ char s;int i,j;for(i=1;i<=M;i++)

for(j=i+1;j<=M;j++)

{

if(t[i]>t[j]){s=t[i];t[i]=t[j];t[j]=s;}

} }

int Search_bin(char *t,char k){ int low=1,high=M,mid;while(low<=high){

mid=(low+high)/2;

if(k==t[mid])return mid;

else if(k

else low=mid+1;} return 0;}

void main(){ char *t,k;int s;Create(&t);output(t);printf(“nplease input you search char:”);k=getchar();s=Searth(t,k);if(s>=0)printf(“1: use search find is A[%d]n”,s);else printf(“1:can not find itn”);px(t);output(t);s=Search_bin(t,k);if(s==0)printf(“n1:can not find it n”);else printf(“n2:use Search_bin find is A[%d]n”,s);getchar();}

实验结果：

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

实验报告

课程名：数据结构

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

撰写时间：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;}

四、运行结果

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

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

#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++的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。

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

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