数据结构：链表详解与应用
目录
单向链表
特点
linklist.h
main.c
linklist.c
循环链表
双向链表
单向链表
解决顺序存储的缺点：插入、删除和动态存储问题。
动态存储：程序运行起来后，决定链表的容量。内存的使用率相对比较高。
特点
一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续；可以被存储在任意内存未被占用的位置上。
在链表中存储数据，数据域、指针域（自己的下一个在哪里）：节点
linklist.h
#ifndef __LINKLIST__H__
#define __LINKLIST__H__
typedef struct person
{
char name[32];
int age;
char sex;
int score;
} DATATYPE;
typedef struct node
{
DATATYPE data;
struct node *next;
} LinkNode;
typedef struct list
{
LinkNode *head;
int clen;
} LinkList;
LinkList *CreateLinkList();
int InsertHeadLinkList(LinkList *list, DATATYPE *data);
int InsertTailLinkList(LinkList *list, DATATYPE *data);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ModifyLinkList(LinkList *list, char *name, DATATYPE *newdata);
int DestroyLinkList(LinkList *list);
int IsEmptyLinkList(LinkList* list);
int GetSizeLinkList(LinkList* list);
void RevertLinkList(LinkList *list);
LinkNode* FindMidList(LinkList* list);
LinkNode* FindLastklist(LinkList* list,int k);
#endif //!__LINKLIST__H__main.c
#include
#include "linklist.h"
int main(int argc, char** argv)
{
LinkList* ll = CreateLinkList(); // ll指针是实参
DATATYPE data[] = {
{"zhangsan", 20, 'f', 90}, {"lisi", 21, 'm', 92}, {"wangmazi", 30, 'm', 80},
{"guanerge", 50, 'm', 70}, {"liubei", 55, 'm', 98},
};
/*
InsertHeadLinkList(ll, &data[0]);
InsertHeadLinkList(ll, &data[1]);
InsertHeadLinkList(ll,&data[2]);
InsertHeadLinkList(ll, &data[3]);
*/
InsertTailLinkList(ll, &data[0]);
InsertTailLinkList(ll, &data[1]);
InsertTailLinkList(ll, &data[2]);
InsertTailLinkList(ll, &data[3]);
InsertTailLinkList(ll, &data[4]);
ShowLinkList(ll);
// printf("---------------------find-------------------
");
// LinkNode* ret = FindLinkList(ll, "zhangsan");
// if (NULL == ret)
// {
// printf("can't find person
");
// }
// else
// {
// printf("find it,name:%s score: %d
", ret->data.name, ret->data.score);
// }
// printf("---------------------delete-------------------
");
// DeleteLinkList(ll, "guanerge");
// ShowLinkList(ll);
// printf("---------------------modify-------------------
");
// ModifyLinkList(ll, "lisi", &data[2]);
// ShowLinkList(ll);
// printf("-----------------------revert-----------------------
");
// RevertLinkList(ll);
// ShowLinkList(ll);
// DestroyLinkList(ll);
// ll = NULL;
// printf("-------------------fine mid-------------------
");
// FindMidList(ll);
// LinkNode* ret = FindMidList(ll);
// if (NULL == ret)
// {
// printf("can't fine mid
");
// }
// else
// {
// printf("find it,name:%s
", ret->data.name);
// }
printf("----------------find lastk----------------
");
LinkNode* ret = FindLastklist(ll, 4);
if (NULL == ret)
{
printf("can't find lastk
");
}
else
{
printf("find it,name:%s
", ret->data.name);
}
return 0;
}
linklist.c
#include "linklist.h"
#include
#include
#include
/**
* @brief Create a Link List object创建一个单向链表头结构
*
* @return LinkList* 指向单向链表表头结构的指针
*/
LinkList *CreateLinkList()
{
LinkList *ll = malloc(sizeof(LinkList));
if (NULL == ll)
{
printf("create malloc error
");
return NULL;
}
ll->head = NULL;
ll->clen = 0;
return ll;
}
/**
* @brief 单向链表的头插操作
*
* @param list 待操作的链表
* @param data 需要新增的数据
* @return int 0成功 1失败
*/
int InsertHeadLinkList(LinkList *list, DATATYPE *data)
{
LinkNode *newnode = malloc(sizeof(LinkNode));
if (NULL == newnode)
{
printf("inserthead malloc error
");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
newnode->next = list->head;
list->head = newnode;
list->clen++;
return 0;
}
/**
* @brief 在链表的最后新增元素
*
* @param list 待操作的链表
* @param data 需要新增的数据
* @return int 0成功 1失败
*/
int InsertTailLinkList(LinkList *list, DATATYPE *data)
{
if (IsEmptyLinkList(list))
{
return InsertHeadLinkList(list, data);
}
LinkNode *newnode = malloc(sizeof(LinkNode));
if (NULL == newnode)
{
printf("insert malloc error
");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
LinkNode *tmp = list->head;
while (tmp->next)
{
tmp = tmp->next;
}
tmp->next = newnode;
list->clen++;
return 0;
}
/**
* @brief 显示单向链表中的数据
*
* @param list 待操作的单向链表表头指针
* @return int 0成功
*/
int ShowLinkList(LinkList *list)
{
LinkNode *tmp = list->head; // 这里的指针指向head的地址，形参
while (NULL != tmp)
{
printf("name:%s age:%d ssex:%c score:%d
", tmp->data.name, tmp->data.age, tmp->data.sex, tmp->data.score);
tmp = tmp->next;
}
return 0;
}
/**
* @brief 按照名字查找下一个节点
*
* @param list 需要被查找的链表
* @param name 需要被查找的名字
* @return LinkNode* NULL失败 ！=NULL成功
*/
LinkNode *FindLinkList(LinkList *list, char *name)
{
LinkNode *tmp = list->head;
int len = GetSizeLinkList(list);
int i = 0;
for (i = 0; i < len; i++)
{
if (0 == strcmp(tmp->data.name, name))
{
return tmp;
}
tmp = tmp->next;
}
return NULL;
}
int DeleteLinkList(LinkList *list, char *name)
{
if (IsEmptyLinkList(list))
{
printf("delete error
");
return 1;
}
LinkNode *tmp = NULL;
LinkNode *prev = NULL;
if (0 == strcmp(list->head->data.name, name))
{
tmp = list->head;
list->head = list->head->next;
free(tmp);
list->clen--;
return 0;
}
else
{
tmp = list->head;
prev = list->head;
while (1)
{
tmp = tmp->next;
if (NULL == tmp)
{
break;
}
if (0 == strcmp(tmp->data.name, name))
{
prev->next = tmp->next;
free(tmp);
list->clen--;
return 0;
}
prev = tmp;
}
}
return 1;
}
/**
* @brief
*
* @param list 根据节点名字修改的内容
* @param name 需要被修改的用户名
* @param newdata
* @return int
*/
int ModifyLinkList(LinkList *list, char *name, DATATYPE *newdata)
{
if (IsEmptyLinkList(list))
{
printf("delete error
");
return 1;
}
LinkNode *tmp = FindLinkList(list, name);
memcpy(&tmp->data.name, newdata, sizeof(DATATYPE));
return 0;
}
/**
* @brief 释放链表占用的内存（表头+节点）
*
* @param list 需要被释放的链表的表头指针
* @return int 0成功 1失败
*/
int DestroyLinkList(LinkList *list)
{
if (list == NULL)
{
free(list);
return 1;
}
LinkNode *tmp = list->head;
while (tmp != NULL)
{
list->head = tmp->next;
free(tmp);
tmp = tmp->next;
}
free(list->head);
free(list);
return 0;
}
int IsEmptyLinkList(LinkList *list)
{
return 0 == list->clen;
}
int GetSizeLinkList(LinkList *list)
{
return list->clen;
}
/**
* @brief 单向链表的逆序
*
* @param list 待操作的链表
*/
void RevertLinkList(LinkList *list)
{
if ((IsEmptyLinkList(list)) || (1 == GetSizeLinkList(list)))
{
printf("no need revert
");
return;
}
LinkNode *prev = NULL;
LinkNode *curr = list->head;
LinkNode *last = NULL;
while (curr != NULL)
{
last = curr->next;
curr->next = prev;
prev = curr;
curr = last;
}
list->head = prev;
}
/**
* @brief 查找链表中间节点
*
* @param list 需要被操作的链表
* @return LinkNode* NULL 失败，！=NULL 找到的指针
*/
LinkNode *FindMidList(LinkList *list)
{
LinkNode *fast = list->head;
LinkNode *slow = list->head;
while (fast)
{
fast = fast->next;
if (NULL == fast)
{
break;
}
slow = slow->next;
fast = fast->next;
}
return slow;
}
/**
* @brief 查找链表第k个节点
*
* @param list 待操作的链表的表头指针
* @param k 倒数第k个节点
* @return LinkNode* NULL失败
*/
LinkNode *FindLastklist(LinkList *list, int k)
{
LinkNode *fast = list->head;
LinkNode *slow = list->head;
while (k)
{
fast = fast->next;
k--;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
双向链表
doublelink.h
#ifndef __DOULINK__H__
#define __DOULINK__H__
typedef struct person
{
char name[32];
int age;
char sex;
int score;
} DATATYPE;
typedef struct dounode
{
DATATYPE data;
struct dounode *prev;
struct dounode *next;
} DouLinkNode;
typedef struct list
{
DouLinkNode *head;
int clen;
} DouLinkList;
typedef enum {DIR_FORWARD,DIR_BACKWARD}DIRECT;
DouLinkList *CreateDouLinkList();
int InsertHeadDouLinkList(DouLinkList *dl,DATATYPE* data);
int ShowDouLinkList(DouLinkList *dl,DIRECT dir);
int InserTailDouLinkList(DouLinkList *dl,DATATYPE* data);
DouLinkNode* FindDouLinkList(DouLinkList *dl,char *name);
int ModifyDouLinkList(DouLinkList *dl,char *name,DATATYPE* newdata);
int DeleteDouLinkList(DouLinkList *dl,char *name);
int IsEmptyDouLinkList(DouLinkList *dl);
int GetSizeDouLinkList(DouLinkList *dl);
int DestroyDouLinkList(DouLinkList *dl);
#endif
