数据结构代码(用C语言) 单链表的插入和删除

发布网友发布时间：2022-04-18 04:38

我来回答

共5个回答

懂视网时间：2022-04-18 08:59

python单链表中如何插入和输出节点？下面本篇文章就来带大家了解一下单链表是什么，如何对单链表执行的一些非常基本的操作，例如：插入、输出，希望对大家有所帮助。

单链表是什么？

首先在了解单链表之前，我们必须了解一下节点是什么。

节点是链表的构建块，它由两部分组成：

1、数据部分：用于包含数据

2、地址部分：用于指向下一个节点位置的指针。

在单链表中，每个节点的地址部分包含有关下一个节点位置的信息；这形成一系列的链条或链环。链接列表的第一个节点由头部指针跟踪；最后一个节点指向None。

让我们看看下面的图表来更好地理解这一点：

注意：在上图中，最后一个元素1指向None。即使这些节点彼此连续绘制，实际上它们可能或可能不在连续的存储器位置中。

单链表如何插入和输出节点？

1、创建单链表

首先，您必须创建一个节点才能创建单链表。为此，我们使用data和nextNode属性创建一个Node类。如前所述，data属性将包含数据，而nextNode将简单地指向链表中的下一个节点。我们将默认值nextNode是无。您可以使用getter和setter方法来执行此操作。

现在已经创建了Node类，现在是时候创建LinkedList类了。这只有一个属性，head。默认情况下，这将指向“ None”。如果头部指向“ None”，则表示链接列表为空。为了跟踪链表中的节点数，我们可以向LinkedList类添加一个 size属性，并将其默认为0。

2、插入节点

这是LinkedList类的方法。我们可以在链接列表中的任何位置插入新节点，但为了使编码简单有效，我们将始终将新节点添加到链表的开头；换句话说，头部将始终指向最近添加的节点。

如果我们将新节点添加到列表的末尾，我们需要执行额外的工作来查找列表的末尾然后添加它。这是一种浪费的操作。但是，如果你维护另一个指针，让我们称它为尾指针，使其指向最后一个节点，这可以完成。

下面我们介绍前一种方法，即如何在链表的开头插入节点。

假设我们需要在链表中添加7，我们需要执行以下步骤：

●　创建一个节点对象，其中7表示数据，下一个节点指向头节点

●　将头指针指向此新节点

最后，将size属性增加1，如果插入成功，返回True，这是一个好习惯；这样，用户就知道发生了什么。

3、输出节点

这是LinkedList类的方法。要打印链表中所有节点中的数据，我们需要一次遍历一个节点并打印每个节点的数据部分。

实现代码：

class Node:
 def __init__(self,data,nextNode=None):
 self.data = data
 self.nextNode = nextNode
 def getData(self):
 return self.data
 def setData(self,val):
 self.data = val
 def getNextNode(self):
 return self.nextNode
 def setNextNode(self,val):
 self.nextNode = val
class LinkedList:
 def __init__(self,head = None):
 self.head = head
 self.size = 0
 def getSize(self):
 return self.size
 def addNode(self,data):
 newNode = Node(data,self.head)
 self.head = newNode
 self.size+=1
 return True
 
 def printNode(self):
 curr = self.head
 while curr:
  print(curr.data)
  curr = curr.getNextNode()
myList = LinkedList()
print("Inserting")
print(myList.addNode(5))
print(myList.addNode(15))
print(myList.addNode(25))
print("Printing")
myList.printNode()
print("Size")
print(myList.getSize())

单链表的优点和缺点是什么？

优点：

●　它是一种动态数据结构，在这种结构中，插入和删除很简单，因为我们不需要移动元素。只需更新下一个指针就可以完成这项工作。

●　使用链表可以很容易地实现堆栈和队列数据结构。

缺点

●　下一个指针占用了额外的内存。

●　无法随机访问。必须从头遍历链接列表才能到达特定节点。

热心网友时间：2022-04-18 06:07

