vip网站解析建设,手机百度app下载安装,为企业做好服务优化营商环境,西安百度推广代运营可能是顺序表研究的细致了一点#xff0c;单链表操作一下子就实现了。这里先实现带头结点的单链表操作。大概有以下知识点.1;结点#xff1a;结点就是单链表中研究的数据元素#xff0c;结点中存储数据的部分称为数据域#xff0c;存储直接后继地址的部分称为指针域。2;结点…可能是顺序表研究的细致了一点单链表操作一下子就实现了。这里先实现带头结点的单链表操作。大概有以下知识点.1;结点结点就是单链表中研究的数据元素结点中存储数据的部分称为数据域存储直接后继地址的部分称为指针域。2;结点示意图3;头指针头指针始终指向链表第一个元素当有头结点时头结点就是链表第一个元素。头指针具有标识左右故头指针命名为链表的名字这里为linklist。头指针是一定存在的。4;头结点引入头结点的目的是将链表首元结点的插入和删除操作与其他结点的插入和删除操作统一起来。(即头指针地址不在发生变化)5;单链表结点结构体表示1 structLNode2 {3 int data; //姑且认为其数据为整型4 struct LNode *next;5 };67 typedef struct LNode * linklist6;单链表的操作集合头文件 defs.h1 #ifndef _DEFS_H_2 #define _DEFS_H_34 #include5 #include6 #include78 struct LNode //单链表结点的定义9 {10 intdata;11 struct LNode *next;12 }13 typedef struct LNode *linklist1415 //操作集合16 void InitList(linklist *L); //申请头结点头指针地址改变17 void DestroyList(linklist *L); //须释放头结点头指针地址改变18 void ClearList(linklist L); //保留头结点头指针地址不变19 voidListEmpty(linklist L);20 intListLength(linklist L);21 int GetElem(linklist L, int i, int *e);22 int LocateElem(linklist L, inte);23 int PriorElem(linklist L, int cur_e, int *pri_e);24 int NextElem(linklist L, int cur_e, int *nex_e);25 int ListInsert(linklist L, int i, int e); //插入不改变头指针的值26 int ListDelete(linklist L, int i, int *e); //删除操作也不改变头指针的值27 voidTravelList(linklist L);28 #endif7;InitList操作实现1 #includedefs.h23 void InitList(linklist *L) //接受头指针的地址值4 {5 *L (linklist)malloc(sizeof(struct LNode)); //*L表示头指针67 if (*L NULL)8 {9 printf(分配结点失败。\n);10 exit(-1);11 }12 (*L)-next NULL; //置头结点的next域为空13 }InitList.c8;DestroyList操作的实现1 #includedefs.h23 void DestroyList(linklist *L) //接受的参数为头指针的地址值4 {5 linklist p ;6 while (*L)7 {8 p (*L)-next; //释放结点之前先保存结点的下一个地址防止线索被断9 free(*L);10 *L p; //将下一个结点作为释放结点11 }12 }DestroyList.c9;ClearList操作的实现1 #includedefs.h23 void ClearList(linklist L) //保留头结点4 {5 linklist p L-next; //p将头指针的next值保存起来p指向首元结点6 L-next NULL;78 DestroyList(p); //调用撤销函数释放后面的结点910 }ClearList.c10;ListEmpty操作的实现1 #includedefs.h23 voidListEmpty(linklist L)4 {5 if (L-next NULL) //判断头结点指针域是否为空6 printf(链表为空.\n);7 else8 printf(链表不为空.\n);9 }ListEmpty.c11;ListLength操作实现1 #includedefs.h23 intListLength(linklist L)4 {5 int j0; //作为计数器6 linklist p L-next; //p指向首元结点作为移动指针78 while (p) //从首元结点开始9 {10 j;11 p p-next;12 }13 returnj;14 }ListLength.c12;GetElem操作实现1 #includedefs.h23 int GetElem(linklist L, int i, int *e) //1 i ListLength(L)4 {5 int j 0; //j作为计数器6 linklist p L;78 while (p j9 {10 j;11 p p-next;12 }13 if (!p || i1) //取值位置不合理14 exit(0);1516 *e p-data;17 return 0;18 }GetElem.c13;LocateElem操作实现1 #includedefs.h23 int LocateElem(linklist L, inte)4 {5 linklist p L-next; //p作为移动指针p指向第一个元素6 int j 0; //j作为计数器78 while(p)9 {10 j;11 if (p-data e)12 returnj;13 p p-next;14 }15 return 0;16 }LocateElem.c14;PriorElem操作实现1 #includedefs.h23 int PriorElem(linklist L, int cur_e, int *pri_e) //第一个元素无前驱4 {5 linklist p L-next; //p指向首元结点6 linklist q;78 while(p)9 {10 q p-next; //q为p的后继1112 if (q q-data cur_e) //则p就是q的前驱13 *pri_e p-data;14 p q; //循环15 }16 return 0;17 }PriorElem.c15;NextElem操作的实现1 #includedefs.h23 int NextElem(linklist L, int cur_e, int *nex_e) //最后一个元素无后继4 {5 linklist p L-next; //p指向首元结点6 linklist q;78 while(p)9 {10 q p-next; //q为p的后继1112 if (q p-data cur_e) //p有后继且p的数据域与当前值相等13 *nex_e q-data;14 p q; //更新p15 }16 return 0;17 }NextElem.c16;ListInsert操作的实现1 #includedefs.h23 int ListInsert(linklist L, int i, int e) //1 i ListLength(L)4 {5 int j0; //j为基数器6 linklist p L; //p为移动指针p指向头结点7 linklist q, s;89 while (p j10 {11 j;12 p p-next;13 }1415 if (!p || i1) //插入位置不合理16 return 0;1718 q p-next; //q指向第i个结点1920 s (linklist)malloc(sizeof(structLNode));21 if (!s) //分配失败22 exit(-1);2324 s-data e; //置s的数据域为e25 s-next q; //插入操作,是指针连起来26 p-next s;27 return 0;28 }ListInsert.c17;ListDelete操作的实现1 #includedefs.h23 int ListDelete(linklist L, int i, int *e) //1 i ListLength(L)4 {5 int j 0; //j为计数器6 linklist p L;7 linklist q;89 while (p j10 {11 j;12 p p-next;13 }1415 if (!p || i1) //删除位置不合理16 exit(0);17 q p-next; //q指向第i个结点1819 *e q-data; //先将第i个结点的数据域带出20 p-next q-next; //连起指针21 free(q); //释放第i个结点2223 return 0;24 }ListDelete.c18;TravelList操作实现1 #includedefs.h23 voidTravelList(linklist L)4 {5 linklist p L-next; //p指向首元结点6 int j 0; //j为计数器78 while(p)9 {10 j;11 printf(第%d个结点的数据域的值为%d\n, j, p-data);12 p p-next; //更新p13 }14 }TravelList.c19;makefile的实现其代码与顺序表的一样,这里换成另一种写法1 object main.o InitList.o DestroyList.o ClearList.o ListEmpty.o \2 ListLength.o GetElem.o LocateElem.o PriorElem.o NextElem.o \3 ListInsert.o ListDelete.o TravelList.o45 test : $(object)6 gcc -g -Wall -o test $(object)78 $(object) : defs.h910 .PHONY : clean11 clean :12 rm -f *.o20;顺序表与单链表的比较顺序表是用一段地址连续的存储单元来存放数据元素适合查找不适合频繁插入和删除(没一次操作都是O(n))单链表是用不连续的存储单元其数据元素之间是用指针来连接每一次的查找都必须通过头指针来遍历因此其不适合频繁的查找。但是对于插入和删除操作它不需要移动其它元素算法时间复杂度为O(1)因此特别适合频繁的插入和删除操作。
