首页 > 代码库 > 算法2---链表1---链表简单的实现
算法2---链表1---链表简单的实现
1 链表的基本知识
1.1 基本定义及优缺点
链表中各个对象按照顺序排列，注意到和数组的区别，数组的线性顺序是由数组下标决定的，但是链表的顺序是由各个对象里的指针决定的。
链表包含两个方面：1 数据部分，保存的是节点的实际数据；2 地址部分，保存的是下一个节点的地址（单链表）。
那么链表的优缺点
优点：方便理解，操作方便；
缺点：1在插入和删除操作的时候，往往需要移动大量的数据；2如果表比较大，有时候会难以分配足够的连续空间，导致内存分配失败，而无法存储；
1.2 分类
单链表：每个节点中只包含一个指针；
双向链表：每个节点包含两个指针，一个指向下一个节点，一个指向上一个节点；
单循环链表：在单链表中，将终端节点的指针域NULL改为指向表头节点或开始节点的就构成单循环链表。
双循环链表：首节点的指向上一个节点的指针指向链表尾节点，尾节点指向下一个节点的指针指向表头及诶到哪构成双循环链表；
2 链表的实现C语言版本
2.1 简单的实现
首先我们不考虑各种适应性，首先就固定data的形式；
包含两个文件夹list_simple.h,list_simple.c
list_simple.h
#ifndef _list_simple_Htypedef struct{ char key[10]; char name[20]; int age;}Data;typedef struct Node{ Data nodeData; struct Node *nextNode;}CLType;CLType *CLAddEnd (CLType *head,Data nodeData);CLType *CLAddFirst(CLType *head,Data nodeData);CLType *CLFindNode(CLType *head,char *key);CLType *CLinsertNode(CLType *head,char *findkey,Data nodeData);int CLDeleteNode(CLType *head,char *key);int CLLength(CLType *head);void CLAllNode(CLType *head);#endif/*=======================================*///追加结点；CLType *CLAddEnd (CLType *head,Data nodeData){ CLType *node,*htemp; if (!(node=(CLType)malloc(sizeof(CLType))))//分配空间 { printf("内存分配失败！\n"); return NULL; } else { node->nodeData=http://www.mamicode.com/nodeData;//保存数据 node->nextNode=NULL//设置结点指针为空，即为表尾； if (head==NULL) { head=node; return head; } htemp=head; while(htemp->nextNode!=NULL) { htemp=htemp->nextNode; } htemp->nextNode=node; return head; }}/*=======================================*///插入头结点CLType *CLAddFirst(CLType *head,Data nodeData){ CLType *node; if (!(node=(CLType)malloc(sizeof(CLType)))) { printf("内存分配失败\n"); return NULL; } else { node->nodeData=http://www.mamicode.com/nodeData; node->nextNode=head; head=node; return head; }}/*=======================================*///查找结点CLType *CLFindNode(CLType *head,char *key){ CLType *htemp; htemp=head; while(htemp) { if (stcmp(htemp->nodeDate.key,key)==0) { return htemp; } htemp=htemp->nextNode; } return NULL;}/*=======================================*/CLType *CLinsertNode(CLType *head,char *findkey,Data nodeData){ CLType *node,*nodetemp; if (!(node=(CLType)malloc(sizeof(CLType)))) { printf("内存分配失败！\n"); return NULL; } node->nodeData=http://www.mamicode.com/nodeData; nodetemp=CLFindNode(head,findkey); if (nodetemp) { node->nextNode=nodetemp->nextNode; nodetemp->nextNode=node; } else { printf("未找到争取的的插入位置\n"); free(node); } return head;}/*=======================================*///delete the node;int CLDeleteNode(CLType *head,char *key){ CLType *node,*htemp; htemp=head; node=head; while(htemp) { if (strcmp(htemp->nodeData.key,key)==0) { node->nextNode=htemp->nextNode; free(htemp); return 1; } else { node=htemp; htemp=htemp->nextNode; } } return 0;}/*=======================================*///计算链表的长度int CLLength(CLType *head){ CLType *htemp; int len=0; htemp=head; while(htemp) { len++; htemp=htemp->nextNode; } return len;}/*=======================================*///显示所有的结点void CLAllNode(CLType *head){ CLType *htemp; Data nodeData; htemp=head; printf("当前链表共有%d个结点，链表的所有数据如下:\n", CLLength(head)); while(htemp) { nodeData=htemp->nodeData; printf("node:(%s,%s,%d)\n",nodeData.key,nodeData.name,nodeData.age ); htemp=htemp->nextNode; }}
list_simple.c
#include <stdlib.h>#include <stdio.h>#include <string.h>#include "list_simple.h"void main(){ CLType *node,*head=NULL; Data nodeData; char key[10]; char findkey[10]; printf("链表测试，输入链表中的数据，输入格式为：关键字 姓名 年龄 \n"); do { fflush(stdin); scanf("%s",nodeData.key); if (strcmp(nodeData.key,"0")==0) { break;//输入0，退出 } else { scanf（"%s%d",nodeData.name,&nodeData.age); head=CLAddEnd(head,nodeData); } }while(1); CLAllNode(head); printf("演示插入结点，输入插入位置的关键字：\n"); scanf("%s",&findkey); printf("输入插入结点的数据（关键字 姓名 年龄）\n"); scanf("%s%s%d",nodeData.key,nodeData.name,&nodeData.age); head=CLInsertNode(head,findkey,nodeData); CLAllNode(head); printf("演示删除结点，输入要删除的关键字：\n"); fflush(stdin); scanf("%s",key); CLDeleteNode(head,key); CLAllNode(head); printf("演示在链表中查找，出入要查找的关键字：\n"); fflush(stdin); scanf("%s",key); node=CLFindNode(head,key); if(node) { nodeData=node->nodeData; printf("关键字对应的结点为(%s%s%d)\n",key,nodeData.key,nodeData.name ); } else { printf("在链表中没有找到你对应的结点\n"); }}
代码都已经编译通过！可以直接用
后面我们给出一个任意链表中存储任意类型的数据的实现方法，尽请期待：算法2---链表2---链表任意存储的实现
算法2---链表1---链表简单的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。