辽宁工程技术大学上机实验报告 作者邮箱：2904305706@qq.com 实验名称 线性表的合并 1、掌握顺序表的基本操作 2、实现线性表的合并 C语言程序开发环境 Visual C++ 6.0 成绩 教师 实验 目的 实验 准备
实验 内容 1.问题分析及结构选择 结构选择：根据实验要求，本实验采用线性表的顺序存储结构。 问题分析：先创建空表La ,Lb, Lc，再对其进行初始化并分配存储空间。 向La和Lb中输入数据元素，开始遍历La 和L b 中的元素，并比较大小，将较小的元素插入Lc中，遍历结束后，若La 和Lb中还有剩余元素，则将剩余元素插入到Lc中，即实现了La和Lb的合并。 2.主要存储结构及定义 用动态分配的的一维数组来描述顺序存储结构，其具体定义如下： #define LIST_INIT_SIZE 100//线性表存储空间的初始分配量 #define LISTINCREMENT 10//线性表存储空间的存储增量 typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }sqlist; 3.各函数及说明 Status InitList_sq(sqlist &L); //构造一个空的线性表 Status ListInsert_Sq(sqlist &L,int i,ElemType e); //在顺序线性表L中第i个元素之前插入元素e Status MergeList(sqlist La,sqlist Lb,sqlist &Lc;); //已知顺序线性表La和Lb的元素按值非递减排列 //归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列 4.主要功能函数算法流程 Status InitList_sq(sqlist &L); { 第一步:分配存储空间 L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); 第二步：初始表长和存储容量 L->length=0; L->listsize=LIST_INIT_SIZE; } Status ListInsert_Sq(sqlist *L,int i,int e) { 第一步：判断存储空间是否不足，不足则增加分配
实验 内容 if(L->length>=L->listsize) newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int)); 第二步：插入e,并进行元素右移 q=&(L->elem[i-1]); for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p; *q=e; } Status MergeList(sqlist La,sqlist Lb,sqlist *Lc) { 第一步：给Lc分配存储空间 pa=La.elem;pb=Lb.elem; Lc->listsize=Lc->length=La.length+Lb.length; pc=Lc->elem=(int *)malloc((Lc->listsize)*sizeof(int)); 第二步：遍历La和Lb中的元素，并比较大小，将较小的元素插入Lc中 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while((pa<=pa_last)&&(pb<=pb_last)){ if(*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } 第三步：La和Lb中还有剩余元素，则将剩余元素插入到Lc中 while(pa<=pa_last) *pc++=*pa++; while(pb<=pb_last) *pc++=*pb++; } main() { sqlist La,Lb,Lc; 第一步：创建La，向La输入数据 InitList_sq(&La); 第二步：创建Lb，向Lb输入数据 InitList_sq(&Lb); 第三步：将La和Lb合并为Lc，并将Lc输出 MergeList(La,Lb,&Lc); }
5.调试主要问题及解决方案 序号 01 02 03 调试 过程 问题 类型 调用 指针 逻辑 问题描述 函数调用出错 指针使用各式错误 逻辑混乱 解决办法 修改实参列表 改为正确格式 梳理逻辑，改正代码 本次实验的收获、体会、经验、问题和教训： 通过本次实验，我总结了数据结构这门课程学习过程中的一些问题。虽然老师在课堂上讲的以及书本上的知识能够理解，但是一旦上机进行实验时，自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到实验 总结 自己的程序中再加以必要的连接以完成程序的编写，希望自己能够在接下来的学习中对这些问题进行改正 见附页 程序 代码
附页
#include \#include \
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10
typedef struct{ int *elem; int length; int listsize; }sqlist;
int InitList_sq(sqlist *L){
L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); if(!L->elem) exit(0);
L->length=0;
L->listsize=LIST_INIT_SIZE; return 1; }
int ListInsert_Sq(sqlist *L,int i,int e){ int *newbase,*p,*q;
if(i<1||i>L->length+1) return 0; if(L->length>=L->listsize){
newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int)); if(!newbase) exit(-1); L->elem=newbase;
L->listsize=L->listsize+LISTINCREMENT; }
q=&(L->elem[i-1]);
for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p; *q=e;
++L->length; return 1; }
void MergeList(sqlist La,sqlist Lb,sqlist *Lc){ int *pa,*pb,*pc; int *pa_last,*pb_last; pa=La.elem;pb=Lb.elem; Lc->listsize=Lc->length=La.length+Lb.length; pc=Lc->elem=(int *)malloc((Lc->listsize)*sizeof(int));