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

实验1 顺序表基本操作【实验目的】<1>熟悉C语言的上机环境，掌握C语言的基本结构<2>会定义线性表的顺序存储结构<3>熟悉对顺序表的一些基本操作<4>熟悉与线性表相关的函数的定义和使用【实验内容】[实验任务一]顺序表的基本操作1.顺序表的插入操作【操作步骤】<1>启动辅助教学软件<2>选择“C语言”<3>选择“顺序表”<4>选择“顺序表插入”<5>输入建立表的数据<6>输入插入数据元素<7>输入插入位置<8>选择单步执行2.顺序表的删除操作【操作步骤】<1>启动辅助教学软件<2>选择“C语言”<3>选择“顺序表”<4>选择“顺序表插入”<5>输入建立表的数据<6>输入删除位置<7>选择单步执行[实验任务二]编写C语言程序1. 编程实现顺序表的插入操作。

2.编程实现顺序表的删除操作。

实验2 链表的基本操作【实验目的】<1>学会定义单链表的结点类型<2>熟悉单链表的一些基本操作，依据这些操作函数定义<3>掌握线性表的链式存储结构的特点<4>掌握循环链表和双向链表的定义、构造方法等。

【实验内容】[实验任务一]验证单链表的基本操作<1>单链表的插入操作<2>单链表的删除操作[实验任务二]编写C语言程序<1>用C语言实现构造单链表<2>用C语言实现输出单链表实验3 二叉树的基本操作【实验目的】<1>熟悉二叉树的结点结构<2>熟悉二叉树的基本操作<3>学会利用递归方法编写二叉树的遍历算法【实验内容】[实验任务一]二叉树的遍历<1>先序遍历<2>中序遍历<3>后续遍历[实验任务二]编写算法<1>根据二叉树的任一遍历算法，编写求二叉树中结点个数的算法。

实验2 链表基本操作实验一、实验目的1． 定义单链表的结点类型。

2． 熟悉对单链表的一些基本操作和具体的函数定义。

3． 通过单链表的定义掌握线性表的链式存储结构的特点。

二、实验内容与要求该程序的功能是实现单链表的定义和主要操作。

如：单链表建立、输出、插入、删除、查找等操作。

该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。

程序中的单链表（带头结点）结点为结构类型，结点值为整型。

要求：同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。

必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。

三、 算法分析与设计。

头结点......2.单链表插入s->data=x; s->next=p->next; p->next=s;3.单链表的删除：p->next=p->next->next;四、运行结果1.单链表初始化2.创建单链表3.求链表长度4.检查链表是否为空5.遍历链表6.从链表中查找元素7.从链表中查找与给定元素值相同的元素在顺序表中的位置8.向链表中插入元素插入元素之后的链表9.从链表中删除元素删除位置为6的元素(是3)10.清空单链表五、实验体会经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。

