当前位置：文档库 › 实验一线性表的抽象数据类型的实现

实验一线性表的抽象数据类型的实现

数据结构实验

课程设计题目：实验一线性表的抽象数据类型的实现

姓名：杨静学号：2011114105

班级：2班（44号）组长：

指导老师：解德祥

计算机与信息学院

实验一线性表的抽象数据类型的实现

实验目的

1.掌握线性表的顺序存储结构和链式存储结构；

2.熟练掌握顺序表和链表基本算法的实现；

3.掌握利用线性表数据结构解决实际问题的方法和基本技巧；

4.按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程

序清单及及相关实验数据与运行结果）；

5.按时提交实验报告。

实验环境:计算机、C语言程序设计环境

实验学时:2学时，选做实验。

实验内容

一、顺序表的基本操作实现实验

要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：

①创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在

20之内；

②打印（遍历）该线性表（依次打印出表中元素值）；

③在线性表中查找第i个元素，并返回其值；

④在线性表中第i个元素之前插入一已知元素；

⑤在线性表中删除第i个元素；

⑥求线性表中所有元素值（整数）之和；

二、链表（带头结点）基本操作实验

要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：

①创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键

盘上输入），长度限定在15之内；

②打印（遍历）该链表（依次打印出表中元素值）；

③在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；

④在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返

回FALSE；

⑤在链表中按照有序方式插入一已知字符元素；

⑥在线性表中删除第i个结点；

⑦计算链表的长度。

实验步骤：

C源程序代码如下：

#include

#define OK 1#define ERROR 0

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{ElemType elem[MAXSIZE]; int last;

}SeqList;

void CreateSeqList(SeqList *L)