单链表功能大全，嘿嘿
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int nDate;
struct node *pstnext;
}Node;
//链表输出
void output(Node *head)
{
Node *p = head->pstnext;
while(NULL != p)
{
printf("%d ", p->nDate);
p = p->pstnext;
}
printf("\r\n");
}
//链表建立
Node* creat()
{
Node *head = NULL, *p = NULL, *s = NULL;
int Date = 0, cycle = 1;
head = (Node*)malloc(sizeof(Node));
if(NULL == head)
{
printf("分配内存失败\r\n");
return NULL;
}
head->pstnext = NULL;

p = head;
while(cycle)
{
printf("请输入数据且当输入数据为0时结束输入\r\n");
scanf("%d", &Date);
if(0 != Date)
{
s = (Node*)malloc(sizeof(Node));
if(NULL == s)
{
printf("分配内存失败\r\n");
return NULL;
}
s->nDate = Date;
p->pstnext = s;
p = s;
}
else
{
cycle = 0;
}
}
p->pstnext = NULL;
return(head);
}
//单链表测长
void length(Node *head)
{
Node *p = head->pstnext;
int j=0;
while(NULL != p)
{
p = p->pstnext;
j++;
}
printf("%d\r\n", j);
}
//链表按值查找
void research_Date(Node *head, int date)
{
Node *p;
int n=1;
p = head->pstnext;
while(NULL != p && date != p->nDate)
{
p = p->pstnext;
++n;
}
if(NULL == p)
{
printf("链表中没有找到该值");
}else if(date == p->nDate)
{
printf("要查找的值%d在链表中第%d个位置\r\n", date, n);
}
return;
}
//按序号查找
void research_Number(Node *head, int Num)
{
Node *p=head;
int i = 0;
while(NULL != p && i < Num)
{
p = p->pstnext;
i++;
}
if(p == NULL)
{
printf("查找位置不合法\r\n");
}else if(i == 0)
{
printf("查找位置为头结点\r\n");
}else if(i == Num)
{
printf("第%d个位置数据为%d\r\n", i, p->nDate);
}
}
//在指定元素之前插入新结点
void insert_1(Node *head, int i, int Newdate)
{
Node *pre = head, *New = NULL;
int j = 0;
while(NULL != pre && j < i-1)
{
pre = pre->pstnext;
j++;
}
if(NULL == pre || j > i-1)
{
printf("插入位置不存在\r\n");
}else
{
New = (Node*)malloc(sizeof(Node));
if(NULL == New)
{
printf("分配内存失败\r\n");
return;
}
New->nDate = Newdate;
New->pstnext = pre->pstnext;
pre->pstnext = New;
}

}
//在指定元素之后插入新结点
void insert_2(Node *head, int i, int Newdate)
{
Node *pre = head, *New = NULL;
int j = 0;
while(NULL != pre->pstnext && j < i)
{
pre = pre->pstnext;
j++;
}
if(j == i)
{
New = (Node*)malloc(sizeof(Node));
if(NULL == New)
{
printf("分配内存失败\r\n");
return;
}
New->nDate = Newdate;
New->pstnext = pre->pstnext;
pre->pstnext = New;
}else
{
printf("插入位置不存在\r\n");
}
}
//删除指定结点
void Delete_1(Node *head, int i3)
{
Node *p = head, *pre = NULL;
int j = 0;
while(NULL != p && j < i3)
{
pre = p;
p = p->pstnext;
j++;
}
if(NULL == p)
{
printf("删除位置不存在\r\n");
}else
{
pre->pstnext = p->pstnext;
free(p);
}
}
//指定删除单链表中某个数据，并统计删除此数据的个数
int Delete_2(Node *head, int Delete_date)
{
int count = 0;
Node *p = head, *q;
while(NULL != p->pstnext)
{
q = p->pstnext;
if(q->nDate == Delete_date)
{
p->pstnext = q->pstnext;
free(q);
++count;
}
else
{
p = q;
}
}
return count;
}
//链表逆置
void Reverse_list(Node *head)
{
Node *q, *s;
if(NULL == head->pstnext || NULL == head->pstnext->pstnext)
{
return;
}
q = head->pstnext->pstnext;
head->pstnext->pstnext = NULL;
while(NULL != q)
{
s = q->pstnext;
q->pstnext = head->pstnext;
head->pstnext = q;
q = s;
}
}
//单链表的连接
void connect_list(Node *head, Node *head_New)
{
Node *p = head;
while(NULL != p->pstnext)
{
p = p->pstnext;
}
p->pstnext = head_New->pstnext;
}
//单链表销毁
void destroy_list(Node* head)
{
while (NULL != head)
{
Node* temp = head;
head = head->pstnext;
free(temp);
}
}
void main()
{
int date, num; //待查找数据
int i3; //指定删除元素的位置
int i1, i2, Newdate_1, Newdate_2; //待插入的新数据
int Delete_date, k; //待删除的数据与其个数
Node *Head = NULL; //定义头结点
Node *Head_New = NULL;

//链表建立
Head = creat();
printf("输出建立的单链表\r\n");
output(Head);

//单链表测长
printf("单链表长度为\r\n");
length(Head);

//链表按值查找
printf("请输入待查找的数据\r\n");
scanf("%d", &date);
research_Date(Head, date);

//链表按序号查找
printf("请输入待查找序号\r\n");
scanf("%d", &num);
research_Number(Head, num);

//在指定第i1个元素之前插入新元素Newdate
printf("在指定第i个元素之前插入新元素Newdate");
printf("请输入i与元素且以逗号间隔\r\n");
scanf("%d,%d", &i1, &Newdate_1);
insert_1(Head, i1, Newdate_1);
printf("插入后新链表\r\n");
output(Head);

//在指定第i2个元素之后插入新元素Newdate
printf("在指定第i个元素之后插入新元素Newdate");
printf("请输入i与元素且以逗号间隔\r\n");
scanf("%d,%d", &i2, &Newdate_2);
insert_2(Head, i2, Newdate_2);
printf("插入后新链表\r\n");
output(Head);

//指定删除i3元素
printf("删除元素的位置\r\n");
scanf("%d", &i3);
Delete_1(Head, i3);
printf("删除后新链表\r\n");
output(Head);

//指定删除单链表中某个数据，并统计删除此数据的个数
printf("请输入待删除的元素\r\n");
scanf("%d", &Delete_date);
k = Delete_2(Head, Delete_date);
printf("删除后新链表\r\n");
output(Head);
printf("删除指定元素在链表中的个数为：");
printf("%d\r\n", k);

//单链表逆置
Reverse_list(Head);
printf("逆置后输出\r\n");
output(Head);

//单链表的连接
printf("建立一个新链表\r\n");
Head_New = creat();
printf("输出新链表");
output(Head);
printf("将新链表连接到原来链表的尾部并输出\r\n");
connect_list(Head, Head_New);
output(Head);
destroy_list(Head);

return;
}

