数据结构实验一（顺序表基本操作）.doc

实验1: 顺序表基本操作一、 实验目的1・学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表 的一些基木操作和具体的函数定义2•掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集 等运算3•掌握对多函数程序的输入、编辑、调试和运行过程二、 实验要求1. 预习C语言中结构体的定义与基本操作方法2. 对顺序表的毎个基本操作用单独的函数实现3. 编写完整程序完成下面的实验内容并上机运行4. 整理并上交实验报告三、实验内容：1. 编写程序实现顺序表的下列基本操作：(1) 初始化顺序表Lao(2) 将La置为空表3) 销毁Lao(4) 在La中插入一个新的元素5) 删除La中的某一元素⑹在La中查找某元素，若找到，则返冋它在La中第一次出现的位置, 否则返回07)打卬输出La中的元素值2. 编写程序完成下而的操作：(1) 构造两个顺序线性表La和Lb,其元素都按值非递减顺序排列2) 实现归并La和Lb得到新的顺序表Lc, Lc的元索也按值非递减顺 序排列3) 假设两个顺序线性表La和Lb分别表示两个集合A和B,利用 union_Sq 操作实现 A=A U B o四、思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B,如何实现A=A AB ?* 01_顺序表,cpp -顺序表基本操作*对顺序表的每个基本操作都用单独的函数来实现*水上飘2(X)9年写//dsOl.cpp :定义控制台应川程序的入口点。

#include "stdafx.h"# include#include# includc#include#define L1ST_INIT_SIZE 100#define LISTINCREMENT 1()using namespace std;〃存储空间基址〃当前长度〃当前分配的存储容量typedef struct { double *elem; int length; int listsize;}Sqlist;〃构造一个空的线性表Sqlist InitList( Sqlist &L){L.elem = (double *)malloc(LIST_INIT_SIZE * sizeof(double));if( !L.elem ) exit( -2 );〃存储分配失败L」ength = 0 ;L.listsize = LIST_INIT_SIZE; return L;〃空表长度为0 〃初始存储容量//给线性表随机赋值void Start( Sqlist &L, int a ){L」ength = a ;for( int i = 0; i < a; i++ )L.elemliJ = rand() % 100;〃输出线性表的值 void Output( Sqlist &L)int m ;m = L」ength ;for( int i = 0; i < m; i++ ){if(i% 10==0)cout endl;cout setw(5) L.elem[iJ ; }cout endl;〃使线性表按值非递减排列void Notdegression( Sqlist &L, int a ){int m, n ;n = a - 1 ;while( n ){for( int i = 0; i < (a・l); i++ ){if( L.elem[i] > L.elem[i+1]) {m = L.elem[iJ ;L.elem[i] = L.elem[i+1]; L.clcm[i+1] = m ;}else continue ;〃归并La和Lb,得到元索也按非递减排列的Lc void Merger( Sqlist &La, Sqlist &Lb, Sqlist &Lc )double *pb, *pc, *pa_last, *pb」ast;pa = La.elem ;//pa指向La的基地址pb = Lb.elem ;Lc.listsize = Lc」ength = La.length + Lb.length ;//pb指向Lb的基地址pc = Lc.clcm = (double *)malloc(Lc.listsizc * sizcof(doublc));if( !Lc.elem ) exit( -2 );pa.last = La.elem + La.length - 1 ;〃存储分配失败//La表尾元素的位置//Lb表尾兀素的位置pb_last = Lb.elem + Lb」ength - 1 ;〃实现A = A U Bvoid Union_sq( Sqlist &La, Sqlist &Lb ){double *pa, *pb, *pa_last, *pb_last, *p ;while( pa <= pa_last && pb <= pb_last) {if( *pa < *pb )* pc++ = *pa++ ;else*pc++ = *pb++ ;} whilc( pa <= pa_last)while( pb <= pb_last)* pc++ = * pb++ ;pa = La.elem ; pb = Lb.elem ;pb_last = Lb.elem + Lb」ength - 1 ; pa_last = La.elem + La.length - 1 ; La.listsize += Lb.listsize ;while( pa < pa_last)〃归并La和Lb于Lc〃插入La的剩余元素〃插入Lb的剩余元索//pa指向La的基地址//pb指向Lb的基地址//La农尾元素的位置//Lb表尾元素的位置/*除去La中相等的元素，只留下相等元素中的一个〃被删除元素Z后的元素左移〃将Lb的元素插入到La中if( *pa == *(pa+l)){p = pa ；for( ++p; p <= pa_last; p++ ) *(p-l) = *p ;La」ength—;}pa++ ；}pa_last = La.elem + La」ength - 1 ; while( pb <= pb_last)whilc( *pa != *pb && pa <= pa_last) pa++ ；一元素相等if( pa == (pa_last+1)){*(pa++) = *pb++ ; La」ength++ ;}else〃判断*pb是否与La中的某//La的当前长度增一pb++ ；pa = La.clcm ;pa_last = La.elem + La」ength ・ 1 ;int main(){Sqlist La; Sqlist Lb; Sqlist Lc ;int a, b ;cout ”请输入La的元索个数：H;cin a ;cout endl ”请输入Lb的元素个数：”;cin b ;cout endl;srand(time(NULL));La = InilList( La );Lb = InitList( Lb );Start( La, a );cout "La随机生成的值：” endl;Output( La);Start( Lb, b );cout "Lb随机生成的值：" endl ;Output( Lb);//cin.get();Notdcgrcssion( La, a );cout "La的值按非递减顺序排列：” endl;〃构造线性农La〃构造线性表Lb〃使La元索按非递减排列Output( La);Notdegression( Lb, b );cout "Lb的值按非递减顺序排列：" endl ;〃使Lb元素按非递减排列Output( Lb );Mcrgcr( La, Lb, Lc ); 〃归并 La 和 Lb 于 Lccout "归并La和Lb于Lc,也为非递减排列：" endl;Output( Lc);Union_sq( La, Lb );〃实现A = A U Bcout 11 实现 A = A U B： M endl; Output( La);。