Question

数据结构（C语言版）中的删除链表中的一个节点

下面是老师发的作业，有谁能帮我做下啊~~要删除链表中的一个节点，在这个程序里面再编译一个程序，实现上述功能~~谢谢！！

****************************************************************
//---------------------------包含头文件

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h> //利用malloc动态分配内时要用到的头文件

//---------利用typedef定义数据类型------

typedef int DataType;

//int a;与DataType a;等价

//--------------定义结构体--------------

typedef struct Lnode
{

int a;
struct Lnode *next;

}Lnode,*LinkList;

//---------函数的声明-------------------

void create(LinkList *L); //创建链表

void ListInitiate(LinkList head,int count);
void ListInitiate1(LinkList head,int count);
void Print(LinkList head);
int ListLength(LinkList head);

//-------主函数部分----------------------
void main()
{
LinkList L;
int cou;
create(&L);
printf("请输入你要创建结点的个数: ");
scanf("%d",&cou);

ListInitiate1(L,cou); //函数的调用
Print(L);
printf("\n链表的长度为: %d",ListLength(L));

}

//-------函数部分-----------------------------

void create(LinkList *L)//创建链表
{
if((*L=(LinkList)malloc(sizeof(Lnode)))==NULL)exit(1);
(*L)->next = NULL;
}

void ListInitiate(LinkList head,int count) //比较这两个函数初始化的链表有什么不同.
{
LinkList p;
int i;
for(i=0;i<count;i++)
{
if((p=(LinkList)malloc(sizeof(Lnode)))==NULL)exit(1);
printf("请输入第%d个结点的值: ",i+1);
scanf("%d",&p->a);
p->next=head->next;
head->next=p;
}
printf("链表初始化成功");
}

void ListInitiate1(LinkList head,int count) //比较这两个函数初始化的链表有什么不同.
{
LinkList p,q=head;
int i;
for(i=0;i<count;i++)
{
if((p=(LinkList)malloc(sizeof(Lnode)))==NULL)exit(1);
printf("请输入第%d个结点的值: ",i+1);
scanf("%d",&p->a);
q->next =p;
q=p;
}
p->next = NULL; //思考为什么这里一定要加句.而上一个不用加?

}
void Print(LinkList head)//在屏幕上打印出链表的内容.
{
LinkList p = head->next;
printf("你的链表为:\n");
while(p)
{
printf("%d → ",p->a);
p=p->next;
}
printf("NULL");
}

int ListLength(LinkList head)//求链表的长度
{

int size=0;
while(head ->next)
{
size++;
head = head->next;
}
return size;
}

Answer 1

代码如下：

#include <stdio.h>

#include <stdlib.h>

typedef struct List

{

int a;

List* next;

}list;

void newList(list* l)//创建结点

{

list* a[4];

for (int i = 0; i < 4; i++)

{

a[i] = (list*)malloc(sizeof(list));

a[i]->a = i+1 ;

}

l->next = a[0];

a[0]->next = a[1];

a[1]->next = a[2];

a[2]->next = a[3];

a[3]->next = NULL;

}

void printfList(list* l)//打印结点的数据内容

{

printf("该链表的内容是：\n");

while (l->next)

{

printf("%d\t", l->next->a);

l = l->next;

}

printf("\n");

}

void setList(list* l,int x,int y)

{

list* head = l;

l = l->next;

while (l)

{

if (l->a >=y || l->a <=x)//将结点的数据区与指定区域进行比较

{ 

head->next = l;//将满足条件的结点连接在新表的最后一个结点

//指针后移

l = l->next;

head = head->next;

}

else

{

//不满足的结点进行删除

list* l1 = l;

l = l->next;

free(l1);

}

}

head->next = NULL;

}

int main()

{

list* l = (list*)malloc(sizeof(List));

newList(l);//初始化链表

printfList(l);//输出旧表内容

setList(l,1,3);//进行修改

printfList(l);//输出修改后的链表

//system("pause");

return 0;

}

扩展资料

链表的特点

1、插入、删除数据效率高，时间复杂度为O(1)级别（只需更改指针指向即可），随机访问效率低，时间复杂度O(n)级别（需要从链头至链尾进行遍历）。

2、和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

常用的链表类型

1、单链表

1）每个节点只包含一个指针，即后继指针。

2）单链表有两个特殊的节点，即首节点和尾节点。用首节点地址表示整条链表，尾节点的后继指针指向空地址null。

3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

2、循环链表

1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。

2）适用于存储有循环特点的数据，比如约瑟夫问题。

3、双向链表

1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。

2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。

Answer 2

temp=p;
p=p->next;
temp->next=NULL;
这三句存在问题，temp=p,让temp指向p所指向的节点,p=p->next，p指向后移
temp->next=NULL,让temp的后继为空，这里出了问题，链表从temp指向的节点断开,相当于删除p之后的所有节点。

