`
阿尔萨斯
  • 浏览: 4398182 次
社区版块
存档分类
最新评论

对链表的相关操作及数据结构的再理解

 
阅读更多

结点的操作

由于链表是n个离散结点彼此通过指针相连,所以对链表的相关操作主要通过头指针(存放了头结点的地址)对结点进行操作来实现。

1.如何将q所指向的结点插入到p所指向结点的后面?

有两个方法

第一种: 采用临时变量

r=p->pNext;//用r保存p所指向结点的下一个结点地址

p->pNext=q;//此时p的指针域指向q所指的结点的地址

q->pNext=r;

第二种:不采用临时变量

q-pNext=p->pNext;//让p和q所指向结点的指针域指向后面的同一个结点

p-pNext=q;//再让p的指针域指向q结点

2.如何删除一个节点(思路:用一个临时变量r来保存要删除的结点,再删除p后面的那个结点)

r=p->pNext;

p->pNext=p->pNext->pNext;

free(r);

r=NULL;

3.如何判断链表是否为空(思路:空链表只有一个头结点,所以只需让头结点的指针域为NULL即可)

对链表的相关操作

实例说明:

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
	int data;//数据域
	struct Node *pNext;//指针域
}NODE,*PNODE;
PNODE CreateList();//创建链表
void TraverseList(PNODE);//遍历链表
bool IsEmpty(PNODE);//判断链表是否为空
int Length(PNODE);//求链表长度
bool InsertNode(PNODE,int,int);//插入结点
bool DeleteNode(PNODE,int,int *);//删除结点
bool QueryNode(PNODE,int);//查找结点 
bool ModifyNode(PNODE,int,int);//修改结点
void SortList(PNODE);//遍历排序

int main()
{
	PNODE pHead=NULL;
	pHead=CreateList();//将创建链表的头指针的地址赋给pHead
	if(0==Length(pHead))
	{
		printf("链表无有效节点,退出程序!\n");
		exit(-1);
	}
	TraverseList(pHead);
	if(InsertNode(pHead,2,100))
	{
		printf("插入后");
        TraverseList(pHead); 
	}
	else
	{
		printf("插入操作失败!\n");
	}
	SortList(pHead);
	printf("排序后");
	TraverseList(pHead);

	return 0;
}
PNODE CreateList()
{
	int len;//用来保存需要创建链表的结点个数
	int i;
	int val;//用来临时存放新节点的值
	PNODE pHead=(PNODE)malloc(sizeof(NODE));//动态分配一块内存,该内存保存头结点的地址,并将其赋给pHead
	PNODE pTail=pHead;
	PNODE pNew;
    pTail->pNext=NULL;//将尾结点的指针域赋为NULL
	if(NULL==pHead)
	{
		printf("分配失败,程序终止运行!\n");
		exit(-1);
	}
	printf("请输入你要创建链表的结点个数:len=");
	scanf("%d",&len);
	for(i=0;i<len;i++)
	{
		printf("请输入第%d个结点的值:",i+1);
		scanf("%d",&val);
		pNew=(PNODE)malloc(sizeof(NODE));//创建新临时结点
        if(NULL==pNew)
		{
			printf("分配失败,程序终止运行!\n");
			exit(-1);
		}
		pNew->data=val;
		pTail->pNext=pNew;//将新结点挂到原尾结点的后面
        pNew->pNext=NULL;//将新结点的指针域赋为NULL
		pTail=pNew;//将新结点置为尾结点
	}
	return pHead;
}
void TraverseList(PNODE pHead)
{
	PNODE p=pHead->pNext;//将头结点的指针域指向首结点(链表的第一个有效结点),并赋给指针变量p,此时p指向首节点的地址
	printf("遍历整个链表:");
	while(NULL!=p)//当p指向首节点的地址不为NULL(即链表不为空),循环输入个结点的值
	{
		//当p指向尾结点的地址时,可输出尾结点的值
		//但此时尾结点指针域为NULL,将跳出while循环
		printf("%d  ",p->data);
		p=p->pNext;//将p指向下一个结点的地址赋给p指针
	}
	printf("\n"); 
}
bool IsEmpty(PNODE pHead)
{
	if(NULL==pHead->pNext)
		return true;
	else
		return false;
}
int Length(PNODE pHead)
{
	PNODE p=pHead->pNext;//此时p指向链表的首结点(第一个有效结点)的地址
	int len=0;
	while(NULL!=p)
	{
		++len;
		p=p->pNext;
	}
    return len;
}
bool InsertNode(PNODE pHead,int pos,int val)
{
	int i=0;
	PNODE p=pHead,q;
         PNODE pNew;
	while(NULL!=p&&i<pos-1)//目的是为了使p指向要插入位置的前一个结点
	{
		p=p->pNext;
		++i;//如链表只有两个有效结点,要插入的位置结点pos=3,i=2时,2<3-1不成立,循环结束,
	}
	if(i>pos-1||NULL==p)//p为NULL说明要插入位置结点的前一个结点不存在,i>pos-1是为了防止用户输入pos为像0、-1等非法数据
		return false;
         pNew=(PNODE)malloc(sizeof(NODE));//为新节点分配内存
	if(NULL==pNew)
	{
		printf("动态内存分配失败,程序终止!\n");
		exit(-1);
	}
         pNew->data=val;
	q=p->pNext;
	p->pNext=pNew;
         pNew->pNext=q;
         return true; 
}
bool DeleteNode(PNODE pHead,int pos,int *pVal)
{
	int i=0;
	PNODE p=pHead,q;
	while(NULL!=p->pNext&&i<pos-1)//当链表不为空,p指向要删除位置的前一个结点
	{
		p=p->pNext;
		++i;
	}
	if(i>pos-1||NULL==p->pNext)//当pos值小于或等于0,或指向了尾结点(此时要删除的下一个结点不存在)时;
		return false;
	q=p->pNext;
	*pVal=q->data;
	p->pNext=p->pNext->pNext;
	free(q);
	q=NULL;
	return true;
}
void SortList(PNODE pHead)
{
	int i,j,t;
	int len=Length(pHead);//用len来保存链表的长度
	PNODE p,q;
         for(i=0,p=pHead->pNext;i<len-1;p=p->pNext,i++)//比较趟数
	{
		for(j=i+1,q=p->pNext;j<len;q=q->pNext,j++)//比较对数
		{
			if(p->data>q->data)
			{
				t=p->data;
				p->data=q->data;
				q->data=t;
			}
		}
	}
}
bool QueryNode(PNODE pHead,int pos)
{
	int i=0;
	PNODE p=pHead,q;
	while(NULL!=p->pNext&&i<pos-1)
	{
		p=p->pNext;
		++i;
	}
	if(i>pos-1||NULL==p)
		return false;	
	q=p->pNext;
	printf("第%d号位置上结点的值为:%d\n",pos,q->data);
	return true;
}
bool ModifyNode(PNODE pHead,int pos,int val)
{
	int i=0;
	PNODE p=pHead,q;
	while(NULL!=p->pNext&&i<pos-1)
	{
		p=p->pNext;
		++i;
	}
	if(i>pos-1||NULL==p)
		return false;	
     q=p->pNext;
	 q->data=val;
	 printf("修改第%d号位置上结点的值为:%d\n",pos,q->data);
	 return true;
}


注意:

1.在vc++中,c编译器不支持bool函数,但c++编译器支持,所以这里我用的是c++编译器。

2.c编译过程中常见错误:illegal use of this type as an expression 是由于c语言不允许临时定义变量,所有定义的变量都必须放在函数开头,这也是c和c++的重要区别

数据结构的再理解

狭义上的理解:数据结构是专门研究数据存储(包括个体的存储和个体关系的存储)问题。

广义上的理解:数据结构既包含数据的存储也包含数据的操作。算法是对存储数据的操作。

算法:

狭义上的理解:算法和数据的存储方式密切相关

广义上的理解:算法和数据的存储方式无关(这就是泛型的思想)

泛型:利用某种技术达到的效果就是不同的存储方式,执行的操作是一样的。泛型主要通过模板,运算符的重载,指针来实现,在c++中经常用到。

补充

线性结构:

连续存储【数组】

优点:存取速度快

缺点:插入删除元素很慢,空间通常是有限制的,事先必须知道数组的长度,而且需要大块连续内存块

离散存储【链表】

优点:插入删除元素很快,空间没有限制的;

缺点: 存取速度很慢

结束语

链表相关操作中,个人感觉较难的是链表的创建,对结点的插入,删除和排序。今天就写到这,明天开始学习线性结构中的两种应用之一 --栈
分享到:
评论

相关推荐

    数据结构课程设计链表操作

    本项目提供的"数据结构链表操作.doc"文档很可能包含了对以上操作的详细步骤、代码示例和分析,是学习和理解链表操作的宝贵资源。通过这个课程设计,学生可以深入理解链表的工作原理,掌握链表操作的实现细节,提高...

    数据结构-双向链表

    理解并熟练掌握双向链表的原理和操作,对于提升编程能力,特别是数据结构和算法的理解,有着极大的帮助。 总之,双向链表是一种强大的数据结构,它的设计使得在链表中进行插入、删除和查找等操作更为灵活。通过理解...

    C++ 数据结构 链表

    本文将深入探讨C++中的三种关键链表数据结构:单链表、循环链表和双向链表,以及如何通过面向对象编程来实现它们。 1. **单链表**: 单链表是最基础的链式数据结构,每个节点包含一个数据元素和一个指向下一个节点...

    数据结构链表代码

    链表操作的效率与链表的长度有关,插入和删除操作通常比数组快,因为它们不需要移动元素,但访问特定位置的元素可能较慢,因为需要从头开始遍历。 在进行链表实现时,还需要考虑一些额外的细节,如错误处理(如内存...

    链表演示程序(数据结构课程设计)

    链表是一种基础且重要的数据结构,它在计算机科学中扮演着关键角色,特别是在处理动态数据集合时。在这个链表演示程序中,我们看到一个用Java语言实现的链表,它是针对数据结构课程设计的一个项目。这个项目的目标是...

    数据结构课设报告,城市链表

    数据结构课设报告——城市链表 1. 课程设计目标与任务 ...总结,本课程设计旨在提升学生对数据结构中链表的理解和应用能力,通过实现城市链表,学习了链表的基本操作,并锻炼了问题解决和文档撰写的能力。

    数据结构 链表的操作可反复操作

    文件名"Baidu.cpp"等可能暗示这是一段用C++编写的代码,C++提供了丰富的STL库,其中包括`std::list`容器,可以方便地实现链表操作。 在实际编程中,链表的这些操作可反复执行,意味着程序可能包含循环或递归结构,...

    数据结构 链表的操作 win32 VS

    在数据结构实验中,通过实际编程实现链表操作,有助于加深对链表的理解。你可以尝试实现不同的链表操作,比如排序链表、反转链表、合并两个有序链表等,进一步提升你的编程技能。 总结,链表是编程中不可或缺的数据...

    数据结构链表合并

    理解并掌握链表的操作对于理解和优化算法至关重要,因为许多高级数据结构和算法都是基于链表构建的。在实际编程中,还需要考虑内存管理,例如在合并后释放不再使用的链表节点,以及错误处理等细节。

    单向链表实验报告(数据结构)

    通过这些实验,学生能够深入理解单向链表的动态特性,以及如何使用基本的链表操作解决实际问题。此外,这也有助于提高编程能力和问题解决技巧,因为这些操作都需要对指针操作和链表结构有清晰的理解。

    链表的基本操作 数据结构

    `read me 2.txt`文件可能是对项目或源码的简单说明,包括编译和运行指南,或者关于链表操作的额外注解。 了解并熟练掌握链表的操作是学习数据结构的基础,对于理解和解决复杂算法问题至关重要。通过实践这些基本...

    数据结构双向链表

    总的来说,双向链表是数据结构中一个重要的工具,理解和掌握其原理和操作对学习算法和提升编程技能至关重要。通过分析`DoubleLinkList`文件,初学者可以深入理解双向链表的实现细节,为后续的编程学习打下坚实基础。

    数据结构 三叉链表表示的二叉树

    在计算机科学中,数据结构是...通过理解和熟练掌握这种数据结构,能提高在实际编程中的效率,特别是在需要频繁进行层次操作的场景下。同时,这也是数据结构学习中的一个重要环节,对于提升算法设计和分析能力大有裨益。

    数据结构链表,队列,栈和二叉树的各种操作

    链表操作包括插入、删除、查找等,它们通常比数组更灵活,但访问速度较慢。 队列是一种先进先出(FIFO)的数据结构,就像银行的排队系统。常见的队列操作有入队(将元素添加到队尾)和出队(从队头移除元素)。队列...

    算法大全-面试题-链表-栈-二叉树-数据结构

    "算法大全-面试题-链表-栈-二叉树-数据结构"这个压缩包文件提供了丰富的知识资源,旨在帮助学习者深入理解和应用这些核心概念。 链表是一种线性数据结构,与数组不同,它的元素在内存中不是连续存储的。链表由一...

    数据结构线性链表课件

    线性链表是数据结构的一种基本类型,对于理解更复杂的数据结构和算法设计至关重要。本课件“数据结构线性链表”旨在帮助学习者深入理解线性链表的概念、操作以及其在实际问题中的应用。 线性链表是一种非连续存储...

    数据结构C++链表

    这个项目提供了实际操作链表的实践经验,对于理解数据结构和C++编程非常有帮助。链表的使用场景广泛,如在实现LRU缓存、解决动态规划问题等。通过这个项目,你可以深入理解链表的内部工作原理,学习如何使用指针管理...

    《数据结构》链表的插入和删除操作

    本篇文章将详细探讨《数据结构》中链表的插入和删除操作,旨在帮助学习者深入理解并熟练掌握这一核心概念。 首先,我们来了解链表的基本构成。链表由一系列节点组成,每个节点包含两部分:数据域(存储数据)和指针...

Global site tag (gtag.js) - Google Analytics