软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 数据库 -> 线性表的链式表示和实现 -> 正文阅读
数据库 最新文章
Python&MySQL&PyQt
最新用python来操作mysql完全解析
mongodb的安装详解
1.PDO简介
《MySQL必知必会学习笔记》:高级联结
【翻译自mos文章】怎么对Microsoft(Office)
MyCAT全局表描述及示例
ocp
关于SQL数据表存储过程表名前缀换成dbo代码
数据库调优教程(二)慢查询数据准备

[数据库]线性表的链式表示和实现

  2016-04-01 16:56:34




头文件 head.h
<pre name="code" class="cpp">#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef int ElemType;

typedef struct DLNode{
	ElemType data;
	struct DLNode *next, *prior;
}DLNode;

typedef struct DLNode *LinkList_DL;

Status InitList_DL(LinkList_DL *L);

Status DestoryList_DL(LinkList_DL *L);

Status ClearList_DL(LinkList_DL *L);

Status ListEmpty_DL(LinkList_DL L);

int ListLength_DL(LinkList_DL L);

Status GetElem_DL(LinkList_DL L, int i, ElemType *e);

int LocateElem_DL(LinkList_DL L, ElemType e);

Status PriorElem_DL(LinkList_DL L, ElemType cur_e, ElemType *pri_e);

Status NextElem_DL(LinkList_DL L, ElemType cur_e, ElemType *next_e);

LinkList_DL GetElemP_DL(LinkList_DL L, int i);

Status ListInsert_DL(LinkList_DL L, int i, ElemType e);

Status ListDelete_DL(LinkList_DL L, int i, ElemType *e);

Status ListTraverse_DL(LinkList_DL L);

Status ListTraverseBack_DL(LinkList_DL L);


</pre><pre name="code" class="cpp">实现方法
<pre name="code" class="cpp">#include"head.h"

/*
	和循环链表不同的是,该方法没有尾指针,L就是头结点,
	if(L->next->next == L)
		则只有一个元素
*/
Status InitList_DL(LinkList_DL *L)
{
	//产生空的双向循环链表L

	(*L) = (LinkList_DL)malloc(sizeof(DLNode));
	if (!(*L))
	{
		printf("双线性链表初始化失败!");
		return ERROR;
	}
	else
	{
		(*L)->next = (*L)->prior = (*L);
		return OK;
	}
}

Status DestoryList_DL(LinkList_DL *L)
{
	//销毁双向循环链表L,该方法和单向循环链表一样

	LinkList_DL p, q = (*L)->next;		//指向第一个结点
	while (q != (*L))					//判断不为空
	{
		//注意顺序!!!!
		p = q->next;					//必须先将q的下一个元素指向p,要不然在下一步释放时就没有了!!!
		free(q);
		q = p;
	}
	free(*L);
	*L = NULL;

	return OK;
}

Status ClearList_DL(LinkList_DL *L)
{
	//将表L置为空表

	LinkList_DL p, q = (*L)->next;		//q指向第一个结点

	while (q != (*L))					//没有到表头,清空之后就只剩下表头,和初始化时一样的
	{
		p = q->next;					//必须先将q的下一个元素指向p,要不然在下一步释放时就没有了!!!
		free(q);
		q = p;
	}
	(*L)->next = (*L)->prior = (*L);

	return OK;
}

Status ListEmpty_DL(LinkList_DL L)
{
	//判断该表L是否为空

	if ((L->next) == L)
		return TRUE;
	else
		return FALSE;
}

int ListLength_DL(LinkList_DL L)
{
	//返回表L中元素的个数

	int n = 0;
	LinkList_DL p = L->next;			//第一个元素

	while (p != L)						//没有到表尾
	{
		n++;
		p = p->next;
	}

	return n;
}

Status GetElem_DL(LinkList_DL L, int i, ElemType *e)
{
	//当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR

	int n = 1;
	LinkList_DL p = L->next;				//L为头结点,p为第一个结点
//	L = L->next;							//第一个结点

	if (i<1 || i>ListLength_DL(L) + 1)
		return ERROR;

	while (p != L && n<i)
	{
		p = p->next;
		n++;
	}

	*e = p->next->data;

	return OK;
}

int LocateElem_DL(LinkList_DL L, ElemType e)
{
	//返回L中与元素e相等的元素的位置

	int n = 1;
	LinkList_DL p = L->next;

	while (p != L)
	{
		if ((p->data) == e)
			return n;
		n++;
		p = p->next;
	}

	return ERROR;
}

Status PriorElem_DL(LinkList_DL L, ElemType cur_e, ElemType *pri_e)
{
	//返回元素cur_e的前驱

	LinkList_DL p = L->next->next;	//第二个结点

	while (p != L)					//p没有到表头
	{
		if ((p->data) == cur_e)
		{
			*pri_e = p->prior->data;
			return OK;
		}
		p = p->next;
	}
	return FALSE;
}

Status NextElem_DL(LinkList_DL L, ElemType cur_e, ElemType *next_e)
{
	LinkList_DL p = L->next->next;		//这样做是为了防止该元素没有后继元素

	while (p != L)
	{
		if ((p->prior->data) == cur_e)
		{
			*next_e = p->data;
			return TRUE;
		}
		p = p->next;
	}
	return FALSE;
}

