数据结构(Java版) 线性表的实现与应用完整版

《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的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、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。

数据结构顺序表的主要代码（LIZHULIN）1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***//***********单链表的初始化、建立、输出*****************/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/****************单链表的初始化*************************/Initlist(LinkList *L){ /*动态申请存储空间*/L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/L->next = NULL;}/*************建立一个带头结点的单链表，在表尾插入***************/Create_L(LinkList *L,int n){LinkList *p,*q; int i;Initlist(L); /*单链表初始化*/q=L;printf("input the value\n");for(i = n;i>0;--i){p = (LinkList*)malloc(sizeof(struct Lnode));scanf("%d",&p->data); /*输入元素值*/q->next = p;p->next = NULL;q=p;/*插入到表尾*/}} /* Create_L *//*************建立一个带头结点的单链表，在表头插入**************Create_L(LinkList *L,int n){LinkList *p; int i;Initlist(L); /*单链表初始化/*需要注意第一个数据插入时的情况/*Insert the Firset nodep = (LinkList*)malloc(sizeof(struct Lnode));printf("input the value\n");scanf("%d",&p->data); /*输入元素值L->next = p;p->next = NULL;/*将第二个及后面的数据插入for(i = n-1;i>0;--i){p = (LinkList*)malloc(sizeof(struct Lnode));printf("input a value\n");scanf("%d",&p->data); /*输入元素值p->next = L->next;L->next = p;/*插入到表头}} /* Create_L *//*************************求单链表的长度***********************/int Length_LinkList(LinkList *L){LinkList *p;int i=0;p=L->next;while(p!=NULL){i++;p=p->next;}return i;}/*Length_LinkList*//*************************在第i个结点前插入数据x *********************/ Insert_LinkList(LinkList *L, int i, int x){LinkList *p,*s;int j=0;p=L;/*寻找第i个结点*/while(j<i-1 && p!=NULL){++j;p=p->next;}if (!p) return 0;/*如果表长小于i，则无意义*//*插入元素x */s=(LinkList *)malloc(sizeof(struct Lnode));s->data=x;s->next=p->next;p->next=s;}/*********************删除第i个元素，并用y将其值返回************************/ int Delete_LinkList(LinkList *L, int i){LinkList *p,*q;int y;int j=0;p=L;/*寻找第i个结点*/while(j<i-1 && p!=NULL){++j;p=p->next;}if (!p) return 0;/*如果表长小于i，则无意义*/q=p->next;y=q->data;p->next=q->next;free(q) ;return y;} /*Delete_LinkList*//*******************单链表值的输出****************/void display(LinkList *L) /*字母链表的输出*/{LinkList *p;p=L->next;while (p!=NULL){printf("%d ",p->data);p=p->next;}}/*************主程序**********************/ main(){LinkList *L;int len;int n=0;int x=15;int y;int i=4;L = (LinkList*)malloc(sizeof(struct Lnode));/*L->data = 0;*/L->next =NULL;printf("input the length of L ,n\n");scanf("%d",&n);printf("\n");Create_L(L,n);Insert_LinkList(L, i, x);/* y=Delete_LinkList(L,i);printf("the delete elment is y=%d\n",y);len=Length_LinkList(L);printf("the length of L is %d",len);*/display(L);getch();}2．/***无头结点的单链表建立、插入、求长度、插入、删除、输出*****/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/*************Create ***************/Link_Creat(LinkList *L,int n){LinkList *q,*p;int i;printf("input the data\n");scanf("%d",&L->data);p=L;for(i=2; i<=n;i++){q=(LinkList *)malloc(sizeof(struct Lnode));scanf("%d",&q->data);p->next=q;q->next=NULL;p=q;}}/**************OutPut*********************/Link_Display(LinkList *L){LinkList *p;p=L;while(p!=NULL){printf("%d ",p->data);p=p->next;}}/***************Main()**************************/main(){LinkList *L;int n;L=(LinkList *)malloc(sizeof(struct Lnode));L->data=0;L->next=NULL;printf("Please input the length of LinkList, n\n");scanf("%d",&n);Link_Creat(L,n);Link_Display(L);getch();}3．/*********顺序表的建立、查找、插入运算********/#include <stdio.h>#include <stdlib.h>typedef int datatype;#define list_maxsize 20/********* define for node struct ************/typedef struct{datatype data[list_maxsize];int length;}SqList;/********** InitList ************/void InitList(SqList *L){L->length = 0;}/*******Creat SqList********/void Create_SqList(SqList *L){int i=0;InitList(L);printf("input SqList.data\n");scanf("%d",&L->data[0]);while(L->data[i]!=-1){++i;scanf("%d",&(L->data[i]));}L->length = i;}/********* the length of SqList****************/int ListLength(SqList *L){return L->length;}/************ GetElem L->data[i]************/int GetElem(SqList *L, int i){if(i<1 || i>L->length){ printf("Position Error");return;}elsereturn L->data[i-1];}/**************** Output the SqList**************/ void Display_SqList(SqList *L){int i,n;n=ListLength(L);printf("the length is %d ",n);for(i=0;i<n;i++)printf("%d ", L->data[i]);}/****************Main()**************************/ main(){SqList *L;/*printf("input the length of SqList\n");scanf("%d",&len);*/Create_SqList(L);Display_SqList(L);getch();}4．/*********顺序表的归并运算********/#include <stdio.h>#include <stdlib.h>typedef int datatype;#define list_maxsize 20/********* define for node struct ************/typedef struct{datatype data[list_maxsize];int length;}SqList;/********** InitList ************/void InitList(SqList *L){L->length = 0;}/************ Creat SqList*************/void Create_SqList(SqList *L){int i=0;InitList(L);printf("input the data of SqList\n");scanf("%d",&L->data[0]);while(L->data[i]!=-1){++i;scanf("%d",&(L->data[i]));}L->length = i;}/********* the length of SqList****************/int ListLength(SqList *L){return L->length;}/************ GetElem L->data[i]************/int GetElem(SqList *L, int i){if(i<1 || i>L->length){ printf("Getelem Position Error");return;}return L->data[i-1];}/************ Insert Operation *********/void ListInsert(SqList *L,int i, int x){SqList *q, *p;if(i<1 || i>L->length){printf("the insert position error");return ;}q = &(L->data[i-1]); /*q为插入位置*/for(p=&(L->data[L->length-1]); p>=q; --p)*(p+1) = *p;L->data[i-1] = x;++L->length;}/********* LA and LB Merged LC ***************/ void MergeList(SqList *LA,SqList *LB,SqList *LC) {int La_len,Lb_len,ai,bj;int i,j;int k;i=j=1;InitList(LC);La_len = ListLength(LA);Lb_len = ListLength(LB);LC->length = La_len+Lb_len;/*for(k=0;k<LC->length;k++)LC->data[k] = 0; */k=0;while((i<=La_len)&&(j<=Lb_len)){ai= GetElem(LA, i);bj= GetElem(LB, j);if(ai<bj){++k;ListInsert(LC,k,ai);++i;}elseif(ai==bj){++k;ListInsert(LC,k,ai);++k;ListInsert(LC,k,bj);++i;++j;}else{++k;ListInsert(LC,k,bj);++j;}}while(i<=La_len){/*Append the residual node into LA */ai= GetElem(LA, i);++i;++k;ListInsert(LC,k,ai);}while(j<=Lb_len){/*Append the residual node into LA */bj= GetElem(LB, j);++j;++k;ListInsert(LC,k,bj);}LC->length = La_len+Lb_len;}/**************** Output the SqList**************/ void Display_SqList(SqList *L){int i,n;n=ListLength(L);printf("the length is %d ",n);for(i=0;i<n;i++)printf("%d ", L->data[i]);}/****************Main()**************************/ main(){SqList *LA , *LB, *LC;Create_SqList(LA);Create_SqList(LB);MergeList(LA,LB,LC);Display_SqList(LC);getch();}5．/**** 用带头结点的循环单链表解决约瑟夫问题***********/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/****************单链表的初始化*************************/Initlist(LinkList *L){ /*动态申请存储空间*/L = (LinkList *)malloc(sizeof(struct Lnode));/*建立头结点*/L->next = L;}/*************建立一个带头结点的循环单链表，数据值为1,2,3,...n,在表尾插入***************/Create_L(LinkList *L,int n){LinkList *p; int i;Initlist(L); /*单链表初始化p=L;for(i = n;i>0;--i){q = (LinkList*)malloc(sizeof(struct Lnode));q->data = i; /*输入元素值p->next =qq->next = L;/*插入到表尾}} /* Create_L *//*******************单链表值的输出****************/void display(LinkList *L) /*字母链表的输出*/{LinkList *p;p=L->next;while (p->next!=L){printf("%d ",p->data);p=p->next;}}/*************主程序**********************/ main(){LinkList *L;int n;L = (LinkList*)malloc(sizeof(struct Lnode));/*L->data = 0;*/L->next =L;printf("input the length of L ,n\n");scanf("%d",&n);printf("\n");Create_L(L,n);display(L);getch();}6．/******** 无头结点的循环单链表的建立**************/#include<stdio.h>#include<stdlib.h>typedef struct Lnode{ /*定义线性表的单链表存储结构*/int data;struct Lnode *next;}LinkList;/*************Create ***************/Link_Creat(LinkList *L,int n){LinkList *q,*p;int i;printf("input the data\n");scanf("%d",&L->data);p=L;for(i=2; i<=n;i++){q=(LinkList *)malloc(sizeof(struct Lnode));scanf("%d",&q->data);p->next=q;q->next=NULL;p=q;}p->next = L;/*尾结点指向第一个结点*/}/**************OutPut*********************/Link_Display(LinkList *L){LinkList *p;p=L;printf("%d ",p->data);p=p->next;while(p->next !=L){printf("%d ",p->data);p=p->next;}}/***************Main()**************************/ main(){LinkList *L;int n;L=(LinkList *)malloc(sizeof(struct Lnode));L->data=0;L->next=NULL;printf("Please input the length of LinkList, n\n");scanf("%d",&n);Link_Creat(L,n);Link_Display(L);getch();}。