热心网友时间：2022-04-18 07:25

热心网友时间：2022-04-18 09:00

struct A{
char a[20];
struct A *next;
}a;

struct A *apo; //首节点
int charu(struct A *s) //插入
{
struct A p = apo->next;

while(p)
{
if(!strcmp(p->a, s->a))
return 0;
p = p->next;
}
p = apo->next;
s->next = p->next;
p->next = s;

return 1;
}

int shanchu(struct *s) //删除
{
struct A p = apo->next;
struct A m;

m = p;
while(p)
{
if(!strcmp(p->a, s->a))
{
if(p == apo->next) //如果是第一个节点
{
app->next = p->next;
free(p);
}
else
{
m->next = p->next;
free(p);
}
return 0;
}
else
{
m = p;
p = p->next;
}
}
return 1;
}

热心网友时间：2022-04-18 10:51

　建立一个单链表，实现插入与删除功能的代码如下：
　　///单链表
　　#include<iostream>
　　using namespace std;
　　
　　typedef int elemtype; //数据类型模版
　　
　　struct Lnode //结点
　　{
　　elemtype data;
　　Lnode *next;
　　};
　　
　　///建表
　　void creat_Link(Lnode &head)
　　{
　　Lnode *p,*q;
　　int n;
　　p=new Lnode;
　　head=p;
　　cout<<"输入链表长度:"<<endl;
　　cin>>n;
　　cout<<"输入数据:"<<endl;
　　cin>>p->data;
　　q=p;
　　for(int i=1;i<=n-1;i++)
　　{
　　p=new Lnode;
　　//cout<<"输入数据:";
　　cin>>p->data;
　　q->next=p;
　　q=p;
　　}
　　q->next=NULL;
　　}
　　
　　///表的输出
　　void output_Link(Lnode *&head)
　　{
　　if(head==NULL)
　　{cout<<"空链表!"<<endl;
　　return;}
　　Lnode *q;
　　q=head;
　　//cout<<"此链表为:";
　　while(q!=NULL)
　　{
　　cout<<q->data<<" ";
　　q=q->next;
　　}
　　cout<<endl;
　　}
　　
　　
　　///表的插入
　　void insert_Link(Lnode *&head)
　　{
　　int i;
　　cout<<"输入要插入的位置:";
　　
　　cin>>i;
　　Lnode *q,*iq;
　　q=head;
　　for(int j=1;j<i;j++)
　　{
　　iq=q;
　　q=q->next;
　　}
　　
　　cout<<"输入插入的数据:";
　　Lnode *p;
　　p=new Lnode;
　　cin>>p->data;
　　p->next=iq->next;
　　iq->next=p;
　　cout<<endl;
　　
　　}
　　
　　///表的数据删除
　　void Delete_Link(Lnode *&head)
　　{
　　cout<<"输入删除的位置:";
　　int i;
　　cin>>i;
　　if(i==1)
　　head=head->next;
　　else
　　{
　　Lnode *p,*q;
　　q=head;
　　for(int j=1;j<i;j++)
　　{ p=q;
　　q=q->next;
　　}
　　p->next=q->next;
　　delete q;
　　cout<<endl;
　　}
　　}
　　
　　
　　int main()
　　{
　　Lnode *head;
　　head=NULL;
　　creat_Link(head);
　　
　　insert_Link(head);
　　output_Link(head);
　　Delete_Link(head);
　　output_Link(head);
　　return 0;
　　}
　　[扩展]
　　以“结点的序列”表示线性表称作线性链表（单链表），链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
分享
本回答专业性由科学教育分类达人甄好斌认证
其他类似问题
2011-12-20单链表的建立插入删除查询1
2011-04-25编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本...15
2010-11-14单链表的建立插入删除1
2010-04-26用c++处理单链表创建，插入，删除等9
2007-11-291单链表的定义、创建、插入和删除操作，将数据元素显示出来。13
更多关于单链表的插入和删除的问题>>
为您推荐：

