最近复习了一下链表,原来学过但是有些地方还是不太清楚。于是借着这次月考核的机会好好复习了一下链表。
首先链表的每个节点有两个部分,前面存储数据,后面存储下一个节点的地址。因此链表的存储空间可以不是连续的。
采用结构体构建一个链表节点。
typedef struct Node{
char data;
struct Node * next;
}Node, * LinkList;
构建链表时,采用有头结点的方式建立链表。链表的初始化:
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
*:这里说明一下传的参数问题,因为初始化是要改变头结点的内容,因此采用传指针的方式。而这里我们定义的LinkList本身就是指针,因此在主函数中调用是需要取地址操作的。
头插法建立链表:
void CreateFromHead(LinkList L)
{
Node *s;
char c;
int flag = 1;
while(flag)
{
c = getchar();
if(c!='$')
{
s = ( Node *)malloc(sizeof(Node));
s->data = https://www.it610.com/article/c;
s->next = L->next;
L->next = s;
}
else
flag = 0;
}
}
头插法的原理是,把每一个新的节点都当成首元素节点插入链表中,因此最先插入的节点反而到了最后面,也就是链表中的数据和输入的数据顺序相反。
尾插法建立链表:
void CreateFromTail(LinkList L)
{
Node *r,*s;
char c;
int flag = 1;
r = L;
while(flag)
{
c = getchar();
if(c!='$')
{
s = (Node *)malloc(sizeof(Node));
s->data = https://www.it610.com/article/c;
r->next = s;
r = s;
}
else
{
flag = 0;
r->next = NULL;
}
}
}
尾插法建立链表的原理是,多定义一个指针r始终指向链表的最后一个节点。将新的节点首先连接在r后面,然后再将r指针修改为指向新增指针,即实现r指针永远指向为节点。
在指定位置插入数据到链表内部:
int Insert(LinkList L,int i,char *e)
{
Node *pre,*s;
char E;
int k = 0;
E = *e;
if(i<=0)
return 0;
pre = L;
while(pre!=NULL&&knext;
k = k+1;
}
if(pre==NULL)
return 0;
s = (Node *)malloc(sizeof(Node));
s->data = https://www.it610.com/article/E;
s->next = pre->next;
pre->next = s;
return 1;
}
这里插入时要找到的插入位置的前面一个节点,所以循环的终止条件是 k < i-1。找到之后第i-1个节点之后,插入第i+1个节点的地址给新节点,再将新节点的地址给第 i-1 个节点的指针域。这两者之间的顺序不可颠倒,否则会造成数据丢失。
删除指定位置的节点:
int Del(LinkList L,int i,char *e)
{
Node *pre,*s;
int k = 0;
pre = L;
while(pre->next&&knext ;
k = k+1;
}
if(pre->next == NULL)
{
printf("删除节点的位置不合理!");
return 0;
}
//s = (Node *)malloc(sizeof(Node));
s = pre->next;
pre->next = s->next;
*e = s->data;
free(s);
return 1;
}
删除节点的原理与插入节点的原理很像。用样是先寻找到指定位置的节点的前一个节点,然后不同夫人得是,将目标节点给一个新定义的指针,然后将第i+1 个节点给第 i-1 个节点即可,这样就删除了第 i 个节点。再将被删除的节点所占的空间释放。
按位置查找链表中的元素:
char CheckByLocate(LinkList L,int i)
{
Node *pre,*s;
pre = L;
int k;
while(pre->next&&knext;
k++;
}
if(k==i)
{
return pre->data;
}
else
return NULL;
}
按给定值查找链表中的节点 :
int CheckByValue(LinkList L,char e)
{
Node *pre,*s;
pre = L;
int k=0;
while(pre->next)
{
if(pre->data!=e)
{
pre = pre->next;
k++;
}
else
{
return k;
}
}
return 0;
}
完整的代码:
【c语言|C语言建立链表以及增删改查】
#include
#includetypedef struct Node{
char data;
struct Node * next;
}Node, * LinkList;
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}void CreateFromHead(LinkList L)
{
Node *s;
char c;
int flag = 1;
while(flag)
{
c = getchar();
if(c!='$')
{
s = ( Node *)malloc(sizeof(Node));
s->data = https://www.it610.com/article/c;
s->next = L->next;
L->next = s;
}
else
flag = 0;
}
}void CreateFromTail(LinkList L)
{
Node *r,*s;
char c;
int flag = 1;
r = L;
while(flag)
{
c = getchar();
if(c!='$')
{
s = (Node *)malloc(sizeof(Node));
s->data = https://www.it610.com/article/c;
r->next = s;
r = s;
}
else
{
flag = 0;
r->next = NULL;
}
}
}int Insert(LinkList L,int i,char *e)
{
Node *pre,*s;
char E;
int k = 0;
E = *e;
if(i<=0)
return 0;
pre = L;
while(pre!=NULL&&knext;
k = k+1;
}
if(pre==NULL)
return 0;
s = (Node *)malloc(sizeof(Node));
s->data = https://www.it610.com/article/E;
s->next = pre->next;
pre->next = s;
return 1;
}int Del(LinkList L,int i,char *e)
{
Node *pre,*s;
int k = 0;
pre = L;
while(pre->next&&knext ;
k = k+1;
}
if(pre->next == NULL)
{
printf("删除节点的位置不合理!");
return 0;
}
//s = (Node *)malloc(sizeof(Node));
s = pre->next;
pre->next = s->next;
*e = s->data;
free(s);
return 1;
}char CheckByLocate(LinkList L,int i)
{
Node *pre,*s;
pre = L;
int k;
while(pre->next&&knext;
k++;
}
if(k==i)
{
return pre->data;
}
else
return NULL;
}int CheckByValue(LinkList L,char e)
{
Node *pre,*s;
pre = L;
int k=0;
while(pre->next)
{
if(pre->data!=e)
{
pre = pre->next;
k++;
}
else
{
return k;
}
}
return 0;
}void PrintList(LinkList L)
{
Node *p;
p = L->next;
while(p)
{
printf("->%c",p->data);
p = p->next;
}
}int main(){
LinkList H;
int i = 2;
char e = 'z';
InitList(&H);
//CreateFromHead(H);
CreateFromTail(H);
//Insert(H,i,&e);
i = 1;
//Del(H,i,&e);
//e = CheckByLocate(H,i);
//printf("%c\n",e);
i = CheckByValue(H,e);
printf("%d\n",i);
PrintList(H);
return 0;
}
推荐阅读
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 【C】题目|【C语言】题集 of ⑥
- 单片机|自学单片机好找工作吗(会单片机能找什么工作?)
- 单片机|keil把源代码生成lib的方法
- c语言|一文搞懂栈(stack)、堆(heap)、单片机裸机内存管理malloc
- c语言|C语言初期学习遇到的特殊点 【三子棋详解】【初学者福音,详细总结,复习能手】
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历