实验 一 线性表的基本操作实现及其应用
一、实验目的
1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。
2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。
二、实验内容
√
1、单链表的表示与操作实现 ( * )
2、约瑟夫环问题
3、Dr.Kong的艺术品
三、实验要求
1、按照数据结构实验任务书，提前做好实验预习与准备工作。
2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范，及时完成实验报告。
四、实验步骤
（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）
㈠、数据结构与核心算法的设计描述
（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）
1、单链表的结点类型定义
/* 定义DataType为int类型 */ typedef int DataType;
/* 单链表的结点类型 */ typedef struct LNode { DataType data; struct LNode *next; }LNode,*LinkedList;
2、初始化单链表
LinkedList LinkedListInit( ) { // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }
3、清空单链表
void LinkedListClear(LinkedList L) {// 每个模块或函数应加注释，说明函数功能、入口及出口参数}
4、检查单链表是否为空
int LinkedListEmpty(LinkedList L) { …. }
5、遍历单链表 void LinkedListTraverse(LinkedList L) { …. }
6、求单链表的长度
int LinkedListLength(LinkedList L) { ….}
7、从单链表表中查找元素
LinkedList LinkedListGet(LinkedList L,int i) { //L是带头结点的链表的头指针， 返回第 i 个元素 }
8、从单链表表中查找与给定元素值相同的元素在链表中的位置
LinkedList LinkedListLocate(LinkedList L, DataType x) { …… }
9、向单链表中插入元素
void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 x }
10、从单链表中删除元素
void LinkedListDel(LinkedList L,DataType x) { // 删除以 L 为头指针的单链表中第 i 个结点 }
11、用尾插法建立单链表
LinkedList LinkedListCreat( ) { …… } ㈡、函数调用及主函数设计
（ 可用函数的调用关系图说明） ㈢ 程序调试及运行结果分析 ㈣ 实验总结
五、主要算法流程图及程序清单
1、主要算法流程图：
2、程序清单
（程序过长，可附主要部分）
说明：以后每次实验报告均按此格式书写。
我在布置实验室时，仅给出实验名称、实验目的、实验内容及相关数据结构。
题目一程序参考框架 # include # include # include # include # include /* 定义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() { } /* 清空单链表 */ void LinkedListClear(LinkedList L) { } /* 检查单链表是否为空 */ int LinkedListEmpty(LinkedList L) { } /* 遍历单链表 */ void LinkedListTraverse(LinkedList L) { } int LinkedListLength (LinkedList L) { } LinkedList LinkedListGet (LinkedList L, int i) { } LinkedList LinkedListLocate ( LinkedList L, ElemType x) { }
void LinkedListInsert(LinkedList L, int i, ElemType x) {LinkedList pre,p,s;int j; pre=L;j=1;p=L->next; while(pre&&jnext;j++;} if(pre==NULL) {printf(\"给的i值超过了表长\");exit(0);} s=(LNode *)malloc(sizeof(LNode)); s->data=x; pre->next=s; s->next=p; }
void LinkedListDel (LinkedList L,ElemType x) { LinkedList pre,p;int j; pre=L;j=1;p=L->next; while(p&&p->data!=x) {pre=p;p=p->next;j++;} if(p==NULL) {printf(\"表中没有值为x的结点\");exit(0);} pre->next=p->next; free(p); }
LinkedList LinkedListCreat( ) { LinkedList L=LinkedListInit(),p,r; ElemType x; r=L; printf(\"please input data,input -1 is end\\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(\"please input the operation\\n\"); printf(\"1.初始化 2.清空3.求链表长度4.检查链表是否为空\\n\"); printf(\"5.检查链表是否为满 6.遍历链表 7.从链表中查找元素\\n\"); printf(\"8.从链表中查找与给定元素值相同的元素在顺序表中的位置\\n\"); printf(\"9.向链表中插入元素10.从链表中删除元素\\n\"); printf(\"其他键退出。。。。。\\n\"); scanf(\"%d\",&d); return(d); }
main() {int quit=0; int i; ElemType e; LinkedList L; while(!quit) switch(scan()) {case 1: ….; break; case 2: ….;break; case 3: ….; break; case 4: ….; break; case 5:LinkedListTraverse(L); break; case 6: ….; break; case 7: ….; break; case 8: ….; break; case 9: ….; break; case 10: ….; break; default: quit=1;} return 0; }
