当前位置：文档之家› 实验1_线性表的基本操作

实验1_线性表的基本操作

北京林业大学实验任务书

北京林业大学

11学年—12学年第 1学期数据结构实验任务书

专业名称：实验学时： 4

课程名称：数据结构任课教师：

实验题目：线性表的基本操作

实验环境： Visual C++

实验目的：

1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，高数成绩，英语成绩，数据结构成绩）的顺序表和链表，使其具有如下功能：

(1) 从指定的文件student.txt，逐个读入学生信息（文件中第一行为学生个数，后面每行存放一个学生信息）；

(2) 逐个显示学生表中所有学生的相关信息；

(3) 统计表中学生个数；

(4) 根据姓名进行查找，返回此学生的学号和各科成绩；

(5) 根据指定的位置可返回相应的学生的全部信息；

(6) 查询所有同学中三门课程平均分最高和最低的同学的信息；

(7) 给定一个学生信息，插入到表中指定的位置，将插入后的结果重新写入文件

student.txt；

(8)删除指定位置的学生记录，将删除后的结果重新写入文件student.txt；

选做内容（利用链表实现，学生信息存储在文件student1.txt中）：

（1）将学生信息按照数据结构成绩高低进行分段管理，依次存储满分，90分段，80分段，…，60分段，不及格分段同学信息。成绩段是递增有序的，每个成绩段

内不要求有序。完成以下操作：

①插入：根据给定的数据结构成绩将学生信息插入到相应成绩段的任意位置；

②删除：根据给定的数据结构成绩将相应学生信息删除（不考虑成绩相同的情

况）；

③查找：根据给定数据结构成绩进行查找，返回相应学生的全部信息。

（2）实现两个多项式的加法运算。

实验提示：（参考SqList.cpp和 LinkList.cpp）

（1）学生信息的定义：

typedef struct {

char no[8]; //8位学号

char name[20]; //姓名

int Maths_score; //高数成绩

int English_score; //英语成绩

int DS_score; //数据结构成绩

}Student;

顺序表的定义

typedef struct {

Student *stu; //指向数据元素的基地址

int length; //线性表的当前长度

}SqList；

链表的定义：

typedef struct LNode{

Student data; //数据域

struct LNode *next; //指针域

}LNode,*LinkList;

（2）对学生信息按照数据结构成绩高低进行分段管理时，可以采用指针数组，数组中存储每个成绩段的第一个学生结点的地址，成绩段是递增有序的，每个成绩

段内不要求有序，如下图所示。在进行插入、删除或查询等操作时，要使用指

针数组。

实验要求：

(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。

(5) 上传一个压缩包到ftp的相应班级所在文件夹，压缩包按以下方式命名：学号姓名.rar。压缩包包含以下四个文件：

顺序表的源程序：SqList.cpp

链表的源程序：LinkList.cpp

数据文件：student.txt

实验报告：实验报告1.doc

数据结构实验报告实验一线性表链式存储运算的算法实现

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称线性表链式存储运算的算法实现指导教师教师评语教师签名：年月日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束

pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点，退出 while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果：

实验一线性表的基本操作实现及其应用

实验一线性表的基本操作实现及其应用一、实验目的 1、熟练掌握线性表的基本操作在两种存储结构上的实现。 2、会用线性链表解决简单的实际问题。二、实验内容题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示： please input the operation： 1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表（设为输出元素） 7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素其他键退出。。。。。其中黑体部分必做题目二、约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 struct node (一)

1．进入选择界面后，先选择7，进行插入： 2.选择4，进行遍历，结果为： 3.选择2，得出当前链表长度.

4.选择3，得出当前链表为. 5.选择分别选择5、6进行测试.

6.选择8，分别按位置和元素值删除. 7.选择9，或非1-8的字符，程序结束.

C语言数据结构线性表的基本操作实验报告

实验一线性表的基本操作一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。五、附源程序及算法程序流程图 1.源程序（1）源程序(实验要求1和3) #include #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct arr {

实验1 线性表及其应用

实验1 线性表及其应用题目1 顺序表的建立与基本操作一、实验目的 1. 通过实验，掌握include命令及头文件的使用 2. 通过实验，掌握顺序表的建立与输出 3. 通过实验，掌握顺序表的基本操作二、实验内容 1. 练习顺序表的建立与输出 2. 练习顺序表的基本操作三、实验前的准备 1. 理解并掌握顺序表的存储结构、基本操作 2. 复习include命令的使用 3. 预习实习指导书，并准备相关的程序清单四、实验步骤与方法（1）建立自己的工作目录（2）在当前文件夹下建立函数结果状态代码的定义文件Status.h（课本p10（1）预定义常量和类型）和数据结构数据文件SqList.h（内容包括顺序表的描述、顺序表建立、顺序表的查询、插入、删除与输出等功能。）（3）理解并运行下列程序： #include #include #include "Status.h" #include "SqList.h" void main() { SqList a; int i, k; InitList_Sq(a); printf("please input the data ,end of -99\n"); k = 0; scanf("%d",&i); while (i != -99) { a.elem[k] = i; k++; scanf("%d",&i); } a.length = k; printf("\n output the data:"); for (i = 0; i<=a.length-1; i++) printf("%d ",a.elem[i]); printf("\n"); } （4）编写算法，通过调用SqList.h中的相关函数，完成顺序表中指定位置数据的输出、元素的插入和删除题目2 链表的操作

数据结构实验一题目一线性表实验报告

北京邮电大学电信工程学院数据结构实验报告实验名称：实验1——线性表学生姓名：班级：班内序号：学号：日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力 2、实验内容：题目1：线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构带头结点的单链表

2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点将x写入到新结点的数据域修改新结点的指针域修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法

a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } 时间复杂度：O(n) 3、按位查找 a、伪代码实现: 初始化工作指针p和计数器j，p指向第一个结点，j=1 循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 若p为空，说明第i个元素不存在，抛出异常否则，说明p指向的元素就是所查找的元素，返回元素地址 b、代码实现 Node* Linklist::Get(int i)//得到指向第i个数的指针 {Node*p=front->next; int j=1; while(p&&j!=i)//p非空且j不等于i，指针后移 {p=p->next; j++;

