文档章节

204LinkList

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

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

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

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

    c1.h 是预处理指令;

    elemtype.h  定义Elemtype数据类型;

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

    bo2-2.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
//bo2-2.cpp
#include"c1.h"
#include"c2-2.h"
using namespace std;

void InitList(LinkList &L)
{
	L = (LinkList)malloc(sizeof(LNode));
	if (!L)
		exit(OVERFLOW);
	L->next = nullptr;
}

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

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

	while (p && j < index - 1)
	{
		p = p->next;
		j++;
	}

	if (!p || j > index - 1)
		return ERROR;

	if (!(s = (LinkList)malloc(sizeof(LNode))))
		exit(OVERFLOW);
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

Status ListDelete(LinkList &L, int index, ElemType &e)
{
	int j = 0;
	LinkList p = L, q;
	
	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);
	q = nullptr;
	return OK;
}

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

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

Status GetElem(LinkList L, int index, ElemType &e)
{
	if (index <= 0)
		return ERROR;
	int j = 0;
	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;
	if (L)
	{
		LinkList p = L;
		while (p->next)
		{
			i++;
			p = p->next;
			if (p->data == e)
				return i;
		}
	}	
	return i;
}

/*
//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)
{
	if (L)
	{
		LinkList p = L, q = L->next;
		if (!q)
			return ERROR;
		while (q->next)
		{
			p = p->next;
			q = q->next;
			if (q->data == cur_e)
			{
				pre_e = p->data;
				return OK;
			}
		}
		return ERROR;
	}
	return ERROR;
}

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

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

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
昌平

暂无相关文章

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部