C-创建可增删查改的单向链表

链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针

比较简单的理解,就是生活中的链条。

下面是本篇文章用到的例子,方便大家理解。(图片来自 C 语言中文网)

图中,第0个结点称为头结点,它存放有第一个结点的首地址,它没有数据,只是一个指针变量。以下的每个结点都分为两个域,一个是数据域,存放各种实际的数据,如学号num,姓名name,性别sex和成绩score等。另一个域为指针域,存放下一结点的首地址。链表中的每一个结点都是同一种结构类型。

 

本篇将实现以下功能
1.链表的创建
2.链表的增删查改
3.链表的输出
4.main 函数对链表的调用

本文部分代码风格参考翁培钧学长的 blog,原文链接。本文在一些现成代码的基础上加上大部分注释方便理解。


首先看一下头文件引用和函数的声明
1

1.先从创建链表开始(需要注意的地方是返回 head)
2

2.增加链节
3

3.删除链节

// 2017.10.07修改


4

4.查找链节
5

5.修改链表
7

6.输出链表
8

//menu 函数为调试所用,大家可以忽略。
9

 

主函数的调用
main

 

本文涉及到的几个知识点总结:
1.文章多次使用 指针 = NULL 的写法,目的是为了防止产生野指针。
2.malloc()动态分配内存与 free()释放内存。

本文没有将源代码直接粘贴过来,目的是让大家可以自己亲手练习一遍,方便的话可以帮我挑挑错。:)

 


#include "stdio.h"
#include "stdlib.h" //malloc函数
typedef struct LinkList{
int data;
struct LinkList *next; //指向下一个链接的指针
}LinkList;LinkList *createLinkList(); //创建链表
void addLinkList(LinkList *head,int position); //增加链节(head,增加的位置)
void deleteLinkList(LinkList *head,int position);//删除链节(head,删除的位置)
void searchLinkList(LinkList *head,int position);//查找链节(hea——d,查看的位置)
void changeLinkList(LinkList *head,int position);//改变链节内容(head,修改的位置)
void outLinkList(LinkList *head); //输出整个链表(head)
void menu(); //为演示而写,可忽略.
int main()
{
LinkList *head; //接受 createLinkList()返回的head;
int n = 0;
int position;
menu(); //演示所写,可忽略
scanf("%d",&n);
printf("***********************\n");
while(n){
switch(n){
case 1:
head = createLinkList();
break;
case 2:
printf(" 请输入位置:\n");
scanf("%d",&position);
addLinkList(head,position);
break;
case 3:
printf(" 请输入位置:\n");
scanf("%d",&position);
deleteLinkList(head,position);
break;
case 4:
printf(" 请输入位置:\n");
scanf("%d",&position);
searchLinkList(head,position);
break;
case 5:
printf(" 请输入位置:\n");
scanf("%d",&position);
changeLinkList(head,position);
break;
case 6:
outLinkList(head);
break;
default:
break;
}
menu();
scanf("%d",&n);
printf("***********************\n");
}
return 0;
}
LinkList *createLinkList()
{
LinkList *head,*p,*next; //定义 LinkList型 head,p,next;
int isAdd = 1, data = 0; //isAdd 表示是否继续输入数据
head = (LinkList *)malloc(sizeof(LinkList)); //分配内存
if(head == NULL){ //如果上步发生错误直接停止程序。
printf(“内存分配失败!\n”);
return NULL; //返回指针类型,所以是NULL 空
}
head->next = NULL; //置空,防止乱指
p = head;
while(isAdd){
printf(“请输入数据(输入0结束):\n”);
scanf(“%d”,&data);
if (data != 0)
{
next = (LinkList *)malloc(sizeof(LinkList));
if (next == NULL)
{
printf(” 内存分配失败!\n”);
return NULL;
}
next->data = data; //赋值
p->next = next; //上一个链节的 next 指向此链节
p = next; // 此代码实现链条的衔接
}else{
isAdd = 0;
}
}
p->next = NULL; //最后一个链节的next置空
return head; //返回 head 头结点,供其他函数
}void addLinkList(LinkList *head,int position)
{
LinkList *p,*tmpNode; //tmpNode 为要插入的链节
int data = 0;
int i = 0; //一定初始化为0,通过 i 与position 比较找出对应链节
p = head;
while(p != NULL){ //当前链接不为空
if (i == position – 1) //目的为了获取加入位置的前一个链节
{
tmpNode = (LinkList *)malloc(sizeof(LinkList));
if (tmpNode == NULL)
{
printf(“内存分配失败!\n”);
return ;
}
printf(“请输入要插入的数据:\n”);
scanf(“%d”,&data);
tmpNode->data = data; //赋值
tmpNode->next = p->next;//新链节连接原 position 位置的链节
p->next = tmpNode; //前一链节连接新链节
break; //连接完毕,跳出循环,结束
}else{
i++;
p = p->next; //使链节往下传递
}
}
}void deleteLinkList(LinkList *head,int position)
{
LinkList *p;
int i = 0;
p = head;
while(p != NULL){
if (i == position – 1)
{
p->next = p->next->next; //前一节点连接后一节点
free(p->next); //释放要删除的链节
p->next = NULL; //置空,防止产生野指针
break;
}else{
i++;
p = p->next;
}
}
}void searchLinkList(LinkList *head,int position)
{
LinkList *p;
int i = 0;
p = head;
while(p != NULL){
if (i == position) //区分上部分函数的 position – 1;
{
printf(“当前链节包含的数据为:%d”,p->data);
break;
}else{
i++;
p = p->next;
}
}
}void changeLinkList(LinkList *head,int position)
{
LinkList *p;
int i = 0;
p = head;
while(p != NULL){
if (i == position)
{
printf(“输入新的数据:\n”);
scanf(“%d”,&p->data); //p->data是int类型,所以需要加取地址符
break;
}else{
i++;
p = p->next;
}
}
}void outLinkList(LinkList *head)
{
LinkList *p;
p = head->next; //头结点是空的,仅仅是哨兵的作用,所以直接从第二个链节的数据开始
while(p != NULL){
printf(“%d\n”,p->data);
p = p->next; //使链表连续
}
}
//调试用,可忽略
void menu()
{
printf(” 请输入序号选择功能:\n”);
printf(“\t1.创建链表\n”);
printf(“\t2.增加链节\n”);
printf(“\t3.删除链节\n”);
printf(“\t4.查找链节\n”);
printf(“\t5.更改链节\n”);
printf(“\t6.输出链节\n”);
printf(“\t0.退出\n”);
printf(“*******************\n”);
}