实验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，插入后表仍然有序。 五、实验结果

顺序表源程序： #include using 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<<\"\\n根据所做操作选择以下数字序号：\"<cout<<\"1:创建顺序表 2:执行插入操作 3:执行删除操作\"<>n;

switch (n) { case 1: {

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

cout<<\"请输入插入位置：\"; cin>>i;

第2页

cout<>x; cout<m=Insert_SeqList(L,x,i); if (m==1) cout<<\"插入操作成功！\"<>i; cout<m=Delete_SeqList(L,i); if (m==1) cout<<\"删除操作成功！\"<Show_SeqList(L); break; } case 5: { cout<<\"请输入所要查找的元素值：\"; cin>>x; cout<m=Locate_SeqList(L,x); if (m==0) cout<<\"所查找元素不在顺序表中！\"<第3页

} case 6: {

Sort_SeqList(L); cout<<\"排序操作完成！\"<>x; cout<m=Insert_SeqList_sort(L,x); if (m==1) cout<<\"插入操作成功！\"<SeqList L1,L2,L3; Init_SeqList(L1); Init_SeqList(L2); Init_SeqList(L3);

cout<<\"创建有序表1：\"<cout<<\"有序表1：\"<cout<<\"有序表2：\"<第4页

}

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

L.length=0; }

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

if(L.length==0) cout<<\"空表！\"<void Create_SeqList(SeqList &L)//顺序表创建算法 {

cout<<\"请输入元素个数:\"; cin>>L.length;

cout<<\"依次输入各个元素的值:\"<>L.data[i]; }

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

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

