`
844604778
  • 浏览: 544730 次
文章分类
社区版块
存档分类
最新评论

数据结构实验一--单链表的基本操作的算法

 
阅读更多

一、实验环境

VC++ 6.0

Windows XP/7

二、程序基本设计

(一)、存储结构的类型定义

typedef struct LNode	/*定义单链表结点类型*/
{
	ElemType data;
    struct LNode *next;
} LinkList;

(二)、单链表示意图




(三)、项目组成图



(四)、在项目中建立algo2_2.cpp的程序文件

其中包含的函数原型及功能是:

详情见代码,略去,,几百字。。


(五)、在实验一的项目中,建立名为exp2_2.cpp程序文件

其中包括的内容为:

详情见代码,略去几十字。。。。

(六)、实验一的项目的模块结构,及函数调用关系图




三、程序代码

代码如下:

/*文件名:algo2-2.cpp*/
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode	/*定义单链表结点类型*/
{
	ElemType data;
    struct LNode *next;
} LinkList;
void InitList(LinkList *&L)
{
	L=(LinkList *)malloc(sizeof(LinkList));  	/*创建头结点*/
	L->next=NULL;
}
void DestroyList(LinkList *&L)
{
	LinkList *p=L,*q=p->next;
	while (q!=NULL)
	{
		free(p);
		p=q;
		q=p->next;
	}
	free(p);
}
int ListEmpty(LinkList *L)
{
	return(L->next==NULL);
}
int ListLength(LinkList *L)
{
	LinkList *p=L;int i=0;
	while (p->next!=NULL)
	{
		i++;
		p=p->next;
	}
	return(i);
}
void DispList(LinkList *L)
{
	LinkList *p=L->next;
	while (p!=NULL)
	{
		printf("%c",p->data);
		p=p->next;
	}
	printf("\n");
}
int GetElem(LinkList *L,int i,ElemType &e)
{
	int j=0;
	LinkList *p=L;
	while (j<i && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL || i<1)     // 当超出上界或者下界时,查询失败
	{
		printf("您输入的元素位置数据不合法!\n");
		return 0;
	}
	else
	{
		e=p->data;
		return 1;
	}
}
int LocateElem(LinkList *L,ElemType e)
{
	LinkList *p=L->next;
	int n=1;
	while (p!=NULL && p->data!=e)
	{
		p=p->next;
		n++;
	}
	if (p==NULL)
		return(0);
	else
		return(n);
}
int ListInsert(LinkList *&L,int i,ElemType e)
{
	int j=0;
	LinkList *p=L,*s;
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL || i<=0)	/*未找到第i-1个结点*/
	{
		printf("插入失败!\n");
		return 0;
	}
	else			/*找到第i-1个结点*p*/
	{
		s=(LinkList *)malloc(sizeof(LinkList));	/*创建新结点*s*/
		s->data=e;								
		s->next=p->next;						/*将*s插入到*p之后*/
		p->next=s;
		printf("插入完成!\n") ;
		return 1;
	}
}
int ListDelete(LinkList *&L,int i,ElemType &e)
{
	int j=0;
	LinkList *p=L,*q;
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL || i <1 ||q==NULL )				/*未找到第i-1个结点*/
	{
		return 0;
	}
	else						/*找到第i-1个结点*p*/
	{
		q=p->next;              /*q指向要删除的结点*/
        e=q->data;  
		p->next=q->next;		/*从单链表中删除*q结点*/
	    free(q);				/*释放*q结点*/
	    return 1;
	}
}



/*文件名:exp2-2.cpp*/
#include <stdio.h>
#include <malloc.h>

typedef char ElemType;

typedef struct LNode	/*定义单链表结点类型*/
{
	ElemType data;
    struct LNode *next;
} LinkList;

extern void InitList(LinkList *&L);
extern void DestroyList(LinkList *&L);
extern int ListEmpty(LinkList *L);
extern int ListLength(LinkList *L);
extern void DispList(LinkList *L);
extern int GetElem(LinkList *L,int i,ElemType &e);
extern int LocateElem(LinkList *L,ElemType e);
extern int ListInsert(LinkList *&L,int i,ElemType e);
extern int ListDelete(LinkList *&L,int i,ElemType &e);
void main()
{
	int pos;
	LinkList *h;
	ElemType e;
	char ele;
	printf("(1)初始化单链表h\n");
	InitList(h);

	printf("\n(2)依次采用尾插法插入a,b,c元素\n");
	ListInsert(h, 1, 'a');
	ListInsert(h, 2, 'b');
	ListInsert(h, 3, 'c');

	printf("\n(3)输出单链表h:");
	DispList(h);

	printf("\n(4)单链表h长度=%d\n",ListLength(h));

	printf("\n(5)单链表h为%s\n",(ListEmpty(h)?"空":"非空"));

Sur:printf("\n(6)请输入你要查询的数据元素的位置(数字):");
	scanf("%d", &pos) ;
	if(GetElem(h,pos,e))
	{
		printf("单链表h的第%d个元素=%c\n", pos, e);
	}
	else
	{
		printf("查询失败!\n");
SurEle:	printf("你是否要继续查询?(Y/N)") ;
		getchar();
		scanf("%c", &ele) ;
		switch (ele)
		{
		case 'Y':
		case 'y': goto Sur ; break;
		case 'N':
		case 'n': printf("您选择放弃再次查询!\n") ; break;
        default: printf("您输入的数据不合法!请重新输入:\n"); goto SurEle ; break;
		}
	}

SurCon:printf("\n(7)请输入你要查找的数据元素的值:") ;
	getchar();
	scanf("%c", &e) ;
	if (LocateElem(h,e))
	{
		printf("查找成功,元素%c的位置=%d\n", e, LocateElem(h,e));
	} 
	else
	{
		printf("查询失败!你输入的数据元素的值不存在!\n") ;
SurConEle:	printf("你是否要继续查询?(Y/N)") ;
		getchar();
		scanf("%c", &ele) ;
		switch (ele)
		{
		case 'Y':
		case 'y': goto SurCon ; break;
		case 'N':
		case 'n': printf("您选择放弃再次查询!\n") ; break;
        default: printf("您输入的数据不合法!请重新输入:\n"); goto SurConEle ; break;
		}
	}

	printf("\n(8)请输入你要插入的数据元素的位置和数据元素值(以逗号隔开):");
	scanf("%d,%c", &pos, &e);
	if (ListInsert(h, pos, e))
	{
			printf("输出成功插入元素后的单链表h:");
			DispList(h);
	}

Dle:printf("\n(10)请输入你要删除的数据元素的位置:");
	//getchar();
	scanf("%d", &pos) ;
	if(ListDelete(h,pos,e))
	{
		printf("删除成功!你删除的位置的数据元素值为%c\n", e) ;
		printf("输出成功删除元素后单链表h:");
		DispList(h);
		printf("你是否要继续删除?(Y/N)") ;
		getchar();
		scanf("%c", &ele) ;
		switch (ele)
		{
		case 'Y':
		case 'y': goto Dle ; break;
		case 'N':
		case 'n': printf("您选择不再继续删除!\n") ; break;
        default: printf("您输入的数据不合法!请重新输入:\n"); goto Dle ; break;
		}
	}
	else
	{
		printf("删除失败!请检查你输入的数据元素的位置!\n") ;
DleEle:	printf("你是否要继续再次尝试删除?(Y/N)") ;
		getchar();
		scanf("%c", &ele) ;
		switch (ele)
		{
		case 'Y':
		case 'y': goto Dle ; break;
		case 'N':
		case 'n': printf("您选择放弃尝试删除!\n") ; break;
        default: printf("您输入的数据不合法!请重新输入\n"); goto DleEle ; break;
		}

	}
	printf("\n(12)释放单链表h\n");
	DestroyList(h);
}













分享到:
评论

相关推荐

    数据结构-基本算法-单链表

    数据结构-基本算法-单链表(学生时代源码,调试可运行)

    数据结构与算法-实验二单链表

    实现单链表完成线性表的基本操作: 初始化线性表、清空线性表、求线性表长度、检查线性表是否为空、遍历线性表、从线性表中查找元素、从线性表中查找与给定元素值相同的元素在线性表中的位置、插入元素、删除元素。

    数据结构-单链表-实验报告.rar_C++_tripk8z_单链表_单链表实验_实验报告

    (3)进一步理解算法与程序的关系,能够将单链表算法转换为对应的程序。 1.2 实验要求: (1)用头插法(或尾插法)建立带头结点的单链表; (2)对已建立的单链表实现插入、删除、查找等基本操作。

    单链表的基本操作(实验)

    (2) 设计一个带选择功能菜单的主函数,菜单中至少具备任意选择删除、插入、查找数据元素,和求单链表表长等几项功能。 (3) 当选择删除功能时,从键盘读入欲删除的元素位置,按指定位置删除;当选择插入功能时,...

    《数据结构与算法》-李春葆 实验报告-单链表

    《数据结构与算法》-李春葆 实验报告-单链表

    数据结构实验——单链表

    1、单链表基本操作的实现 在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ,首先需要在单链表中寻找到第i-1个结点并用指针p指示,然后申请一个由指针s 指示的结点空间,并置x为其数据域值,最后修改第i-1...

    数据结构与算法实验(C++):单链表实验-代码

    2)熟练掌握单链表的基本操作算法; 3)熟练掌握面向对象程序设计方法; 4)能灵活使用单链表解决具体的问题。 (2)实验内容: 1)在主函数中定义对象,并调用成员函数,验证单链表的基本操作; 2)定义单链表类...

    数据结构 实验一:实现单链表各种基本运算的算法.doc

    数据结构 实验一:实现单链表各种基本运算的算法.doc

    算法与数据结构实验一(2)单链表

    设单链表的数据为互不相等的整数,建立一个单 链表,并设计一个算法, 找出单链表中元素值最大 的结点。 要求: (1)单链表的数据从键盘输入; (2)输出单链表所有结点的数据和最大值结点序号。*/ /*2. 设计算法...

    数据结构实验4-单链表(二)

    1、编程实现:两个一元多项式相加的算法。 比如: x8-5x4+2x2+6x+1 2x12+9x10-6x8+5x4+3x-4 ...例如,给出一个单链表,包含的数据元素有1,3,5,7,9,11;其中low=3,high=9,则删除后剩下的元素为1,11。

    数据结构课程单链表实验报告.docx

    数据结构课程单链表实验报告.docx

    数据结构实验一.rar

    1.建立一个顺序表,随机产生10个100以内的整数,并按要求完成:(1)编写...2.有两个有序排序的单链表Ll和L2,分别存放10个数据元素,设计算法实现两个单链表的合并,要求合并后的单链表仍然有序排序,并输出合并结果。

    数据结构的单链表算法

    数据结构单链表:单链表的运算,循环单链表基本运算,约瑟夫环,集合运算,多项式相加,分为插入前插入后。

    数据结构单链表实验报告.doc

    "计算机系 "班级 " "学号 " "姓名 " " "课程名称 "数据结构 "实验日期 "11.7 " "实验名称 "链表的基本操作 "成绩 " " "实验目的: " "熟悉掌握线性表链式存储结构,掌握与应用查找、插入、删除等基本操作算法, " ...

    数据结构单链表插入、删除和修改实验报告

    数据结构单链表插入、删除和修改实验报告 一、实验目的 1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现...

    数据结构实验(单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序)的实现

    单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序等共四个实验的实现过程。

    数据结构——单链表实验

    熟悉单链表的定义,单链表的建立方法及相关基本操作,理解单链表的基本思想,能够根据实际情况选择合适的存储结构。 2.实验内容 1、利用头插法或尾插法建立单链表 2、对已建立的单链表实现插入、删除等基本操作; 3...

    数据结构课程设计-C++实验代码

    这个是我亲手所做的数据结构课程设计,完成了: 实验一 单链表的定义和应用 实验要求: 1.用单链表存储结构定义线性表 2.实现单链表基本操作(5个基本操作:构造,销毁,插入,删除, 取指定数据元素) 3.用单链表...

    数据结构实验一 单链表操作验证

    实验报告有流程图,代码带注释及运行结果和应用算法实现,报告很全

    验证单链表及其上的基本操作

    2、实验验证如下算法的正确性、各种功能及指标: 1)创建单链表; 2)插入操作:分别在当前结点后、表头、表尾插入值为x的结点; 3)删除操作:分别删除表头结点、表尾结点和当前结点的后继结点; 4)存取操作:分别...

Global site tag (gtag.js) - Google Analytics