C语言数据结构之单向链表详解

第C语言数据结构之单向链表详解目录链表静态链表动态链表定义链表节点创建链表创建一个空节点尾插法头插法指定位置插入一个结点遍历链表获取链表长度链表搜索链表数据排序反转链表删除节点数据销毁链表测试

链表

链表实现了，内存零碎数据的有效组织。比如，当我们用malloc来进行内存申请的时候，当内存足够，但是由于碎片太多，没有连续内存时，只能以申请失败而告终，而用链表这种数据结构来组织数据，就可以解决上类问题。

静态链表

#includestdio.h

//1.定义链表节点

typedefstructnode{

intdata;

structnode*next;

}Node;

intmain(intargc,char*argv[]){

//2.创建链表节点

Nodea;

Nodeb;

Nodec;

//3.初始化节点数据

a.data=1;

b.data=3;

c.data=5;

//4.链接节点

a.next=

b.next=

c.next=NULL;

//5.创建链表头

Node*head=

//6.使用链表

while(head!=NULL){

intcurrentData=head-data;

printf("currentData=%i\n",currentData);

head=head-next;//指向下一个节点

return0;

}

动态链表

静态链表的意义不是很大，主要原因，数据存储在栈上，栈的存储空间有限，不能动态分配。所以链表要实现存储的自由，要动态的申请堆里的空间。

有头链表

无头链表

单向链表有有头节点和无头节点两种列表,有头节点在列表的删除,反转,插入等操作会比无头节点简单,但是不好之处就是多占用些空间,而且在多个链表结合处理的时候有头链表每次都需要过滤头节点,而无头链表直接完美融合,而且很多高级语言都是无头链表的便于日后的扩展,下面都是依据无头节点进行演示

定义链表节点

//1.定义链表节点

typedefstructnode{

void*data;

structnode*next;

}Node;

创建链表

/**

*创建链表

Node*createList(){

//1.创建头节点

Node*root=(Node*)malloc(sizeof(Node));

root-data=NULL;

root-next=NULL;

//返回头节点

returnroot;

创建一个空节点

/**

*创建一个空节点

Node*createNode(){

Node*node=(Node*)malloc(sizeof(Node));

node-data=NULL;

node-next=NULL;

returnnode;

}

尾插法

/**

*@briefinsertEndNode尾插法插入节点

*@paramhead需要插入的头指针

*@paramdata需要插入的数据

voidinsertEndNode(Node*node,void*data){

Node*head=node;

//找到数据为空的节点,没有节点那么就扩展

while(head-data!=NULL){

//扩容

if(head-next==NULL){

Node*pNode=createNode();

head-next=pNode;

head=pNode;

break;

head=head-next;

//插入数据

head-data=data;

}

头插法

/**

*@briefinsertHeadNode头插法插入节点

*@paramhead需要插入的头指针

*@paramdata需要插入的数据

voidinsertHeadNode(Node**node,void*data){

Node*pNode=createNode();

pNode-data=data;

pNode-next=*node;

*node=pNode;

指定位置插入一个结点

简单来说就是先找到需要插入的位置,然后将当前位置节点和他前一个节点连接到需要插入的节点就行了

/**

*@briefinsertNOde将数据节点插入到指定数据位置节点,指定数据节点向后移动,如果没有找到插入的位置,那么就插入到最后

*@paraminsertionPoint指定的数据节点

*@paramdata需要插入的数据

voidinsertNode(Node*node,void*insertionPoint,void*data){

Node*pNode=node;

Node*pre=pNode;//父节点

while(pNode!=NULL){

if(pNode-data==insertionPoint){

break;

pre=pNode;//保留当前节点

pNode=pNode-next;

//如果没有找到那么就插入到最后

if(pNode==NULL){

insertEndNode(node,data);

return;

Node*dataNode=createNode();

dataNode-data=data;

pre-next=dataNode;

dataNode-next=pNode;

}

遍历链表

因为我们值存储是使用无类型的指针,所以需要转换为插入时候的类型才行

/**

*@briefprintNodeListDouble遍历链表

*@paramnode链表指针头

voidprintNodeListDouble(Node*node){

Node*head=node;

while(head!=NULLhead-data!=NULL){

double*currentData=head-data;

printf("currentData=%f\n",*currentData);

head=head-next;

获取链表长度

/**

*@brieflistLength计算链表长度

*@paramhead链表头指针

*@return链表长度

intlistLength(Node*head){

intcount=0;

head=head;

while(head){

count++;

head=head-next;

returncount;

链表搜索

/**

*@briefsearchList查找指定节点

*@paramhead链表头指针

*@paramkey需要查找的值

*@return

Node*searchList(Node*head,void*key){

head=head;

while(head){

if(head-data==key){

break;

}else{

head=head-next;

returnhead;

}

链表数据排序

因为我们存储数据类型是使用无类型的指针,那么在排序的时候需要转换为指定类型才行

/**

*@briefbubbleSort对链表值进行排序小到大

*@paramhead链表头指针

voidsortDouble(Node*head){

//1.计算链表长度

intlen=listLength(head);

//2.定义变量记录前后节点

Node*cur=head;

while(cur!=NULL){

Node*cur1=cur-next;

while(cur1!=NULL){

//比较大小,然后交换数据

if(*((double*)cur-data)*((double*)cur1-data)){

double*temp=(double*)cur-data;

cur-data=cur1-data;

cur1-data=temp;

cur1=cur1-next;

cur=cur-next;

}

反转链表

断开链表头，然后以头插法的方式将原链表的数据添加链表。

/**

*@briefreverseList反转链表

*@paramhead链表头指针

voidreverseList(Node**root){

Node*head=*root;

Node*pre=head,*cur=head-next;

pre-next=NULL;

while(cur!=NULL){

Node*node=cur-next;

cur-next=pre;

pre=cur;

cur=node;

*root=pre;

}

删除节点数据

先找到需要删除的节点,之后将后一个结点赋值给前一个结点的next,然后将删除位置的结点释放即可

/**

*@briefdelNode删除指定节点

voiddelNode(Node**root,void*key){

Node*head=*root;

//根节点单独处理

if(head-data==keyhead-next!=NULL){

*root=head-next;

free(head-data);

free(head);

return;

Node*head1=head-next;

Node*pre=head;//根节点

while(head1!=NULL){

if(head1-data==key){

pre-next=head1-next;

free(head1-data);

free(head1);

break;

pre=head1;//当前节点

head1=head1-next;//下一个节点

}

销毁链表

/**

*@bri