数据结构程序设计 数序线性表实现插入删除数据.doc

安徽师范大学数学计算机科学学院实验报告专业名称物联网工程实验室 6号楼2060404实验课程数据结构实验名称顺序表姓名庞现然学号 14111206029 同组人员无实验日期 2015.4.91、实验目的1. 熟练掌握顺序表的类型定义和基本操作算法（以建立、插入、删除、遍历、排序和归并等操作为重点）的实现。

2. 通过实验加深对C语言的使用（特别是函数、数组、结构体和指针）。

3. 掌握模块化程序设计方法。

2、实验原理运用各函数的调用，来实现线性表的基本操作。

3、需求分析输：（1）程序目的：实验线性表的基本操作。

（2）输入的形式：线性表（3）输入值的范围：处理范围内（4）输出的形式：线性表（5）程序能达到的功能：实现线性表的基本操作（6）测试数据：13,5,27,9,32，123,76,98,54,874、概要设计typedef int Status;typedef int ElemType;5、详细设计各函数及其定义：开始1.构造初始化线性表!InitList(&L)2.输入10个元素给线性表L(整数)：1.输出顺序表DispList(&L); 6.输出元素的位置2.输出顺序表的长度 7.插入数据ListInsert(&L,4,56)3.输入所要查询的元素为序n 8.输出此时的线性表DispList(&L)4.输出第n个数据的值 9.输出顺序表的表长5.输入一个要查询的元素的值 10.删除数据元素ListDelete(&L,n,&e) 11.销毁线性表结束1.Status InitList(Sqlist *L)//初始化线性表!{L->elem = (ElemType *)malloc(LIST_Init_Size*sizeof(ElemType));if(! L->elem) exit (OVERFLOW) ; //储存分配失败L->length = 0; //空表长度为0L->listsize = LIST_Init_Size; //初始储存量return OK;}//InitLIst_Sq2.void DestroyList(Sqlist *L)//销毁线性表!{free(L);}//DestroyList_Sq3.Status ListEmpty(Sqlist L)//判定是否为空表!{if(L.length == 0)return ERROR;//如L为空表，则返回0，否则返回1.return OK;}//ListEmpty_Sq4.Status ListLength(Sqlist *L)//求线性表的长度!{return(L->length);}//ListLength_Sq5.void DispList(Sqlist *L)//输出线性表!{int i;/*if ( ListEmpty(L) == 0 ) return;//判断是否为空？ */ for ( i = 0; i<L->length;i++){printf("%d ",L->elem[i]);} printf("\n");}//DIspList_Sq6.int GetElem(Sqlist *L,int i,ElemType *e)//求某个数据元素的值!{if (i<1 || i>L->length) return 0;e = &L->elem[i-1];//该运算返回L中第 i(1≤i≤ListLength(L))个元素的值,存放在e中return OK;}//GetElem_Sq7.int LocateElem(Sqlist *L,ElemType e)//按元素查找!{int i = 0;while (i < L->length && L->elem[i] != e)i++;if (i >= L->length)return 0; //若这样的元素不存在,则返回值为0。

数据结构的课程设计一、课程目标知识目标：1. 理解数据结构的基本概念，掌握线性表、树、图等常见数据结构的特点与应用场景。

2. 学会分析不同数据结构的存储方式和操作方法，并能运用到实际问题的解决中。

3. 掌握排序和查找算法的基本原理，了解其时间复杂度和空间复杂度。

技能目标：1. 能够运用所学数据结构知识，解决实际问题，提高编程能力。

2. 能够运用排序和查找算法，优化程序性能，提高解决问题的效率。

3. 能够运用数据结构知识，分析并解决复杂问题，培养逻辑思维能力和创新意识。

情感态度价值观目标：1. 培养学生对数据结构学科的兴趣，激发学习热情，形成主动探索和积极进取的学习态度。

2. 增强学生的团队协作意识，培养合作解决问题的能力，提高沟通表达能力。

3. 培养学生的抽象思维能力，使其认识到数据结构在计算机科学中的重要性，激发对计算机科学的热爱。

本课程针对高中年级学生，结合学科特点和教学要求，注重理论与实践相结合，培养学生的编程能力和逻辑思维能力。

通过本课程的学习，使学生能够掌握数据结构的基本知识，提高解决实际问题的能力，同时培养良好的学习态度和价值观。

在教学过程中，将目标分解为具体的学习成果，以便进行后续的教学设计和评估。

二、教学内容1. 数据结构基本概念：介绍数据结构的概念、作用和分类，重点讲解线性结构（线性表、栈、队列）和非线性结构（树、图）的特点。

2. 线性表：讲解线性表的顺序存储和链式存储结构，以及相关操作（插入、删除、查找等）。

3. 栈和队列：介绍栈和队列的应用场景、存储结构及相关操作。

4. 树和二叉树：讲解树的定义、性质、存储结构，二叉树的遍历算法及线索二叉树。

5. 图：介绍图的定义、存储结构（邻接矩阵和邻接表）、图的遍历算法（深度优先搜索和广度优先搜索）。

6. 排序算法：讲解常见排序算法（冒泡排序、选择排序、插入排序、快速排序等）的原理、实现及性能分析。

7. 查找算法：介绍线性查找、二分查找等查找算法的原理及实现。

实验一线性表操作一、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。

2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。

3熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。

4熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。

二、实验要求1实验之前认真准备，编写好源程序。

2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。

3不断积累程序的调试方法。

三、实验内容基本题:1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。

加强、提高题：2、编写一个求解Josephus问题的函数。

用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。

然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。

最后分析所完成算法的时间复杂度。

定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。

（可以选做其中之一）加强题：（1）采用数组作为求解过程中使用的数据结构。

提高题：（2）采用循环链表作为求解过程中使用的数据结构。

运行时允许指定任意n、s、m数值，直至输入n = 0退出程序。

实验二栈、队列、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。

二、实验要求1实验之前认真准备，编写好源程序。

2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。

3不断积累程序的调试方法。

三、实验内容基本题（必做）：1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。

2、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。

加强题：3设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。

{if(i%2==0) insert(lb,i/2,la.list[i]); //奇数位次元诩插入lb
else insert(lc,i/2,la.list[i]); //偶数位次元素插入lc
}
printf("\n您输入的线性表元素为:\n\n");
print(la);
printf("线性表的奇数位次的元素为：\n\n");
print(lb);
printf("线性表的偶数位次的元素为：\n\n");
print(lc);
}
void initial(sqlist &v)
{printf(" ****本程序可以实现线性表奇偶位序的元素分别输出****\n\n\n");
int i,a;
printf("请输入一个偶数作为线性表的长度：\n\n");
void initlist(sqlist &);
void print(sqlist); //输出线性表
void main()
{printf(" *****************本程序可以实现线性表的复制******************\n");
sqlist la,lb; //声明线性表
initial(la);
【程序设计细想】：
建立三个线性表la,lb,lc，对线性表la进行输入，然后利用循环结构对la中奇数位序的元素对lb进行插入操作，对偶数位序的元素对lc进行插入操作，从而得到线性表lb和lc。
【程序代码】：
#include<stdio.h>
#include<malloc.h>