LinkList_DL GetElemP_DL(LinkList_DL L, int i)
{
	//在双向链表中返回第i个元素的地址
	//i=0,返回头结点的地址;若第i个元素不存在,返回NULL;

	LinkList_DL p = L;							//p指向头结点

	int n = 1;
	if (i<1 || i>ListLength_DL(L) + 1)
		return NULL;

	while (n <= i)
	{
		p = p->next;
		n++;
	}

	return p;

}

Status ListInsert_DL(LinkList_DL L, int i, ElemType e)
{
	//在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1<=i<=表长+1

	LinkList_DL p, s;

	if (i<1 || i>ListLength_DL(L) + 1)
		return ERROR;

	p = GetElemP_DL(L, i);
	if (!p)
		return ERROR;

	s = (LinkList_DL)malloc(sizeof(struct DLNode));
	if (!s)
		return ERROR;

	//根据图示,由左向右处理
	s->data = e;
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;

	return OK;
}

Status ListDelete_DL(LinkList_DL L, int i, ElemType *e)
{
	//删除带头结点的双链循环线性表L的第i个元素

	LinkList_DL p;

	if (i<1 || i>ListLength_DL(L) + 1)
		return FALSE;

	p = GetElemP_DL(L, i);
	if (!p)
		return FALSE;

	*e = p->data;

	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);

	return OK;
}

Status ListTraverse_DL(LinkList_DL L)
{
	LinkList_DL p = L->next;

	while (p != L)
	{
		printf("%d  ", p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}

Status ListTraverseBack_DL(LinkList_DL L)
{
	LinkList_DL p = L->prior;
	while (p != L)
	{
		printf("%d  ", p->data);
		p = p->prior;
	}
	printf("\n");
	return OK;
}

Status GetElem_DL(LinkList_DL L, int i, ElemType *e);int LocateElem_DL(LinkList_DL L, ElemType e);Status PriorElem_DL(LinkList_DL L, ElemType cur_e, ElemType *pri_e);Status NextElem_DL(LinkList_DL L, ElemType cur_e, ElemType *next_e);LinkList_DL GetElemP_DL(LinkList_DL L, int i);Status ListInsert_DL(LinkList_DL L, int i, ElemType e);Status ListDelete_DL(LinkList_DL L, int i, ElemType *e);Status ListTraverse_DL(LinkList_DL L);Status ListTraverseBack_DL(LinkList_DL L);





测试文件
#include"head.h"

void main()
{
	LinkList_DL L;
	int i, n;
	Status j;
	ElemType e;
	InitList_DL(&L);
	for (i = 1; i <= 5; i++)
		ListInsert_DL(L, i, i); /* 在第i个结点之前插入i */
	//	printf("length=%d\n", ListLength_DL(L));
	printf("正序输出链表:");
	ListTraverse_DL(L); /* 正序输出 */
	printf("逆序输出链表:");
	ListTraverseBack_DL(L); /* 逆序输出 */
	printf("请输入要删除的结点数n【1-%d】:", ListLength_DL(L));
	scanf_s("%d", &n);
	ListDelete_DL(L, n, &e); /* 删除并释放第n个结点 */
	printf("删除第%d个结点,值为%d,其余结点为:", n, e);
	ListTraverse_DL(L); /* 正序输出 */
	printf("链表的元素个数为%d\n", ListLength_DL(L));
	printf("链表是否空:%d(1:是 0:否)\n", ListEmpty_DL(L));
	ClearList_DL(&L); /* 清空链表 */
	printf("清空后,链表是否空:%d(1:是 0:否)\n", ListEmpty_DL(L));
	for (i = 1; i <= 5; i++)
		ListInsert_DL(L, i, i); /* 重新插入5个结点 */
	ListTraverse_DL(L); /* 正序输出 */
	n = 3;
	j = GetElem_DL(L, n, &e); /* 将链表的第n个元素赋值给e */
	if (j)
		printf("链表的第%d个元素值为%d\n", n, e);
	else
		printf("不存在第%d个元素\n", n);
	n = 4;
	i = LocateElem_DL(L, n);
	if (i)
		printf("等于%d的元素是第%d个\n", n, i);
	else
		printf("没有等于%d的元素\n", n);
	j = PriorElem_DL(L, n, &e);
	if (j)
		printf("%d的前驱是%d\n", n, e);
	else
		printf("不存在%d的前驱\n", n);
	j = NextElem_DL(L, n, &e);
	if (j)
		printf("%d的后继是%d\n", n, e);
	else
		printf("不存在%d的后继\n", n);
	DestoryList_DL(&L);

	system("pause");
}

Running Result:
序输出链表:1  2  3  4  5
序输出链表:5  4  3  2  1
输入要删除的结点数n【1-5】:2
除第2个结点,值为2,其余结点为:1  3  4  5
表的元素个数为4
表是否空:0(1:是 0:否)
空后,链表是否空:1(1:是 0:否)
 2  3  4  5
表的第3个元素值为4
于4的元素是第4个
的前驱是3
的后继是5
按任意键继续. . .

上一篇文章      下一篇文章      查看所有文章
2016-04-01 16:56:17  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 人民的名义 人民的名义在线看 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图
中国文化英文 多播视频 装修知识库
2017-4-23 21:56:28
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --