数据结构-单链表元素的删除与插入

格式：docx
大小：50.02 KB
文档页数：4

下载文档原格式

单链表的基本操作

10）调用头插法的函数，分别输入10,20，分别回车：
11）调用尾插法的函数，分别输入30,40
12）查找单链表的第四个元素：
13）主函数中传入参数，删除单链表的第一个结点：
14）主函数传入参数，删除第0个未位置的元素，程序报错：
15）最后，输出单链表中的元素：
return 0;
}
6）编译，连接，运行源代码：
7）输入8，回车，并输入8个数，用空格分隔开，根据输出信息，可以看出，链表已经拆分为两个
五、实验总结
1.单链表采用的是数据+指针的表示形式，指针域总是指向下一个结
点（结构体）的地址，因此，在内存中的地址空间可以是不连续的，操作比顺序存储更加的方便
2.单链表使用时，需要用malloc函数申请地址空间，最后，删除元
素时，使用free函数释放空间。

数据结构简答题和论述题

数据结构简答题和论述题1、试描述数据结构和抽象数据类型的概念与程序设计语⾔中数据类型概念的区别。

【解答】数据结构是指相互之间存在⼀定关系的数据元素的集合。

⽽抽象数据类型是指⼀个数据结构以及定义在该结构上的⼀组操作。

程序设计语⾔中的数据类型是⼀个值的集合和定义在这个值集上⼀组操作的总称。

抽象数据类型可以看成是对数据类型的⼀种抽象。

串:是零个或多个字符组成的有限序列。

串是⼀种特殊的线性表，它的每个结点仅由⼀个字符组成。

空串 :长度为零的串，它不包含任何字符。

空⽩串 :仅由⼀个或多个空格组成的串⼦串 :串中任意个连续字符组成的⼦序列称为该串的⼦串。

串变量和串常量通常在程序中使⽤的串可分为：串变量和串常量。

（1）串变量：串变量和其它类型的变量⼀样，其取值是可以改变的。

（2）串常量：串常量和整常数、实常数⼀样，在程序中只能被引⽤但不能改变其值。

即只能读不能写。

（1）树形图表⽰：树形图表⽰是树结构的主要表⽰⽅法。

（2）树的其他表⽰法① 嵌套集合表⽰法：是⽤集合的包含关系来描述树结构。

② 凹⼊表表⽰法：类似于书的⽬录③ ⼴义表表⽰法：⽤⼴义表的形式表⽰的。

上图 (a)树的⼴义表表⽰法如下：（A（B（E，F（I，J））， C，D（G，H）））1．中序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)访问根结点； (3)遍历右⼦树。

2．先序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1) 访问根结点； (2) 遍历左⼦树； (3) 遍历右⼦树。

3．后序遍历得递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)遍历右⼦树； (3)访问根结点。

2、链表具有的特点是B 插⼊、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正⽐顺序队列（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2）顺序队列的表⽰①和顺序表⼀样顺序队列⽤⼀个向量空间存放当前队列中的元素。

《数据结构》实验指导书

四、实验说明
1.单链表的类型定义
#include <stdio.h>
typedef int ElemType；//单链表结点类型
typedef struct LNode
{ElemType data;
struct LNode *next;
2.明确栈、队列均是特殊的线性表。
3.栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。
六、实验报告
根据实验情况和结果撰写并递交实验报告。
实验四串
一、预备知识
1.字符串的基本概念
2.字符串的模式匹配算法
二、实验目的
1.理解字符串的模式匹配算法（包括KMP算法）
typedef struct
{ElemType *base；
int front,rear；
} SqQueue；
4.单链队列的类型定义
typedef struct QNode
{QElemType data;
typedef struct list
{ElemType elem[MAXSIZE];//静态线性表
int length; //顺序表的实际长度
} SqList;//顺序表的类型名
五、注意问题
1.插入、删除时元素的移动原因、方向及先后顺序。
4.三元组表是线性表的一种应用，通过它可以更好地理解线性表的存储结构。同时矩阵又是图的重要的存储方式，所以这个实验对更好地掌握线性表对将来对图的理解都有极大的帮助。
六、实验报告
根据实验情况和结果撰写并递交实验报告。
实验六树和二叉树
一、预备知识
1.二叉树的二叉链表存储结构

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

数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：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）void InitList(LinkNode *&L)//初始化线性表{L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L->next=NULL;//单链表置为空表}void DestroyList(LinkNode *&L)//销毁线性表{LinkNode *pre=L,*p=pre->next;实验截图（2）bool GetElem(LinkNode *L,int i,ElemType &e) //求线性表中第i个元素值{ int j=0;if (i<=0) return false;//i错误返回假LinkNode *p=L;//p指向头结点,j置为0(即头结点的序号为0) while (j<i && p!=NULL)//找第i个结点p{ j++;p=p->next;}if (p==NULL)//存在值为e的结点,返回其逻辑序号ireturn(i);}实验截图（3）bool ListInsert(LinkNode *&L,int i,ElemType e) //插入第i个元素{ int j=0;if (i<=0) return false;//i错误返回假LinkNode *p=L,*s;//p指向头结点,j置为0(即头结点的序号为0) while (j<i-1 && p!=NULL)//查找第i-1个结点p{ j++;p=p->next;}}实验截图（4）编写exp2-2.cpp程序包含有关代码//文件名:exp2-2.cpp#include "linklist.cpp"int main(){LinkNode *h;ElemType e;printf("单链表的基本运算如下:\n");printf(" (1)初始化单链表h\n");InitList(h);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");return 1;}实验截图（5）运行得到结果实验截图（6）。

写出单链表存储结构的 c 语言描述

写出单链表存储结构的 c 语言描述一、单链表的概述单链表是一种常见的数据结构，它由若干个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

单链表的特点是插入和删除操作效率高，但查找操作效率较低。

二、单链表的存储结构单链表的存储结构采用动态分配内存的方式，每个节点都是一个独立的内存区域，通过指针将它们连接在一起。

下面是单链表存储结构的 c 语言描述：```typedef struct Node{int data; // 数据域struct Node *next; // 指针域} ListNode, *LinkedList;```上面代码中，ListNode 表示节点类型，LinkedList 表示链表类型。

其中 data 是数据域，next 是指针域，用于存放下一个节点的地址。

三、单链表的基本操作1. 初始化操作初始化操作用于创建一个空链表。

```void InitList(LinkedList *L){*L = (ListNode*)malloc(sizeof(ListNode)); // 创建头结点(*L)->next = NULL; // 头结点指针域为空}```2. 插入操作插入操作用于在链表中插入新节点。

```int Insert(LinkedList L, int i, int x)int j = 0;ListNode *p = L;while (p && j < i - 1) // 找到第 i-1 个节点{p = p->next;j++;}if (!p || j > i - 1) // 判断 i 的范围是否合法{return 0;}ListNode *s = (ListNode*)malloc(sizeof(ListNode)); // 创建新节点s->data = x; // 赋值数据域s->next = p->next; // 新节点指向下一个节点p->next = s; // 前一个节点指向新节点 return 1;```3. 删除操作删除操作用于删除链表中的某个节点。

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

单链表实验报告一、实验目的1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。

二、实验内容[问题描述]实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

三、算法设计（1）建立带表头结点的单链表；首先输入结束标志，然后建立循环逐个输入数据，直到输入结束标志。

（2）输出单链表中所有结点的数据域值；首先获得表头结点地址，然后建立循环逐个输出数据，直到地址为空。

（3）输入x,y在第一个数据域值为x的结点之后插入结点y，若无结点x，则在表尾插入结点y;建立两个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，建立循环扫描链表。

当当前结点指针域不为空且数据域等于x的时候，申请结点并给此结点数据域赋值为y，然后插入当前结点后面，退出函数；当当前结点指针域为空的时候，申请结点并给此结点数据域赋值为y，插入当前结点后面，退出函数。

（4）输入k，删除单链表中所有的结点k，并输出被删除结点的个数。

建立三个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，最后一个备用；建立整形变量l=0；建立循环扫描链表。

当当前结点指针域为空的时候，如果当前结点数据域等于k，删除此结点，l++，跳出循环，结束操作；如果当前结点数据域不等于k，跳出循环，结束操作。

当当前结点指针域不为空的时候，如果当前结点数据域等于k，删除此结点，l++，继续循环操作；如果当前结点数据域不等于k，指针向后继续扫描。

循环结束后函数返回变量l的值，l便是删除的结点的个数。

四、实验结果1、新建一个链表：2、输出链表的数据：（4）插入数据：在数据为3后面插入一个数据100：（5）删除数据：删除刚刚插入的数据100：五、总结实验之前由于准备不够充分，所以堂上实验时只完成了建立单链表和数据的输出，而后面两个实验要求也是用来很多时间长完成的。

单链表数据结构

插入
if (p != NULL && j == i-1) { // 找到第i个结点
s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点
s->data = e;
// 数据域赋值
s->next = p->next; //新结点指针指向后一结点
p->next = s; return OK;
6、销毁
4.6 销毁操作
while(L) { p = L->next; free(L); L=p;
// p指向第一结点(头节点为“哑结点”) // 释放首结点 // L指向p
}
// 销毁完成后，L为空(NULL)
算法的时间复杂度为：O(ListLength(L))
判空求表长
4.7 其它操作
if(L->next==NULL) return TRUE; // 空
5、清空
4.5 清空操作
while (L->next) { p = L->next; L->next = p->next; free(p);
// p指向当前结点 // 头结点指向当前结点的后结点 // 释放当前结点内存
}
// 清空完成后，仍保留头结点L
算法的时间复杂度为：O(ListLength(L))
点。
5.1.2 逆序建立单链表
①建立一个带头结点的空单链表；
②输入数据元素ai，建立新结点p，并把p插入在头结点之后成为第一个结点。
③重复执行②步，直到完成单链表的建立。
a1
a2 a1
创建出来的链表点顺序与插入操作
顺序相反。

单链表的基本操作实验问题与对策

单链表的基本操作实验问题与对策单链表是一种非常基础且常见的数据结构，被广泛应用于计算机科学和相关领域中。

它通过使用一系列节点来存储元素，每个节点都包含一个值和一个指向下一个节点的指针。

这些节点以线性方式连接，形成了一个单向链表。

在进行单链表的基本操作实验时，可能会遇到一些常见的问题和挑战。

例如，在进行插入操作时，可能会出现指针错误或内存分配失败的问题。

在删除操作中，可能会遇到无法找到指定元素或无法正确更新节点指针的问题。

在进行查找操作时，可能会遇到查找效率低下或无法找到特定元素的问题。

而在遍历操作中，可能会遇到指针断裂或无限循环的问题。

为了解决这些问题，我们可以采取一些对策。

例如，在进行插入操作时，我们可以使用更高效的数据结构或算法来避免指针错误和内存分配失败的问题。

在删除操作中，我们可以使用更精确的查找算法来找到指定元素并正确更新节点指针。

在进行查找操作时，我们可以使用更优化的查找算法或数据结构来提高查找效率并找到特定元素。

而在遍历操作中，我们可以使用更安全的遍历算法来避免指针断裂和无限循环的问题。

总之，单链表是一种非常有用的数据结构，在进行基本操作实验时可能会遇到一些问题和挑战。

但只要我们采取适当的对策，就可以有效地解决这些问题并更好地应用单链表这种数据结构。

问题1：插入节点时如何确保正确的位置？对策：在插入节点之前，需要遍历链表以找到正确的位置。

可以使用循环来遍历链表，确保插入的位置是正确的。

另外，可以考虑维护一个指向前一个节点的指针，以便在插入时更容易操作。

问题2：如何删除节点？对策：删除节点时，需要找到待删除节点的前一个节点，并将其指针指向待删除节点的下一个节点，然后释放待删除节点的内存。

确保在删除节点之前释放内存，以避免内存泄漏。

问题3：如何遍历链表？对策：遍历链表通常需要使用循环，从链表的头节点开始，沿着指针依次访问每个节点，直到达到链表的末尾。

可以使用循环结构来实现遍历，或者使用递归方法。

数据结构实验指导书(新版)

《数据结构与算法》实验指导书实验及学时数分配几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

（从键盘接受删除元素位置i，实现删除；显示删除后的线性表）二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

单链表的删除与插入源程序如下：
#include<stdio.h>
#include<malloc.h>
#include<windows.h>
typedef int elemtype;
typedef struct LNode //定义单链表存储类型
{
elemtype data;
struct LNode *next;
}linklist;
void creatlistf(linklist *&L ) //建立链表
{
linklist *s;
int i;
elemtype a[10];
printf("请输入10个数:\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
L=(linklist *)malloc(sizeof(linklist));
L->next=NULL;
for(i=0;i<10;i++)
{
s=(linklist *)malloc(sizeof(linklist));
s->data=a[i];
s->next=L->next;
L->next=s;
}
}
void displist(linklist *L) //输出单链表
{
linklist *s;
s=L->next;
while(s!=NULL)
{
printf(" %d",s->data);
s=s->next;
}
printf("\n");
}
void listinsert(linklist *L) //插入元素
{
int i=0,j,m;
linklist *s,*p;
printf("请输入插入位置:");
scanf("%d",&j);
printf("请输入需插入元素:");
scanf("%d",&m);
s=L;
while(i<j-1 && s!=NULL)
{
s=s->next;
i++;
}
if(s==NULL)
printf("输入错误!\n");
else
{
p=(linklist *)malloc(sizeof(linklist)); p->data=m;
p->next=s->next;
s->next=p;
}
}
void listdelete(linklist *&L)//删除元素{
int i,j=0,e;
printf("请输入需删除第几个元素:"); scanf("%d",&i);
linklist *s;
s=L;
while(j<i-1&&s!=NULL)
{
s=s->next;
j++;
}
if(s->next==NULL)
printf("输入错误!\n");
else
{
if(s->next->next!=NULL)
{
e=s->next->data;
s->next->data=s->next->next->data;
s->next->next=s->next->next->next;
printf("成功删除元素%d\n",e);
}
else if(s->next!=NULL&&s->next->next==NULL)
{
printf("成功删除元素%d\n",s->next->data);
free(s->next);
s->next=NULL;
}
else
{printf("&&&&&&&&&");
printf("输入错误!\n");}
}
}
void main()
{printf(" ***************欢迎使用单链表基本运算系统********************\n"); linklist *p;
int m;
creatlistf(p); //建立链表
printf("单链表已建立完毕\n");
while(1)
{
printf("请选择:");
printf(" 1.输出链表\n");
printf(" 2.插入元素\n");
printf(" 3.删除元素\n");
printf(" 4.退出\n");
scanf("%d",&m);
switch(m)
{case 1:displist(p);break;
case 2:listinsert(p);break;
case 3:listdelete(p);break;
case 4:exit(0);
default:printf("输入错误\n");
}
}
}
运行效果如下：。