应该先判断p是不是最后节点
if(p->next==NULL)
如果是，只好去找p的前趋pre，让pre->next=NULL,free(p)
如果不是最后节点，将p的后继节点数值域复制给p，然后将p的后继节点删除,等同与删除p
p->data=p->next->data;
p->next=p->next->next;
free(p);

Answer 3

//---------函数的声明-------------------

void delnode(LinkList *head, LinkList p); //删除节点

//-------函数部分-----------------------------

void delnode(LinkList *head, LinkList p) //删除节点
{
if(*head==NULL ||p==NULL) return;
if(p==*head)
{
*head = (*head)->next;
delete p;
p=NULL;
return;
}
while((*head)->next !=p && (*head)->next);
if(!(*head)->next) return;
else
{
(*head)->next = (*head)->next->next;
delete p;
p=NULL;
}
}

//-------主函数部分----------------------
void main()
{
...
LinkList p=L;
*p = (*p)->next;
delnode(&L, p);
...
}

Answer 4

//-------回答者：dingpwen忘记释放malloc申请的内存空间了。 －－－－
//---------函数的声明-------------------
void delnode(LinkList head,int index);
//index为要删除节点在链表中的位置

//-------函数部分-----------------------------
void delnode(LinkList head,int index)
{
LinkList p,q;
int count=0;
p=head;
q=head;

if(index==0)
{
p=p->next;
free(q);
}

while(p->next)
{
if(count++==index)
{
q->next=p->next;
free(p);
break;
}
size++;
q=p;
p= p->next;
}
return count;
}

void main()
{
int count;
//..前面创建链表的代码....
printf("请输入想删除节点在链表中的位置: ");
scanf("%d",count);
delnode(L,count);
//..其它代码....
}

Answer 5

//结点删除函数在最后

//---------------------------包含头文件

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h> //利用malloc动态分配内时要用到的头文件

//---------利用typedef定义数据类型------

typedef int DataType;

//int a;与DataType a;等价

//--------------定义结构体--------------

typedef struct Lnode
{

int a;
struct Lnode *next;

}Lnode,*LinkList;

//---------函数的声明-------------------

void create(LinkList *L); //创建链表

void ListInitiate(LinkList head,int count);
void ListInitiate1(LinkList head,int count);
void Print(LinkList head);
int ListLength(LinkList head);
bool ListDelete(LinkList L, int i, DataType *e); //删除第i个结点,将删除的结点返回在e中

//-------主函数部分----------------------
int main()
{
LinkList L;
int cou;
create(&L);
printf("请输入你要创建结点的个数: ");
scanf("%d",&cou);

ListInitiate1(L,cou); //函数的调用
Print(L);
printf("\n链表的长度为: %d\n",ListLength(L));
int i;
DataType e;
printf("\n请输入你要删除的结点的序号:");
scanf("%d", &i);
if(ListDelete(L, i, &e)){
printf("删除成功\n");
}else {
printf("删除失败\n");
}
Print(L);
return 0;
}

//-------函数部分-----------------------------

void create(LinkList *L)//创建链表
{
if((*L=(LinkList)malloc(sizeof(Lnode)))==NULL)exit(1);
(*L)->next = NULL;
}

void ListInitiate(LinkList head,int count) //比较这两个函数初始化的链表有什么不同.
{
LinkList p;
int i;
for(i=0;i<count;i++)
{
if((p=(LinkList)malloc(sizeof(Lnode)))==NULL)exit(1);
printf("请输入第%d个结点的值: ",i+1);
scanf("%d",&p->a);
p->next=head->next;
head->next=p;
}
printf("链表初始化成功");
}

void ListInitiate1(LinkList head,int count) //比较这两个函数初始化的链表有什么不同.
{
LinkList p,q=head;
int i;
for(i=0;i<count;i++)
{
if((p=(LinkList)malloc(sizeof(Lnode)))==NULL)exit(1);
printf("请输入第%d个结点的值: ",i+1);
scanf("%d",&p->a);
q->next =p;
q=p;
}
p->next = NULL; //思考为什么这里一定要加句.而上一个不用加?

}
void Print(LinkList head)//在屏幕上打印出链表的内容.
{
LinkList p = head->next;
printf("你的链表为:\n");
while(p)
{
printf("%d → ",p->a);
p=p->next;
}
printf("NULL");
}

int ListLength(LinkList head)//求链表的长度
{

int size=0;
while(head ->next)
{
size++;
head = head->next;
}
return size;
}

bool ListDelete(LinkList L, int i, DataType *e){
//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
int j;
LinkList p, q;
p = L; j = 0;
while(p->next&&j<i-1){ //寻找第i个结点,并令p指向其前趋
p = p->next;
++j;
}
if(!(p->next)||j>i-1){
printf("你所删除的结点不存在!\n");
return false;
}
q = p->next;
p->next = q->next;
*e = q->a;
free(q); //释放结点
return true;
}//ListDelete