数据结构day3(双向链表操作)
链式存储:
双向链表
线性表的链式存储:解决了顺序存储的缺点,插入和删除。动态存储问题。
数据域 + 指针 ---> 节点
注意:用自己结构的指针一般就是 链表。
DoubleLInk.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
DoubleLInk.c文件
#include "doulink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
DouLinkList *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(0==list->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(direct==DIR_FORWARD)
{
for(i=0;i<GetSizeDouLinkList(list);i++)
{
printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
tmp=tmp->next;
}
}
else
{
while(tmp->next)
{
tmp=tmp->next;
}
for(i=0;i<GetSizeDouLinkList(list);i++)
{
printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
tmp=tmp->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 ;i<size;i++)
{
//if(0==strcmp(tmp->data.name))
if(fun(&tmp->data,arg))
{
return tmp;
}
tmp= tmp->next;
}
return NULL;
}
int RevertDouLinkList(DouLinkList *list)
{
int size = GetSizeDouLinkList(list);
if(size<2)
{
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(NULL==ret)
{
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(pos<0 ||pos>GetSizeDouLinkList(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--)
{
tmp=tmp->next;
}
newnode ->prev = tmp;
newnode->next = tmp->next;
if(tmp->next)
{
tmp->next->prev = newnode;
}
tmp->next = newnode;
}
list->clen++;
return 0;
}
main.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("can't 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;
}
原文地址:https://blog.csdn.net/weixin_66436813/article/details/140674315
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!