{ int x,i=0;

printf("请输入正整数，不超过20个:\n"); scanf("%d",&x);

while(i

{ L->elem[i]=x; scanf("%d",&x); i++; }

L->last=i;

}

void PrintList(SeqList *L)

{ int i; printf("数据元素为:\n");

for(i=0;ilast;i++) printf("%d\n",L->elem[i]);

}

int Locate(SeqList *L,int i )

{ if(i>=1&&i<=L->last) return L->elem[i-1];

else return 0;

}

int InsList(SeqList *L,int i,ElemType e)

{

int k;

if((i<1)||(i>L->last+2))

{ printf("插入i位置值不合法"); return(ERROR); }

if(L->last>=MAXSIZE-1)

{

printf("表已满，无法插入"); return(ERROR); }

for(k=L->last;k>=i-1;k++)

L->elem[k+1]=L->elem[k];

L->elem[i-1]=e; L->last++; return(OK);

}

int DelList(SeqList *L,int i,ElemType *e)

{int k;

if((i<1)||(i>L->last+1))

{

printf("删除位置不合法"); return(ERROR);

}

*e=L->elem[i-1];

for(k=i;i<=L->last;k++)

L->elem[k-1]=L->elem[k]; L->last--; return(OK);

}

int SumList(SeqList *L)

{

int i,sum=0;

for(i=0;i<=L->last;i++)

sum=sum+L->elem[i]; return(sum);

}

void jiemian()

{

SeqList L;

int j,i,a;

printf("创建新链表请按1\n打印链表请按2\n按序号查找元素请按3\n在链表中查找与一已知字符相同的第一个结点请按4\n在链表中按照有序方式插入一已知字符元素请按5\n在线性表中删除第i个结点请按6\n计算链表的长度请按7\n操作结束请按0\n");

scanf("%d",&j);

while(j)

{

switch(j)

{

case 1:CreateSeqList(&L); break;

case 2: printf("打印顺序表如下:\n");

PrintList(&L); break;

case 3:printf("请问你要查找第几个元素:\n");

scanf("%d",&i);

if(Locate(&L,i ))

printf("您要找的元素为%d\n",Locate(&L,i ));

else printf("i值不合法!"); break;

case 4:printf("请您输入选择插入位置以及输入插入元素:\n");

scanf("%d%d",&i,&a);

if(InsList(&L,i,a)) PrintList(&L);

else printf("i值不合法!\n"); break;

case 5: printf("请您输入要删除元素的位置:\n");

scanf("%d",&i);

if(DelList(&L,i,&a)) PrintList(&L);

else printf("i值不合法!\n"); break;

case 6:printf("所有元素之和为:%d\n",SumList(&L)); break;

case 7: break;

default: printf("数据输入错误，请重新输入!");

}

printf("操作结束请按7;继续操作请按1-6,请输入您的选择:\n");

scanf("%d",&j);

}

void main()

{ jiemian();}

链表（带头结点）基本操作实验：

#include"stdlib.h"

#include"stdio.h"

struct LNode

{

char elem;

struct LNode* next;

}*l,*p,*q;

void Order(struct LNode * l, int n) {

int i;char swap,*e,*f;

for(i=1;i<=n-1;i++)

{p=l->next;

while(p->next!=l)

{ if(p->elem>p->next->elem) {e=&p->elem;

f=&p->next->elem;

swap=*e;

*e=*f;

*f=swap;

}

p=p->next;

}

return;

}

void Print(struct LNode * l, int n)

{

int i;

p=l->next;

for(i=1;i<=n;i++)

{

printf("%c\n",p->elem);

p=p->next;

}

printf("\n");

return;

}

void Locate(struct LNode * l, int n,int m)

{

int i;

if(m>n)

{ printf("FALSE!\t");return; }

else

{ p=l;

for(i=1;i<=m;i++)

{p=p->next;}

printf("The elem is:%c\n",p->elem);

}

return;

}

void Insertelem(struct LNode * l, int n,char m) {

q=(struct LNode *)malloc(sizeof(struct LNode)); q->next=l->next;

l->next=q;

q->elem=m;

n=n+1;

Order(l,n);

Print(l,n);

return;

}

void Delete(struct LNode * l, int n,int m)

{

int i;

p=l;

for(i=1;i

{p=p->next;}

p->next=p->next->next;

n=n-1;

printf("删除后的链表为:\n");

Print(l,n);

return;

}

void Length(int n)

{

int i;int length=0;

for(i=1;i<=n+1;i++)

{length=length+sizeof(struct LNode);}

printf("--------------------------------------------------------------\n"); printf("The length of the list is:%d\n",length);

return;

}

main()

{

printf("- - - - - - - - - - - - -- 欢迎进入数据结构实验设计- - - - - - - - - - - - - -\n");

int i,a,k,n;char c,s;

l=(struct LNode *)malloc(sizeof(struct LNode));

l->next=NULL;

printf("请输入链表的元素数: ");

scanf("%d",&n);getchar();

if(n<=15)

{

for(i=n;i>0;i--)

{ q=(struct LNode *)malloc(sizeof(struct LNode));

q->next=l->next;

l->next=q;

}

p=l;

while(p->next!=NULL) p=p->next;

p->next=l;

printf("输入元素:");

p=l->next;

for(i=1;i<=n;i++)

{ scanf("%c",&p->elem);

getchar();

p=p->next;

}

Order(l,n);

printf("--------------------------------------------------------------\n"); printf("您输入的元素为:\n");

Print(l,n);

printf("--------------------------------------------------------------\n"); printf("输入您想查找的元素序号:");

scanf("%d",&a);getchar();

Locate(l,n,a);

printf("--------------------------------------------------------------\n"); printf("输入您想插入的元素:");

scanf("%c",&s);getchar();

Insertelem(l,n,s);

n=n+1;

printf("--------------------------------------------------------------\n"); printf("输入您要删除的元素序号:");

scanf("%d",&k);

if(k<1||k>n)printf("ERROR!");

else{Delete(l,n,k);}

n=n-1;

Length(n);

}

else printf("ERROR!");

}

有理数抽象数据类型定义

ADT Rational { //起名要易懂数据对象：D={e1,e2|e1,e2∈Z,e2≠0} //分母不为零数据关系：R={|e1表示分子，e2表示分母} //说明不可丢基本操作： InitRational (&Q,v1,v2) 初始条件:v2 ≠0 操作结果:构造有理数Q，其分子和分母分别为v1与v2。 DestroyRational(&Q) 初始条件：有理数Q存在操作结果：有理数Q被撤销。 RationalPrint(Q) 初始条件：Q存在操作结果：以分数形式输出有理数 RationalAdd (Q1,Q2,&sum)//Substract,Multiply等操作略初始条件：有理数Q1与Q2存在操作结果：用sum返回Q1与Q2的和 } ADT Rational //--采用动态分配的“顺序”存储结构-- typedef int ElemType; typedef ElemType * Rational;

Status InitRational(Rational &Q,ElemType v1, ElemType v2){ //构造有理数Q，分子分母分别为v1,v2，若v2=0则Q赋空，返回Error if(v2==0){Q=NULL;return ERROR;} /*return后括号可有可无*/ Q=(ElemType *)malloc(2*sizeof(ElemType)); //莫忘malloc.h if(!Q)exit(OVERFLOW);//分配存储空间失败, stdlib.h,注意!及适用场合用法Q[0]=v1;Q[1]=v2; /*之前的else可省略，若不省略最好加花括号*/ return(OK); } Status DestroyRational(Rational &Q) //销毁有理数Q { if(Q) { free(Q); Q=NULL; return OK; } } void OutputRational(Rational Q){ //以分数形式输出有理数Q if(!Q)printf(“the rational does not exist! \n‘); printf(“ %d/%d ”,Q[0],Q[1]); }

数据结构实验报告全集

数据结构实验报告全集实验一线性表基本操作和简单程序 1．实验目的（1）掌握使用Visual C++ 6.0上机调试程序的基本方法；（2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）认真阅读和掌握本章相关内容的程序。（3）上机运行程序。（4）保存和打印出程序的运行结果，并结合程序进行分析。（5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

线性表实验报告

线性表实验报告一、实验的目的要求 1、了解线性表的逻辑结构特性，以及这种结构特性在计算机内的两种存储结构。 2、掌握线性表的顺序存储结构的定义及其C语言实现。 3、掌握线性表的链式存储结构——单链表的定义及其C语言实现。 4、掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5、掌握线性表在链式存储结构——单链表中的各种基本操作。 6、认真阅读和掌握实验的程序。 7、上机运行本程序。 8、保存和打印出程序的运行结果，并结合程序进行分析。二、实验的主要内容题目：请编制C语言，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表，并输出该单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；最后在屏幕菜单中选择0，即可结束程序的运行。三、解题思路分析在链表中插入数据，不需要进行大量的数据移动，只需要找到插入点即可，可以采用后插入的算法，在插入点的后面添加结点。在链表中删除数据，先找到删除点，然后进行指针赋值操作。四、程序清单 #include #include #include typedef int ElemType; typedef struct LNode {ElemType data; struct LNode *next; }LNode;

LNode *L; LNode *creat_L(); void out_L(LNode *L); void insert_L(LNode *L,int i,ElemType e); ElemType delete_L(LNode *L,ElemType e); int locat_L(LNode *L,ElemType e); void main() {int i,k,loc; ElemType e,x; char ch; do{printf("\n"); printf("\n 1.建立单链表"); printf("\n 2.插入元素"); printf("\n 3.删除元素"); printf("\n 4.查找元素"); printf("\n 0.结束程序运行"); printf("\n================================"); printf("\n 请输入您的选择(1,2,3,4,0)"); scanf("%d",&k); switch(k) {case 1:{L=creat_L(); out_L(L); }break; case 2:{printf("\n请输入插入位置:"); scanf("%d",&i); printf("\n请输入要插入元素的值：");

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)

完整版信管实验报告(线性表基本操作)

管理学院信管专业12（1）班学号3112004734 姓名钟臻华协作者：无教师评定_________________ 实验题目线性表的基本操作实验评分表

实验报告一、实验目的与要求 1.本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2.根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。二、实验内容 1.分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。 1.顺序表的不删除出环元素算法实现 public class Josephus3{ public Josephus3(int number,int start,int distance){//创建约瑟夫环并求解,参数指定环长度,起始位置,计数 //采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量 S eqList list=new SeqList(number); S tring a=new String("null"); f or(int i=0;i

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

昆明理工大学信息工程与自动化学院学生实验报告（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_线性表的基本操作

实验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——线性表学生姓名：班级：班内序号：学号：日期： 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++;

哈工大数据结构实验一线性表的实验

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：线性表实验实验题目：算术表达式求值班级：0903201 学号：1090320110 姓名：王岳

一、实验目的二、实验要求及实验环境三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 1．逻辑设计 2．物理设计四、测试结果五、系统不足与经验体会六、附录：源代码（带注释） #include using namespace std; template class stack{ private: elementtype ss[512]; int top; public: stack() { this -> top =0; } void null() { this -> top =0; } bool empty() { if (this -> top ==0) return true; else return false; } elementtype pop() { if (this -> empty()) printf("error:empty!!!\n");

else { this -> top--; return this -> ss[this -> top + 1]; } } void push(elementtype x) { if (this -> top == 511) printf("error:full!!!\n"); else { this -> top++; this -> ss[this -> top] = x; } } }; void change(int &i,int &j,double *a,char *input,stack &s){//change front to back char o,p; bool fu=true; while(true){ o=cin.peek(); if((o<'('||o>'9')&&o!='\n') {o=getchar();fu=false; continue;} else if(o>='0'&&o<='9') {scanf("%lf",&a[i]); input[j]=i+'0';i++;j++; } else if(o=='(') {o=getchar();s.push(o);fu=true;continue;} else if(o==')') { o=getchar(); for(;!s.empty();){ input[j]=s.pop();j++; if(input[j-1]=='(') {j--;break;} } } else if(o=='*'||o=='/'){ o=getchar(); for(;!s.empty();){ p=s.pop(); if(p=='*'||p=='/') {input[j]=p;j++;} else {s.push(p);break;} } s.push(o); } else if(o=='+'||o=='-'){ o=getchar(); if(fu) {a[i]=0;input[j]=i+'0';i++;j++;} for(;!s.empty();){ p=s.pop(); if(p!='(') {input[j]=p;j++;} else {s.push(p);break;}

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

姓名学号

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

抽象数据类型线性表的定义

抽象数据类型线性表的定义如下： ADT List { 数据对象：D={ a i | a i∈ElemSet, i =1, 2, ……, n, n≥0} 数据关系：R1 = { < a i-1 , a i > | a i-1 , a i ∈D, i =2, ……, n } 基本操作： InitList (&L ) 操作结果：构造一个空的线性表L 。 DestoryList (&L) 初始条件：线性表L已存在。操作结果：销毁线性表L。 ClearList (&L) 初始条件：线性表L已存在。操作结果：将L重置为空表。 ListEmpty (L) 初始条件：线性表L已存在。操作结果：若L 为空表，则返回TRUE，否则返回FALSE。 ListLength (L) 初始条件：线性表L已存在。操作结果：返回L中数据元素个数。 GetElem ( L, i, &e ) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。

操作结果：用e返回L中第i个数据元素的值。 LocateElem ( L,e, compare() ) 初始条件：线性表L已存在，compare()是判定函数。操作结果：返回L中第1个与e满足关系compare() 的数据元素的位序。若这样的数据元素不存在，则返回值0。 PriorElem ( L, cur_e, &pre_e ) 初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素且不是第1个，则用pre_e返回它的前驱，否则操作失败。 NextElem ( L, cur_e, &next_e ) 初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素且不是最后一个，则用next_e返回它的后继，否则操作失败。 ListInsert ( &L, i, e ) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e， L的长度加1。 ListDelete( &L, i, &e ) 初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，

数据结构实验一实验报告

班级：：学号：实验一线性表的基本操作一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。二、实验容定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK;

实验一线性表

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

线性表一、实验目的 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");