宜昌做网站优化,主题 wordpress,装饰工程 技术支持 东莞网站建设,纯html5网站源码线性表的链式存储 解决顺序存储的缺点#xff0c;插入和删除#xff0c;动态存储问题。 特点#xff1a; 线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素#xff0c;存储单元可以是连续的#xff0c;也可以不连续。可以被存储在任意内存未被占…线性表的链式存储 解决顺序存储的缺点插入和删除动态存储问题。 特点 线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素存储单元可以是连续的也可以不连续。可以被存储在任意内存未被占用的位置上。 所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址。 为了表示每个数据元素ai与其直接后继数据元素ai1之间的逻辑关系对ai来说除了存储其本身的信息外还需要存一个指示器直接后续的信息。把存储元素信息的域叫数据域把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像叫结点(Node); 单链表中c语言的描述
typedef struct person { char name[32]; char sex; int age; int score; }DATATYPE;
typedef struct node { DATATYPE data; struct node *next,*prev; -这里必须要加指针 }LinkNode;
typedef struct list { LinkNode *head; int tlen; 链表元素总个数 这里可以不要 int clen; 当前节点个数 (mutex 这部分有可能是并发的有可能需要加上互斥锁) }LinkList; 以下是一个链表LinkList的操作集这些操作包括创建链表、在链表头部或尾部插入节点、显示链表内容、查找链表中的节点、删除链表中的节点、修改链表节点的数据和销毁链表。这里我假设LinkList是一个指向链表头节点的指针而LinkNode是链表节点的结构体。DATATYPE是一个占位符表示链表节点存储的数据类型可能是整型、字符型或其他自定义类型。以下是对每个函数的基本实现思路不包含完整代码
1. LinkList *CreateLinkList(int len);
这个函数用于创建一个具有指定长度len的空链表。如果len是0则创建一个空链表只有一个头节点头节点的下一个指针指向NULL。如果len大于0则可能需要根据实际需求创建len个空节点或带初始值的节点的链表。但通常len参数在这里可能不太适用因为链表长度是动态变化的更常见的做法是不带参数地创建一个空链表。 2. int InsertHeadLinkList(LinkList *list, DATATYPE data);
在链表的头部插入一个新节点该节点包含指定的数据data。函数返回成功或失败的状态码。
若需要在当前表头结点插入一个新结点 , 只需要修改一个next指针(新结点的next指针) , 可以分两步完成 定义节点结构体首先需要定义一个节点结构体该结构体包含数据域和指针域。数据域用于存储节点的数据指针域用于存储指向下一个节点的指针。 初始化链表创建一个头节点该节点不存储有效数据仅作为链表的入口点。头节点的指针域初始化为NULL表示链表为空。 插入新节点对于每次插入操作首先创建一个新节点并为其数据域赋值。然后将新节点的指针域指向头节点的下一个节点即原链表的第一个节点最后修改头节点的指针域使其指向新节点。
* 修改新结点的next指针 , 使其指向当前的表头结点 * 更改表头指针的值 , 使其指向新节点(之前的表头指针指向的是15 , 修改后指向为新数据的) 3. int ShowLinkList(LinkList *list);
遍历链表并打印出每个节点的数据。这个函数没有返回值或返回一个状态码表示成功或失败但通常打印操作不需要。 4. LinkNode *FindLinkList(LinkList *list, char *name);
在链表中查找具有指定名称name的节点。由于函数返回类型为LinkNode *它返回找到的节点的指针如果未找到则返回NULL。这里假设每个节点都有一个name属性这与DATATYPE数据类型的定义可能不一致需要根据实际数据结构调整。
其中可以定义一个函数指针来找结构体中不同得东西来达到解耦合的情况 5. int DeleteLinkList(LinkList *list, char *name);
从链表中删除具有指定名称name的节点。函数返回成功或失败的状态码。
删除中间节点
(1)使tmp指向想要删除的节点 2将tmp的下一个的prev与tmp本身的上一个相等 3使tmp的上一个的nxt与tmp本身的next相等 得到指向tmp节点的下一个节点。 4但如果是最后的节点 只要使前一个的下一个置为空就行。但无法找到本身的下一个会发生错误所以需要加上一个判断。 6. int ReviseLinkList(LinkList *list, char *name, DATATYPE data);
使链表反转
定义三个指针分别表示正在操作的节点prve以及该节点的上一个tmp该节点的下一个next
1将tmpheadprveNULLnexttmp-next; (2)反转tmp本身的prve和next指针
tmp-》nextprve tmp-prevnext;
(3)将最初定义的大指针一个一个往后移直到最后tmp为空
prve tmp;
tmpnext;
next next-next;
4将head与最初定义的prev相等。 7. int DestroyLinkList(LinkList *list);
销毁链表释放链表占用的所有内存空间。函数返回成功或失败的状态码。
使tmp指向第一个节点一个一个往后释放最后释放head 8. int InsertTailLinkList(LinkList *list, DATATYPE data);
在链表的尾部插入一个新节点该节点包含指定的数据data。函数返回成功或失败的状态码。
9. int ModifyDouLinkList(LinkList *list, DATATYPE data);
改变某个节点的数据。函数返回成功或失败的状态码 9. int InserPosDouLinList(LinkList *list, DATATYPE data);
(1)如果head里没有节点 clen0链表是空或者想要插入的pos0直接调用头插
2head后有节点
将tmp移到想要插入位置的前一个节点
whilepos-1
{ tmptmp-next;
} 使newnode的prev指向tmpnewnode 的next指向原来tmp指向的位置
newnode-prvetmp;
newnode-nexttmp-next; 如果tmp后面没东西直接使tmp的next等于newnode
原本就定义了newnode的prev和next是NULL
如果tmp后面 使原本ttmp的下一个的前向指针指向newnode 同时使 tmp 的后向指针指向newnode。
即
iftmp-next
{
tmp-next-prevnewnode
}
tmp-nextnewnode; pos和clen相同就是尾插。 .h
#ifndef DOULINK_H
#define DOULINK_H
typedef struct{char name[32];char sex;int age;int score;
}DATATYPE;
typedef int (*PFUN)(DATATYPE*data,void* arg);
typedef struct node {DATATYPE data;struct node *next,*prev;
}DouLinkNode;typedef struct{DouLinkNode *head;int clen;
}DouLinkList;
typedef enum{DIR_FORWARD,DIR_BACKWARD}DIRECT;
DouLinkList* CreateDouLinkList();
int InsertHeadLinkList(DouLinkList *list, DATATYPE *data);
int ShowDouLinkList(DouLinkList *list,DIRECT direct);
int GetSizeDouLinkList(DouLinkList *list);
DouLinkNode *FindLinkList(DouLinkList *list, PFUN fun,void* arg);
int RevertDouLinkList(DouLinkList *list);
int DeleteLinkList(DouLinkList *list, PFUN fun,void* arg);
int IsEmptyDouLinkList(DouLinkList *list);
int ModifyDouLinkList(DouLinkList *list,PFUN fun,void* arg,DATATYPE *data);
int DestroyDouLinkList(DouLinkList **list);
int InserPosDouLinkList(DouLinkList *list,DATATYPE *data,int pos);
#endif // DOULINK_H
.c
#include doulink.h
#include stdio.h
#include stdlib.h
#include string.hDouLinkList *CreateDouLinkList()
{//DouLinkList dl ;DouLinkList* dl (DouLinkList*)malloc(sizeof(DouLinkList));if(NULL dl){perror(CreateDouLinkList malloc);//exit(1);return NULL;}dl-head NULL;dl-clen 0 ;return dl;
}int InsertHeadLinkList(DouLinkList *list, DATATYPE *data)
{DouLinkNode*newnode malloc(sizeof(DouLinkNode));if(NULL newnode){perror(InsertHeadLinkList malloc);return 1;}memcpy(newnode-data,data,sizeof(DATATYPE));newnode-next NULL;newnode-prev NULL;if(0list-clen)//empty{list-head newnode;}else{newnode-next list-head;list-head-prev newnode;list-head newnode;}list-clen;return 0;}int ShowDouLinkList(DouLinkList *list, DIRECT direct)
{int i 0 ;DouLinkNode* tmp list-head;if(directDIR_FORWARD){for(i0;iGetSizeDouLinkList(list);i){printf(%s %c %d %d\n,tmp-data.name,tmp-data.sex,tmp-data.age,tmp-data.score);tmptmp-next;}}else{while(tmp-next){tmptmp-next;}for(i0;iGetSizeDouLinkList(list);i){printf(%s %c %d %d\n,tmp-data.name,tmp-data.sex,tmp-data.age,tmp-data.score);tmptmp-prev;}}return 0;
}int GetSizeDouLinkList(DouLinkList *list)
{return list-clen;
}DouLinkNode *FindLinkList(DouLinkList *list, PFUN fun, void *arg)
{DouLinkNode* tmp list-head;int size GetSizeDouLinkList(list);int i 0;for(i 0 ;isize;i){//if(0strcmp(tmp-data.name))if(fun(tmp-data,arg)){return tmp;}tmp tmp-next;}return NULL;
}int RevertDouLinkList(DouLinkList *list)
{int size GetSizeDouLinkList(list);if(size2){return 0;}DouLinkNode* prev NULL;DouLinkNode* tmp list-head;DouLinkNode*next tmp-next;while(1){tmp-next prev;tmp-prev next;prev tmp;tmp next;if(NULL tmp){break;}next next-next;}list-head prev;return 0;
}int DeleteLinkList(DouLinkList *list, PFUN fun, void *arg)
{if(NULL list){fprintf(stderr,DouLinkList is null);return 1;}if(IsEmptyDouLinkList(list)){fprintf(stderr,DouLinkList is empty);return 1;}DouLinkNode* ret FindLinkList(list,fun,arg);if(NULLret){fprintf(stderr,DeleteLinkList error,cant find\n);return 1;}if(ret list-head){list-head ret-next;list-head-prev NULL;}else{if(ret-next)ret-next-prev ret-prev;ret-prev-next ret-next;}free(ret);list-clen--;return 0;
}int IsEmptyDouLinkList(DouLinkList *list)
{return 0 list-clen;
}int ModifyDouLinkList(DouLinkList *list, PFUN fun, void *arg, DATATYPE *data)
{DouLinkNode* ret FindLinkList(list,fun,arg);if(NULL ret){fprintf(stderr,ModifyDouLinkList error,cant find\n);return 1;}memcpy(ret-data,data,sizeof(DATATYPE));return 0;
}int DestroyDouLinkList(DouLinkList **list)
{DouLinkNode* tmp(*list)-head;while(tmp){(*list)-head(*list)-head-next;free(tmp);tmp (*list)-head;}free(*list);(*list) NULL;return 0;
}int InserPosDouLinkList(DouLinkList *list, DATATYPE *data,int pos)
{if(pos0 ||posGetSizeDouLinkList(list)){fprintf(stderr,InserPosDouLinkList error,index error\n);return 1;}if(IsEmptyDouLinkList(list) || 0 pos){return InsertHeadLinkList(list,data);}else{DouLinkNode* tmp list-head;tmp list-head;DouLinkNode* newnode (DouLinkNode*)malloc(sizeof(DouLinkNode));if(NULL newnode){perror(InserPosDouLinkList malloc);return 1;}memcpy(newnode-data,data,sizeof(DATATYPE));newnode-prev NULL;newnode-next NULL;int i pos-1;while(i--){tmptmp-next;}newnode -prev tmp;newnode-next tmp-next;if(tmp-next){tmp-next-prev newnode;}tmp-next newnode;}list-clen;return 0;
}
man.c
#include stdio.h
#include doulink.h
#include string.h
int findbyname(DATATYPE*data,void* arg)
{return (0 strcmp(data-name,(char*)arg));
}
int findbyage(DATATYPE*data,void* arg)
{return data-age *(int*)arg;
}
int main()
{DATATYPE data[5]{{zhangsan,m,20,70},{lisi,f,21,60},{wangmazi,m,25,80},{liubei,f,30,85},{caocao,f,40,90},};DouLinkList* dl CreateDouLinkList();InsertHeadLinkList(dl,data[0]);InsertHeadLinkList(dl,data[1]);InsertHeadLinkList(dl,data[2]);ShowDouLinkList(dl,DIR_FORWARD);printf(-------------back---------------\n);ShowDouLinkList(dl,DIR_BACKWARD);printf(-------------find---------------\n);// char want_name[]lisi;// //DouLinkNode* tmp FindLinkList(dl,findbyname,want_name);// int want_age 25;// DouLinkNode* tmp FindLinkList(dl,findbyage,want_age);// if(NULL tmp)// {// printf(cant find person ,name:%s\n,want_name);// }// else// {// printf(%s:%d\n,tmp-data.name,tmp-data.score);// }// RevertDouLinkList(dl);// printf(-------------rev---------------\n);// ShowDouLinkList(dl,DIR_FORWARD);// DeleteLinkList(dl,findbyname,lisi);// printf(-------------del forware---------------\n);// ShowDouLinkList(dl,DIR_FORWARD);// printf(-------------back---------------\n);// ShowDouLinkList(dl,DIR_BACKWARD);// ModifyDouLinkList(dl,findbyname,zhangsan,data[3]);// printf(-------------modify---------------\n);// ShowDouLinkList(dl,DIR_FORWARD);InserPosDouLinkList(dl,data[3],3);printf(-------------pos---------------\n);ShowDouLinkList(dl,DIR_FORWARD);printf(-------------back---------------\n);ShowDouLinkList(dl,DIR_BACKWARD);DestroyDouLinkList(dl);printf(Hello World!\n);return 0;
}
顺序表和链表 优缺点
顺序表Array
优点
随机访问顺序表支持通过索引快速访问任意位置的元素时间复杂度为O(1)。存储密度高顺序表在物理存储上是连续的存储密度大即存储空间利用率高因为不需要额外存储指针等信息。缓存友好顺序表的数据在物理上连续存储因此可能更好地利用CPU缓存提高访问效率。
缺点
插入和删除操作成本高在顺序表的中间或开始位置插入或删除元素时需要移动大量的元素来保持数据的连续性时间复杂度为O(n)。扩容问题当顺序表的容量不足以存储更多元素时需要进行扩容操作这涉及到申请新的内存空间、复制原有数据到新空间等步骤可能会比较耗时。空间利用率可能不高在顺序表中如果预留的空间过大但实际存储的元素较少会导致空间浪费如果预留的空间过小又需要频繁扩容影响效率。
链表LinkedList
优点
插入和删除操作灵活链表在插入和删除元素时只需要改变指针的指向不需要移动大量的元素时间复杂度为O(1)在已知位置进行操作时。这使得链表非常适合于频繁插入和删除操作的场景。动态分配内存链表中的节点可以动态地申请和释放内存使得链表的大小可以根据需要动态变化无需担心空间浪费或扩容问题。
缺点
访问元素效率低访问链表中的元素需要从头节点开始遍历直到找到所需的元素时间复杂度为O(n)。空间利用率相对较低链表中每个节点除了存储数据本身外还需要额外存储指针或引用信息这增加了存储空间的开销。缓存不友好由于链表的节点在物理上不一定连续存储因此可能无法有效地利用CPU缓存导致访问效率下降。 循环链表 简单的来说就是将原来单链表中最有一个元素的next指针指向第一个元素或头结点链表就成了一个环头尾相连就成了循环链表。circultlar linker list. 注意非空表和空表。多数会加入头结点。 原来结束的条件是
p-next ! NULL ------- p-next ! Head 或者写成 指定长度clen 双向链表 double link list typedef struct DulNode { ElemType date; struct DulNode *pri; sturct DulNode *next }DulNode,*DuLinkList;
