实验二:单链表的基本操作
一、【实验目的】
1、理解和掌握单链表的类型定义方法和结点生成方法。
2、掌握建立单链表和显示单链表元素的算法。
3、掌握单链表的查找、插入和删除算法
二、【实验内容】
1、建立一个整形数的单链表,手动输入10个数,并从屏幕显示单链表元素列表。
2、从键盘输入一个数,查找在以上创建的单链表中是否存在该数;如果存在,显示它的位置;如果不存在,给出相应提示。
3、删除上述单链表中指定位置的元素。
以下是程序部分代码,请调试并补充使之正确运行:
1.LinList.h
typedef struct Node
{
DataType data;
struct Node *next;
} SLNode;
void ListInitiate(SLNode **head) /*初始化*/
{
/*如果有内存空间,申请头结点空间并使头指针head指向头结点*/
if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
(*head)->next = NULL; /*置链尾标记NULL */
}
int ListLength(SLNode *head)
{
SLNode *p = head; /*p指向首元结点*/
int size = 0; /*size初始为0*/
while(p->next != NULL) /*循环计数*/
{
p = p->next;
size ++;
}
return size;
}
int ListInsert(SLNode *head, int i, DataType x)
/*在带头结点的单链表head的数据元素ai(0 ≤i ≤size)结点前*/
/*插入一个存放数据元素x的结点*/
{
SLNode *p, *q;
int j;
p = head; /*p指向首元结点*/
j = -1; /*j初始为-1*/
while(p->next != NULL && j < i - 1)
/*最终让指针p指向数据元素ai-1结点*/
{
p = p->next;
j++;
}
if(j != i - 1)
{
printf("插入位置参数错!");
return 0;
}
/*生成新结点由指针q指示*/
if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
q->data = x;
q->next = p->next; /*给指针q->next赋值*/
p->next = q; /*给指针p->next重新赋值*/
return 1;
}
int ListDelete(SLNode *head, int i, DataType *x)
/*删除带头结点的单链表head的数据元素ai(0 ≤i ≤size - 1)结点*/ /*删除结点的数据元素域值由x带回。删除成功时返回1;失败返回0*/ {
SLNode *p, *s;
int j;
p = head; /*p指向首元结点*/
j = -1; /*j初始为-1*/
while(p->next != NULL && p->next->next!= NULL && j < i - 1)
/*最终让指针p指向数据元素ai-1结点*/
{
p = p->next;
j++;
}
if(j != i - 1)
{
printf("插入位置参数错!");
return 0;
}
s = p->next; /*指针s指向数据元素ai结点*/
*x = s->data; /*把指针s所指结点的数据元素域值赋予x*/ p->next = s->next; /*把数据元素ai结点从单链表中删除指*/
free(s); /*释放指针s所指结点的内存空间*/
return 1;
}
int ListGet(SLNode *head, int i, DataType *x)
/*取数据元素ai和删除函数类同,只是不删除数据元素ai结点*/
{
SLNode *p;
int j;
p = head;
j = -1;
while(p->next != NULL && j < i)
{
p = p->next; j++;
}
if(j != i)
{
printf("取元素位置参数错!");
return 0;
}
*x = p->data;
return 1;
}
void Destroy(SLNode **head)
{
SLNode *p, *p1;
p = *head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
*head = NULL;
}
2. main 程序
#include
#include
void main(void)
{
SLNode *head;
int i , x;
ListInitiate(&head); /*初始化*/
for(i = 0; i < 10; i++)
{
if(ListInsert(head, i, i+1) == 0) /*插入10个数据元素*/
{
printf("错误! \n");
return;
}
}
}
三、【实验源代码】
1.执行代码:
#include
#include
#include
#include "LinList.h"
void main(void)
{
SLNode *head;
int i,x,t;
ListInitiate(&head);
printf("请输入10个数");
for(i = 0; i < 10; i++)
{
scanf("%d",&t);
if(ListInsert(head, i, t) == 0)
{
printf("错误! \n");
return;
}
}
printf("请输入要查找的数字.\n");
scanf("%d",&t);
ListFind(head, t);
printf("请输入要删除的数字.\n");
scanf("%d",&t);
if(ListDelete(head,&t)==1)
printf("删除成功!\n");
else
printf("错误!\n");
ListOutput(head);
}
2.头文件
typedef struct Node
{
int data;
struct Node *next;
} SLNode;
void ListInitiate(SLNode **head) /*初始化*/ {
/*如果有内存空间,申请头结点空间并使头指针head指向头结点*/
if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
(*head)->next = NULL; /*置链尾标记NULL */ }
int ListLength(SLNode *head)
{
SLNode *p = head; /*p指向首元结点*/
int size = 0; /*size初始为0*/
while(p->next != NULL) /*循环计数*/
{
p = p->next;
size ++;
}
return size;
}
int ListInsert(SLNode *head, int i, int x)
/*在带头结点的单链表head的数据元素ai(0 ≤ i ≤ size)结点前*/ /*插入一个存放数据元素x的结点*/
{
SLNode *p, *q;
int j;
p = head; /*p指向首元结点*/
j = -1; /*j初始为-1*/
while(p->next != NULL && j < i - 1)
/*最终让指针p指向数据元素ai-1结点*/
{
p = p->next;
j++;
}
if(j != i - 1)
{
printf("插入位置参数错!");
return 0;
}
/*生成新结点由指针q指示*/
if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
q->data = x;
q->next = p->next; /*给指针q->next赋值*/
p->next = q; /*给指针p->next重新赋值*/
return 1;
}
int ListDelete(SLNode *head, int *x)
/*删除带头结点的单链表head的数据元素ai(0 ≤ i ≤ size - 1)结点*/
/*删除结点的数据元素域值由x带回。删除成功时返回1;失败返回0*/
{
SLNode *p, *s;
int j;
p = head; /*p指向首元结点*/
j = -1; /*j初始为-1*/
while(p->next != NULL && p->next->next!= NULL && p->next->data !=*x) /*最终让指针p指向数据元素ai-1结点*/
{
p = p->next;
j++;
}
// if(j != i - 1)
// {
// printf("插入位置参数错!");
// return 0;
// }
s = p->next; /*指针s指向数据元素ai结点*/
*x = s->data; /*把指针s所指结点的数据元素域值赋予x*/
p->next = s->next; /*把数据元素ai结点从单链表中删除指*/ free(s); /*释放指针s所指结点的内存空间*/ return 1;
}
int ListGet(SLNode *head, int i, int *x)
/*取数据元素ai和删除函数类同,只是不删除数据元素ai结点*/
{
SLNode *p;
int j;
p = head;
j = -1;
while(p->next != NULL && j < i)
{
p = p->next; j++;
}
if(j != i)
{
printf("取元素位置参数错!");
return 0;
}
*x = p->data;
return 1;
}
void Destroy(SLNode **head)
{
SLNode *p, *p1;
p = *head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
*head = NULL;
}
void ListFind(SLNode *head, int t)
{
SLNode *p = head; /*p指向首元结点*/
int s = 0; /*size初始为0*/
while(p->next != NULL&&p->data!=t) /*循环计数*/ {
p = p->next;
s++;
}
if(p->next==NULL)
{
printf("不存在该数字.\n");
}
else
printf("数字 %d 存在的位置是:%d.\n",t,s);
}
void ListOutput(SLNode *p)
{
do
p = p->next;
printf("%d ",p->data);
} while(p->next != NULL); }
四、【实验结果】
五、【实验心得】
实验二链表操作实现 实验日期: 2017 年 3 月 16 日 实验目的及要求 1. 熟练掌握线性表的基本操作在链式存储上的实现; 2. 以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3. 掌握线性表的链式存储结构的定义和基本操作的实现; 4. 通过本实验加深对C语言的使用(特别是函数的参数调用、指针类型的应用)。 实验容 已知程序文件linklist.cpp已给出学生身高信息链表的类型定义和基本运算函数定义。 (1)链表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别,0为男生,1为女生*/ } datatype; typedef struct node{ datatype data; /*数据域*/ struct node *next; /*指针域*/ } LinkNode, *LinkList; (2)带头结点的单链表的基本运算函数原型 LinkList initList();/*置一个空表(带头结点)*/ void createList_1(LinkList head);/*创建单链表*/ void createList_2(LinkList head);/* 创建单链表*/ void sort_xh(LinkList head);/*单链表排序*/ void reverse(LinkList head);/*对单链表进行结点倒置*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(LinkList head);/*打印单链表*/ void save(LinkList head,char strname[]);/*保存单链表到文件*/
重庆文理学院软件工程学院实验报告册 专业:_____软件工程__ _ 班级:_____软件工程2班__ _ 学号:_____201258014054 ___ 姓名:_____周贵宇___________ 课程名称:___ 数据结构 _ 指导教师:_____胡章平__________ 2013年 06 月 25 日
实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素(数据类型为整型)。 2.编程实现把顺序表中从i个元素开始的k个元素删除(数据类型为整型)。 3.编程序实现将单链表的数据逆置,即将原表的数据(a1,a2….an)变成 (an,…..a2,a1)。(单链表的数据域数据类型为一结构体,包括学生的部分信息:学号,姓名,年龄) 实验过程及步骤1. #include
{ ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置(下标值),空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n");
实验二单链表基本操作 一实验目的 1.学会定义单链表的结点类型,实现对单链表的一些基本操作和具体 的函数定义,了解并掌握单链表的类定义以及成员函数的定义与调用。 2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。二实验要求 1.预习C语言中结构体的定义与基本操作方法。 2.对单链表的每个基本操作用单独的函数实现。 3.编写完整程序完成下面的实验内容并上机运行。 4.整理并上交实验报告。 三实验内容 1.编写程序完成单链表的下列基本操作: (1)初始化单链表La。 (2)在La中第i个元素之前插入一个新结点。 (3)删除La中的第i个元素结点。 (4)在La中查找某结点并返回其位置。 (5)打印输出La中的结点元素值。 2 .构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、 Lb合并成一个有序单链表Lc。 合并思想是:程序需要3个指针:pa、pb、pc,其中pa,pb分别指向La表与Lb表中当前待比较插入的结点,pc 指向Lc表中当前最后一个结点。依次扫描La和Lb中的元素,比较当前元素的值,将较小者链接到*pc 之后,如此重复直到La或Lb结束为止,再将另一个链表余下的内容链接到pc所指的结点之后。 3.构造一个单链表L,其头结点指针为head,编写程序实现将L逆置。 (即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。) 四思考与提高 1.如果上面实验内容2中合并的表内不允许有重复的数据该如何操作? 2.如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只含La表中奇数结点,Lc中含有La表的偶数结点?
实验一单链表 #include "stdio.h" #include "stdlib.h" typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void creatLNode(LinkList &head) { int i,n; LNode *p; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; printf("请输入链表的元素个数:"); scanf("%d",&n); for(i=n;i>0;i--) { p=(LNode*)malloc(sizeof(LNode)); printf("第%d个元素:",i); scanf("%d",&p->data); p->next=head->next; head->next=p; } } void InsertLNode(LinkList &L) { LNode *p=L; int i,j=0,e; printf("请输入你要插入的位置(超过链表长度的默认插在最后!):"); scanf("%d",&i); printf("请输入你要插入的元素:"); scanf("%d",&e); while (p->next&&j
LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; } int DeleteLNode(LinkList &L,int i,int &e) { LNode *p; p=L; LNode *q; int j=0; while (p->next&&j
附页(实验2-1代码): 头文件“DEFINE2-1.h”: #define MaxSize 10 typedef struct { char data[MaxSize]; int length; }SqList; #include
理工学院实验报告 系部计算机系班级学号 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的: (1)掌握线性表的链式存储结构的特点; (2)掌握线性表的基本操作:初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件:计算机一台,vc++6.0 实验容与算法思想: 容: 建立一有序的链表,实现下列操作: 1.把元素x插入表中并保持链表的有序性; 2.查找值为x的元素,若找到将其删除; 3.输出表中各元素的值。 算法思想:先创建并初始化一个顺序表(void init_linklist(LinkList)),通过循环,输入一串数据void CreateFromTail(LinkList L);创建主函数;编写算法,完成子函数(查找locate,插入insList,删除DelList,输出output)模块;调用子函数,完成实验要求 运行结果:
附:源程序: #include
实验二单链表的基本算法一.实验目的: 通过上机编程掌握 1.生成单链表的基本算法; 2.在单链表上的插入、删除运算。 二.实验要求: 1. 给出程序设计的基本思想、原理和算法描述。 2. 画出程序流程图;根据数据结构有关知识编出算法程序; 3. 源程序给出注释; 4. 保存和打印出程序的运行结果,并结合程序进行分析。 三.实验内容: 1.编写函数实现单链表的基本运算: (1)单链表的生成 (2)单链表的插入 (3)单链表的删除 2.编写主函数测试单链表的各种基本运算: (1)生成一个至少包含有5个元素的单链表,元素值由计算机输入 (2)在表中的第5个位置上插入元素”7” (3)删除表中的第6个元素 (4)显示(1)—(3)每一步的操作结果
实验原理:首先建立头结点,形成一个单链表,通过malloc函数创建新的结点单元,将要读取的数据赋值给新结点。其次插入链表,从头结点开始依次延指针域查找需要插入的结点,为插入数据元素x生成一个新结点s,将x插入在s和s-1之间。最后链表结点删除,找到指定结点的前趋结点通过改变连接完成删除。 源程序: #include
信息学院 数据结构实验报告 学号:姓名:班级: 课程名称:数据结构实验名称:编写一个程序,实现对顺序表的如下操作: 1)初始化 2)创建一个顺序表(表长度至少为10)3)输出所创建的顺序表 4)键盘输入插入位置和插入元素,完成对表中插入元素的运算 5)键盘输入删除位置,实现对删除算法的调用,并输出被删除元素的值 6)创建两张有序表,实现这两张有序表的合并,并输出合并后的有序表。 实验性质:√①综合性实验②设计性实验③验证性实验实验时间:试验地点:机房 本实验所用设备:pc及C++6.0
【数据结构】: #define Maxsize 100 typedef int ElemType; typedef struct {ElemType elem[Maxsize]; int last; }SqeList;//建立顺序表; 【算法思想】: 通过基本算法熟悉数据结构。 创建表,运用增删改查实现表的操作后, 合并两表。 【算法描述】: void InitList(SqeList *L){printf("表已初始化!\n");L->last=-1;} void CreateForm(SqeList *L1){ InitList(L1); int i,n; printf("请输入要建表中的数组元素的个数,且不超过100:\n"); scanf("%d",&n); printf("你将输入的元素:\n"); for(i=0;i
洛阳理工学院实验报告 系部计算机系班级学号姓名 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的: (1)掌握线性表的链式存储结构的特点; (2)掌握线性表的基本操作:初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件:计算机一台,vc++6.0 实验内容与算法思想: 内容: 建立一有序的链表,实现下列操作: 1.把元素x插入表中并保持链表的有序性; 2.查找值为x的元素,若找到将其删除; 3.输出表中各元素的值。 算法思想:先创建并初始化一个顺序表(void init_linklist(LinkList)),通过循环,输入一串数据void CreateFromTail(LinkList L);创建主函数;编写算法,完成子函数(查找locate,插入insList,删除DelList,输出output)模块;调用子函数,完成实验要求 运行结果:
附:源程序: #include
顺序表的应用数据结构实验报告记录
————————————————————————————————作者:————————————————————————————————日期:
大学数据结构实验报告 课程名称数据结构实验第(三)次实验实验名称顺序表的应用 学生姓名于歌专业班级学号 实验成绩指导老师(签名)日期2018年9月30日一、实验目的 1.学会定义线性表的顺序存储类型,实现C程序的基本结构,对线性表的一些基本操作和具体的函数定义。 2.掌握顺序表的基本操作,实现顺序表的插入、删除、查找以及求并集等运算。 3.掌握对多函数程序的输入、编辑、调试和运行过程。 二、实验要求 1.预习C语言中结构体的定义与基本操作方法。 2.对顺序表的每个基本操作用单独的函数实现。 3.编写完整程序完成下面的实验内容并上机运行。 4.整理并上交实验报告。 三、实验内容: 1.定义一个包含学生信息(学号,姓名,成绩)的顺序表,使其具有如下功能: (1)根据指定学生个数,逐个输入学生信息 (2)逐个显示学生表中所有学生的相关信息 (3)根据姓名进行查找,返回此学生的学号和成绩 (4)根据指定的位置可返回相应的学生信息(学号,姓名,成绩) (5)给定一个学生信息,插入到表中指定的位置 (6)删除指定位置的学生记录 (7)统计表中学生个数 四、实验设计 1.定义一个包含学生信息(学号,姓名,成绩)的顺序表,使其具有如下功能: (1)根据指定学生个数,逐个输入学生信息 for(count=0; count 姓名: 学号: 班级: 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #include 数据结构实验一顺序表的实现 班级学号分数 一、实验目的: 1.熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现; 2.以线性表的各种操作的实现为重点; 3.通过本次学习帮助学生加深C语言的使用,掌握算法分析方法并对已经设计 出的算法进行分析,给出相应的结果。 二、实验要求: 编写实验程序,上机运行本程序,保存程序的运行结果,结合程序进行分析并写出实验报告。 三、实验容及分析: 1.顺序表的建立 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 程序如下: 头文件SqList.h的容如下: #include if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status CreatList_Sq(SqList *L,int n) { int i; printf("输入%d个整数:\n",n); for(i=0;i 实 验 报 告 一、实验目的 1) 加深对图的表示法和图的基本操作的理解,并可初步使用及操作; 2) 掌握用图对实际问题进行抽象的方法,可以解决基本的问题; 3) 掌握利用邻接表求解非负权值、单源最短路径的方法,即利用Dijkstra 算法求最短 路径,同时掌握邻接表的建立以及使用方法,能够解决相关的问题; 4) 学会使用STL 中的map 抽象实际问题,掌握map ,List,,priority_queue 等的应 用。 二、实验内容与实验步骤 (1) 实验内容: 使用图这种抽象的数据结构存储模拟的欧洲铁路路线图,通过Dijkstra 算法求出欧洲旅行最少花费的路线。该实验应用Dijkstra 算法求得任意两个城市之间的最少路费,并给出路费最少的路径的长度和所经过的城市名。 (2) 抽象数据类型及设计函数描述 1) 抽象数据类型 class City : 维护一个城市的信息,包括城市名name ,是否被访问过的标记visted ,从某个城市到达该城市所需的总费用total_fee 和总路径长度total_distance ,求得最短路径后路径中到达该城市的城市名from_city 。 class RailSystem : 用邻接表模拟欧洲铁路系统,该邻接表使用数据结构map 实现,map 的key-value 课程名称:数据结构 班级: 实验成绩: 实验名称:欧洲旅行 学号: 批阅教师签字: 实验编号:实验二 姓名: 实验日期:2013 年6 月 18 日 指导教师: 组号: 实验时间: 值对的数据类型分别为string和list<*Service>,对应出发城市名和该城市与它能 够到达的城市之间的Service链表。 class Service: 为铁路系统模拟了两个城市之间的直接路线,包括两个城市之间直接到达的费用 fee,两城市之间的直接距离distance。 部分设计函数描述 ●RailSystem(const string& filename) 构造函数,调用load_services(string const &filename)函数读取数据 ●load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图 ●reset(void) 遍历cities图,初始化所有城市的信息:visted未访问,total_distance最大 值,total_fee费用最大值,from_city为空 ●~RailSystem(void) 析构函数,用delete将两个map中所有使用new操作符开辟的空间删除 ●void output_cheapest_route(const string& from, const string& to, ostream& out); 输出两城市间的最少费用的路径,调用calc_route(string from, string to)函 数计算最少费用 ●calc_route(string from, string to) 使用Dijkstra算法计算from和to两个城市间的最少费用的路径 (3)采用的存储结构 1)map 上机实验报告 学院:计算机与信息技术学院 专业:计算机科学与技术(师范)课程名称:数据结构 实验题目:单链表建立及操作 班级序号:师范1班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号 一、实验目的: (1)动态地建立单链表; (2)掌握线性表的基本操作:求长度、插入、删除、查找在链式存储结构上的实现; (3)熟悉单链表的应用,明确单链表和顺序表的不同。 二、实验环境: Windows 8.1 Microsoft Visual c++ 6.0 三、实验内容及要求: 建立单链表,实现如下功能: 1、建立单链表并输出(头插法建立单链表); 2、求表长; 3、按位置查找 4、按值查找结点; 5、后插结点; 6、前插结点 7、删除结点; 四、概要设计: 1、通过循环,由键盘输入一串数据。创建并初始化一个单链表。 2、编写实现相关功能函数,完成子函数模块。 3、调用子函数,实现菜单调用功能,完成顺序表的相关操作。 五、代码: #include 数据结构实验一 1、实验目的 ?掌握线性表的逻辑特征 ?掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算 2、实验内容: 建立顺序表,完成顺序表的基本操作:初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空; 1.问题描述:利用顺序表,设计一组输入数据(假定为一组整数),能够对顺序表进行如下操作: ?创建一个新的顺序表,实现动态空间分配的初始化; ?根据顺序表结点的位置插入一个新结点(位置插入),也可以根据给定的值进行插入(值插入),形成有序顺序表; ?根据顺序表结点的位置删除一个结点(位置删除),也可以根据给定的值删除对应的第一个结点,或者删除指定值的所有结点(值删除); ?利用最少的空间实现顺序表元素的逆转; ?实现顺序表的各个元素的输出; ?彻底销毁顺序线性表,回收所分配的空间; ?对顺序线性表的所有元素删除,置为空表; ?返回其数据元素个数; ?按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第i 个结点,查找该元素的值,对查找结果进行返回; ?按值查找,根据给定数据元素的值,只能顺序比较,查找该元素的位置,对查找结果进行返回; ?判断顺序表中是否有元素存在,对判断结果进行返回; .编写主程序,实现对各不同的算法调用。 2.实现要求: ?“初始化算法”的操作结果:构造一个空的顺序线性表。对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间; ?“位置插入算法”的初始条件:顺序线性表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 已存在; 云南大学数学与统计学实验教学中心 实 验 报 告 一、实验目的: 通过实验掌握线性链表的建立及基本操作,巩固课堂内容,练习其程序的设计与实现。 由于顺序存储结构的操作相对比较简单,而且在前期课程《高级语言程序设计》中使用得也多, 所以本次实验侧重于对线性链表存储结构上的操作及应用的实现。 二、实验内容: 本实验包含以下几个子问题: 1、 采用表尾挂入法建立一个以LA 为头指针的单链表: 2、 3、 就地逆转以LB 为头指针的单链表,即得到如下形式的单链表: 4、 将逆转后的LB 表接到LA 表之尾并构成循环链: LA 二、实验要求: 1. 每一个子问题用一个C 语言的函数来完成。 2. 对每一个子问题的结果用一个打印函数输出其结果以验证程序运行是否正确。 打印函数必须是公共的,即:用一个输出函数,既可以对单链表又可对循环链表实现, 打印输出。 3.用主函数调用各个子函数,以完成题目要求。 4.程序设计时应尽量考虑通用性,若改变题给数据仍能实现要求。 [实现提示]: .第3小题题中的“就地逆转”即只允许引入除LB外的两个工作指针来实现。 即可以以循环方式从链表首部起逐个地修改各个结点的指针:从NEXT(向后)指针改变为PRIOR(向前)的指针,并注意保存搜索时的指针。 三、实验环境 Windows win7 程序设计语言C 四、实验过程(请学生认真填写): 1. 实验设计的(各)流程图: 2. 程序设计的代码及解释(必须给出): /*----------------------------------LinkList-------------------------------------*/ /*基本要求---------------------------------------------------------------------*/ /*采用表尾挂入法建立一个以LA为头指针的单链表--------------*/ /*采用表首插入法建立一个以LB为头指针的单链表.---------------*/ /*就地逆转以LB为头指针的单链表,即得到如下形式的单链表.*/ /*将逆转后的LB表接到LA表之尾并构成循环链-------------------*/ /*每一个子问题用一个C语言的函数来完成--------------------------*/ /* 打印函数必须是公共的-------------------------------------------------*/ /*-------------------------------------Start-------------------------------------*/ /*--------------------------------------------------------------------------------*/ #include 实验2 链表的操作 实验容: 1)基础题:编写链表基本操作函数,链表带有头结点 (1)CreatList_h()//用头插法建立链表 (2)CreateList_t()//用尾插法建立链表 (3)InsertList()向链表的指定位置插入元素 (4)DeleteList()删除链表中指定元素值 (5)FindList()查找链表中的元素 (6)OutputList()输出链表中元素 2)提高题: (1)将一个头节点指针为heada的单链表A分解成两个单链表A和B,其头结点指针分别为heada和headb,使得A表中含有原单链表A中序号为奇数的元素,B表中含有原链表A中序号为偶数的元素,且保持原来的相对顺序。 (2)将一个单链表就地逆置。 即原表(a1,a2,。。。。。。 an),逆置后新表(an,an-1,。。。。。。。a1) /* 程序功能 :单链表基本功能操作 编程者 :天啸 日期 :2016-04-14 版本号 :3.0 */ #include { printf("请输入第%d个数:\n",i+1); scanf("%d",&goal); p = (struct List*)malloc(sizeof(struct List)); p -> data = goal; p -> next = L->next; //将L指向的地址赋值给p; L -> next = p; } } void CreateList_t(List *L) //尾插法 { int i; int n; int goal; List *p; List *q=L; printf("请输入数据的个数:\n"); scanf("%d",&n); for (i=0;i #include void Print(struct Student* pHead) { struct Student *pTemp; int iIndex=1; printf("----the List has %d members:----\n",iCount); printf("\n"); pTemp=pHead; while(pTemp!=NULL) { printf("the NO%d member is:\n",iIndex); printf("the name is: %s\n",pTemp->cName); printf("the number is: %d\n",pTemp->iNumber); printf("\n"); pTemp=pTemp->pNext; iIndex++; } } struct Student* Insert(struct Student* pHead) { struct Student* pNew; printf("----Insert member at first----\n"); pNew=(struct Student*)malloc(sizeof(struct Student)); scanf("%s",&pNew->cName); scanf("%d",&pNew->iNumber); pNew->pNext=pHead; pHead=pNew; iCount++; return pHead; } void Delete(struct Student* pHead,int iIndex) { int i; struct Student* pTemp; struct Student* pPre; pTemp=pHead; pPre=pTemp; printf("----delete NO%d member----\n",iIndex); for(i=1;i数据结构实验报告
数据结构实验一顺序表的实现
数据结构实验二-
单链表的基本操作
数据结构实验一顺序表
数据结构实验二链表
单链表基本操作实验
链表的基本操作(基于C)