当前位置：文档之家 › 关于单链表的操作

关于单链表的操作

  • 格式：doc
  • 大小：62.00 KB
  • 文档页数：7

关于单链表的操作单向链表结构描述示例：struct linklist{ int data；struct linklist *next；}；struct linklist *head；单链表的建立在链表的操作中用到的几个函数：(1)malloc（size）在内存的动态存储区申请一个长度为size字节的连续空间。

并将此存储空间的起始地址作为函数值返回。

malloc函数的原型为： void *malloc(unsigned int size)函数值为指针（地址），这个指针是指向void类型的，也就是不规定指向任何具体的类型。

如果内存缺乏足够大的空间进行分配，则malloc的函数值为“空指针”。

(2)calloc（n， size）在内存的动态存储区申请n个长度为size 字节的连续空间，函数返回值为分配空间的首地址。

若此函数未被成功执行，函数返回值为0。

函数返回值为该空间的首地址。

其函数原型为：void *calloc(unsigned int n，unsigned int size)(3)free（p）释放由指针p所指向的存储单元，而所释放的存储单元的大小是最近一次调用malloc（）函数或calloc（）函数时所申请的存储空间。

free 函数的原型为：void free(void *ptr)系统可以回收所释放的空间，另行分配作为它用。

(4)realloc函数。

其函数的原型为：void realloc(void *ptr，unsigned int size)其作用是将ptr所指向的存储区（原先用malloc函数分配的）的大小改为size个字节。

可以使原先分配区扩大和缩小。

它的函数返回值是一个指针，即新的存储区的首地址。

例1 使用表首插入法建立链表。

表首插入法建立链表，这种方法的特点是：新产生的结点作为新的表头插入链表。

#include <stdio.h>void main(）{struct linklist{ int data；struct linklist *next；}；struct linklist *head，*p； /*head头指针，p申请单元指针*/head=NULL； /*空链表*//*申请空间，并将指针p强制转换成所指向的结构体类型*/p=(struct linklist*)malloc(sizeof(struct linklist))；scanf("%d"，&p−>data)； /*得到数据，放结点数据域*/while(p−>data>0) /*假设所给数据都大于0*/{ p−>next=head；/*建立链接，当前结点指针域存放下一结点地址*/ head=p； /*用头指针保存当前结点*//*为下一个结点申请空间*/p= (struct linklist*)malloc(sizeof(struct linklist))；scanf("%d"，&p−>data)； /*得到新结点数据*/ }}运行该程序，输入准备建立链表的各数据，以0结束数据的输入，即可得到一个链表。

由于是表首添加法，最后输出链表中的数据的输入顺序正好与输入顺序相反。

例2 表尾插入法建立链表若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为表尾插入法。

表尾插入法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针p2、申请单元指针p1。

表尾插入法最先得到的是头结点。

#include <stdio.h>void main( ){struct linklist{ int data；struct linklist *next；}；struct linklist *head，*p1，*p2；head=NULL； /*空链表*/p1=（struct linklist*）malloc（sizeof（struct linklist））；/*申请空间*/p2=p1;scanf（"%d"，&p1->data）； /*得到数据*/while（p1->data>0）{ if（head==NULL） head=p1；else p2->next=p1； /*建立连接*/p2=p1； / *保存当前结点*//*为下一个结点申请空间*/p1=(struct linklist*)malloc(sizeof(struct linklist))；scanf("%d"，&p1−>data)； /*得到下一个结点数据*/ }p2−>next=NULL；/*最后的尾结点指针域为空指针*/}运行该程序，输入准备建立链表的各数据，以0作为结束数据的输入，即可得到一个链表，该链表的输出顺序与输入顺序一致。

单链表的有关操作链表的基本操作包括建立链表、链表结点的插入、删除、输出和查找等。

下面介绍完成单链表的基本操作的函数。

1.输出链表中所有结点要依次输出链表中各结点的数据比较容易。

首先要知道表头结点的地址，即要知道head的值，然后设一个指针变量p，先指向第一个结点，输出p所指的结点，然后使p后移一个结点，再输出，直到链表的尾结点。

void print（struct linklist *head） /*输出链表所有结点*/{ struct linklist *p；p=head； /*p指向链表第一个结点*/while（p！=NULL）{ printf（"%d"，p->data）；p=p->next； /*p指向下一个结点*/}}head的值由实参传过来，即将已有的链表的头指针传给被调用的函数，在p rint函数中从head所指的第一个结点出发，顺序输出各结点，直到链表的结尾。

2.统计链表中结点个数只需将上述输出结点改成计数即可。

int count（struct linklist *head）{ int n=0；struct linklist *p；p=head；while（p！=NULL）{ n++；p=p->next；}return（n）；}调用此函数，即可返回链表中结点的个数。

3.插入结点的操作将一个结点插入到一个已有链表的某个位置。

该任务可分解成两个步骤：即先查找到插入点，再插入结点。

指针head指向链表的头结点，p指针指向要插入结点的前一个结点，q指针指向新产生的结点。

void ins（struct linklist *head，int i，int x）/*在第i个结点处插入值为x结点*/{ int j；struct linklist *p，*q；p=head；j=1；while（（p！=NULL）&&（j<i）） /*找插入位置*/{ p=p->next；j++；}q=（struct linklist *）malloc（sizeof（struct linklist））；/*产生插入结点*/q->data=x；q->next=p->next； /*q插入p之后 */p->next=q；}运行该程序，根据所给的i值，在循环的控制下，找到第i个结点的前一个位置，用指针p指向它，然后实施在第i-1个(p指针所制结点之后)插入一个结点的操作。

4.删除操作假设删除链表中第i个结点，先找到第i-1个结点和第i个结点，然后将第i+1个结点链接在第i-1个结点后，即改变链接关系，再释放第i个结点所占空间，完成删除操作。

void del（struct linklist *head， int i） /*删除结点*/{ int j；struct linklist *p，*q；p=head；j=1；while（（p！=NULL）&&（j<i））/*找第i-1个结点和第i个结点并用指针q、p指向*/{ q=p；p=p->next；j++；}if（p==NULL）printf（"找不到结点！"）；else{ q->next=p->next； /*删除第i个结点 */free（p）；}}5.链表的查找操作链表结点的查找是指在链表中查找值为某指定值的结点。

链表的查找过程是从链表的头指针所指的第一个结点出发，顺序查找；或发现有指定值的结点，以指向该结点的指针值为查找结果；或查找到链表的结尾，若未发现有指定值的结点，则查找结果为NULL，表示链表中没有指定值的结点。

在下例中，以指定学号作为查找结点的标志。

查找一个结点的函数find如下：struct student *find(struct student *head, int num){ struct student *p1,*p2;if(head==NULL){ printf("\n list null!\n");return(head);}p1=head;while(num!=p1->num&&p1!=NULL){ p2=p1;p1=p1->next;}if(p1!=NULL)printf("find:%d,%6.2f\n",p1->num, p1->score);else printf("%d not found!\n",num);}说明：一般查找操作总是与其它相关操作相联系的。

如：插入、删除操作等，故在查找的过程中，设置了两个工作指针p2与p1，p1指向要查找的结点，p2指向要查找结点的左边的一个结点。

以方便进行插入和删除操作。

例3 假设链表结点信息包括学生学号、成绩，结点定义如下：typedef struct plist{ int no;float score;struct plist *next;}plist;设已经建立了两个具有上述结构的链表，且两个链表都是以学号升序排列，要求编写一个函数，将两个链表（按升序）合并。

算法：①函数应有两个链表指针形参：p1, p2指向它们各自的表头；②最初链表的头指针head=NULL，新链表的当前结点指针p=NULL；③产生新链表的头结点；④当两个链表的指针均没指向表尾，则依次选择两个链表中的结点并入到新链表中；⑤当某一个链表已到表尾，则将另一个链表的剩余部分直接链接到新链表的表尾。

完成此功能的程序为：plist *merge(plist *p1, plist *p2)/*p1与p2分别为两个链表的头指针*/{ plist *p, *head;if(p1->no<p2->no ){ head=p=p1;p1=p1->next;} /*产生新链表的头结点*/else{ head=p=p2;p2=p2->next;}while(p1!=NULL &&p2!=NULL)if(p1->no<p2->no){ p->next=p1; /*p1指示的结点并入到新链表*/p=p1; /*p1指向新链表的表尾*/p1=p1->next; /*p1指向后继*/}else{ p->next=p2; /*p2指示的结点并入到新链表*/p=p2;p2=p2->next; /*p2指向后继*/}if(p1!=NULL) /*p1没有到达表尾*/p->next=p1; /*p1指示的链表后部分链接新链表的表尾*/ else p->next=p2; /*p2指示的链表后部分链接新链表的表尾*/return head;}循环while(p1!=NULL &&p2!=NULL)终止时，表示有p1指示的链表为空或p 2所指示的链表为空，再只将另一非空的链表（p2指示的链表或p1所指示的链表）链入到新链表中即可。

合集下载

数据结构实验报告--单链表

数据结构实验报告--单链表

数据结构实验报告--单链表数据结构实验报告--单链表1.引言1.1 研究目的本实验旨在通过实践的方式，深入了解单链表的数据结构以及相关操作，提升对数据结构的理解和应用能力。

1.2 实验内容本实验主要包括以下几个方面的内容：●单链表的基本定义和实现●单链表的插入、删除、遍历操作●单链表的逆置操作●单链表的查找和修改操作2.理论基础2.1 单链表的定义单链表是一种常见的线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。

2.2 单链表的基本操作①单链表的插入操作在单链表中，可以通过插入操作在指定位置插入一个新节点，该操作主要包括以下步骤：●创建一个新的节点，并为其赋值●将新节点的next指针指向插入位置的后一个节点●将插入位置的前一个节点的next指针指向新节点②单链表的删除操作在单链表中，可以通过删除操作删除指定位置的节点，该操作主要包括以下步骤：●将删除位置的前一个节点的next指针指向删除位置的后一个节点●释放删除节点的内存③单链表的遍历操作单链表的遍历操作主要是依次访问链表中的每一个节点，并执行相应的操作。

④单链表的逆置操作单链表的逆置操作可以将一个单链表中的节点顺序进行颠倒。

⑤单链表的查找操作在单链表中，可以通过查找操作找到指定值的节点。

⑥单链表的修改操作在单链表中，可以通过修改操作修改指定位置的节点的值。

3.实验过程3.1 实验环境本次实验使用C语言进行编程，需要先安装相应的编程环境，如gcc编译器。

3.2 实验步骤①单链表的创建和初始化首先创建一个空链表，并初始化链表的头指针。

②单链表的插入操作按照需求，在链表的指定位置插入一个新节点。

③单链表的删除操作按照需求，删除链表中的指定位置的节点。

④单链表的遍历操作依次访问链表中的每一个节点，并输出其值。

⑤单链表的逆置操作将单链表中的节点顺序进行逆置。

⑥单链表的查找操作按照需求，在链表中查找指定值的节点。

3.2.7 单链表的修改操作按照需求，修改链表中指定位置的节点的值。

数据结构-单链表基本操作实现（含全部代码）

数据结构-单链表基本操作实现（含全部代码）

数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：InitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

最坏是O(n),即从头查找p之前的结点,然后删除p所指结点LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第⼀个等于e的元素，返回指针时间复杂度O(n)代码：/*Project: single linkeed list (数据结构单链表)Date: 2018/09/14Author: Frank YuInitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

单链表基本操作的实现

单链表基本操作的实现

单链表基本操作的实现单链表是一种常见的数据结构，它由多个节点组合而成，每个节点包含一个数据元素和一个指向下一个节点的指针。

通过指针，我们可以方便地在单链表中进行插入、删除和遍历等操作。

以下是关于单链表基本操作的实现。

1. 单链表的创建单链表的创建需要定义一个空的头结点，它的作用是方便在链表的头部进行添加和删除节点操作。

一个空的头节点可以在链表初始化的过程中进行创建。

```typedef struct Node{int data;struct Node *next;}Node;Node *createList(){Node *head = (Node*)malloc(sizeof(Node)); //创建空的头节点head->next = NULL;return head; //返回头节点的地址}```2. 单链表的插入单链表的插入可以分为在链表头部插入、在链表尾部插入和在链表中间插入三种情况。

a. 在链表头部插入节点：```void insertAtHead(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = head->next;head->next = node;}```b. 在链表尾部插入节点：```void insertAtTail(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;Node *p = head;while(p->next != NULL){p = p->next;}p->next = node;}```c. 在链表中间插入节点：```void insertAtMid(Node *head, int data, int pos){ Node *node = (Node*)malloc(sizeof(Node)); node->data = data;node->next = NULL;Node *p = head;int count = 0;while(p->next != NULL && count < pos-1){ p = p->next;count++;}if(count == pos-1){node->next = p->next;p->next = node;}else{printf("插入位置错误!");}}```3. 单链表的删除单链表的删除可以分为在链表头部删除、在链表尾部删除和在链表中间删除三种情况。

单链表 头指针 尾指针 删除指定节点的方法

单链表 头指针 尾指针 删除指定节点的方法

单链表的头指针和尾指针是单链表中非常重要的概念，它们分别指向链表的第一个节点和最后一个节点。

删除指定节点也是单链表中常见的操作之一。

本文将介绍单链表的头指针、尾指针以及删除指定节点的相关方法。

一、单链表简介单链表是由节点构成的链式结构，每个节点包括数据域和指针域。

数据域存储节点的数据，指针域指向下一个节点。

单链表中的第一个节点被称为头节点，最后一个节点的指针域为NULL。

二、头指针和尾指针1. 头指针头指针是指向链表中第一个节点的指针，它的作用是方便对链表的操作。

通过头指针可以找到链表的第一个节点，从而对链表进行遍历或其他操作。

2. 尾指针尾指针是指向链表中最后一个节点的指针，它的作用是快速定位链表的尾部。

通过尾指针可以直接找到链表的最后一个节点，而不需要遍历整个链表。

三、删除指定节点的方法单链表中的节点删除操作是常见而重要的操作，通过删除指定节点可以对链表进行精确的控制。

1. 删除指定节点的基本思路要删除单链表中的指定节点，需要找到待删除节点的前一个节点，然后修改指针域将其指向待删除节点的下一个节点。

具体步骤如下：- 遍历链表，找到待删除节点的前一个节点prev；- 将待删除节点的指针域赋值给prev的指针域，跳过待删除节点；- 释放待删除节点的内存空间。

2. 删除指定节点的实现实现删除指定节点的方法可以通过编程语言来完成。

下面以C语言为例，给出删除指定节点的代码示例：```cvoid deleteNode(Node* head, int value){Node* prev = head;Node* cur = head->next;while (cur != NULL){if (cur->data == value){prev->next = cur->next;free(cur);return;}prev = cur;cur = cur->next;}}```以上代码中，首先定义了两个指针prev和cur，分别指向头节点和下一个节点。