兔子不恰胡萝卜
2022-03-16 21:51
采纳率: 85.7%
浏览 114

数据结构——链表,不带头结点的头插法和尾插法

我想知道不带头结点的头插法和不带头结点的尾插法错在哪里,以及main函数部分有没有错,再者就是整体还能不能优化(前面两个是最主要的问题)

(注释是听网课记下的,不知道对了没有,帮忙看一下)

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

//单链表结构体
//->是箭头
typedef int ElemType;
typedef struct node //node是结点的意思
{
ElemType data;
struct node* next;//next指向结点本身
}LNode, * LinkList;

//头插入法:带头结点(输入数据与输出数据相反)

void CreLinkListHead(LinkList L, int n)
{
LNode* s;//等价于LinkList s
ElemType x;
int i;
printf("头插法--输入结点:\n");
for (i = n; i > 0; i--)
{
scanf_s("%d", &x);//从键盘输入结点x的值
s = (LNode*)malloc(sizeof(LNode));//生成一个s结点
s->data = x;//数据域
s->next = L->next;//s的指针域指向下一个结点L的地址编号
L->next = s;
}
}

//输出链表信息

void OutPut(LinkList L)
{
LNode* p;
p = L->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

//尾部插入法:带头结点(输入数据与输出数据相同)

void CreLinkListTail(LinkList L, int n)
{
LNode* s, * r;//r结点
ElemType x;
int i;
r = L;//r结点的初始化,首先指向链表L
printf("尾插法--输入结点:\n");
for (i = n; i > 0; i--)
{
scanf_s("%d", &x);
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
//上面三条语句和头部插入法相同
r->next = s;//r的下一个结点是s
r = s;//r指向s
}
if (r != NULL)//r后没有结点
{
r->next = NULL;
}
}

//尾部插入法:不带头结点(输入数据与输出数据相同)

LNode* CreLinkListTailNo(int n)
{
LNode* s, * r;//r结点
LinkList L = NULL;
r = L;//r结点的初始化,首先指向链表L
ElemType x;
int i;
printf("输入结点:\n");
for (i = n; i > 0; i--)
{
scanf_s("%d", &x);
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
if (L == NULL)//链表的第一个结点的处理
{
L = s;
r = s;
continue;
}
r->next = s;//r的下一个结点是s
r = s;//r指向s
}
if (r != NULL)//r后没有结点
{
r->next = NULL;
}
return L;
}

//头插入法:不带头结点(输入数据与输出数据相反)

LNode* CreLinkListNo(int n)
{
LinkList L = NULL;
LNode* s;//等价于LinkList s
ElemType x;
int i;
printf("输入结点:\n");
for (i = n; i > 0; i--)
{
scanf_s("%d", &x);//从键盘输入结点x的值
s = (LNode*)malloc(sizeof(LNode));//生成一个s结点
s->data = x;//数据域
s->next = L;//s的指针域指向下一个结点L的地址编号
L = s;
}
}

//单链表插入操作:第i个位置插入s结点

int InsertList(LinkList L, int i, ElemType x)//x为数据域
{
LNode* p, * s;
int j = 0;
p = L;//p指向L的头
while (p->next != NULL && j < i)//p结点的下一个结点不能为空
{
p = p->next;//p指向p的下个结点
j++;
}
if (p == NULL)//链表的末尾
{
printf("插入位置i不合理!");
return 0;
}
else
{
s = (LNode*)malloc(sizeof(LNode));
s->data = x;//s的数据域
s->next = p->next;//s指向下一个结点,p当前所指向结点的下一个
p->next = s;//p的下一个结点等于s
return 1;
}
}

//单链表删除操作:删除第i个结点(s是要删除的结点)

int DeleteList(LinkList L, int i)
{
LNode* p, * s;
int j = 0;
p = L;//p从L开始
while (p->next != NULL && j < i)
{
p = p->next;
j++;
}
if (p == NULL)
{
printf("删除位置不合理!");
return 0;
}
else
{
s = p->next;//s所指向的结点是p的下个结点
p->next = s->next;//等价于p->next=p->next->next
free(s);//在内存里释放掉s所指向结点的空间
return 1;
}
}

void main()
{
int n;//n个结点
printf("请在键盘中输入链表有几个结点:\n");
scanf_s("%d", &n);//输入n个结点

//带头结点
//LinkList L = (LinkList)malloc(sizeof(LNode));//空链表的创建
//L->next = NULL;//指针域为空
//
//不带头结点尾插法建立单链表L
//LinkList L = CreLinkListTailNo(n);
//printf("不带头结点尾插法--输出建立后的单链表:\n");
//OutPut(L); //输出建立后的单链表
//
//不带头结点头插法建立单链表L
LinkList L = CreLinkListNo(n);
printf("不带头结点头插法--输出建立后的单链表:\n");
OutPut(L); //输出建立后的单链表
//

//CreLinkListTail(L, n);//尾插入法建立单链表L
//printf("尾插法--输出建立后的单链表:\n");
//OutPut(L); //输出建立后的单链表

//CreLinkListHead(L, n);//头插法建立单链表L
//printf("头插法--输出建立后的单链表:\n");
//OutPut(L);//输出建立后的单链表

//DeleteList(L, 3);//删除第3个位置的元素
//printf("输出删除后的单链表:\n");
//OutPut(L);//输出删除成功后的单链表

//InsertList(L, 3, 100);//在第3个位置插入一个数据元素100
//printf("输出插入后的单链表:\n");
//OutPut(L);//输出插入成功后的单链表

}

2条回答 默认 最新

相关推荐 更多相似问题