六、C语言版原代码# include<stdio.h># include<stdlib.h>/* 定义ElemType 为int类型*/typedef int ElemType;# define TRUE 1# define FALSE 0# define NULL 0# define flag -1/*单链表的结点类型*/typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkedList;/*初始化单链表*/LinkedList LinkedListInit(){LinkedList L;L=(LinkedList)malloc(sizeof(LNode));L->next=NULL;return L;}/*清空单链表*/void LinkedListClear(LinkedList L){L->next=NULL;printf("链表已经清空\n");}/*检查单链表是否为空*/int LinkedListEmpty(LinkedList L){if(L->next==NULL) return TRUE;else return FALSE;}/*遍历单链表*/void LinkedListTraverse(LinkedList L) {LinkedList p;p=L->next;if(p==NULL) printf("单链表为空表\n");else{printf("链表中的元素为：\n");while(p!=NULL){printf("%d ",p->data); p=p->next;}}printf("\n");}int LinkedListLength (LinkedList L){LinkedList p;int j;p=L->next;j=0;while(p!=NULL){j++;p=p->next;}return j;}LinkedList LinkedListGet(LinkedList L,int i) {LinkedList p;int j;p=L->next;j=1;while(p!=NULL&&j<i){p=p->next;j++;}if(j==i) return p;else return NULL;}int LinkedListLocate(LinkedList L,ElemType x) {LinkedList p;int j;p=L->next;j=1;while(p!=NULL&&p->data!=x){p=p->next;j++;}if(p) return j;else return 0;}void LinkedListInsert(LinkedList L,int i,ElemType x) {LinkedList p,s;int j;j=1;p=L;while(p&&j<i){p=p->next;j++;}if(p==NULL||j>i)printf("插入位置不正确\n");else{s=(LNode *)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;printf("%d 已插入到链表中\n",x);}}void LinkedListDel(LinkedList L,int i) {LinkedList p,q;int j;j=1;p=L;while(p->next&&j<i){p=p->next;j++;}if(p->next==NULL)printf("删除位置不正确\n");else{q=p->next;p->next=q->next;free(q);printf("第%d 个元素已从链表中删除\n",i);}}LinkedList LinkedListCreat(){LinkedList L=LinkedListInit(),p,r;ElemType x;r=L;printf("请依次输入链表中的元素，输入-1结束\n"); scanf("%d",&x);while(x!=flag){p=(LinkedList)malloc(sizeof(LNode));p->data=x;r->next=p;r=p;scanf("%d",&x);}r->next=NULL;return L;}int scan(){int d;printf("请选择要进行的操作\n");printf("-------------------------------------------------------\n"); printf("1.初始化 2.清空 3.求链表长度 4.检查链表是否为空\n"); printf("-------------------------------------------------------\n"); printf("5.遍历链表 6.从链表中查找元素\n");printf("-------------------------------------------------------\n"); printf("7.从链表中查找与给定元素值相同的元素在顺序表中的位置\n"); printf("-------------------------------------------------------\n"); printf("8.向链表中插入元素 9.从链表中删除元素 10创建线性表\n"); printf("-------------------------------------------------------\n"); printf("其他键退出。

实验二链表的基本操作链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表的基本操作包括插入、删除和查找节点，这些操作在实际编程中非常常见且重要。

我们来看链表的插入操作。

链表的插入操作可以将新节点插入到链表的任意位置，包括链表的头部、尾部或者中间位置。

插入操作的具体步骤如下：1. 创建一个新节点，并为新节点赋值。

2. 将新节点的指针指向原链表中要插入位置的前一个节点。

3. 将原链表中要插入位置的前一个节点的指针指向新节点。

4. 将新节点的指针指向原链表中要插入位置的后一个节点。

接下来是链表的删除操作。

链表的删除操作可以删除链表中的任意节点，包括链表的头部、尾部或者中间位置。

删除操作的具体步骤如下：1. 找到要删除的节点的前一个节点。

2. 将要删除的节点的前一个节点的指针指向要删除的节点的下一个节点。

3. 释放要删除的节点的内存空间。

最后是链表的查找操作。

链表的查找操作可以根据节点的值或者位置来查找节点。

查找操作的具体步骤如下：1. 遍历链表，依次比较节点的值或者位置，直到找到目标节点。

2. 返回目标节点的值或者位置。

除了基本的插入、删除和查找操作，链表还有一些其他的操作，如获取链表的长度、反转链表等。

获取链表的长度可以通过遍历链表并计数节点的数量来实现。

反转链表可以通过修改节点的指针的指向来实现，具体步骤如下：1. 遍历链表，依次修改每个节点的指针的指向，将指针指向上一个节点。

2. 最后将头节点的指针指向空。

链表的基本操作在实际编程中非常常见且重要。

它们可以用于实现各种功能和算法，如链表的排序、合并两个链表等。

在使用链表的过程中，我们需要注意链表为空或者操作位置无效的情况，以避免出现错误。

链表是一种常见的数据结构，具有灵活性和高效性。

了解链表的基本操作对于编程非常重要，它们可以帮助我们实现各种功能和算法。

