工学院 数据结构实验报告

数据结构实验报告

湖南师范大学工程与设计学院

数据结构实验报告

姓 名：钟智君 年 级：2013

专 业：计算机科学与技术 学 号：2013180502 任课教师：肖柳明

开课时间：2014~2015学年第一学期

- 1 -

数据结构实验报告

实验（一） 实验时间 2014年11月14日下午1：00—4：00 实验地点 工程与设计学院前栋403 实验题目 线性表的存储及操作 实验目的 1) 掌握顺序存储结构和链式存储结构的特点； 2) 掌握常见算法。 已知两个按元素值有序的线性表A和B，编程实现：将A和B有序归并成一个按元素值有序的线性表。 实验内容 - 2 -

数据结构实验报告

一、算法基本思想：

1) 从键盘输入两个按元素值有序的线性表A和B的值；

2) 根据输入把数据元素分别以顺序存储结构和线性链表存储； 3) 有序归并成一个新的按元素值有序的线性表C； 4) 输出显示合并后的线性表C。 测试数据：A=（3,5,8,11），B=（2,6,8,9,11,15,20） 二、

顺序存储结构： typedef struct{ int elem[100]; int length; int listsize; }SqList; t

链式存储结构：

typedef struct LNode{ int data;

struct LNode *next; }LNode,*LinkList; int create_sq(SqList &a,int n){} int displaya(SqList &a){}

结构定义：

int create_List(LinkList &b,int n){} int displayb(LinkList b){}

void getList_Sq(SqList a,LinkList b,LinkList c){} void getList_Sq1(SqList a,LinkList b,SqList &c){} int display(SqList c){} int displayc(LinkList b){}

- 3 -

数据结构实验报告

int main(int argc, char *argv[]){} 三、

算法描述：

设两个指针分别指向LA表和LB表中某个元素，若设i当前所指元素为a，j当前所指元素为b，则插入LC中元素c=min（a，b）。i和j的初值都为1，在所指元素插入LC后，在LA和LB中顺序后移。

创建顺序表：

int create_sq(SqList &a,int n) {

int num; int i=0;

while(i

cin>>num; a.elem[i]=num; a.length=i++; } return 1; } 创建链表

int create_List(LinkList &b,int n) {

LNode *q=b; q->next=NULL; LNode *p;

for(int i=n;i>0;--i) {

int num;

p=(LinkList)malloc(sizeof(LNode));

- 4 -

数据结构实验报告

cin>>num; p->data=num; p->next=NULL; q->next=p; q=q->next; } }

有序归并两个表： 顺序存储

void getList_Sq1(SqList a,LinkList b,SqList &c) {

int k=0,i=0;

while(b!=NULL||kb->data) {

c.elem[i++]=b->data; c.length=i-1; b=b->next; } else {

c.elem[i++]=a.elem[k++]; c.length=i-1; }

while(b!=NULL) {c.elem[i++]=b->data; b=b->next; c.length=i-1;}

- 5 -

数据结构实验报告

while(k

c.elem[i++]=a.elem[k++]; k++;

c.length=i-1; } return; } 链式存储

void getList_Sq(SqList a,LinkList b,LinkList c) {

int k=0; LNode *p=c;

while(b->next!=NULL||k<=a.length) if(a.elem[k]>b->data) {

p->next=b; p=b; b=b->next; p->next=NULL; } else {

LNode *q=(LinkList)malloc(sizeof(LNode)); q->data=a.elem[k]; p->next=q; p=q;

p->next=NULL; k++;

- 6 -

数据结构实验报告

}

while(b!=NULL) {p->next=b; p=b; b=b->next;} while(k<=a.length) { while(1);

LNode *q=(LinkList)malloc(sizeof(LNode)); q->data=a.elem[k]; p->next=q; p=q;

p->next=NULL; k++; } return; } 四、

程序清单：

#include #include

using namespace std; typedef struct{ int elem[100]; int length; int listsize; }SqList; typedef struct LNode{ int data;

struct LNode *next;

- 7 -

数据结构实验报告

}LNode,*LinkList;

int create_sq(SqList &a,int n) {

int num; int i=0;

while(i

cin>>num; a.elem[i]=num; a.length=i++; } return 1; }

