下载文档原格式
C语⾔——线性表及其应⽤程序要求1.建⽴含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。
2.利⽤前⾯的实验先建⽴⼀个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插⼊元素68。
3.建⽴⼀个带头结点的单链表，结点的值域为整型数据。
要求将⽤户输⼊的数据按尾插⼊法来建⽴相应单链表。
输⼊和输出的格式1.顺序线性表的建⽴、插⼊及删除顺序表#include<stdio.h>#include<stdlib.h>#define ListSize 50typedef int DataType;//线性表的顺序存储⽅式typedef struct {DataType data[ListSize];int l;}SeqList;//创建顺序线性表void CreateList(SeqList *A,int n){int i;for(i=0;i<n;i++){scanf("%d",&(A->data[i]));}A->l=n;}//在顺序线性表中插⼊某个元素void InsertList(SeqList *A,DataType x,int i){int j;if(i<1 || i>A->l) //插⼊时的条件{printf("插⼊位置错误!\n");exit(0);}else{printf("插⼊成功!\n");}if(A->l >= ListSize){printf("列表溢出!\n");exit(0);}for(j=A->l-1;j>=i-1;j--){A->data[j+1]=A->data[j]; //插⼊时，把各个元素向后移动后，然后在进⾏插⼊}A->data[i-1]=x;A->l++;}//在顺序线性表中删除某个元素void DeleteList(SeqList *A,int i){int j;if(A->l==0) //删除时的条件{printf("列表为空!\n");exit(0);}if(i<1 || i>A->l){printf("删除位置错误!\n\n");exit(0);}for(j=i;j<=A->l-1;j++) //删除时，把各个元素向前移动，覆盖掉要删除的元素{A->data[j-1]=A->data[j];}A->l--;}//输出线性表void DisList(SeqList *L){int i;for(i=0;i<L->l;i++)printf("%d ",L->data[i]);printf("\n");}void main(){SeqList *A=(SeqList*)malloc(sizeof(SeqList));int a=7;printf("请输⼊7个整型元素:\n");CreateList(A,a);printf("输出SeqList的长度: \n");printf("长度=%d\n",A->l);printf("表内元素为");DisList(A);DataType x;printf("请输⼊需要插⼊的元素的位置!\n");int i;scanf("%d",&i);printf("请输⼊需要插⼊的元素!\n");scanf("%d",&x);InsertList(A,x,i);printf("长度=%d\n",A->l);printf("表内元素为");DisList(A);printf("请输⼊需要删除的元素的位置!\n");scanf("%d",&i);DeleteList(A,i);printf("表内元素为");DisList(A);printf("长度=%d\n",A->l);}输⼊和输出的格式顺序表输⼊输出：定义输⼊7个整型元素，回车进⾏插⼊和删除，输出线性表2.链式线性表的建⽴、插⼊及删除单链表#include <stdio.h>#include <stdlib.h>typedef int ElemType;//定义结点类型typedef struct Node{ElemType data; //单链表中的数据域struct Node *next; //单链表的指针域}Node,*LinkedList;//单链表的初始化LinkedList LinkedListInit(){Node *A;A = (Node *)malloc(sizeof(Node)); //申请结点空间if(A == NULL) //判断是否有⾜够的内存空间printf("申请内存空间失败\n");A->next = NULL; //将next设置为NULL,初始长度为0的单链表return A;}//单链表的建⽴LinkedList LinkedListCreat(){Node *A;A = (Node *)malloc(sizeof(Node)); //申请头结点空间A->next = NULL; //初始化⼀个空链表Node *r;r = A;ElemType x;while(scanf("%d",&x) != EOF){Node *p;p = (Node *)malloc(sizeof(Node));p->data = x;r->next = p;r = p;}r->next = NULL;return A;}//单链表的插⼊，在链表的第i个位置插⼊x的元素LinkedList LinkedListInsert(LinkedList A,int i,ElemType x){Node *pre; //pre为前驱结点pre = A;int tempi = 0;for (tempi = 1; tempi < i; tempi++)pre = pre->next; //查找第i个位置的前驱结点Node *p; //插⼊的结点为pp = (Node *)malloc(sizeof(Node));p->data = x;p->next = pre->next;pre->next = p;return A;}//单链表的删除，在链表中删除数据值为x的元素LinkedList LinkedListDelete(LinkedList A,ElemType x){Node *p,*pre; //pre为前驱结点，p为查找的结点。
线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。
2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。
3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。
4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。
线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。
2. 插入操作：将一个新元素插入到线性表中的指定位置。
3. 删除操作：将线性表中的某个元素删除。
4. 更新操作：将线性表中的某个元素更新为新的值。
线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。
线性表的顺序存储结构通常采用数组来实现。
数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。
但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。
线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。
每个元素包含数据和指向下一个元素的指针。
链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。
但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。
线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。
2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。
3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。
线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。
2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。
线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。
2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。
【数据结构】线性表的基本操作【数据结构】线性表的基本操作1：定义1.1 线性表的概念1.2 线性表的特点2：基本操作2.1 初始化操作2.1.1 空表的创建2.1.2 非空表的创建2.2 插入操作2.2.1 在指定位置插入元素2.2.2 在表头插入元素2.2.3 在表尾插入元素2.3 删除操作2.3.1 删除指定位置的元素2.3.2 删除表头的元素2.3.3 删除表尾的元素2.4 查找操作2.4.1 按值查找元素2.4.2 按位置查找元素2.5 修改操作2.5.1 修改指定位置的元素 2.5.2 修改指定值的元素3：综合操作3.1 反转线性表3.2 合并两个线性表3.3 排序线性表3.4 删除重复元素3.5 拆分线性表4：线性表的应用场景4.1 数组的应用4.2 链表的应用4.3 栈的应用4.4 队列的应用附件：无法律名词及注释：- 线性表：根据某种规则排列的一组元素的有限序列。
- 初始化操作：创建一个空的线性表，或者创建一个已经包含一定元素的线性表。
- 插入操作：在线性表的指定位置或者表头、表尾插入一个新元素。
- 删除操作：从线性表中删除掉指定位置或者表头、表尾的元素。
- 查找操作：在线性表中按照指定的元素值或者位置查找元素。
- 修改操作：更改线性表中指定位置或者值的元素。
- 反转线性表：将线性表中的元素顺序颠倒。
- 合并线性表：将两个线性表合并成一个新的线性表。
- 排序线性表：按照某种规则对线性表中的元素进行排序。
- 删除重复元素：将线性表中重复的元素删除，只保留一个。
- 拆分线性表：将一个线性表分成多个不重叠的子线性表。
一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：. 创建一个新的顺序表，实现动态空间分配的初始化；. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；. 利用最少的空间实现顺序表元素的逆转；. 实现顺序表的各个元素的输出；. 彻底销毁顺序线性表，回收所分配的空间；. 对顺序线性表的所有元素删除，置为空表；. 返回其数据元素个数；. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；. 判断顺序表中是否有元素存在，对判断结果进行返回；. 编写主程序，实现对各不同的算法调用。
2．实现要求：对顺序表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价；. “初始化算法”的操作结果：构造一个空的顺序线性表。
对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；. “位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；. “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；. “逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；. “输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；. “销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；. “置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；. “求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；. “按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值. “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；. “判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
数据结构线性表一、引言数据结构是计算机存储、组织数据的方式，它决定了数据访问的效率和灵活性。
在数据结构中，线性表是一种最基本、最常用的数据结构。
线性表是由零个或多个数据元素组成的有限序列，其中数据元素之间的关系是一对一的关系。
本文将对线性表的概念、分类、基本操作及其应用进行详细阐述。
二、线性表的概念1.数据元素之间具有一对一的关系，即除了第一个和一个数据元素外，其他数据元素都是首尾相连的。
2.线性表具有唯一的第一个元素和一个元素，分别称为表头和表尾。
3.线性表的长度是指表中数据元素的个数，长度为零的线性表称为空表。
三、线性表的分类根据线性表的存储方式，可以将线性表分为顺序存储结构和链式存储结构两大类。
1.顺序存储结构：顺序存储结构是将线性表中的数据元素按照逻辑顺序依次存放在一组地质连续的存储单元中。
顺序存储结构具有随机访问的特点，可以通过下标快速访问表中的任意一个元素。
顺序存储结构的线性表又可以分为静态顺序表和动态顺序表两种。
2.链式存储结构：链式存储结构是通过指针将线性表中的数据元素连接起来，形成一个链表。
链表中的每个节点包含一个数据元素和一个或多个指针，指向下一个或前一个节点。
链式存储结构具有动态性，可以根据需要动态地分配和释放节点空间。
链式存储结构的线性表又可以分为单向链表、双向链表和循环链表等。
四、线性表的基本操作线性表作为一种数据结构，具有一系列基本操作，包括：1.初始化：创建一个空的线性表。
2.插入：在线性表的指定位置插入一个数据元素。
3.删除：删除线性表中指定位置的数据元素。
4.查找：在线性表中查找具有给定关键字的数据元素。
5.更新：更新线性表中指定位置的数据元素。
6.销毁：释放线性表所占用的空间。
7.遍历：遍历线性表中的所有数据元素，进行相应的操作。
8.排序：对线性表中的数据元素进行排序。
9.合并：将两个线性表合并为一个线性表。
五、线性表的应用1.程序语言中的数组：数组是一种典型的顺序存储结构的线性表，常用于存储具有相同类型的数据元素。
实验一线性表基本操作的编程实现【实验目的】线性表基本操作的编程实现要求：线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构要求是链表存储结构（顺序存储结构建议作为课外实验完成），可以依次完成主要功能来体现功能的正确性，用菜单进行管理完成大部分功能，要求可以重复运行。
还鼓励学生利用基本操作进行一些更实际的应用型程序设计。
【实验性质】验证性实验（学时数：2H）【实验内容】1.线性表的链表存储，实现数据插入、删除运算。
为了体现功能的正常性，同时要编制数据输入函数和遍历函数，数据输入最好同时提供计算机自动产生数据。
2.其他建议改进的功能或细节：存储结构修改为循环链表、双向链表、循环双向链表等。
原始数据从文本文件读入。
结果存入文本文件【注意事项】1.开发语言：使用C++，不能使用C。
至于是否使用对象，初期可以不用，但是建议尽量尽快使用对象。
2.可以自己增加其他功能。
3．如果是自己开发的，请在程序界面上注明 ***原创。
如果是参考他人或改编他人的，则注明：*** 参考他人版。
希望大家诚实对待自己的努力。
如果有小组，版权页上写上全组人员。
4.在实验报告中也应该如实写出哪些程序功能是自己编的，哪些是参考别人的。
5.初始成绩全部学生都是不及格，然后逐步通过提交更好的版本来刷新成绩。
实验当日仅仅是不及格变为及格。
之后通过班长全班学生提交源代码，为了方便，建议把程序做成一个cpp。
之后在实验后的三天时间内提交实验报告。
过时不候。
结合实验当时的检测，实验后源代码的检测，实验报告的书写给出当次的成绩。
分为五级制。
程序提交在实验之后的三天里可以刷新。
但是一般不应该超过二次。
提交的程序必须要语法正确的。
目前由于老师的审查平台是c++6.0，所以为了统一起见，不接受其他平台的开发系统。
程序名一律类似为：T423-2-17-翁靖凯-链表实验程序.cpp所有信息之间为中横线。
数据结构实验报告实验名称：实验一线性表——题目1学生：申宇飞班级：信通3班班序号： 03学号： 2012210064日期： 2013年11月4日1.实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。
实验容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。
2.程序分析2.1 存储结构链表的具体存储表示为：① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）② 链表中结点的逻辑次序和物理次序不一定相同。
为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）链表的结点结构┌──┬──┐│data│next│└──┴──┘data 域--存放结点值的数据域next 域--存放结点的直接后继的地址（位置）的指针域（链域）地址 存单元1000H头指针 1020H 1080H 10C0H2.2 关键算法分析1、关键算法：1：头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。
将新结点加入链表中伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:s->next=front->next;d:front->next=s2：尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:r->next=s;d:r=s3：析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:front=pd:p=p->nexte:delete front4：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=front->next;j=1;b:while(p&&j!=1)b1:p=p->nextb2:j++c:if(!p) throw ”error”d:return p5：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点 b1：判断p 指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j 的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node <T> * p=front->next;j=1;b:while(p)b1: if(p->next==x) return jp=p->nextj++c:return “error”6：插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x7：删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:delete q8：遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述If front->next==NULLThrow ”an empty list ”Node<T>* temp=front->next;while(temp->next){ cout<<temp->data<<" ";temp=temp->next;}9：获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 伪代码描述int n=0if ront->next==NULLn=0;else{ Node<T>* temp=front->next;while(temp->next)n++;temp=temp->next;}return n;2、代码详细分析：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while (x>p->data) { p=p->next;}（2）新建一个节点s，把p的数据赋给s：s->data=p->data;（3）把s加到p后面：s->next=p->next; p->next=s;（4）p节点的数据用x替换：p->data=x;示意图如图所示3、关键算法的时间复杂度：O（1)3.程序运行结果程序截图1. 流程图：开始初始化一个对象2.测试条件：插入、删除元素的位置一定要在链表的长度围之。
【数据结构】线性表的基本操作线性表的基本操作⒈创建线性表⑴静态创建静态创建是指在编译或运行前确定线性表的大小并分配相应的内存空间。
可以使用数组来实现静态创建。
⑵动态创建动态创建是指在运行时根据需要动态分配内存空间。
可以使用链表来实现动态创建。
⒉插入元素⑴头部插入在线性表的头部插入一个元素，即将现有的元素全部后移一位。
⑵中间插入在线性表的指定位置插入一个元素，需要将指定位置之后的元素全部后移一位。
⑶尾部插入在线性表的尾部插入一个元素，即在现有元素的后面新增一个元素。
⒊删除元素⑴头部删除删除线性表的头部元素，即将头部元素后面的元素全部前移一位。
⑵中间删除删除线性表的指定位置元素，需要将指定位置之后的元素全部前移一位。
⑶尾部删除删除线性表的尾部元素。
⒋查找元素⑴按值查找按给定的值，在线性表中查找相应的元素，并返回其位置。
⑵按索引查找按给定的索引，直接在线性表中查找相应的元素。
⒌修改元素⑴按索引修改按给定的索引，直接修改线性表中相应位置的元素。
⑵按值修改按给定的值，在线性表中查找相应的元素，并修改其值。
⒍获取元素个数获取线性表中元素的个数。
⒎判断线性表是否为空判断线性表中是否没有任何元素。
⒏清空线性表将线性表中的元素全部删除，使线性表为空。
⒐销毁线性表释放线性表所占用的内存空间，销毁线性表。
附件：●暂无附件法律名词及注释：暂无相关法律名词及注释。
线性表的操作及其应用一、问题描述线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。
这些数据结构都可用来解决约瑟夫环问题。
约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。
设计算法求约瑟夫环中人员的出列顺序。
二、基本要求1、选择合适的存储结构，建立线性表；2、利用顺序存储结构求解约瑟夫环问题；3、利用单链表和循环链表分别求解约瑟夫环问题；4、利用队列求解约瑟夫环问题。
三、测试数据约瑟夫环的测试数据为7，报数为1至3。
四、算法思想由于用到四种不同的存储结构，它们的算法思想依次是：1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。
用已经输出总人数和顺序表长作比较，作为外层循环条件。
并对每一个输出后的元素重新赋值以为标记。
对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。
每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。
2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。
设立判断指针指向表头，并将该指针是否为空作为外层循环条件。
做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。
接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。
3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。
并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。
二章线性表线性表是最简单、最基本、也是最常用的一种线性结构。
它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。
2.1 线性表的逻辑结构2.1.1 线性表的定义线性表是一种线性结构。
线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。
在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。
在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。
综上所述，线性表定义如下：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：(a1，a2，… a i-1，a i，a i+1，…a n)其中n为表长，n＝0 时称为空表。
表中相邻元素之间存在着顺序关系。
将a i-1 称为a i 的直接前趋，a i+1 称为a i 的直接后继。
就是说：对于a i，当i=2，...，n 时，有且仅有一个直接前趋a i-1.，当i=1，2，...，n-1 时，有且仅有一个直接后继a i+1，而a1 是表中第一个元素，它没有前趋，a n 是最后一个元素无后继。
需要说明的是：a i为序号为i 的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型; 在字符串中，它是字符型; 等等。
2.1.2 线性表的基本操作在第一章中提到，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。
线性表上的基本操作有：⑴线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表⑵求线性表的长度：Length_List(L)初始条件：表L存在操作结果：返回线性表中的所含元素的个数⑶取表元：Get_List(L,i)初始条件：表L存在且1<=i<=Length_List(L)操作结果：返回线性表L中的第ｉ个元素的值或地址⑷按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。
实验一线性表的基本操作一、实验目的（1）掌握线性表顺序存储和链式存储的方法及基本运算的实现。
（2）掌握将算法在VC++6.0语言环境下实现的过程。
二、实验准备（1）复习线性表的定义，掌握顺序存储、链式存储的方法及操作。
（2）复习C语言中指针与结构体的概念、定义方式。
（3）掌握链表的C语言的实现。
（4）实验的计算机中安装了Microsoft VC++ 6.0。
三、实验内容顺序表1）首先创建一个顺序表：从键盘读入一组整数（长度小于等于20），按输入顺序放入顺序表，输入以－1结束（注意－1不放到顺序表内）；将创建好的顺序表元素依次输出到屏幕上。
2）在已创建好的顺序表中插入一个元素：从键盘读入需插入的元素值和插入位置，调用插入函数完成插入操作；然后将顺序表元素依次输出到屏幕上。
3）在已创建好的顺序表中删除一个元素：从键盘读入欲删除的元素位置（序号），调用删除函数完成删除操作；然后将顺序表元素依次输出到屏幕上。
算法提示：➢需求分析：1.功能（1）建立一顺序表（2）显示顺序表中每个元素（3）在上述的顺序表中的指定位置插入指定的元素，并输出顺序表中所有数据。
（4）在上述的顺序表中的指定位置删除指定的元素，并输出顺序表中所有数据。
2．输入要求从键盘输入顺序表中所有数据，输入以－1结束（注意－1不放到顺序表内）；需插入的数据元素的位置、值；要删除的数据元素的位置（序号）。
3. 测试数据顺序表中所有数据：15，26，58，27，9插入的数据元素的位置、值：1，28；6，28；0，28要删除的数据元素的位置：3➢概要设计：1.数据结构：提示：相关常量和顺序表数据类型定义#define MAXNUM 20#define true 1#define false 0typedef struct{int data[MAXNUM];int length;}list_type;2．模块划分：a)建立顺序表的createlist函数；b)显示输出顺序中每个结点的数据的showlist函数；c)insertlist函数：插入函数。
数据结构——线性表（顺序实现） 好好学习基础知识，出⼈头地就靠它了，内外兼修。
（好吧，我现在内外都不⾏）写这篇⽂章的⽬的就是为了，巩固刚学完的线性表，个⼈能⼒有限，若有不当之处，望指出。
线性表 好了，扯完了，说正事： 1、定义 线性表是⼀种及其常⽤的并且最简单的⼀种数据结构。
简单来说，线性表就是集合⾥的元素的有限排列。
（在这⾥我把集合定义为具有相同属性的元素，会有些狭义） 在线性表中数据元素之间的关系是⼀对⼀的关系，即除了第⼀个和最后⼀个数据元素之外，其它数据元素都是⾸尾相接的（注意，这句话只适⽤⼤部分线性表，⽽不是全部。
⽐如，循环链表逻辑层次上也是⼀种线性表（存储层次上属于链式存储），但是把最后⼀个数据元素的尾指针指向了⾸位结点）[] 怎么说呢，毕竟数据结构毕竟是逻辑结构，逻辑上符合线性结构的特征即可，存储结构能实现就⾏。
线性表的很重要！很重要！很重要！后⾯的栈，队列，串等都是基于线性表的基础上实现的，所以说⼀定要学好线性表 2、线性表的特点： 对于任意的的⾮空线性表或者线性结构有： 1、存在唯⼀⼀个被称为 ”第⼀个“的元素 2、存在唯⼀⼀个被称为 ”最后⼀个“的元素 3、出第⼀个元素之外，每⼀个元素都存在⼀个后继 4、除最后⼀个元素之外，每⼀个元素都存在⼀个前驱 3、基本操作 1、Create（*L）创建空表 2、InitEmpty（*L）初始化 3、getLength（*L）获取长度 4、Insert（*L）插⼊元素 5、Remove（*L）移除元素 6、IsEmpty（*L）空表检测 7、IsFulled（*L）表满检测（顺序表常⽤，链式表基本不⽤） 8、Delete（*L）删除表 9、getElemt（*L）获取元素 10、Traverse（*L）遍历输出所有元素 11、Clear（*L）清除所有元素 4 、实现 好了最⿇烦的事情开始了，数据结构在计算机上的的映射。
众所周知，线性表有两种实现⽅法，⼀种是顺序表，另⼀种是链式表，这两种结构实现最⼤的不同在于前者逻辑关系⽆需存储空间，⽽后者则需要⽤额外的空间（顺便记录⼀下，指针⼤⼩只由环境有关（严格意义上说和CPU的位数有关）本篇只实现顺序结构）。
实验报告
课程名称数据结构
实验项目线性表的实现及应用
实验仪器PC机一台
学院_____ 专业
班级/学号
姓名
实验日期
成绩
指导教师
北京信息科技大学
信息管理学院
（数据结构课程上机）实验报告
3.
1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模
版供学生使用；
2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；
3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；
4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；
5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。
目录
一、实验题目 ..................... 错误!未定义书签。
二、实验流程图 ................... 错误!未定义书签。
三、实验程序清单 ................. 错误!未定义书签。
四、实验验证数据 ................. 错误!未定义书签。
五、实验体会............................................ 错误!未定义书签。
实验一线性表的建立与遍历
一、实验题目
1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。
2、给定一个输入序列，建立线性链表，访问输出线性链表中各结点的内容。
二、实验流程图
1、顺序表的建立流程图
图输入流程图图输出流程图
2、①链表头插法的建立及链表的输出
图链表输出图头插法建立链表
②尾插法建立
图尾插法建立
三、实验程序清单
1、/*顺序表的建立及遍历*/
#include <>
typedef struct{
int data[100];
int length;
}Seqlist;
void creat(Seqlist &L);
void show(Seqlist L);
int main()
{
Seqlist L;
=0;
creat(L);
show(L);
return 0;
}
void creat(Seqlist &L)
{
int a;
printf("请输入要创建的元素的个数:\t");
scanf("%d",&a);
for(int i=0;i<a;i++)
{
printf("请输入第%d个元素\t",i+1);
scanf("%d",&[i]);
++;
}
}
void show(Seqlist L)
{
int i;
printf("线性表中的元素为:\n");
for(i=0;i<;i++)
printf("%d\t",[i]);
printf("\n");
}
2、
①/*头插法链表的建立*/
#include <>
#include <>
typedef struct node
{
char data;
struct node *next;
}JD;
JD *CreateList_Front();
int main()
{
JD *head,*p;
head=CreateList_Front();
p = head;
while(p != NULL)
{
printf("%c ", p->data);
p = p->next;
}
printf("\n");
}
JD *CreateList_Front()
{JD *head, *p;
char ch;
head = NULL;
printf("依次输入字符数据(‘#’表示输入结束):\n");
ch = getchar();
while(ch != '#')
{
p = (JD*)malloc(sizeof(JD));
p->data = ch;
p->next = head;
head = p;
ch = getchar();
}
return head;
}
②/*链表尾插法建立及遍历*/
#include <>
#include <>
typedef struct link
{
char data;
struct link *next;
}linklist;
linklist *CreateList_End(); 用带头结点的尾插法创建单链表");
printf(" ");
printf("2.链表输出显示");
printf(" ");
printf("3.退出\n");
printf("做出选择：\n");
scanf("%d",&choice);
switch(choice)
{
//尾插法
case 1:
head = CreateList_End();
break;
//输出链表
case 2:
ShowLinklist(head);
break;
//退出程序
case 3:
return 0;
break;
default:
break;
}
}
return 1;
}
linklist *CreateList_End()
{
char ch;
linklist *head, *s, *r;
head = (linklist*)malloc(sizeof(linklist));
r=head;
printf("请依次输入字符数据('#'表示输入结束):\n");
ch = getchar();
while(ch != '#')
{
s = (linklist*)malloc(sizeof(linklist));
s->data = ch;
r->next=s;
r=s;
ch=getchar();
}
r->next = NULL;
return head;
}
void ShowLinklist(linklist *h)
{
linklist *s;
s = h;
while(s != NULL)
{
printf("%c ", s->data);
s = s->next;
}
printf("\n");
}
四、实验验证数据
1、顺序表的建立及输出结果如下：
图顺序输出2、链表头插法建立及遍历，结果如下：
图头插法
3、链表尾插法的建立及遍历，结果如下：
图尾插法
五、实验体会
通过这次实验的练习，虽然在编程的过程中出现的一些小的错误，例如变量未定义，但是在自己不断的修正下，结果不断完善。
通过这次实验让我更加明白一个顺序表怎么建立，先大体上估计一个数组的大小，自己来确定这个顺序表的长度，然后进行输出。
在链表实验中还做了头插法和尾插法建立及遍历链表，通过实验结果可以更加明白，插法建立链表输出结果是逆序的，而尾插法建立链表输出结果是正序。
