结点的操作
由于链表是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++中经常用到。
补充
线性结构:
连续存储【数组】
优点:存取速度快
缺点:插入删除元素很慢,空间通常是有限制的,事先必须知道数组的长度,而且需要大块连续内存块
离散存储【链表】
优点:插入删除元素很快,空间没有限制的;
缺点: 存取速度很慢
结束语
链表相关操作中,个人感觉较难的是链表的创建,对结点的插入,删除和排序。今天就写到这,明天开始学习线性结构中的两种应用之一 --栈
分享到:
相关推荐
课题:设计一个基于链表的数据结构,实现一个简单的学生信息管理系统。 1. 确定课程目标和内容:本课题的目标是让学生掌握链表...教材应包含理论知识、实例代码和练习题等内容,以便学生更好地理解和掌握链表数据结构
本程序的主要目的在于帮助同学熟练掌握线性表的基本操作在链式存储结构上的...通过本实验, 对链表基本操作及其组合应用的演练,加深对链表存储方法及其基本操作的理解,为以后进 一步学习更复杂的数据结构打下基础。
适用于考研初试数据结构顺序表,链表,队列,栈,串,二叉树基础操作的代码练习,里面有实现函数和注释,可以通过运行程序来加深对数据结构的理解。顺序表包含静态存储和动态存储的结构体定义,初始化,插入和删除...
通过这次专题实习,巩固和加深对所学相关知识点的理解,进一步熟悉基本自定义类、函数的应用加强对模块化程序设计和面向对象程序设计的理解。掌握C++语言程序设计的基本思想,了解简单的系统分析和设计方法。 在main...
3、加深对二叉树的理解,逐步培养解决实际问题的编程能力 一)基础题 1、编写二叉排序树的基本操作函数 (1)SearchNode( TREE *tree, int key,TREE **pkpt,TREE **kpt ) 查找结点函数; (2)InsertNode( TREE ...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
经过一上午的学习,对数据结构有了新的认识和理解 数组 数组是由有限个相同类型的变量所组成的有序集合,它可以进行元素的插入、删除、查找等操作,它的物理存储方式是顺序存储,访问方式是随机访问,利用下标查找...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
C语言数据结构 双向链表的建立与基本操作 双向链表比单链表有更好的灵活性,其大部分操作与线性表相同。下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题。 1.双向链表的建立 双向链表在初始...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了指针操作的基本技巧。 JavaScript解决方案 在JavaScript中,链表通常通过构建一个ListNode类来表示,其中包含val和next两个...
包含链表的建立,插入,删除,查找操作,结构清晰,指针及结构体运用灵活,针对性强,有助于对C语言的深入理解
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
数据结构各种算法的源代码,包括链表,树,图的基本结构与操作,排序,合并的各种算法,关键路径,最小生成树等等
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...
数据结构是计算机存储、组织数据的方式,它涉及到数据的逻辑结构、物理结构以及对数据的基本操作。数据结构的选择会影响到程序的效率、可读性和可维护性。常见的数据结构有数组、链表、栈、队列、树、图等。 算法则...