数据结构上机实验报告.doc

数据结构实验报告一、 实验题目 顺序表的引用二、 实验内容 有序表的查找与合并三、 实验目的 掌握线性表的概念及原理，运用线性表的原理完成实验题目中的内容。四、 实验要求 为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序代码（写在纸上与盘中均可），以便在实验课中完成老师所布置的实验内容。五、 概要设计原理 让两个指针同时扫描两个顺序表，判断大小，将其中小的一方，输入到新建立的顺序表中，并将小的一方的指针指向后一个元素，一次循环到其中一个指针指向空；六丶详细程序清单及注释说明#include#include#include#include#includeusing namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef ElemType;typedef struct ElemType *elem;int length;int listsize;SqList;typedef int Status;Status InitList_Sq(SqList &L)L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;/构建一个空的线性表Status ListInsert_Sq(SqList &L,int i,ElemType e)int *p;int *q;if(iL.length+1)return ERROR;if(L.lengthL.listsize)L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for(p=&(L.elemL.length);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;/在L的第i个位置之前杀入一个新的元素e,L长度加1Status ListDelete_Sq(SqList &L,int i,ElemType &e)if(iL.length)return ERROR;int *p;int *q;p=&(L.elemi);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;/删除L的第i个数据元素,并用e返回其值,L长度减1void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)int *pa;int *pb;int *pc;int *pa_last;int *pb_last;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=*pb)*pc+=*pc+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;/归并La和Lb,Lc递减排列bool ListEmpty_Sq(SqList L)return !L.length;Status ListDestroy_Sq(SqList &L)free(L.elem);return INFEASIBLE;void main()SqList La;SqList Lb;SqList Lc;InitList_Sq(La);InitList_Sq(Lb);InitList_Sq(Lc);coutLc初始化:endl;coutLc.elem:Lc.elemendl;coutLc.length:Lc.lengthendl;coutLc.listsize:Lc.listsizeendl;cout请输入有序表1:endl;int j;int x;int i=1;docoutj;ListInsert_Sq(La,1,j);coutx;while(x=1);cout有序表1为:;docoutLa.elemi-1 ;i=i+1;while(i=La.length);coutendl;cout请输入有序表2:endl;docoutj;ListInsert_Sq(Lb,1,j);coutx;while(x=1);i=1;cout有序表2为:;docoutLb.elemi-1 ;i=i+1;while(i=Lb.length);coutendl;MergeList_Sq(La,Lb,Lc);i=1;cout合并后:;docoutLc.elemi-1 ;i=i+1