线性表的操作算法

数 据 结 构

实验报告

课题名称：线性表的操作算法 姓名： 班级： 学号：

一、 内容提要

1、 掌握使用cFree上机调试线性表的基本方法；

2、 分别用数组和链表作为存储结构，实现线性表的插入、删除、查找、排序、合并等操作。

二、 实验要求

1、 设计对线性表进行链式存储操作的内容； 2、 写出相应程序；

3、 保存和打印出程序的运行结果，并结合程序进行分析；

三 、实验目的

1、理解数据结构中单链表的定义和建立。 2、掌握单链表中结点结构的C语言描述。

3、熟练掌握单链表的插入、删除、查找、排序、合并等算法的设计与C语言实现。 4、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。

四、算法流程图

开始

创建

遍 插 删 查 查找 查找 合 历 入 除 找 前驱 后继 并

主函数 输出

结束 五、概要设计

1.界面设置 1.建立顺序表，输入数据元素 2.输出顺序表 3.在i位置插入元素e 4.删除第i个元素，返回其值 5.查找值为e的元素 6.清空顺序表 7.输出指定元素的前驱元素 8.输出指定元素的后继元素 9.将两个非递减的线性表la和lb合并成一个新的非递减的线性表 0.结束程序运行 请输入您的选择(1,2,3,4,5,6,7,8,9,0) 2.功能函数说明与定义

//加载头文件 #include #include #define MAXSIZE 100 typedef int ElemType; //定义结构体类型 typedef struct

{ElemType a[MAXSIZE]; int length; }SqList; SqList a,la,lb,lc;

//以下是9个函数的声明 //顺序表的初始化-置空表 void init(SqList *slt); //创建顺序表

void creat_list(SqList *L); //输出顺序表

void out_list(SqList L); //插入

void insert_sq(SqList *L,int i,ElemType e); //删除

ElemType delete_sq(SqList *L,int i); //查找

ElemType locat_sq(SqList L,ElemType e);

//清空

void DestroyList(SqList *L); //查找前驱

ElemType PriorElem(SqList *L,ElemType cur_e); //查找后继

ElemType NextElem(SqList *L,ElemType cur_e); //合并

void MergeList(SqList *la,SqList *lb,SqList lc);

3.各部分函数的建立

1. 顺序表的初始化-置空表 void init(SqList *slt) {

slt->length=0; }

2. 顺序表结点输入，顺序表的创建 void creat_list(SqList *L) {int i;

printf(\顺序表的长度n=\ for(i=0;ilength;i++){printf(\元素 %d=\ scanf(\ }

printf(\顺序表创建成功！！！\ }

3. 遍历顺序表

void out_list(SqList L) {int i;

printf(\

for(i=0;i<=L.length-1;i++)printf(\ printf(\按Enter键，继续。\ }

4. 在顺序表的i位置插入值为e的结点 void insert_sq(SqList * L,int i,ElemType e) {int j;

if(L->length==MAXSIZE)printf(\ else if(i<1||i>L->length+1) printf(\

else {for(j=L->length-1;j>=i-1;j--)L->a[j+1]=L->a[j]; L->a[i-1]=e; L->length++; }

}

5. 删除顺序表中第i个位置的结点 ElemType delete_sq(SqList *L,int i) {ElemType x;int j;

if(L->length==0)printf(\是空表格。 underflow !\ else if(i<1||i>L->length){printf(\ x=-1;} else{ x=L->a[i-1]; for(j=i;j<=L->length-1;j++) L->a[j-1]=L->a[j]; L->length--; } return(x); }

6. 查找值为e的元素

ElemType locat_sq(SqList L, ElemType e) {int i=0;

while(i<=L.length-1 && L.a[i]!=e)i++; if(i<=L.length-1) return(i+1); else return(-1); }

7. 清空顺序表

void DestroyList(SqList *L) {

//free(L); L->length=0;

printf(\顺序表清空成功!!!\ return; }

8. 查找前驱

ElemType PriorElem(SqList *L,ElemType cur_e) {

int i=0,pre; SqList *p; p=L;

while(i<=L->length&&p->a[i]!=cur_e) {

i++; }

if(i>L->length) return -1; else {

pre=p->a[i-1];