实验1-2顺序表和链表基本操作

实验1-2顺序表和链表基本操作_参考答案

【综合文库】

实验1、2：线性表的应用参考代码

一、实验预备知识

1．复习C中编写函数的相关内容。

2．复习如何用主函数将多个函数连在一起构成一个C完整程序。二、实验目的

1．掌握线性表的顺序和链式存储结构

2．熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算 3．熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算三、实验要求

1．编写初始化并创建线性表和输出线性表的算法。

2．编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。 3．编写有序表的插入和删除运算算法。

4．编写一个主函数，将上面函数连在一起，构成一个完整的程序。

5．将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。四、实验内容

顺序表实验内容：

1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。 2．初始化并建立顺序表。（开辟的存储空间大小为8） 3．编写顺序表输出算法。

4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次顺序表。

5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次顺序表。 6．编写一个排序算法，对线性表中元素从小到大排列。 7．向有序表分别插入20和50，插入后表仍然有序。（修改开辟的存储空间大小为15）单链表实验内容：

1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。 2．建立一个带表头结点的单链表（前插入法和尾插入法均可）。 3．编写单链表输出算法。

4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次单链表。

5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次单链表。 6．编写一个排序算法，对链表中元素从小到大排列。 7．向有序链表分别插入20和50，插入后表仍然有序。五、实验结果

顺序表源程序： #includeusing namespace std;

const int MAXSIZE=8;//做有序表插入操作时，将8改为15 typedef int DataType;

第1页

typedef struct {

DataType data[MAXSIZE];int length; }SeqList;

void Init_SeqList(SeqList &L);//创建空顺序表算法 void Show_SeqList(SeqList L);//顺序表输出算法 void Create_SeqList(SeqList &L);//顺序表创建算法

int Insert_SeqList(SeqList &L,DataType x,int i);//顺序表的插入算法 int Delete_SeqList(SeqList &L,int i);//顺序表的删除算法

int Locate_SeqList(SeqList L,DataType x);//顺序表的按值查找算法 void Sort_SeqList(SeqList &L);//顺序表的排序算法

int Insert_SeqList_sort(SeqList &L,DataType x);//有序表的插入算法

void Merge(SeqList LA,SeqList LB,SeqList &LC);//两个有序顺序表的合并算法 void menu();//菜单算法

void main()

{menu();}

void menu()//菜单算法 {

SeqList L;

Init_SeqList(L); int m; while(1) { cout<<\根据所做操作选择以下数字序号：\

cout<<\创建顺序表 2:执行插入操作 3:执行删除操作\cout<<\执行输出操作 5:执行查找操作 6:执行排序操作\cout<>n;

switch(n){ case 1:{

Create_SeqList(L);break;} case 2:{

cout<>i;

第2页

cout<x; cout<

m=Insert_SeqList(L,x,i); if (m==1)cout<<\插入操作成功！\ elseif (m==0) cout<<\插入位置不合法！\ else cout<<\发生溢出！\ break; } case 3:{ cout<>i;cout<

m=Delete_SeqList(L,i); if (m==1)cout<<\删除操作成功！\ elseif (m==0) cout<<\删除位置不合法！\ else cout<<\空表！\ break;} case 4:{

Show_SeqList(L);break;} case 5:{ cout<>x;cout<

m=Locate_SeqList(L,x); if (m==0)cout<<\所查找元素不在顺序表中！\ elsecout<<\所查找元素是顺序表的第\个元素！\ break;

第3页

} case 6:{

Sort_SeqList(L); cout<<\排序操作完成！\ break;} case 7:{cout<x; cout<

m=Insert_SeqList_sort(L,x); if (m==1)cout<<\插入操作成功！\ else cout<<\发生溢出！\ break; } case 8:{

SeqList L1,L2,L3;Init_SeqList(L1); Init_SeqList(L2); Init_SeqList(L3);

cout<<\创建有序表1：\Create_SeqList(L1); Sort_SeqList(L1); cout<<\创建有序表2：\Create_SeqList(L2); Sort_SeqList(L2);

cout<<\有序表1：\Show_SeqList(L1);

cout<<\有序表2：\Show_SeqList(L2); Merge(L1,L2,L3); cout<<\合并后：\Show_SeqList(L3);break;} case 0: return; }}

第4页

}

void Init_SeqList(SeqList &L)//创建空顺序表算法 {

L.length=0; }

void Show_SeqList(SeqList L)//顺序表输出算法 {

if(L.length==0) cout<<\空表！\ else for(int i=0;i

void Create_SeqList(SeqList &L)//顺序表创建算法 {

cout<>L.length;

cout<<\依次输入各个元素的值:\ for(int i=0;i>L.data[i]; }

int Insert_SeqList(SeqList &L,DataType x,int i)//顺序表的插入算法{

if(MAXSIZE<=L.length) return -1;

if(iL.length+1) return 0;

for(int j=L.length-1;j>=i-1;j--) L.data[j+1]=L.data[j];L.data[i-1]=x;L.length++;return 1; }

int Delete_SeqList(SeqList &L,int i)//顺序表的删除算法 {

if(L.length ==0) return -1;if(iL.length) return 0;

for(int j=i;j

第5页