实验1__线性表的应用

实验一线性表的应用一、实验教学目的 1、熟悉将算法转换成程序代码的过程。 2、了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。 3、熟悉链表数据结构的定义和插入、删除等基本操作，会使用链表的基本操作解决一些实际问题二、实验教学内容 1、实验题目 (1)用C语言数组实现顺序表,并在顺序表上实现：①在第3个位置插入666; ②将第8个元素删除；③在顺序表中查找值为65的元素。 (2)已知有两个多项式Pn(x)和Qm(x)，基于链表设计算法实现Pn(x)+Qm(x)运算，而且不重新开辟存储空间。 ⑶基于链表编程实现多项式乘法运算 2、实验要求： (1)要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。 (2)熟悉链表及其运算的实现。 ①自己编写实现函数； ②对所编写的算法进行时间复杂度分析。 ⑶实验⑴、⑵必做，实验⑶选做。 3、实验预备知识（1）复习C语言相关知识（如：结构体、用typedef自定义类型、函数）。（2）阅读顺序表与链表的类型定义和相应的插入、删除、查找等基本操作。 4、实验环境

（1）一台运行 Windows 2000/XP 操作系统的计算机。（2）选用turbo c、visual c++、delphi、c++ builder 或visual basic等任何一种语言。 5、实验说明（1）顺序存储定义 #define MAXSIZE 100/*表中元素的最大个数*/ typedef int datatype; /*元素类型*/ typedef struct {datatype data[MAXSIZE]; /*静态线性表*/ int last; /*表的实际长度*/ }seqlist; /*顺序表的类型名*/ （2）建立顺序表时可利用随机函数自动产生数据。（3）注意问题 ①插入、删除时元素的移动原因、方向及先后顺序。 ②不同的函数形参与实参的传递关系。（4）链表类型定义 typedef int datatype;/*元素类型*/ typedef struct node {datatype data; struct node *next; }lnode,*linklist;/*单链表的类型定义*/ （5）为了算法实现简单，最好采用带头结点的单向链表。（6）注意问题 ①重点理解链式存储的特点及指针的含义。 ②注意比较顺序存储与链式存储的各自特点。 ③注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 ④单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。三、实验内容和实验步骤：（由学生填写）四、实验用测试数据和相关结果分析：（由学生填写）五、实验总结：（由学生填写）六、程序参考模板

数据结构_实验1_线性表的基本操作

实验1 线性表的基本操作一、需求分析目的：掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间；二、概要设计 ●基础题主要函数：初始化线性表InitList（List* L，int ms）向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc）查找顺序表中的元素 FindList（List L，int item）输出顺序表元素OutputList（List L）实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题

要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素方法：按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。方法：分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。本程序主要包含7个函数主函数main() 初始化线性表InitList（List* L，int ms）向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc）查找顺序表中的元素 FindList（List L，int item）输出顺序表元素OutputList（List L）提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE;

线性表实验报告

一．实验名称 1.线性表基本操作； 2.处理约瑟夫环问题二．试验目的： 1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．定义单链表的结点类型。 3．熟悉对单链表的一些基本操作和具体的函数定义。 4．通过单链表的定义掌握线性表的链式存储结构的特点。 5．熟悉对单链表的一些其它操作。三．实验内容 1.编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。 2.编制一个能求解除约瑟夫环问题答案的程序。实验一线性表表的基本操作问题描述： 1. 实现单链表的定义和基本操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义程序中的单链表（带头结点）结点为结构类型，结点值为整型。 /* 定义DataType为int类型*/ typedef int DataType; /* 单链表的结点类型*/ typedef struct LNode {DataType 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) /* 从单链表表中查找与给定元素值相同的元素在链表中的位置*/ int LinkedListLocate(LinkedList L, DataType x) void LinkedListInsert(LinkedList L,int i,DataType x) //向单链表中插入元素 /* 从单链表中删除元素*/ void LinkedListDel(LinkedList L,DataType x)

