软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 数据库 -> 线性表的链式表示和实现 -> 正文阅读

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


[img]http://img.blog.csdn.net/20160331204400430?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[img]http://img.blog.csdn.net/20160331204415117?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast[img]http://img.blog.csdn.net/20160331204425946?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[img]http://img.blog.csdn.net/20160331204437805?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
头文件 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  
数据库 最新文章
Python&MySQL&PyQt
最新用python来操作mysql完全解析
mongodb的安装详解
1.PDO简介
《MySQL必知必会学习笔记》:高级联结
【翻译自mos文章】怎么对Microsoft(Office)
MyCAT全局表描述及示例
ocp
关于SQL数据表存储过程表名前缀换成dbo代码
数据库调优教程(二)慢查询数据准备
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-19 13:28:45
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --