文档章节

205LinkList

把南墙撞开
 把南墙撞开
发布于 2016/05/11 09:47
字数 839
阅读 20
收藏 0
点赞 2
评论 0

注意:要严格按照后缀名新建文件。

如果按.h创建文件,后来简单重命名为.cpp文件,编译会出错。

顺序表的实现 包含6个文件:

    c1.h 是预处理指令;

    elemtype.h  定义Elemtype数据类型;

    c2-2.h 是LinkList的数据结构;

    bo-nohead.cpp 是SqList的基本操作函数(basic operations 缩写为 bo);

    function.h 定义bo2-2.cpp中,链表遍历函数ListTraverse所需要的访问函数;

    main.cpp 是实现、测试函数。

//c1.h
#include<iostream>
#include<process.h>
#include<malloc.h>

#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef int Status;
//elemtype.h
typedef int ElemType;
//c2-2.h
#ifndef C2_2_H
#define C2_2_H

#include"elemtype.h"
struct LNode
{
	ElemType data;
	LNode *next;
};

typedef LNode* LinkList;

void InitList(LinkList &L);
void ListTraverse(LinkList L, void(*vi)(ElemType));
Status ListInsert(LinkList &L, int index, ElemType e);
Status ListDelete(LinkList &L, int index, ElemType &e);
bool ListEmpty(LinkList L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int index, ElemType &e);
int LocateElem(LinkList L, ElemType e);
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e);
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e);
void ClearList(LinkList &L);
void DestroyList(LinkList &L);

#endif
//bo-nohead.cpp
#include"c1.h"
#include"c2-2.h"
using namespace std;

void InitList(LinkList &L)
{
	L = nullptr;
}

void ListTraverse(LinkList L, void(*vi)(ElemType))
{
	int i = 0;
	if (L)
	{
		LinkList p = L;
		while (p)
		{
			vi(p->data);
			p = p->next;
			i++;
			if (!(i % 10))
				cout << endl;
		}
		cout << endl;
	}
}

Status ListInsert(LinkList &L, int index, ElemType e)
{
	int j = 1;
	LinkList p = L, s;

	if (index < 1)
		return ERROR;

	s = (LinkList)malloc(sizeof(LNode));
	s->data = e;

	if (index == 1)
	{
		s->next = L;
		L = s;
	}
	else
	{
		while (p && j < index - 1)
		{
			p = p->next;
			j++;
		}
		if (!p)
			return ERROR;
		s->next = p->next;
		p->next = s;
	}
	return OK;
}

Status ListDelete(LinkList &L, int index, ElemType &e)
{
	int j = 1;
	LinkList p = L, q;
	if (index == 1)
	{
		L = p->next;
		e = p->data;
		free(p);
		return OK;
	}
	else
	{
		while (p->next && j < index - 1)
		{
			p = p->next;
			j++;
		}
		if (!p->next || j > index - 1)
			return ERROR;
		q = p->next;
		p->next = q->next;
		e = q->data;
		free(q);
		return OK;
	}
}

bool ListEmpty(LinkList L)
{
	if (L)
		return false;
	else
		return true;
}

int ListLength(LinkList L)
{
	int i = 0;
	LinkList p = L;
	while (p)
	{
		i++;
		p = p->next;
	}
	return i;
}

Status GetElem(LinkList L, int index, ElemType &e)
{
	if (index < 1)
		return ERROR;
	int j = 1;
	LinkList p = L;
	while (p && j < index)
	{
		p = p->next;
		j++;
	}

	if (!p)
		return ERROR;
	e = p->data;
	return OK;
}

int LocateElem(LinkList L, ElemType e)
{
	int i = 0;
	LinkList p = L;
	while (p)
	{
		i++;
		if (p->data == e)
			return i;
		p = p->next;
	}
	return 0;
}

/*
//this function is not efficient
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
int location = LocateElem(L, cur_e);
if (location > 1)
{
GetElem(L, location - 1, pre_e);
return OK;
}
else
return ERROR;
}

Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
int location = LocateElem(L, cur_e);
if (location >= 1 && location < ListLength(L))
{
GetElem(L, location + 1, next_e);
return OK;
}
else
return ERROR;
}
*/
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
	LinkList p = L, q ;
	while (p->next)
	{
		q = p->next;
		if (q->data == cur_e)
		{
			pre_e = p->data;
			return OK;
		}
		p = q;	
	}
	return ERROR;
}

Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
	if (L)
	{
		LinkList p = L;
		while (p->next)
		{
			if (p->data == cur_e)
			{
				next_e = p->next->data;
				return OK;
			}
			p = p->next;
		}
	}
	return ERROR;
}

void ClearList(LinkList &L)
{
	LinkList p;
	while (L)
	{
		p = L;
		L = L->next;
		free(p);
	}

}

void DestroyList(LinkList &L)
{
	LinkList q;
	while (L)
	{
		q = L->next;
		free(L);
		L = q;
	}
}
//function.h
#ifndef FUNCTION_CPP
#define FUNCTION_CPP

#include"c1.h"
#include"elemtype.h"
using namespace std;

void print(ElemType e)
{
	cout << e << " ";
}

#endif
//main.cpp
#include "c1.h"
#include "c2-2.h"
#include "function.h"
using namespace std;

int main()
{
	LinkList L;
	InitList(L);
	cout << "ListEmpty: " << ListEmpty(L) << endl;
	cout << "ListLength: " << ListLength(L) << endl;
	
	for (int i = 0; i < 100; i++)
		cout << ListInsert(L, i + 1, i);
	cout << endl;
	ListTraverse(L, print);
	cout << "ListEmpty: " << ListEmpty(L) << endl;
	cout << "ListLength: " << ListLength(L) << endl;
	cout << endl;

	ElemType e;
	ListDelete(L, 1, e);
	ListDelete(L, 97, e);
	ListTraverse(L, print);
	cout << endl;

	cout << "ListLength: " << ListLength(L) << endl;

	cout << "GetElem: " << GetElem(L, 98, e);
	cout << " e = " << e << endl;

	cout << "LocateElem: " << LocateElem(L, 99) << endl;

	cout << "PriorElem: " << PriorElem(L, 99, e);
	cout << "  e = " << e << endl;

	cout << "NextElem: " << NextElem(L, 98, e);
	cout << "  e = " << e << endl;

	ClearList(L);
	DestroyList(L);

	cin.get();
	return 0;
}

© 著作权归作者所有

共有 人打赏支持
把南墙撞开
粉丝 0
博文 67
码字总数 20424
作品 0
昌平

暂无相关文章

10个免费的服务器监控工具

监控你的WEB服务器或者WEB主机运行是否正常与健康是非常重要的。你要确保用户始终可以打开你的网站并且网速不慢。服务器监控工具允许你收集和分析有关你的Web服务器的数据。 有许多非常好的服...

李朝强 ⋅ 17分钟前 ⋅ 0

压缩工具之zip-tar

zip 支持目录压缩。使用yum安装zip包,使用yum安装unzip包 zip 1.txt.zip 1.txt #将1.txt文件压缩,新生成的压缩文件为1.txt.zip,原文件保留 zip -r 123.zip 123/ #-r对目录操作。将123/目录...

ZHENG-JY ⋅ 17分钟前 ⋅ 0

Dubbo @Activate注解使用和实现解析

Activate注解标识一个扩展是否被激活和使用,可以放在定义的类上和方法上,dubbo用它在SPI扩张类定义上,标识这个扩展实现激活的条件和时机,先看下定义: /** * Activate * <p/> * ...

哲别0 ⋅ 24分钟前 ⋅ 0

6.5 zip压缩工具 tar打包 打包并压缩

1.tar tar命令格式 [-zjxcvfpP] filename tar -z:表示同时用gzip压缩。 -j:表示同时用bzip2压缩。 -J:表示同时用xz压缩。 -x:表示解包或者解压缩。 -t:表示查看tar包里的文件。 -c:表示建...

oschina130111 ⋅ 26分钟前 ⋅ 0

Linux系统工程狮养成记

如今的社会,随着时代的发展,出现了很多职业,像电子类,计算机类的专业,出现了各种各样的工程师,有算法工程师,java工程师,前端工程师,后台工程师,Linux工程师,运维工程师等等,不同...

六库科技 ⋅ 33分钟前 ⋅ 0

Linux 机器的渗透测试命令备忘表

如下是一份 Linux 机器的渗透测试备忘录,是在后期开发期间或者执行命令注入等操作时的一些典型命令,设计为测试人员进行本地枚举检查之用。 此外,你还可以从这儿(https://gbhackers.com/c...

寰宇01 ⋅ 34分钟前 ⋅ 0

windows 安装java开发环境,配置jdk

下载jdk安装文件 链接:https://pan.baidu.com/s/1UEKPjnAdMqNj612B39Pfsg 密码:ipqx 如果javac无法使用 1,检查环境变量名称中是否有空格。。。,去除后即可 2,将JAVA_HOME替换为原始路径...

阿豪boy ⋅ 36分钟前 ⋅ 0

简析log4j的实现方式

刚加入新公司,对日志的要求比较严格,对此特意花了几天时间看了一下log4j的源码,大概了解了一下log4j的实现方式,总结如下: log4j的实现分为两个步骤:log4j.xml的加载,logger的使用 这里...

zdatbit ⋅ 今天 ⋅ 0

win环境下jdk7与jdk8共存配置

1.jdk安装包 jdk安装包 安装步骤略 2.jdk等配置文件修改 在安装JDK1.8时(本机先安装jdk1.7再安装的jdk1.8),会将java.exe、javaw.exe、javaws.exe三个文件copy到了C:\Windows\System32,这...

泉天下 ⋅ 今天 ⋅ 0

windows profesional 2017 build problem

.net framework .... https://stackoverflow.com/questions/43330915/could-not-load-file-or-assembly-microsoft-build-frameworkvs-2017...

机油战士 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部