2008-10-25 21:30提问者采纳
#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct Node)
typedef struct Node
{
int data;
struct Node *next;
}node;
int n;
node *Creat(void)
{
int data;
node *head;
node * p1=(node*)malloc(LEN);
node * p2=(node*)malloc(LEN);
head=NULL;
n=0;
puts("Please input a num:");
scanf("%d",&p1->data);
while(p1->data!=0)
{
n++;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(node*)malloc(LEN);
scanf("%d",&p1->data);
}
free(p1);
p1=NULL;
p2->next=NULL;
return head;
}
void Print(node *head)
{
node *p;
p=head;
if(head==NULL)
{
printf("No Records?!");
return;
}
else
do
{
printf("%d-->",p->data);
p=p->next;
}while(p!=NULL);
printf("\n");
}
node* Insert(node *head)
{
int data;
node *p0=(node*)malloc(LEN),*p1,*p2;
p1=head;
if(head==NULL)
{
printf("No Records?!");
return NULL;
}
puts("Please input a num to insert:");
scanf("%d",&p0->data);
while(p1->data<p0->data&&p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p1->data>=p0->data)
{
if(p1==head)
head=p0;
else
p2->next=p0;
p0->next=p1;
}
else
printf("Not find!\n");
return head;
}
node *Delete(node *head)
{
node *p0,*p1,*p2,*p3;
p0=(node*)malloc(LEN);
if(head==NULL)
{
printf("No Reacord?!");
return NULL;
}
puts("Please input a num to delete:");
scanf("%d",&p0->data);
while(head->data==p0->data)
head=head->next;
p1=head;
if(head->next!=NULL)
do
{
p2=p1;
p1=p1->next;
while(p1!=NULL&&p1->data==p0->data)
{
p3=p1;
p1=p1->next;
free(p3);
}
p2->next=p1;
}while(p1!=NULL);
return head;
}
int main()
{
node *head;
head=Creat();
Print(head);
head=Insert(head);
Print(head);
head=Delete(head);
Print(head);
return 0;
}
Please input a num:
2 3 4 5 6 0
2-->3-->4-->5-->6-->
Please input a num to insert:
4
2-->3-->4-->4-->5-->6-->
Please input a num to delete:
5
2-->3-->4-->4-->6-->
Press any key to continue
VC6.0