c语言链表总结-单链表-详细备注版本

链表是学习数据结构的大门，在微软等大公司招聘c\c++技术人员的时候有3个会必然出现的东西，指针、链表、二叉树！在看一下内容时请确认您已经熟悉C语言的指针，否则请先复习指针的基础知识。以下以单链表为说明对象！我从一个初学者的角度来对链表进行说明：理论上的东西大家可以参考c语言数据结构一书，在此主要用一些例子来说明:看下面链表的基本形式：Structlink_c{Charname[20];Structlink_c*link;}可以看到这是一个结构体，结构体中有一个link_c的指针link。如图所示，head是链表的头指针，他指向链表的第一个节点，如果head为空则说明链表是空的。而节点中的link指向下一节点的首地址，如果link为空则代表此节点为这个链表的最后一个节点(非循环表，循环表的最后一个link指向head)。这里要注意的是Link要与他后面所指的节点的结构相同，所以其类型必须是link。下面我们创建一个简单的链表并且进行基本操作。〃定义链表的基础结构体Structstudent{Intnum;Structstudent*next;};〃创建一个只有头节点的空链表Structstudent*creat()//返回的是一个结构体指针{Structstudent*head;//定义并初始化头指针Head=(structstudent*)malloc(sizeof(structstudent));〃如果内存分配失败则返回空If(!head)//这种写法我也很不适应，但是比较规范{Returnnull;}//head头结点的指向的next为空，链表只有一个节点。Head->next=NULL;Returnhead;}以上建立了一个单节点的链表。接下来可以根据以上代码进行优化修改，创建一个多链接的链表创建有n个节点的链表Structstudent*creat(intn)//返回的是一个结构体{IntI;Structstudent*head,*p,*s;//定义并初始化头指针Head=(structstudent*)malloc(sizeof(structstudent));〃如果内存分配失败则返回空If(!headl){Returnnull;}P=head;For(i=0,i<n,i++){S=(structstudent*)malloc(sizeof(structstudent));If(!s){Returnnull;}p->next=s;s->next=NULL;p=s;//i+1后s的前驱节点就变成了上一循环的s也就是现在的p，，，此处有点绕}Returnhead;返回头节点指针}上面已经建立了一个比较简单的链表结构，下面进行一些链表的基本操作链表的查询操作Structstudent*search(structstudent*head,int*num)//head是头指针，num是要查找的数据{structstudent*p；〃定义一个节点指针int*m；//临时保存节点内的数据p=head->next;//头指针是不包含数据的，所以搜索的第一个节点是头指针指向的节点while(p!=NULL)//没有到最后一个节点{M=P->num;If(strcmp(num,m)==0)//strcmp应用可查csdn{Returnp;}Elsep=p->next;//如果判断不正确则指向下一个节点}If(p==NULL){〃没有找到数据，可以做消息弹出}}接下来是链表的插入操作，将s节点插入到p节点以前设结构体中的intnum是一个关键字，链表以这个关键字进行的排序Structstudent*instert(structstudent*s,structstudent*head)//s就是要插入的结构体*插入的节////点必须和原链表结构相同。{Structstudent*p,*q;If(!head)//如果头节点为空{Head=s;//s就是新的头节点s->next=NULL;returns;}P=head;Q=p;//q用来临时存储前驱节点While(p)//当p不为空时，这时的p=head{If(p->num<s->num)//如果关键码小于要插入的节点则指向下一节点{Q=pP=p->next;}ElseQ->next=s//这个需要认真的理解一下了，说明很难说明，可以参考上面的土s->next=preturnhead;〃当p为空时，没有找到q节点，所以s节点放到最后。Q->next=ss->next=NULLreturnhead;}链表的删除操作原理：理解链表的删除首先要明白函数malloc()与free()之间的关系。前者我们在创建或者插入一个节点的时候都用到，而后者则是删除的时候需要用到的。删除关键字为Key的节点Structstudent*del(intkey,structstudent*head){Structstudent*p,*q;〃如果表空If(!head)Return(0);〃如果头节点就是要删除的节点If(head->num==key)P=head;Head=head->next;Free(p);Returnhead;〃从头开始搜索遍历P=head;Q=p;If(p->num!=key){Q=p;//q始终保持为p的前驱节点p->next;}Else{q->next=p->next;//p节点的前驱节点Q指向p的nextfree(p)//释放Preturnhead;}Returnhead;}总结：上面从链表的各个方面进行了简