package com.zhy.sqlist;class Sqlist{int[] datas ;int length ;}public class SqlListOp{private static Sqlist sqlist ;static{sqlist = new Sqlist();sqlist.datas = new int[]{123,234,345,456,678,908,123,999};sqlist.length = sqlist.datas.length ;}/*** 删除数组中指定元素方法1* @author Administrator**/public void del_key_01(Sqlist sqlist, int key ){int k = 0 ;for(int i = 0 ; i< sqlist.length ; i++){if(sqlist.datas[i] != key){sqlist.datas[k++] = sqlist.datas[i] ;}}sqlist.length = k ;}/*** 删除数组中指定元素方法2* @author Administrator**/public void del_key_02(Sqlist sqlist, int key ){int k = 0 ;for(int i = 0 ; i< sqlist.length ; i++){if(sqlist.datas[i] == key){k++ ;}else{sqlist.datas[i-k] = sqlist.datas[i] ;}}sqlist.length -= k ;}/*** 输出所有元素* @param sqlist*/public void print(Sqlist sqlist){System.out.println("sqlist长度为：" + sqlist.length);for(int i = 0 ; i < sqlist.length ; i++){System.out.print(sqlist.datas[i]+" ");}}/*** 反转整个数组*/public void reverse(Sqlist sqlist ){int tmp ;for( int i = 0 ; i < sqlist.length/2; i++) //注意sqlist.length/2 {tmp = sqlist.datas[i] ;sqlist.datas[i] = sqlist.datas[sqlist.datas.length - i - 1] ;sqlist.datas[sqlist.datas.length - i -1 ] = tmp ;}}/*** 反转指定下标范围 [start , end )* @param sqlist* @param start* @param end*/public void reverse(Sqlist sqlist , int start , int end ){int tmp ;for( int i = start ; i < (start + end)/2 ; i++){tmp = sqlist.datas[i] ;sqlist.datas[i] = sqlist.datas[start + end - i - 1] ;sqlist.datas[start + end - i -1 ] = tmp ;}}/*** 数组循环左移k为* abcdefg 循环左移3位--> defgabc* 1、先反转得到gfedcba* 2、再分别反转前 length - k 位和后k位*/public void cleft(Sqlist sqlist , int k ){k = k % sqlist.length ;reverse(sqlist);reverse(sqlist , 0 , sqlist.length - k );reverse(sqlist , sqlist.length - k , sqlist.length );}public static void main(String[] args){SqlListOp listOp = new SqlListOp() ;listOp.print(sqlist);//listOp.del_key_02(sqlist, 123) ;//listOp.reverse(sqlist);listOp.cleft(sqlist, 9);//listOp.reverse(sqlist, 2, 6);System.out.println();listOp.print(sqlist);}}。

数据结构实验二线性表数据结构实验二线性表一、实验目的本实验旨在帮助学生掌握线性表的基本概念、构造和基本操作，以及通过实际编程实现线性表的功能。

二、实验内容本实验包括以下几个部分：⑴线性表的定义和基本概念介绍线性表的定义，以及线性表中的元素、长度等基本概念。

⑵线性表的顺序存储结构介绍线性表的顺序存储结构的原理和实现方式，包括顺序表的定义、顺序表的初始化、插入和删除等操作。

⑶线性表的链式存储结构介绍线性表的链式存储结构的原理和实现方式，包括链表的定义、链表的插入和删除等操作。

⑷线性表的应用介绍线性表的应用场景和实际应用，如多项式的表示和运算等。

三、实验步骤⑴实验准备准备实验所需的编程环境和开发工具，如C语言编译器、集成开发环境等。

⑵实验设计根据实验要求和目标，设计实现线性表的相关功能，包括定义线性表、初始化线性表、插入和删除元素等。

⑶编码实现根据实验设计，编写程序代码实现线性表的功能。

⑷调试测试对编写的程序进行调试和测试，确保程序的正确性和可靠性。

⑸实验总结总结实验过程中遇到的问题和解决方案，对实验结果进行分析和评价。

四、实验注意事项⑴遵守实验守则在进行实验过程中，要遵守实验守则，注意安全和人身财产的保护。

⑵注意程序的健壮性在编写程序时，要考虑到各种异常情况的处理，保证程序的健壮性。

⑶注意代码的可读性和可维护性编写代码时，要注意代码的可读性和可维护性，使其易于阅读和修改。

⑷注意实验文档的完整性实验报告应包含所有实验内容的详细说明和实验过程的总结分析。

附件：本文档无附件。

法律名词及注释：本文档不涉及法律名词及注释。

数据结构实验线性表及其应用在计算机科学的领域中，数据结构是一门极其重要的基础学科，它为我们有效地组织和管理数据提供了理论和方法。

而线性表作为一种常见且基础的数据结构，在实际的程序设计和算法应用中有着广泛的应用。

线性表是一种最基本的数据结构，它是由零个或多个数据元素组成的有限序列。

在这个序列中，每个元素都有其特定的位置和值。

从存储结构上来看，线性表可以分为顺序存储和链式存储两种方式。

顺序存储的线性表，就像是一排紧密排列的格子，每个格子里存放着一个数据元素。

这种存储方式的优点是可以随机访问表中的任意元素，时间复杂度为 O(1)。

比如说，如果我们要获取顺序表中第 5 个元素的值，只需要通过简单的计算就能直接找到对应的位置并获取其值。

然而，顺序存储也有它的不足之处。

当需要插入或删除元素时，可能需要移动大量的元素，以保持数据的连续性，这会导致时间复杂度较高，为 O(n)。

相比之下，链式存储的线性表则更加灵活。

它就像是一串珍珠项链，每个珍珠（数据元素）通过一根线（指针）与下一个珍珠相连。

在链式存储中，插入和删除元素相对较为方便，只需要修改相关指针的指向即可，时间复杂度通常为 O(1)。

但是，由于无法直接通过计算得到某个元素的位置，所以随机访问的效率较低，时间复杂度为 O(n)。

在实际应用中，线性表有着多种多样的用途。

比如，我们可以用线性表来实现一个学生成绩管理系统。

将每个学生的成绩作为一个元素存储在线性表中，可以按照学号或者成绩进行排序。

当有新的学生成绩需要添加时，根据具体的存储方式选择合适的插入操作；当需要删除某个学生的成绩时，也能快速准确地进行删除。

再比如，在一个购物网站的商品列表中，也可以使用线性表来存储商品的信息。

用户可以按照价格、销量、评价等因素对商品进行排序和筛选。

而网站后台在处理商品的上下架、库存管理等操作时，也会频繁地对线性表进行插入、删除和修改等操作。

此外，在文本编辑软件中，我们输入的文字也可以看作是一个线性表。

数据结构实验报告（⼀）线性表的应⽤实验说明数据结构实验⼀ 线性表的实验——线性表的应⽤⼀、实验⽬的通过本实验使学⽣了解线性表的⼀种简单应⽤，熟悉线性表顺序存储与链式存储的特性，特别训练学⽣编程灵活控制链表的能⼒，为今后编程控制更为复杂的数据结构奠定基础。

⼆、实验内容1.⽤顺序表和链表分别分别编程实现教材中例⼦2-1与2-2。

要求：（1）只能⽤C语⾔编程实现；（2）完全保持书中算法2.1与算法2.2形式，不允许有任何变化，除⾮语法上不允许;所调⽤各函数参照书中19页的功能描述，其中函数名、参数个数及性质、函数功能必须与书中完全⼀致，不能有变化。

2.利⽤线性表表⽰⼀元多项式完成多项式的加、减、乘、求导、求值运算。

要求：（1）输⼊的⼀元多项式可以采⽤只输⼊各项的系数与指数这种简化的⽅式。

如对于多项式2x2+6x5，输⼊可为： 2,2 6,5 这样的简单形式。

（2）遇到有消项时应当处理，如2x2+6x5与3x2-6x5进⾏相加时，结果为5*x^2。

（3）当给定x的值时，能计算表达式相加或相减的结果。

（4）操作的结果放⼊⼀个新线性表中，原来的两个表达式存储表⽰不变，也可以不是产⽣新的线性表，⽽是将两上线性表合并为⼀个。

（5）要求程序功能模块划分合理（每个函数功能单⼀、可重⽤性好），使⽤空间尽可能少，算法尽可能⾼效。

实验报告1.实现功能描述使⽤线性表表⽰⼀元多项式完成多项式的加、减，乘，求导、求值运算。

2.⽅案⽐较与选择（1）因为使⽤的是线性表，所以主要⽅案有数组法和链表法。

（2）从时间复杂度来说，使⽤数组法更优；从空间复杂度来说，链表法更优。

因为数组法是指定好空间的，若式⼦⼤⼩超出设置⼤⼩，那程序必然出错；若式⼦⼤⼩⼩于设置⼤⼩，那就意味着有多余的空间被浪费了。

综合来讲，若计算式⼦较为庞⼤，使⽤链表法更佳；相反，若计算式⼦较⼩，数组法更佳。

3.设计算法描述（1）单个项式的数据存储使⽤了结构体，数组法是在⼀个结构体中定义两个⼀维数组；链表法是通过⼀个结构体作为⼀个节点，通过next指针连接起来。

【数据结构】线性表顺序表详解和代码实例线性表(List)是零个或者多个数据元素的有限序列.⾸先它是⼀个序列.⾥⾯的元素是有顺序的,如果有多个元素,除开头和结尾以外的元素都有⼀个前驱和⼀个后继.⽽开头元素只有后继,结尾元素只有前驱.其次线性表是有限的，也就是⾥⾯的元素个数是有限的。

1ADT 线性表（List）2Data3线性表的数据对象集合为{a1, a2, a3, ......, an},每个元素类型为DataType。

4Operation5InitList(L); //初始化线性表6 IsEmptyList(L); //判断线性表是否为空7 ClearList(L); //清空线性表8 GetElemList(L, i, *e); //获取第i个位置的数据9 SearchList(L, e); //查找与数据e相等的元素10 InsertNodeList(L, i, e);//在第i个位置插⼊元素11 DeleteNodeList(L, i, *e);//删除第i个位置的元素，e获取删除元素12 GetLengthList(L); //获取线性表的长度13endADT关于线性表的基本操作就上⾯⼏种，还有⼏个例如线性表的排序，合并，逆序等等操作。

为了⽂章篇幅，就下次再介绍了。

线性表的顺序存储结构，就是指 ⽤⼀段地址连续的存储单元⼀次存储线性表的数据元素。

学过⾼级语⾔的朋友，相信对数组这玩意⼉都不会陌⽣吧。

数组就是⼀种顺序存储结构。

链式存储结构就是可以⽤⼀组任意的内存单元存储线性表中的元素。

与顺序存储不同的是，这组内存单元可以是连续的，也可以是不连续的。

这就意味着，元素可以存储在内存的任意位置。

正因为如此，在链式结构中，每个元素不仅要存它的信息，还需要存储它后继元素的存储地址。

我们把存储元素信息的域称为数据域，⽽把存储后继元素地址的域称为指针域。

由这两部分共同组成的数据元素ai，则可以称之为节点(Node)。

数据结构实验报告--实验一、线性表的实现线性表是常用的数据结构之一，其中最常用的是顺序存储结构。

本实验使用C语言实现了顺序存储结构的线性表。

首先，定义了一个结构体来表示线性表：```#define MAXSIZE 100 //线性表最大长度typedef struct {int data[MAXSIZE]; //存放线性表元素int length; //线性表当前长度} SqList; //线性表类型定义```其中，data数组存放线性表元素，length表示线性表当前长度。

接着，定义了三个基本操作：1. 初始化线性表```void InitList(SqList *L) {L->length = 0;}```2. 插入元素```bool ListInsert(SqList *L, int i, int e) {if (i < 1 || i > L->length + 1) { //插入位置不合法}if (L->length >= MAXSIZE) { //线性表已满return false;}for (int j = L->length; j >= i; j--) { //将第i个位置之后的所有元素后移一位L->data[j] = L->data[j - 1];}L->data[i - 1] = e; //将元素e插入到第i个位置L->length++; //线性表长度加1return true;}```3. 删除元素以上三个操作就是线性表的基本操作，通过这三个操作就能完成线性表的所有操作。

实验二、栈和队列的实现2.1 栈的实现栈是一种后进先出(Last In First Out)的数据结构。

我们可以用线性表来实现栈，只需要对线性表的插入和删除操作进行限制就行了。

具体实现如下：void InitStack(Stack *S) {S->top = -1; //初始化栈顶指针}bool Push(Stack *S, int e) {if (S->top == STACK_SIZE - 1) { //栈已满，无法插入元素}S->top++; //栈顶指针加1S->data[S->top] = e; //插入元素e到栈顶return true;}以上代码实现了栈的初始化、入栈和出栈操作。

《数据结构》实验报告实验题目：线性表的操作实验目的：1.掌握上机调试线性表的基本方法；2.掌握线性表的一些基本操作；实验内容：将两个有序链表合并为一个有序链表一、需求分析1.实验程序中先创建两个有序链表，演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入两个链表中的相应数据。

2.将两个链表合并时可按数据从大到小或从小到大合并，用户根据提示可选择一种排序方式。

3.程序执行命令包括：（1）构造链表；（2）输入数据；（3）合并两个链表，根据用户需求选择一种排序方式；（4）将合并结果输出；（5）结束4.测试数据：链表1数据为：2，4，6，7，10链表2数据为：1，3，5，6，7，12按从小到达合并为：1，2，3，4，5，6，6，7，7，10，12；按从大到小合并为：12，10，7，7，6，6，5，4，3，2，1；二、概要设计1.基本操作Linklist creat （）操作结果：构造一个链表，并输入数据，返回头节点指针。

void print(Linklist head)初始条件：链表已存在；操作结果：将链表输出。

void MergeList_1(Linklist La,Linklist Lb)初始条件：有序线性链表La 和Lb 已存在；操作结果：将La 和Lb 两个链表按从小到大的顺序合并。

void MergeList_2(Linklist La,Linklist Lb)初始条件：有序线性链表La 和Lb 已存在；操作结果：将La 和Lb 两个链表按从大到小的顺序合并。

2.本程序包括四个模块：（1）主程序模块；（2）链表数据输入模块；（3）链表合并模块；（4）链表输出模块；三、详细设计1.元素类型，节点类型，指针类型主程序模块 数据输入 按从小到大合并两链表 按从大到小合并两链表 将新链表输出 将新链表输出typedef struct LNode //定义节点{int data;struct LNode *next;}LNode,* Linklist;2.每个模块的分析（1）主函数模块int main(){Linklist head1,head2;int i;printf("请输入链表1数据（由小到大，输入0表示输入结束）：\n");head1=creat(); //创建链表1，将头结点指针返回为head1printf("请输入链表2数据（由小到大，输入0表示输入结束）：\n");head2=creat();printf("请选择排序方式（输入1则从小到达合并，输入其它整数则按从大到小合并）：");scanf("%d",&i); //创建链表2，将头结点指针返回为head2if(i==1) //选择两种排序方式，如果输入1，则合并后按从小到大输出；输入其它数，合成链表按从大到小输出{printf("按小到大将两表合并得：\n");MergeList1(head1,head2); //将创建好的两表的头结点地址head1，head2作为函数参数}else{ printf("按从大到小将两表合并得：\n");MergeList2(head1,head2); //将创建好的两表的头结点地址head1，head2作为函数参数}return 0;}（2）数据输入创建链表模块Linklist creat() //创建链表函数，并将创建链表的头结点指针返回{Linklist head,p,s;int z=1,x;head=(LNode *) malloc(sizeof(LNode));p=head;while(z){scanf("%d",&x);if(x!=0) //输入0表示链表数据输入结束{s=(LNode *)malloc(sizeof(LNode));s->data=x;p->next=s;s->next=NULL;p=s;}elsez=0;}return(head);}（3）合并链表模块，两个函数分别表示两种排序方式，将链表合并后直接在函数中调用链表输出函数void print(Linklist head)将链表输出void MergeList_1(Linklist La,Linklist Lb)//已知链表La和Lb元素都按从小到大排列，将La和Lb合并成新链表，其中元素也按从小到大排列{Linklist pa,pb,pc,Lc;pa = La->next; pb = Lb->next;Lc = pc = La; //把La的头节点作为新建链表Lc的头结点while (pa && pb){if (pa->data <= pb->data){pc->next = pa;pc = pa;pa = pa->next;}else{pc->next = pb;pc = pb;pb = pb->next;}}pc->next = pa ? pa : pb; //插入剩余段print(Lc); //将链表Lc输出}void MergeList_2(Linklist La,Linklist Lb)//已知链表La和Lb的元素都按从小到大排列，合并La和Lb得到新链表，其中元素按照从大到小的顺序排列{Linklist pa,qa,pb,qb,Lc; //设指针qa,qb,分别作为pa,pb的前驱的指针pa=La->next;pb=Lb->next;Lc=La;Lc->next=NULL;while(pa&&pb){if(pa->data<=pb->data){qa=pa;pa=pa->next;qa->next=Lc->next;Lc->next=qa;}else{qb=pb;pb=pb->next;qb->next=Lc->next;Lc->next=qb;}}while(pa) //如果pa不为空，则将La链的剩余段倒叙插入到头节点的后面{qa=pa;pa=pa->next;qa->next=Lc->next;Lc->next=qa;}while(pb) //如果pb不为空，则将Lb链的剩余段倒叙插入到头结点的后面{qb=pb;pb=pb->next;qb->next=Lc->next;Lc->next=qb;}print(Lc); //将新合成的链表Lc输出}(4)链表输出模块，实现最终链表的输出void print(Linklist head) //链表输出函数，将链表输出{LNode *p;p=head->next;if(head!=NULL)do{printf("%d ",p->data);p=p->next;} while (p);printf("\n");四、程序使用说明及测试结果1.程序使用说明（1）本程序的运行环境为VC6.0；（2）进入演示程序后显示提示信息：请输入链表1数据（由小到大，输入0表示输入结束）：按要求输入数据请输入链表2数据（由小到大，输入0表示输入结束）：按要求输入数据请选择排序方式（输入1则从小到达合并，输入其它整数则按从大到小合并）：输入数据选择合并方式2.测试结果对链表1输入数据2，4，6，7，10，0对链表2输入数据1，3，5，6，7，12，0输入数据选择排序方式：如果输入：1 输出结果为：1，2，3，4，5，6，6，7，7，10，12如果输入：3（整数非1）输出结果为：12，10，7，7，6，6，5，4，3，2，13.调试中遇到的错误分析第一次运行时有问题，看以看出它的排序方式是对的，但是输出是多出前面一个很大的数，可能是输出函数void print(Linklist head)有问题，检查程序：此处逻辑出错，直接将p指针指向head，然后就将p->data输出，因此第一个数是头指针head所对应节点的值，所以可将p=head;改为p=head->next;这样p就指向第一个节点。

数据结构线性表实验报告五篇第一篇：数据结构线性表实验报告实验报告课程名：数据结构实验名：线性表及其操作姓名：班级：学号：撰写时间：2014.09.24一实验目的与要求1.掌握线性表的实现2.掌握线性表的基本操作的实现二实验内容• 分别完成线性表的顺序表示及链式表示• 在两种表示上, 分别实现一些线性表的操作, 至少应该包括–在第i个位置插入一个元素–删除第i个元素–返回线性表长–返回第i个元素的值三实验结果与分析#include #include //---------线性表链式表示-----------struct V//声明一个结构体类型struct V { int value;struct V * next;//定义结构体变量};void PrintLink(struct V*p)//定义一个结构体指针{ while(p!=NULL)//只要指针指向的变量不为NULL；就会一直循环链表指向下一个结构体{printf(“%d, ”,(*p).value);p=(*p).next;//指针指向下一个结构体} printf(“n”);} void Link(){struct V*head;head=(struct V*)malloc(sizeof(struct V));//开辟一个长度为size的内存(*head).value=-100;//表头为-100(*head).next=NULL;printf(“------------线性表链式表示------------n”);int i,n=10;struct V*p=head;printf(“10个数据:n”);for(i=0;i(*p).next=(struct V*)malloc(sizeof(struct V));p=(*p).next;(*p).value=2*i;(*p).next=NULL;} PrintLink(head);//调用PrintLink函数printf(“删除第四个数据:n”);int k=4;p=head;for(i=1;ip=(*p).next;} struct V*temp=(*p).next;//k表示插入和删除的位置(*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十个数据:n”);k=10;p=head;for(i=1;ip=(*p).next;} temp=(*p).next;(*p).next=(struct V*)malloc(sizeof(struct V));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);}//---------线性表顺序表示-----------void seq1(){ int i,n=10,k=4;int a[10];//---------输出数组元素------------printf(“-------------线性表顺序表示---------n”);for(i=0;ia[i]=i;} printf(“数组元素为:n”);for(i=0;iprintf(“%3d”,a[i]);} printf(“n”);//--------插入一个数组元素---------int m=n+1,j=12;//插入元素12 int b[20];for(i=0;i if(i{b[i]=a[i];}else if(i==k){b[i]=j;}else{b[i]=a[i-1];} } printf(“输出插入一个元素的数组:n”);for(i=0;i{if(i{c[i]=a[i];}else{c[i]=a[i+1];} } printf(“输出删除一个元素的数组:n”);for(i=0;i printf(“数组元素为:n”);for(i=1;i<=a[0];i++){a[i]=i;} for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-----在k 位置插入一个元素------------for(i=a[0];i>=k;i--){a[i+1]=a[i];} a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-------在k---------------for(i=0;i>k;i++){a[i]=a[i+1];} a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);} int main(int argc,char *argv[]){ seq1();seq2();Link();return 0;} 图1：实验结果截图实验分析：已在程序中按规定格式标注。

数据结构——线性表（顺序实现） 好好学习基础知识，出⼈头地就靠它了，内外兼修。

（好吧，我现在内外都不⾏）写这篇⽂章的⽬的就是为了，巩固刚学完的线性表，个⼈能⼒有限，若有不当之处，望指出。

线性表 好了，扯完了，说正事： 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. 实验目的1.1 理解线性表的概念和特性1.2 学习线性表的顺序存储结构和链式存储结构1.3 掌握线性表的基本操作：初始化、插入、删除、查找、修改、遍历等1.4 熟悉线性表的应用场景2. 实验内容2.1 线性表的顺序存储结构实现2.1.1 定义线性表结构体2.1.2 初始化线性表2.1.3 插入元素2.1.4 删除元素2.1.5 查找元素2.1.6 修改元素2.1.7 遍历线性表2.2 线性表的链式存储结构实现2.2.1 定义链表节点结构体2.2.2 初始化链表2.2.3 插入元素2.2.4 删除元素2.2.5 查找元素2.2.6 修改元素2.2.7 遍历链表3. 实验步骤3.1 实现顺序存储结构的线性表3.2 实现链式存储结构的线性表3.3 编写测试程序，验证线性表的各种操作是否正确3.4 进行性能测试，比较两种存储结构的效率差异4. 实验结果与分析4.1 执行测试程序，检查线性表的操作结果是否正确4.2 对比顺序存储结构和链式存储结构的性能差异4.3 分析线性表的应用场景，总结线性表的优缺点5. 实验总结5.1 总结线性表的定义和基本操作5.2 回顾实验中遇到的问题和解决方法5.3 提出对线性表实现的改进方向和思考附件：请参考附件中的源代码和实验报告模板。

法律名词及注释：1. 版权：指对某一作品享有的法律上的权利，包括复制权、发行权、改编权等。

2. 法律责任：指违反法律或合同规定所承担的责任。

3. 保密义务：指个人或组织根据法律、法规、合同等规定需要承担的保密责任。

4.知识产权：指人们在社会实践中所创造的智力劳动成果所享有的权利，包括专利权、著作权、商标权等。