通过学习和掌握链表的基本操作，我们可以更好地应用链表来解决实际问题。

实验一顺序表和单链表的基本操作的实现一、顺序表实验内容：1.编写函数,通过数组,建立一个顺序表。

2.编写函数,实现对该顺序表的遍历。

3.编写函数,在顺序表中进行顺序查找某一元素,查找成功则返回其存储位置i,否则返回错误信息。

4.编写函数,实现在顺序表的第i个位置上插入一个元素e的算法。

5.编写函数,实现删除顺序表中第i个元素的算法。

6.编写函数,实现输入一个元素data,把它插入到有序表中,使顺序表依然有序。

7.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

实验目的及要求：1.掌握顺序表的存储结构形式及其描述2.掌握顺序表的建立、查找、插入和删除操作。

实验程序：#include <stdio.h>#include <stdlib.h>#define M 100 //最大限void creat_list(int a[], int n); //建立顺序表void datafind_list(int a[],int d); //按值查找元素void find_list(int a[],int i); //按位查找元素void in(int a[], int i,int e); //插入接点void delet(int a[], int i); //删除接点void print_list(int a[] ); //打印顺序表int main(){int a[M];int data;int num;int place; int ch;printf("输入数据个数：");scanf("%d",&num);creat_list(a, num);print_list(a);while(1){printf("请选择操作：\n");printf("***************************************************************\n") ;printf("1.按值查找 2.按位查找 3.插入接点 4.删除接点 \n");printf("***************************************************************\n") ;scanf("%d",&ch);switch(ch){case 1:printf("Pleae enter the data you want to find:\n"); //按值查找scanf("%d",&data);datafind_list(a,data);break;case 2:printf("Pleae enter where you want to find:\n"); //按位查找scanf("%d",&place);printf("The place is :%d\n",place);find_list(a, place);break;case 3:printf("Pleae enter where you want to insert:\n"); //插入接点scanf("%d",&place);printf("input a data what you want to insert");scanf("%d",&data);in(a,place,data);print_list(a); break;case 4:printf("Pleae enter where you want to delet:\n"); //删除接点scanf("%d",&place);printf("The place is :%d\n",place);printf("Pleae enter where you want to delet:\n");scanf("%d",&place);printf("The place is :%d\n",place);delet(a, place);print_list(a);break;default: printf("输入错误，请重新选择");break;}}return 0;}void creat_list(int a[], int n) //建立顺序表{ int i;int j;int x;printf("输入数据：");scanf("%d",&a[1]);for (i = 2; i <= n; i++){ scanf("%d",&x);for (j = 1; j <= i - 1; j++){ if (x == a[j]){break;} }if (j > i - 1){a[i] = x;}elsei--;}a[0] = n;}void datafind_list(int a[],int d) //按值查找元素{ int i;int j=0;for(i=1;i<=a[0];i++){if(d==a[i])printf("the data is %d and its place is %d\n",d,i);else j++;}if (j==a[0]){printf("error\n");}}void find_list(int a[],int i) //按位查找{if (i < 1 || i > a[0] + 1){printf("error");}else printf("%5d",a[i]);}void in(int a[], int i,int e) //插入表中某个元素{ int j;if (i < 1 || i > a[0] + 1){printf("error");}else{ a[0] = a[0] + 1;for (j = a[0]; j >i; j--) //后移插入位置后的数{a[j] = a[j-1];}a[i]=e;}}void delet(int a[], int i) //删除表中某个元素{ int j;if (i < 1 || i > a[0] + 1){printf("error");exit(0);}for (j = i + 1; j <= a[0]; j++) //前移被删数的位置 {a[j - 1] = a[j];}a[0] = a[0] - 1;}void print_list(int a[] ) //打印顺序表{ int i;printf("\n");printf("顺序表是：");for (i = 1; i <= a[0]; i++){printf("%5d",a[i]);}printf("\n");}实验结果：实验分析：实验成功实现顺序表的基本操作！成功完成本实验，需要掌握顺序表的结构和理解顺序表结构的实验原理。