int displaya(SqList &a) {

int i=0;

cout<

cout<

cout<

int create_List(LinkList &b,int n) {

- 8 -

数据结构实验报告

LNode *q=b; q->next=NULL; LNode *p; for(int i=n;i>0;--i) {

int num;

p=(LinkList)malloc(sizeof(LNode)); cin>>num; p->data=num; p->next=NULL; q->next=p; q=q->next; } }

int displayb(LinkList b) {

cout<

cout<data<<\ \ b=b->next; }

cout<

- 9 -

数据结构实验报告

void getList_Sq(SqList a,LinkList b,LinkList c) {

int k=0; LNode *p=c;

while(b->next!=NULL||k<=a.length) if(a.elem[k]>b->data) {

p->next=b; p=b; b=b->next; p->next=NULL; } else {

LNode *q=(LinkList)malloc(sizeof(LNode)); q->data=a.elem[k]; p->next=q; p=q;

p->next=NULL; k++; }

while(b!=NULL) {p->next=b; p=b; b=b->next;} while(k<=a.length) { while(1);

LNode *q=(LinkList)malloc(sizeof(LNode));

- 10 -

数据结构实验报告

q->data=a.elem[k]; p->next=q; p=q;

p->next=NULL; k++; } return; }

void getList_Sq1(SqList a,LinkList b,SqList &c) {

int k=0,i=0;

while(b!=NULL||kb->data) {

c.elem[i++]=b->data; c.length=i-1; b=b->next; } else {

c.elem[i++]=a.elem[k++]; c.length=i-1; }

while(b!=NULL) {c.elem[i++]=b->data; b=b->next; c.length=i-1;} while(k

- 11 -

数据结构实验报告

c.elem[i++]=a.elem[k++]; k++; c.length=i-1; } return; } int display(SqList c) {

int i=0;

cout<

cout<

cout<

int displayc(LinkList b) {

cout<

cout<data<<\ \ b=b->next; }

cout<

int main(int argc, char *argv[])

- 12 -

数据结构实验报告

{

SqList a;

LNode *b=(LinkList)malloc(sizeof(LNode)); int n,m,l;

cout<<\请输入a中的数据个数\

cin>>n;

cout<<\请创建a中的数据\ create_sq(a,n); displaya(a);

cout<<\请输入b中的数据个数\

cin>>m;

cout<<\请创建b中的数据\ create_List(b,m); displayb(b->next);

cout<<\请选择你想C要用的存放类型:\

cout<<\数字1,类型为链式存取，数字2为顺序存储,其他错误\ cin>>l; if(l==1) {

LinkList c=(LinkList)malloc(sizeof(LNode)); getList_Sq(a,b->next,c); displayc(c->next); }

else if(l==2) {

SqList c;

getList_Sq1(a,b->next,c); display(c); }

else cout<<\输入错误\

- 13 -

数据结构实验报告

system(\ return EXIT_SUCCESS; } 五、

运行结果：

2 3 5 6 8 8 9 11 11 15 20 六、

分析与总结：

- 14 -

数据结构实验报告

1，顺序存储结构和链式存储结构有所不同，顺序存储结构是在一组连续的地址中进行存储，而链式存储结构则是通过NEXT域找到下一个元素，因此，在定义两种结构时应该区分开来。包括后面的DISPLAY显示函数也要区分开来。

2，在创建两种线性表时，也要注意使数据停止输入的条件.

3，顺序存储结构和链式存储结构不能直接合并，因为两种结构有所不同，所以在编写程序过程中，要把顺序存储结构转化链式存储结构，如果是这种转换方式就需要将C定义为链式存储结构，如果将链式存储结构转化为顺序存储结构，则需要将C定义为顺序存储结构。

4，这是数据结构第一个实验，也是我第一次入手编数据结构的程序。在此实验中，两输入的线性表必须得元素非递减排序，得出来的合并表才会是非递减的。其实这个程序还不完善，必须再加上排序。两种存储方法中，顺序存储结构所需空间开销更大，所以链式存储结构更合理。

- 15 -

数据结构实验报告

- 16 -

本文来源：https://www.bwwdw.com/article/gjb3.html