内容简介: 上篇博客讲到了单链表的实现和简单的使用,今天我们再详细介绍一下单链表。其实链表与数组不同在于,数组在分配内存的时候是连续的内存空间地址,是物理地址的连续,也可以叫做静态分配内存。链表,单向链表,双链表他的内存是动态的,也就是说你要用的时候,再生成下一个节点即可,不需要一次性就把内存要一块过去,可以一点点要,扩展也方便一些。但是数组的时间复杂度要小于链表,在一定情况下,效率更高,比如查询。但是删除元素的话,链表更方便一些,因为链表只有把next指针指向其他节点,就可以方便完成增加和删除,数组是需要
上篇博客讲到了单链表的实现和简单的使用,今天我们再详细介绍一下单链表。其实链表与数组不同在于,数组在分配内存的时候是连续的内存空间地址,是物理地址的连续,也可以叫做静态分配内存。链表,单向链表,双链表他的内存是动态的,也就是说你要用的时候,再生成下一个节点即可,不需要一次性就把内存要一块过去,可以一点点要,扩展也方便一些。但是数组的时间复杂度要小于链表,在一定情况下,效率更高,比如查询。但是删除元素的话,链表更方便一些,因为链表只有把next指针指向其他节点,就可以方便完成增加和删除,数组是需要换掉整个内存,整个数据都要移动。
我们这篇就来讲一下如何对单链表进行元素删除操作,顺便实现一下数组数据的删除,让大家有直观的感受,对比俩种数据结构差异。
2.单链表删除
#include <stdio.h> #include <malloc.h> #include <string.h> #define N 10 typedef struct node { char name[20]; struct node *link; }stud; stud * creat(int n) /*建立新的链表的函数*/ { stud *p,*h,*s; int i; if((h=(stud *)malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } h->name[0]=’\0’; h->link=NULL; p=h; for(i=0;i<n;i ) { if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } p->link=s; printf("请输入第%d个人的姓名",i 1); scanf("%s",s->name); s->link=NULL; p=s; } return(h); } stud * search(stud *h,char *x) /*查找函数*/ { stud *p; char *y; p=h->link; while(p!=NULL) { y=p->name; if(strcmp(y,x)==0) return(p); else p=p->link; } if(p==NULL) printf("没有查找到该数据!"); } stud * search2(stud *h,char *x) /*另一个查找函数,返回的是上一个查找函数的直接前驱结点的指针,*/ /*h为表头指针,x为指向要查找的姓名的指针*/ /*其实此函数的算法与上面的查找算法是一样的,只是多了一个指针s,并且s总是指向指针p所指向的结点的直接前驱,*/ /*结果返回s即是要查找的结点的前一个结点*/ { stud *p,*s; char *y; p=h->link; s=h; while(p!=NULL) { y=p->name; if(strcmp(y,x)==0) return(s); else { p=p->link; s=s->link; } } if(p==NULL) printf("没有查找到该数据!"); } void del(stud *x,stud *y) /*删除函数,其中y为要删除的结点的指针,x为要删除的结点的前一个结点的指针*/ { stud *s; s=y; x->link=y->link; free(s); } main() { int number; char fullname[20]; stud *head,*searchpoint,*forepoint; number=N; head=creat(number); printf("请输入你要删除的人的姓名:"); scanf("%s",fullname); searchpoint=search(head,fullname); forepoint=search2(head,fullname); del(forepoint,searchpoint); }
假如我们已经知道了要删除的结点p的位置,那么要删除p结点时只要令p结点的前驱结点的链域由存储p结点的地址该为存储p的后继结点的地址,并回收p结点即可。
3.数组删除
下面我们来实现一下数组的元素删除
#include <stdio.h> //查找和删除的业务逻辑 /***************************************** *1、查找要删除数字的下标 *2、从下标开始,后面一个覆盖前面一个数字 *3、数组总长度-1 ******************************************/ int main() { int count = 7; //数组元素个数 double Nums[] = {423.2, 457.7, 409.0, 412.3, 407.6, 580.3, 320.5}; int JudgementNum; //用户进行下一步操作的判断数 double InsertNum; //用户要插入的数据 double DeleteNum; //用户要删除的数据 int DeleteIndex = -1; //删除某个数据的下标(索引),要给一个不可能的初值,方便判断。 int i; //循环变量 printf("当前采集到的数据为:\n"); for(i = 0; i < count; i++) { printf("%.2lf\t", Nums[i]); } printf("\n\n是否需要删除部分数据?\n提示:输入数字1进行删除操作,输入数字0确认当前数据采集无误。\n"); printf("请输入:"); scanf("%d", &JudgementNum); if(JudgementNum == 1) { printf("\n请输入要删除的数据:"); scanf("%lf", &DeleteNum); for(i = 0; i < count; i++) //穷举法,是常用算法之一 { if(DeleteNum == Nums[i]) //Nums[i]表示数组中的第i个元素 { //找到后并记录当前数据的下标(索引) DeleteIndex = i; break; //找到了要删除的数据,直接跳出循环,提升效率 } } //根据索引的判断,如果你要删除的数的下标和所给定索引的初值相同,那么肯定就是没找到。 if(DeleteIndex == -1) { printf("没有找到该数据,删除失败!\n"); } else { //如果找到了,建立一个循环并且从下标开始,数组中的元素后面一个覆盖前面一个,且数组长度 - 1 for(i = DeleteIndex; i < count - 1; i++) { Nums[i] = Nums[i+1]; } count--; //并打印输出后的结果 printf("\n第%d个数据将被删除,删除后的结果为:\n", DeleteIndex + 1); for(i = 0; i < count; i++) { printf("%.2lf\t", Nums[i]); } } }else if(JudgementNum == 0) { printf("当前数据采集无误并保存!"); } else { printf("删除数据操作发生错误!"); } //注意:以下程序实现的是删除数据之后的插入操作 printf("\n\n是否需要添加部分数据?\n提示:输入数字1进行添加操作,输入数字0保存当前数据。\n"); printf("请输入:"); scanf("%d",&JudgementNum); if(JudgementNum == 1) { printf("\n请输入要添加的数据:"); scanf("%lf", &InsertNum); //进行添加操作,再数组长度+1 Nums[count] = InsertNum; count++; printf("\n添加数据后的结果为:\n"); for(i = 0; i < count; i++) { printf("%.2lf\t", Nums[i]); } }else if(JudgementNum == 0) { printf("当前数据已被保存。\n"); } else { printf("添加数据操作发生错误\n"); } return 0; }
C中定义好一组数后,是通过访问元素下标来访问元素,所以正如注释数组如果找到了元素,删除以后,还做了被删除元素后面的数据,先去移动的操作,因为数组内存空间是连续的,你直接删除元素,但是数组空间会有空隙,要后面的元素不断填满,直到末尾数据也移动到了前一位即可。
3.单链表插入
下面,我们再讲一下单链表的插入,单链表的基本大家就算了解了。实际业务开始其实和我所举的例子还有差别,因为我们现在是直接调用。但是业务中,我们的代码是要给别人调用的,所以会有封装这样要求,但是其实也不难。我会在文章后面加上业务代码实现的。
#include <stdio.h> #include <malloc.h> #include <string.h> #define N 10 typedef struct node { char name[20]; struct node *link; }stud; stud * creat(int n) /*建立单链表的函数*/ { stud *p,*h,*s; int i; if((h=(stud *)malloc(sizeof(stud)))==NULL) h->name[0]=''; h->link=NULL; p=h; for(i=0;i<n;i++) { if((s= (stud *) malloc(sizeof(stud)))==NULL) p->link=s; printf("请输入第%d个人的姓名:",i+1); scanf("%s",s->name); s->link=NULL; p=s; } return(h); } stud * search(stud *h,char *x) /*查找函数*/ { stud *p; char *y; p=h->link; while(p!=NULL) { y=p->name; if(strcmp(y,x)==0) return(p); else p=p->link; } if(p==NULL) printf("没有查找到该数据!"); } void insert(stud *p) /*插入函数,在指针p后插入*/ { char stuname[20]; stud *s; /*指针s是保存新结点地址的*/ if((s= (stud *) malloc(sizeof(stud)))==NULL) printf("请输入你要插入的人的姓名:"); scanf("%s",stuname); strcpy(s->name,stuname); /*把指针stuname所指向的数组元素拷贝给新结点的数据域*/ s->link=p->link; /*把新结点的链域指向原来p结点的后继结点*/ p->link=s; /*p结点的链域指向新结点*/ } main() { int number; char fullname[20]; /*保存输入的要查找的人的姓名*/ stud *head,*searchpoint; number=N; head=creat(number); /*建立新链表并返回表头指针*/ printf("请输入你要查找的人的姓名:"); scanf("%s",fullname); searchpoint=search(head,fullname); /*查找并返回查找到的结点指针*/ insert(searchpoint); /*调用插入函数*/ }
4.单链表封装实现
4.1 单链表头文件
这是封装的单链表头文件
typedef void LinkList; /* typedef struct _tag_LinkListNode LinkListNode; struct _tag_LinkListNode { LinkListNode* next; }; */ typedef struct _tag_LinkListNode { struct _tag_LinkListNode* next; }LinkListNode; LinkList* LinkList_Create(); void LinkList_Destroy(LinkList* list); void LinkList_Clear(LinkList* list); int LinkList_Length(LinkList* list); int LinkList_Insert(LinkList* list, LinkListNode* node, int pos); LinkListNode* LinkList_Get(LinkList* list, int pos); LinkListNode* LinkList_Delete(LinkList* list, int pos);
4.1 单链表封装实现
这是封装实现
#include<stdio.h> #include "stdlib.h" #include "string.h" #include "linklist.h" typedef struct _tag_LinkList { //这个句柄里面,需要保存所有节点信息。需要有一个起始点 //就是带头节点的链表。。。 LinkListNode header; int length; }TLinkList; LinkList* LinkList_Create() { TLinkList *ret = (TLinkList *)malloc(sizeof(TLinkList)); if (ret == NULL) { return NULL; } //memset(ret, 0, sizeof(TLinkList)); ret->header.next = NULL; ret->length = 0; return ret; } void LinkList_Destroy(LinkList* list) { if (list == NULL) { return ; } free(list); return ; } void LinkList_Clear(LinkList* list) { TLinkList *tList =NULL; if (list == NULL) { return ; } tList = (TLinkList *)list; tList->length = 0; tList->header.next = NULL; return ; } int LinkList_Length(LinkList* list) { TLinkList *tList = (TLinkList *)list; if (tList == NULL) { return -1; } return tList->length; } int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) { int i = 0; TLinkList *tList = NULL; LinkListNode *current = NULL; tList = (TLinkList *)list; //准备环境让辅助指针变量 指向链表头节点 current = &tList->header; for (i=0; i<pos &&(current->next!=NULL); i++) { current = current->next; } //让node节点链接后续链表 node->next = current->next ; //让前边的链表。链接node current->next = node; tList->length ++; return 0; } LinkListNode* LinkList_Get(LinkList* list, int pos) { int i = 0; TLinkList *tList = NULL; LinkListNode *current = NULL; LinkListNode *ret = NULL; tList = (TLinkList *)list; if (list == NULL || pos <0 ||pos>=tList->length) { return NULL; } //准备环境让辅助指针变量 指向链表头节点 current = &tList->header; for (i=0; i<pos &&(current->next!=NULL); i++) { current = current->next; } ret = current->next; return ret; } LinkListNode* LinkList_Delete(LinkList* list, int pos) { int i = 0; TLinkList *tList = NULL; LinkListNode *current = NULL; LinkListNode *ret = NULL; tList = (TLinkList *)list; if (list == NULL || pos <0 ||pos>=tList->length) { return NULL; } //准备环境让辅助指针变量 指向链表头节点 current = &tList->header; for (i=0; i<pos &&(current->next!=NULL); i++) { current = current->next; } ret = current->next; //删除算法 current->next =ret->next; tList->length--; return ret; }
4.3 调用示例
这是调用demo
#include<stdio.h> #include "stdlib.h" #include "string.h" #include "linklist.h" typedef struct Teacher { LinkListNode node; char name[64]; int age; }Teacher; int main() { Teacher t1,t2, t3; int length, i = 0; LinkList *list = NULL; t1.age = 31; t2.age = 32; t3.age = 33; list = LinkList_Create(); length = LinkList_Length(list); //业务节点是teacher和算法分类的。。。。思想 LinkList_Insert(list, (LinkListNode *)&t1, LinkList_Length(list)); LinkList_Insert(list, (LinkListNode *)&t2, LinkList_Length(list)); LinkList_Insert(list, (LinkListNode *)&t3, LinkList_Length(list)); //遍历链表 for (i=0; i<LinkList_Length(list); i++) { Teacher *tmp = (Teacher *)LinkList_Get(list, i); if (tmp != NULL) { printf("age:%d ", tmp->age); } } while(LinkList_Length(list) > 0) { Teacher *tmp = (Teacher *)LinkList_Delete(list, 0); if (tmp != NULL) { printf("age:%d ", tmp->age); } } LinkList_Destroy(list); return 0; }
好了,我们下篇博客,双链表见!
以上所述就是小编给大家介绍的《数据结构之单链表详解二》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数据结构 1 线性表详解 链表、 栈 、 队列 结合JAVA 详解
- Runtime数据结构详解
- conntrack中的数据结构详解
- 数据结构之单链表详解一
- 3.10 solidity数据结构详解
- HBase数据结构与基本语法详解
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Java语言精粹
Jim Waldo / 王江平 / 电子工业出版社 / 2011-6 / 39.00元
这是一本几乎只讲java优点的书。 Jim Waldo先生是原sun微系统公司实验室的杰出工程师,他亲历并参与了java从技术萌生、发展到崛起的整个过程。在这《java语言精粹》里,jim总结了他所认为的java语言及其环境的诸多精良部分,包括:类型系统、异常处理、包机制、垃圾回收、java虚拟机、javadoc、集合、远程方法调用和并发机制。另外,他还从开发者的角度分析了在java技术周围......一起来看看 《Java语言精粹》 这本书的介绍吧!