数据结构实验一题目一线性表实验报告

数据结构实验报告实验名称：实验1——线性表学生姓名：班级：班内序号：学号：日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力 2、实验内容：题目1：线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构带头结点的单链表

数据结构线性表实验报告

实验报告实验一线性表实验目的： 1.理解线性表的逻辑结构特性； 2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容： 2－21设计单循环链表，要求：（1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。（2）设计一个测试主函数，实际运行验证所设计单循环链表的正确性。 2－22 .设计一个有序顺序表，要求：（1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。（2）设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。（3）设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。程序代码： 2－21（1）头文件LinList.h如下： typedef struct node { DataType data; struct node *next; }SLNode; /*（1）初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);

实验一线性表与应用(I)

姓名学号

ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i

线性表的基本操作实验报告

实验一：线性表的基本操作【实验目的】学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。【实验内容】 1.顺序表的实践 1) 建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。 2) 在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。 3) 在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。 2.单链表的实践 3.1) 建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。 2) 将该单链表的所有元素显示出来。 3) 在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。 4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。 5) 实现单链表的求表长操作。【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了刚创

建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 1、#include "stdio.h" #include "malloc.h" #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; int length; int listsize; } SqList; Status InitList( SqList &L ) { int i,n; L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType)); if (!L.elem) return(OVERFLOW); printf("输入元素的个数:"); scanf("%d",&n); printf("输入各元素的值:"); for(i=0;i

201560140140--袁若飞--实验1：线性表的基本操作及其应用

数据结构实验1：线性表的基本操作及其应用班级：RB软工移151 学号：201560140140 姓名：袁若飞

实验一线性表一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，题目一、二是必做题。题目三、题目四选作。三、实验准备知识 1、请简述线性表的基本特性和线性表的几种基本操作的机制 ①答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 ②答：线性表的几种基本操作的机制有六个：（1）初始化线性表initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。（2）求表长度List_length(L)——即求表中的元素个数。（3）按序号取元素get_element(L,i)——取出表中序号为i的元素。（4）按值查询List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。（5）插入元素List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n+1。（6）删除元素List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1<=i<=n。 2、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。

实验一线性表

数据结构试验报告线性表学院：姓名：学号：时间：专业班级：

线性表一、实验目的 1．掌握线性结构中顺序表和链表的基本概念、基本操作和应用； 2．掌握线性表的基本操作：建表、插入、删除、输出等运算在顺序存储结构和链式存储结构上的实现。 3．通过本次实习加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现。二、实验内容 1．编写生成线性表的函数，线性表的元素从键盘输入，分别使用顺序和链式存储结构存储；2．编写在线性表中插入一个元素的函数； 3．编写在线性表中删除一个元素的函数； 4．编写输出线性表的函数； 5．编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏幕输出。三、实验报告要求 1.画出程序流程图并做简单分析 2.源代码（包括主要结构、主要语句、函数注释说明） 3.运行结果（包括程序如何使用，输入数据和输出结果） 4.实验体会和问题分析四、基本原理（一）线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。例如26个英文元素的字母表（A，B，C，D，···），其数据结构的描述为： Linear_list=(D，R) 其中，D={ a i |a i属于ElemSet，i=1，2，3，···}，R={| i=2，3，4，…… }。本实验是以数组的形式把线性表存放在计算机内存的一个连续的区域内，这样便有：

LOC(a i+1)=LOC(a i)+m LOC(a i)=L0+m*(i-1) 其中，m是存放每个元素所占的内存字数，L0是a的地址，即首地址。（二）程序说明插入一个新元素到第i个位置，既把元素a i向后移一个位置，成为元素a i+1，把新元素放入到第i个位置，其他元素依次后移。插入后的表长是n+1（n是原表长）。修改第i个元素，到第i个位置是把元素a i冲掉后存上新值。删除第i个元素就是把余后的元素依次向前移一个位置。即：以元素a i+1，a i+2，···，依次取代a i，a i+1，···。删除后的表长是n-1（n是原表长）。（三）线性表链式存储（选作）。五、实验程序 #include #include #define MAXSIZE 20 // 数组最大界限 typedef int ElemType; //数据元素类型 typedef struct { ElemType a[MAXSIZE]; //一维数组子域 int length; //表长度域 }SqList; // 顺序存储的结构体类型 SqList a,b,c; 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); int locat_sq(SqList L,ElemType e); //主函数 void main() { int i,k,loc; ElemType e,x; char ch; do { printf("\n\n\n");