if(i<1||i>L.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(i<1||i>L.length) return 0;

for(int j=i;j第5页

}

int Locate_SeqList(SeqList L,DataType x)//顺序表的按值查找算法 {

int i=0;

while(iif(ivoid Sort_SeqList(SeqList &L) //排序算法 {

int i,k,j;

DataType temp;

for(i=0;itemp=L.data [i]; L.data [i]=L.data [k]; L.data [k]=temp; } } }

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

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

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

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

第6页

int i,j,k; i=j=k=0;

while(iwhile(iwhile(jLC.length=k; }输入输出结果：

图1-1主菜单

第7页

图1-2顺序表的创建和输出操作

图1-3 顺序表的插入操作

图1-4顺序表的删除操作

第8页

图1-5顺序表的排序操作

图1-6有序表的插入操作

图1-7两个有序表的合并操作

单链表的源程序：

第9页

#include \"iostream\" using namespace std;

typedef int DataType; typedef struct node { DataType data; struct node *next; }LNode,*LinkList;

void Init_LinkList(LinkList &L);//创建空单链表

void Create1LinkList(LinkList &L,int n);//前插入法创建单链表的算法 void Create2LinkList(LinkList &L,int n);//后插入法创建单链表的算法 void PrintLinkList(LinkList L);//单链表的输出算法

int InsertLinkList(LinkList &L,int i,DataType x);//单链表的插入算法 int DeleteLinkList(LinkList &L,int i);//单链表的删除算法

void Select_Sort_LinkList(LinkList &L);//链表的排序算法（选择排序） void Insert2(LinkList L,DataType x);//有序表的插入

void Merge(LinkList L1,LinkList L2,LinkList &L3);//两个有序表的合并算法 void menu();//菜单函数

int main() { menu(); return 0; }

void Init_LinkList(LinkList &L)//创建空单链表 { L=new LNode; L->next=NULL; }

void Create1LinkList(LinkList &L,int n)//前插入法创建单链表的算法 { LNode *s; for(int i=1;i<=n;i++) { s=new LNode; cout<<\"请输入第\"<>s->data; s->next=L->next; L->next=s; } }

第10页

void Create2LinkList(LinkList &L,int n)//后插入法创建单链表的算法 { LNode *s,*r=L; for(int i=1;i<=n;i++) { s=new LNode; cout<<\"请输入第\"<>s->data; r->next=s; r=s; } r->next=NULL; }

void PrintLinkList(LinkList L)//单链表的输出算法 { if(L->next==NULL) { cout<<\"空表！\"<next; while(p) { cout<data<<\" \"; p=p->next; } cout<int InsertLinkList(LinkList &L,int i,DataType x)//单链表的插入算法 { int j=0; LNode *p=L,*s; while(p&&jnext; j++; } if(!p||j>i-1) return 0; s=new LNode; s->data=x; s->next =p->next ; p->next =s;

第11页

return 1; }

int DeleteLinkList(LinkList &L,int i)//单链表的删除算法 { if(L->next ==NULL) return -1; int j=0; LNode *p=L,*q; while((p->next !=NULL)&&(jnext ; j++; } if((p->next==NULL)||(j>i-1)) return 0; q=p->next ; p->next =q->next ; delete q; return 1; }

void Select_Sort_LinkList(LinkList &L)//链表的排序算法（选择排序）{ if(L->next ==NULL) { cout<<\"空表，不需要排序！\"<next==NULL) return; for(p=L->next;p->next!=NULL;p=p->next) { s=p; for(q=p->next;q!=NULL;q=q->next) { if(q->datadata) s=q; } if(s!=p) { temp=s->data; s->data=p->data; p->data=temp; } }

第12页

cout<<\"排序成功！\"<void Insert2(LinkList L,DataType x)//有序表的插入 { LNode *p=L,*s; while(p->next!=NULL&&p->next->datanext; s=new LNode; s->data=x; s->next=p->next; p->next=s; cout<<\"插入操作成功！\"<void Merge(LinkList L1,LinkList L2,LinkList &L3)//两个有序表的合并算法{ LNode *p1,*p2,*p3,*s; p1=L1->next ; p2=L2->next ; L3=p3=new LNode; L3->next =NULL; while(p1&&p2) { s=new LNode; if(p1->data data ) { s->data =p1->data ; p1=p1->next ; } else { s->data =p2->data ; p2=p2->next ; } p3->next =s; p3=s; } if(p1) p3->next =p1; if(p2) p3->next =p2; }

第13页

void menu()//菜单函数 { LinkList L; Init_LinkList(L); int m; while(1) { cout<<\"\\n根据所做操作选择以下数字序号：\"<cout<<\"1:前插入创建单链表 2:尾插入创建单链表 3:执行插入操作\"<>n;

switch (n) { case 1: {

cout<<\"请输入结点个数：\"; cin>>i; Create1LinkList(L,i); PrintLinkList(L); break; } case 2: {

cout<<\"请输入结点个数：\"; cin>>i; Create2LinkList(L,i); PrintLinkList(L); break; } case 3: {

cout<<\"请输入插入位置：\"; cin>>i; cout<>x; cout<if (InsertLinkList(L,i,x)==1) cout<<\"插入操作成功！\"<cout<<\"插入位置不合法！\"<第14页

case 4: {

cout<<\"请输入删除位置：\"; cin>>i; cout<>x; cout<>i;

Create2LinkList(L1,i); Select_Sort_LinkList(L1);

第15页

}

cout<<\"创建有序表2：\"<>i;

Create2LinkList(L2,i); Select_Sort_LinkList(L2); cout<<\"有序表1：\"<cout<<\"有序表2：\"<case 0:return; } }

输入输出结果：

图2-1主菜单

图2-2创建单链表（用头插入法）

第16页

图2-3创建单链表（用尾插入法）

图2-4单链表的插入操作

图2-5单链表的插入操作（插入位置不合法情况）

第17页

图2-6单链表的删除操作

图2-7单链表的删除操作（删除位置不合法情况）

图2-8单链表的排序操作

第18页

图2-9有序表的插入操作

图2-10两个有序表的合并操作

建议：代码较长，为了方便阅读和调试，可写成多文件结构！

第19页