#include <stdio.h>
#include <stdlib.h>
typedef int dataType;
// 不带头结点的单链表
typedef struct linkNode
{
dataType data;
struct linkNode *next;
}node,*linkList;
// 1.初始化不带头结点的单链表
void init(linkList *list)
{
*list = NULL; // 表示链表指针指向空处
}
// 2.输出单链表元素
void display(linkList list)
{
node *p = list; // p为工作指针,初值为第一个结点
if(!p)
{
printf("链表为空!\n");
return;
}
while (p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
// 3.查找单链表中的第i个元素
node *find(linkList list, int i)
{
if(i < 1) return NULL;
int j = 1;
node *p = list;
while (p && j!=i)
{
p = p->next;
j++;
}
return p;
}
// 4.在单链表尾部插入元素
void rearInsert(linkList *list, dataType x)
{
node *p = *list,*q; // p初值为当前链表指针指向的位置
q = (node*)malloc(sizeof(node)); // 创建新节点
q->data = x;
q->next = NULL; // 新节点的指针域置空
if(!p) *list = q; // 如果当前链表为空
else
{
while (p->next) // 找到最后一个结点
p = p->next;
p->next = q;
}
}
// 5.在单链表第i个位置后插入元素
void insert(linkList *list,int i,dataType x)
{
node *p = *list,*q; // p初值为当前链表指针指向的位置
q = (node*)malloc(sizeof(node)); // 创建新节点
q->data = x;
p = find(p,i); // 找到第i个结点
if(!p)
{
if(i == 0) // 如果是在第1个元素前插入
{
q->next = *list; // 若在链表前插入,则把链表挂在新结点后
*list = q; // 更新链表指针的的地址,让它指向q
}
else
{
printf("位置不存在,无法插入元素!\n");
exit(1);
}
}
else
{
q->next = p->next; // 把p结点后的结点挂在q结点后
p->next = q; // 把新结点插入p结点后
}
}
// 6.删除一个值为x的结点
void del(linkList *head, dataType x)
{
node *p = *head,*pre = NULL; // p为工作指针,q为前驱指针
if(!*head) // 1.链表为空时
{
printf("链表为空,无法删除!\n");
exit(1); // 遇到错误终止程序
}
while (p && p->data != x) // 寻找x结点
{
pre = p;
p = p->next;
}
if(p) // 找到x结点
{
if(!pre) // 如果要删除的是第一个结点
*head = p->next;
else pre->next = p->next;
free(p);
} else printf("未找到结点%d\n",x);
}
// 7.删除倒数第m个元素
void delM(linkList *list, int m)
{
// p为链表的工作指针,pre为p的前驱指针,q指向待删结点
node *p = *list, *pre = NULL, *q;
if(!p)
{
printf("单链表为空,无法删除!\n");
return;
}
int n = 0, i, j = 1; // n为链表个数,i、j为链表位序
while (p) // 统计链表结点个数
{
n++;
p = p->next;
}
i = n-m+1; // 删除的是第i个结点
if(i < 1 || i > n)
{
printf("不存在该结点,无法删除!\n");
return;
}
p = *list; // 重置p指针指回首结点
while (p->next && j < i) // 寻找要删除的结点
{
j++;
pre = p;
p = p->next;
}
q = p; // q指向待删结点
if(!pre) // 删除的是首结点
*list = p->next;
else
pre->next = p->next;
free(q);
}
int main()
{
linkList list; // 声明一个指向链表的指针
init(&list); // 初始化链表
display(list);
for (int i = 1; i <= 10; i++) // 循环插入值
rearInsert(&list,i);
display(list); // 输出链表
int i = 1;
node *n = find(list,i); // 查找第i个元素
if(n) printf("链表的第%d个元素是%d\n",i,n->data);
else printf("链表访问越界!\n");
dataType x = 5;
printf("在第%d个位置后面插入元素%d\n",i,x);
insert(&list,i,x);
display(list); // 输出链表
printf("删除一个值为%d的元素\n",x);
del(&list,x);
display(list); // 输出链表
printf("删除倒数第%d个元素\n",5);
delM(&list,5);
display(list); // 输出链表
return 0;
}
版权属于:
lixiangrong
作品采用:
《
署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
》许可协议授权
评论 (0)