实验2链表的基本操作一、需求分析1，初始化链表2，调用插入函数建立一个链表3，链表的插入和删除4，链表元素的查找4，将链表分为奇链表和偶链表5，链表的逆置二、概要设计1.基础题1)编写链表基本操作函数typedefstruct list{Int data;Struct list* next}LIST;LIST* InitList() //初始化LIST* InsertList(LIST * L,int item,int re) //向链表指定位置插入元素LIST* InsertOrderList(LIST *L,int item) //向有序链表指定位置插入元素void FindList(LIST*L, int item)//查找链表中的元素void display(LIST *L)//显示链表void divide(LIST* La, LIST *Lb)//拆分链表LIST * turn(LIST *L)//转置链表2)调用上述函数实现下列操作，操作步骤如下。

A.初始化链表B.调用插入函数建立一个链表C.在链表中寻找指定的元素D.在链表中删除指定值的元素E.遍历并输出链表注意每完成一个步骤，必须及时输出顺序表元素，便于观察操作结果2.提高题a)将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a，b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

解题思路将单链表A中含有序号为偶数的元素删除，并在删除时把这些结点链接起来构成单链表B即可。

b)将链接存储线性表逆置，即最后一个结点变成第一个结点原来倒数第二个结点变成第二个结点，如此等等。

解题思路依次遍历源链表，将每个元素依次赋给一个新链表并将新链表从后到前连接。

3.主函数void main(){LIST *L1,*L2,*L3;int i;L1=InitList();printf("创建链表L1:\n");for(i=1;i<=5;i++){L1=InsertList(L1,i*2,i);}display(L1);for(i=1;i<=9;i+=4){printf("在L1的%d位置插入3:\n",i);L1=InsertList(L1,3,i);display(L1);}//有序表L2 = InitList();printf("\n有序表实验:\n");printf("创建链表L2:\n");for (i = 1; i <= 5; i++){L2 = InsertList(L2, i * 2, i); }display(L2);for (i = 1; i <= 13; i +=6 ){printf("插入%d:\n",i);L2 = InsertOrderList(L2,i);display(L2);}//删除元素实验printf("\n删除元素实验:\n"); printf("L2插入1:\n", i);L2 = InsertList(L2,1,1);display(L2);for (i = 1; i < 12; i += 5){printf("删除L2中%d\n",i);L2 = DeleteList(L2, i);display(L2);}//查找printf("\n查找元素实验:\n"); printf("查找L2中%d\n", 13); FindList(L2,13);printf("查找L2中%d\n", 6); FindList(L2, 6);//分解printf("\n分解实验:\n");printf("L2:\n");display(L2);L3 = InitList();printf("将L2偶序数拆分到L3\n"); divide(L2,L3);printf("L2:\n");display(L2);printf("L3:\n");display(L3);printf("\n逆序实验:\n");printf("L2:\n");display(L2);L2 = turn(L2);printf("转置L2:\n");display(L2);}三、详细分析插入实验，函数能够在链表前、中、后插入元素，并判断插入位置是否超过链表长度，若超过则接入链尾。

实验一顺序表与链表
姓名：学号：实验日期：
教师评语：
一、实验目的
1、掌握线性表中元素的前驱、后继的概念。

2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。

3、对线性表相应算法的时间复杂度进行分析。

4、理解顺序表、链表数据结构的特点（优缺点）。

二、实验内容和要求
1、试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,a n）逆置为(a n,a n-1,…,a1)。

2、假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各个不相同），现要求另开辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列。

试用单链表编写求C的算法。

3、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。

已知s 为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

三、实验小结
1。

一、实验目的二、实验内容和要求三、源代码1)顺序表的代码2)单链表的代码四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现。

4、掌握顺序表的存储结构形式及其描述和基本运算的实现。

