线性表及其实现（实验二）

实验 二 线性表及其实现

一．实验目的及要求

（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以

线性表的各种操作（建立、插入、删除等）的实现为实验重点；

（2） 通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用； （3） 掌握循环链表和双链表的定义和构造方法

二.实验内容：

（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线

性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。

（2） 建立一个按元素递增有序的单链表L，并编写程序实现： a） 将x插入其中后仍保持L的有序性；

b） 将数据值介于min和max之间的结点删除，并保持L的有序性； c） 将单链表L逆置并输出；

（3） 编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链

表。

三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）

（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作

的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。

? 程序代码：

顺序存储：

头文件：

#define INIT_SIZE 100 #define INCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define INFEASIBLE -1 #define OVERFLOW -2

typedef int Status; typedef int ElemType; typedef struct {

ElemType *elem;

int length; int listsize;

}Sq;

Status Init_Sq(Sq &L);

Status Insert_Sq(Sq &L,int i,ElemType e); Status Delete_Sq(Sq &L,int i,ElemType &e);

主函数：

#include\#include\#include\ int main() {

Sq L;

printf(\、建立\\n\printf(\、退出程序\\n\int a;//选择是否建立 scanf(\switch(a) { case 1: }

printf(\请输入要放入顺序表中的元素个数(不要超过100)\\n\int i;//进行用户输入循环 printf(\请输入具体元素\\n\for(i=0;i

int b;//选择操作 do{

printf(\请选择下列操作\\n\ printf(\、向表中添加元素\\n\ printf(\、删除表中某一元素\\n\ printf(\、退出程序\\n\

scanf(\ Init_Sq(L); break;

printf(\程序结束！\\n\ exit(OVERFLOW);

printf(\是否建立顺序表？\\n\

case 2:

default:printf(\输入错误！\\n\

scanf(\

}

scanf(\ switch(b) { case 1: }

case 3:

printf(\程序结束！\\n\

exit(OVERFLOW);

ElemType x;//新元素

int c;//新元素位置 scanf(\int j;//新表输出循环 printf(\新表为：\\n\for(j=0;j

printf(\}

printf(\break;

printf(\请输入要添加的元素，和添加的位置(空格隔开)\\n\ Insert_Sq(L,c,x);

case 2:

int d;//需要删除元素的位置

ElemType y;//被删除的元素 printf(\请输入删除元素的位置\\n\scanf(\Delete_Sq(L,d,y);

printf(\被删除的元素是%d\\n\printf(\剩下的元素为：\\n\int f;//输出循环 for(f=0;f

printf(\}

printf(\break;

default:printf(\输入出错！\\n\

}while(b!=3); return 0;

功能函数：

#include\#include\#include\

Status Init_Sq(Sq &L) {

L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0;

L.listsize=INIT_SIZE; return OK; }

Status Insert_Sq(Sq &L,int i,ElemType e) {

if(L.length==100) {

int *newpase;

if(!newpase) exit(OVERFLOW); L.elem=newpase; L.listsize+=INCREMENT;

newpase=(ElemType *)realloc(L.elem,(L.length+INCREMENT)*sizeof(ElemType));

}

if(i<1||i>L.length+1) {

return ERROR; }

L.length+=1;

int b=L.length;//用于循环 while(i<=b) {

L.elem[b]=L.elem[b-1];

b--; }

L.elem[i-1]=e; return OK; }

Status Delete_Sq(Sq &L,int i,ElemType &e) {

if(i<1||i>L.length+1) {

return ERROR; }

e=L.elem[i-1]; int j;

for(j=i-1;j

L.elem[j]=L.elem[j+1]; }

L.length-=1; return OK; }

链式存储：

头文件：

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define INFEASIBLE -1 #define OVERFLOW -2

typedef int Status; typedef int ElemType; typedef struct LNode{ ElemType data;

void Create_L(int n,LinkList &L);

Status Insert_L(LinkList &L,int i,ElemType e); Status Delete_L(LinkList &L,int i,ElemType &e); Status GetElem_L(LinkList L,int i,ElemType &e);

主函数：

#include\#include\ int main() {

printf(\是否建立链表\\n\ int a;//选择

struct LNode *next; }LNode,*LinkList;

本文来源：https://www.bwwdw.com/article/79wt.html