《线性表的操作算法.doc》由会员分享，可在线阅读，更多相关《线性表的操作算法.doc（19页珍藏版）》请在三一文库上搜索。
1、 数 据 结 构实验报告 课题名称：线性表的操作算法 姓名： 班级： 学号： 1、 内容提要 1、 掌握使用cFree上机调试线性表的基本方法；2、 分别用数组和链表作为存储结构，实现线性表的插入、删除、查找、排序、合并等操作。2、 实验要求 1、 设计对线性表进行链式存储操作的内容；2、 写出相应程序； 3、 保存和打印出程序的运行结果，并结合程序进行分析；三 、实验目的 1、理解数据结构中单链表的定义和建立。 2、掌握单链表中结点结构的C语言描述。 3、熟练掌握单链表的插入、删除、查找、排序、合并等算法的设计与C语言实现。 4、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。 4、
2、算法流程图 开始 创建 遍 插 删 查 查找 查找 合 历 入 除 找 前驱 后继 并 主函数 输出 结束 5、 概要设计 1. 界面设置1. 建立顺序表，输入数据元素2. 输出顺序表3.在i位置插入元素e4.删除第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 100typedef int ElemType;
3、/定义结构体类型typedef struct ElemType aMAXSIZE; 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
4、 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
5、) int i; printf(n 顺序表的长度n=);scanf(%d,&(L-length); for(i=0;ilength;i+)printf(n 元素 %d=,i); scanf(%d,&(L-ai); printf(顺序表创建成功！); 3. 遍历顺序表void out_list(SqList L) int i; printf(n); for(i=0;ilength=MAXSIZE)printf(n overflow !); else if(iL-length+1) printf(n erroe i !); else for(j=L-length-1;j=i-1;j-)L-aj+1
6、=L-aj; L-ai-1=e; L-length+; 5. 删除顺序表中第i个位置的结点ElemType delete_sq(SqList *L,int i)ElemType x;int j; if(L-length=0)printf(n 是空表格。 underflow !); else if(iL-length)printf(n error i !); x=-1; else x=L-ai-1; for(j=i;jlength-1;j+) L-aj-1=L-aj; L-length-; return(x);6. 查找值为e的元素ElemType locat_sq(SqList L, Elem
7、Type e)int i=0; while(i=L.length-1 & L.ai!=e)i+; if(ilength=0; printf(顺序表清空成功!); return;8. 查找前驱ElemType PriorElem(SqList *L,ElemType cur_e) int i=0,pre; SqList *p; p=L; while(ilength&p-ai!=cur_e) i+; if(iL-length) return -1; else pre=p-ai-1; return pre; 9. 查找后继ElemType NextElem(SqList *L,ElemType cu
8、r_e) int i=0,nextE; SqList *p; p=L; while(ilength&p-ai!=cur_e) i+; if(iL-length) return -1; else nextE=p-ai+1; return nextE; 10. 将两个非递减的线性表合并成一个新的非递减的线性表void MergeList(SqList *la,SqList *lb,SqList lc)/SqList *lc;int i,j,k;i=j=k=0;int x,y;while(ilength)lc.ak+=la-ai+;/insert_sq(&lc,i,la-ai);/i+;while(
9、jlength) lc.ak+=lb-aj+;/insert_sq(&lc,i,lb-aj);/i+;/j+; /下面的for循环是对顺序表lc进行非递减排序 for(x=0; xk; x+)for(y=0; ylc.ay+1)int temp = lc.ay;lc.ay = lc.ay+1;lc.ay+1 = temp;/打印排序后的顺序表lcprintf(nn一个新的非递减的线性表为(排序后):n);for(i=0;ik;i+)printf(%dt,lc.ai);/out_list(lc);6、 运行结果1.界面选项（根据提示选择需要进行的操作）2.根据提示创建一个长度为5，0、1、2、3
10、、4号元素分别为1，2,3,4,5的顺序表3.输出顺序表4.在4号位置插入一个元素75.删除第3个元素6.查找值为7的元素，结果为位置为37.查找元素4的前驱，结果为78.查找元素7的后继元素，结果为49.清空顺序表10.创建2个非递减的线性表la和lb并合并成一个新的非递减线性表。源代码/加载头文件#include#include#define MAXSIZE 100typedef int ElemType;/定义结构体类型typedef struct ElemType aMAXSIZE; int length; SqList;SqList a,la,lb,lc;/以下是9个函数的声明voi
11、d 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 c
12、ur_e);void MergeList(SqList *la,SqList *lb,SqList lc);/主函数int main()int i,k,loc;ElemType e,x; doprintf(nnn); printf(n 1.建立顺序表，输入数据元素);printf(n 2.输出顺序表); printf(n 3.在i位置插入元素e); printf(n 4.删除第i个元素，返回其值); printf(n 5.查找值为e的元素);printf(n 6.清空顺序表);printf(n 7.输出指定元素的前驱元素);printf(n 8.输出指定元素的后继元素); printf(n 9
13、.将两个非递减的线性表la和lb合并成一个新的非递减的线性表lc); printf(n 0.结束程序运行); printf(n=); printf(n 请输入您的选择(1,2,3,4,5,6,7,8,9,0); scanf(%d,&k); switch(k) case 1:creat_list(&a); break;case 2:out_list(a); break; case 3:printf(n i,e(用逗号分隔开)=); scanf(%d,%d,&i,&e); insert_sq(&a,i,e);out_list(a); break; case 4:printf(n i=?);scan
14、f(%d,&i); x=delete_sq(&a,i);out_list(a); printf(n x=%d,x); break; case 5:printf(n e=);scanf(%d,&e); loc=locat_sq(a,e); if (loc=-1)printf(n 未找到 %d,loc); else printf(n 已找到，元素位置是 %d,loc); break;case 6:DestroyList(&a); break;case 7:ElemType cur_e, pre;printf(n输入求前驱元素的指定元素的值：);scanf(%d,&cur_e);pre=PriorE
15、lem(&a,cur_e);if(pre!=-1) printf(该元素的前驱元素为：%dn,pre);elseprintf(顺序表中没有该元素!); break;case 8:ElemType cur_e, nextE;printf(n输入求后继元素的指定元素的值：);scanf(%d,&cur_e); nextE=NextElem(&a,cur_e);if(nextE!=-1) printf(该元素的后继元素为：%dn,nextE);elseprintf(顺序表中没有该元素!); break;case 9:printf(先创建线性表la);creat_list(&la);printf(nn
16、再创建线性表lb);creat_list(&lb);printf(n);MergeList(&la,&lb,lc); while(k!=0); DestroyList(&a); printf(n 再见!); printf(n 按Enter键，返回。);/*/* 函数功能：顺序表的初始化-置空表 */* 函数参数：指向sequence_list型变量的指针变量slt*/* 函数返回值：空 */* 文件名：sequlist.c, 函数名：init() */*/ void init(SqList *slt) slt-length=0; /*/* 函数功能：顺序表的初始化 */* 函数参数：指向SqL
17、ist型变量的指针变量L */* 函数返回值：空 */* 文件名：sequlist.c, 函数名：create_list() */*/void creat_list(SqList *L) int i; printf(n 顺序表的长度n=);scanf(%d,&(L-length); for(i=0;ilength;i+)printf(n 元素 %d=,i); scanf(%d,&(L-ai); printf(顺序表创建成功！); /*/* 函数功能：打印顺序表的各结点值 */* 函数参数：SqList型变量L */* 函数返回值：空 */* 文件名：sequlist.c, 函数名：out_li
18、st() */*/void out_list(SqList L) int i; printf(n); for(i=0;ilength=MAXSIZE)printf(n overflow !); else if(iL-length+1) printf(n erroe i !); else for(j=L-length-1;j=i-1;j-)L-aj+1=L-aj; L-ai-1=e; L-length+; /*/* 函数功能：删除顺序表中第i个位置的结点 */* 函数参数：指向SqList型变量的指针变量L */* int型变量 i */* 函数返回值：空 */* 文件名：sequlist.c，
19、函数名：delete_sq() */*/ElemType delete_sq(SqList *L,int i)ElemType x;int j; if(L-length=0)printf(n 是空表格。 underflow !); else if(iL-length)printf(n error i !); x=-1; else x=L-ai-1; for(j=i;jlength-1;j+) L-aj-1=L-aj; L-length-; return(x);/查找值为e的元素ElemType locat_sq(SqList L, ElemType e)int i=0; while(i=L.l
20、ength-1 & L.ai!=e)i+; if(ilength=0; printf(顺序表清空成功!); return;/*在一个非空的线性表中，除第一个数据元素之外，其余数据元素有且只有一个前驱。故本函数处理时从第2个数据元素开始寻找与指定元素相等的数据元素。找到指定元素时，返回的是当前元素的地址的前一个地址中的数据元素。*/ElemType PriorElem(SqList *L,ElemType cur_e) int i=0,pre; SqList *p; p=L; while(ilength&p-ai!=cur_e) i+; if(iL-length) return -1; else
21、 pre=p-ai-1; return pre; /*在一个非空的线性表中，除最后一个数据元素之外，其余数据元素有且只有一个后继。故本函数处理时从第1个数据元素开始寻找与指定元素相等的数据元素，直到倒数第2个数据元素，控制条件采用的是i小于线性表的长度（iL.length）。找到指定元素时，返回的是当前元素的地址的后一个地址中的数据元素。*/ElemType NextElem(SqList *L,ElemType cur_e) int i=0,nextE; SqList *p; p=L; while(ilength&p-ai!=cur_e) i+; if(iL-length) return -
22、1; else nextE=p-ai+1; return nextE; /*/*将两个非递减的线性表合并成一个新的非递减的线性表 */*/void MergeList(SqList *la,SqList *lb,SqList lc)/SqList *lc;int i,j,k;i=j=k=0;int x,y;while(ilength)lc.ak+=la-ai+;/insert_sq(&lc,i,la-ai);/i+;while(jlength) lc.ak+=lb-aj+;/insert_sq(&lc,i,lb-aj);/i+;/j+; /下面的for循环是对顺序表lc进行非递减排序 for(x=0; xk; x+)for(y=0; ylc.ay+1)int temp = lc.ay;lc.ay = lc.ay+1;lc.ay+1 = temp;/打印排序后的顺序表lcprintf(nn一个新的非递减的线性表为(排序后):n);for(i=0;ik;i+)printf(%dt,lc.ai);/out_list(lc);