5、熟练掌握动态链表结构及有关算法的设计二、实验内容题目一：顺序表的基本操作[问题描述]实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的顺序表；（2）输出顺序表中的数据元素（3）求顺序表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。

[测试数据] 由学生任意指定。

题目二：单链表的基本操作[问题描述]实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的单链表合并成一个有序单链表。

[测试数据]由学生任意指定。

三、源代码(一)顺序表的基本操作#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct { //结构体ElemType *elem;int length;int listsize;}SqList;SqList Lx;Status InitList_Sq(SqList &L) //分配空间{ L.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,ElemType e) //插入新元素{ int *q,*p;ElemType *newbase;if(i<1 || i>L.length+1) return ERROR;if(L.length>=L.listsize){ newbase=new ElemType[L.listsize+LISTINCREMENT];if(!newbase) exit(OVERFLOW);L.elem=newbase;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 OK;}Status Listlength(SqList L) //长度{ int *p=L.elem; //判断线形表是否存在while(p){ return (L.length); }}Status GetElem(SqList L, int i,ElemType &e) //取元素{ if(i<1 || i>L.length)return ERROR;else{ e=L.elem[i-1];return e;}}void MergeList(SqList La,SqList Lb,SqList &Lc) //合并{ ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ ListInsert(Lc,++k,ai);++i; }else{ ListInsert(Lc,++k,bj);++j; }}while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void show(SqList L,int i) //显示{ int j;ElemType k;cout<<"顺序表显示如下:"<<endl;for(j=0;j<i-1;j++){ k=L.elem[j];cout<<k<<"->"; }if(j==i-1 && i>0){ k=L.elem[j]; cout<<k; }cout<<endl;}void create(SqList &L,int n) //输入元素{ int e;for(int i=0;i<n;i++)L.elem[i]=e;L.length=i+1; }}Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除{ ElemType *p, *q;if(i<1 || i>L.length) return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p) *(p-1)=*p;--L.length;return OK;}Status Listxiugei(SqList &L,int i,ElemType &e) //修改{ if(i<1 || i>L.length)return ERROR;else{ L.elem[i-1]=e;return OK; }}void shuru(SqList &L1) //顺序表的创建{ int a;InitList_Sq(L1);cout<<"请输入顺序表的长度：";cin>>a;cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);}void chaxun(SqList &L1) //取第i个位置的元素{ int j;ElemType e1;cout<<"请选择所要取出元素的位置:";while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>j; }GetElem(L1,j,e1);cout<<"取出的元素为:"<<e1<<endl; }void xiugai(SqList &L1) //修改第i个位置的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要修改元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要修改元素的位置:";cin>>j; }cout<<"要修改成的元素:";cin>>e1;Listxiugei(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a);}void shanchu(SqList &L1) //删除顺序表里的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>j; }ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);}void charu(SqList &L1) //插入元素到顺序表里{ int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>j; }cout<<"要插入的元素:";cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);}void hebing(SqList &L3) //合并两个顺序表{ SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输入第一个有序表的长度："; cin>>a;cout<<"请输入第一个有序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);cout<<"请输入第二个有序表的长度："; cin>>b;cout<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下："; show(L3,a+b);}void main() //主菜单{ int choice;for(;;){ cout<<" 顺序表的基本操作"<<endl;cout<<" 1.顺序表的创建"<<endl;cout<<" 2.顺序表的显示"<<endl;cout<<" 3.顺序表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到顺序表里"<<endl;cout<<" 7.删除顺序表里的元素"<<endl;cout<<" 8.合并两个顺序表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择：";cin>>choice;switch(choice){ case 1: shuru(Lx);break;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度:"<<Listlength(Lx)<<endl;break; case 4: chaxun(Lx);break;case 5: xiugai(Lx);break;case 6: charu(Lx);break;case 7: shanchu(Lx);break;case 8: hebing(Lx);break;case 9: cout<<"退出系统!"<<endl;exit(0);break;default : cout<<"输入有误，请重新选择"<<endl;break; }}}(二)单链表的基本操作#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode //存储结构{ ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n) //尾插法创建单链表{ LinkList p;L=new LNode;L->next=NULL; //建立一个带头结点的单链表LinkList q=L; //使q指向表尾for(int i=1;i<=n;i++){ p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; }}Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素{ LinkList p=L->next;int j=1;while(p&&j<i){ p=p->next;++j; }if(!p||j>i) return error; //第i个元素不存在 e=p->data;return ok;}Status LinkInsert(LinkList &L,int i,ElemType e) //插入{ LinkList p=L;int j=0;while(p&&j<i-1){ p=p->next;++j; } //寻找第i-1个结点 if(!p||j>i-1)return error; //i小于1或者大于表长加1 LinkList s=new LNode; //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;return ok;}Status ListDelete(LinkList &L,int i,ElemType &e) // 删除{ LinkList p=L;LinkList q;int j=0;while(p->next&&j<i-1){ //寻找第i个结点，并令p指向其前驱p=p->next;++j; }if(!(p->next)||j>i-1) return error; //删除位置不合理q=p->next;p->next=q->next; //删除并释放结点e=q->data;delete(q);return ok;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) { //合并两个顺序链表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; }else{ pc->next=pb;pc=pb;pb=pb->next; }}pc->next=pa?pa:pb;delete(Lb);}void show(LinkList L) //显示{ LinkList p;p=L->next;while(p){ cout<<p->data<<"-->";p=p->next; }cout<<endl;}int Length(LinkList L,int i) //表长{ i=0;LinkList p=L->next;while(p){ ++i;p=p->next; }return i;}void xiugai(LinkList L) //修改{ int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输入要修改的元素位置(0<i<length):";cin>>i;GetElem(L,i,e);cout<<"该位置的元素:"<<e<<endl;cout<<"修改后的元素值:";cin>>k;while(p&&j<i){ p=p->next;++j; }m=p->data;p->data=k;cout<<"修改后的单链表显示如下:"<<endl;show(L);}void hebing() //合并两个单链表{ int a,b;LinkList La,Lb,Lc;cout<<"请输入第一个有序链表的长度:"<<endl;cin>>a;cout<<"请输入第一个有序链表的元素共（"<<a<<"个）："<<endl;CreateList(La,a);show(La);cout<<"请输入第二个有序链表的长度:"<<endl;cin>>b;cout<<"请输入第二个有序链表的元素共（"<<b<<"个）："<<endl;CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下："<<endl;show(Lc);}void main() //主函数{ int select;int x;ElemType y;LinkList list;for(;;){ cout<<" 单链表的基本操作"<<endl;cout<<" 1.单链表的创建"<<endl;cout<<" 2.单链表的显示"<<endl;cout<<" 3.单链表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到单链表里"<<endl;cout<<" 7.删除单链表里的元素"<<endl;cout<<" 8.合并两个单链表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择:";cin>>select;switch(select){ case 1:cout<<"请输入单链表的长度:"<<endl;cin>>x;cout<<"请输入"<<x<<"个元素"<<endl;CreateList(list,x);break;case 2: cout<<"单链表显示如下:"<<endl;show(list);break;case 3: int s;cout<<"单链表的长度为:"<<Length(list,s)<<endl;break;case 4: cout<<"请选择所要取出元素的位置:";while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>x; }GetElem(list,x,y);cout<<"该位置的元素为:"<<y<<endl;break;case 5: xiugai(list); break;case 6: cout<<"请选择要插入的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>x; }cout<<"要插入的元素值:";cin>>y;LinkInsert( list,x,y);cout<<"插入后单链表显示如下:"<<endl;show(list);break;case 7: cout<<"请选择要删除的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>x; }ListDelete(list,x,y);cout<<"要删除的元素值:"<<y<<endl;cout<<"删除后的单链表显示如下:"<<endl;show(list);break;case 8: hebing();break;case 9: exit(0);default : cout<<"输入有误，请重新输入"<<endl;break;}}}四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。