1、数据结构之单链表、双向链表、循环链表
list.h
#ifndef _LIST_H_
#define _LIST_H_
typedef struct List{
int elem;
List *next;
}LinkList;
typedef struct CircularList {
int elem;
CircularList * next;
}CircularLinkedList;
typedef struct DoubleList {
int elem;
DoubleList * prior;
DoubleList * next;
}DoubleLinkedList;
typedef int(*compare)(void const *, void const*);
typedef void(*visit)(int *elem);
//function
LinkList * InitList();
void CreateList(LinkList * plList);
void DestroyList(LinkList * plList);
void ClearList(LinkList * plList);
int IsListEmpty(LinkList * plList);
int GetListLength(LinkList * plList);
void GetListElem(LinkList * plList, int i, int *elem);
int LocateListElem(LinkList * plList, int elem, compare comp);
int GetPriorListElem(LinkList * plList, int elem, int *priorElem, compare comp);
int GetNextListElem(LinkList * plList, int elem, int *nextElem, compare comp);
void InsertListElem(LinkList * plList, int i, int elem);
int DeleteListElem(LinkList *plList, int i, int *elem);
void TraverseList(LinkList * plList, visit v);
CircularLinkedList * InitCircularList();
void CreateCircularLinkedList(CircularLinkedList * pclList);
int IsCircularLinkedListEmpty(CircularLinkedList * pclList);
void DeleteCircularLinkedList(CircularLinkedList * pclList, int i, int *elem);
DoubleLinkedList * InitDouLinkedList();
void CreateDoubleLinkedList(DoubleLinkedList * pdlList);
void InsertDoubleLinkedList(DoubleLinkedList * pdlList, int i, int elem);
#endif
list.cpp
#include <stdio.h>
#include <stdlib.h>
#include "List.h"
///初始化链表，建立链表的头结点。
LinkList * InitList() {
LinkList * plList = NULL;
plList = (LinkList *)malloc(sizeof(LinkList));
plList->elem = 0;
plList->next = NULL;
return plList;
}
///建立链表，并赋值。
void CreateList(LinkList * plList) {
LinkList * temp = NULL;
LinkList * head = plList;
int value = 0;
while (scanf("%d", &value)) {
temp = (LinkList *)malloc(sizeof(LinkList));
temp->elem = value;
temp->next = NULL;
plList->next = temp;
plList = temp;
head->elem++;
}
}
/// 销毁链表
void DestroyList(LinkList * plList) {
LinkList * temp = NULL;
while (plList != NULL) {
temp = plList;
plList = plList->next;
free(temp);
}
}
///清空链表，只保留头结点
void ClearList(LinkList * plList) {
LinkList * head = NULL;
LinkList * temp = NULL;
head = plList;
plList = head->next;
while (plList != NULL) {
temp = plList;
plList = plList->next;
free(temp);
temp = NULL;
head->elem--;
}
head->next = NULL;
}
///判断链表是否为空
int IsListEmpty(LinkList * plList) {
int iRet = 0;
LinkList * head = NULL;
head = plList;
plList = head->next;
if (plList != NULL) {
iRet = 1;
}
return iRet;
}
///返回链表长度，头结点中保存长度
int GetListLength(LinkList * plList) {
int iRet = -1;
if (plList == NULL) {
return iRet;
}
iRet = plList->elem;
return iRet;
}
///获取第i个元素
void GetListElem(LinkList * plList, int i, int *elem) {
plList = plList->next;
*elem = -1;
int j = 0;
while (plList != NULL) {
++j;//第j个元素
if (j == i) {
*elem = plList->elem;
break;
}
plList = plList->next;
}
}
///查找数据元素 返回元素序号,元素存在返回序号，不存在返回0
int LocateListElem(LinkList * plList, int elem, compare comp){
int iRet = 0;
plList = plList->next;
int j = 0;
while (plList != NULL) {
++j;
if (!(*comp)(&elem,&plList->elem)) {
iRet = j;
break;
}
plList = plList->next;
}
return iRet;
}
///获取元素的前驱元素
int GetPriorListElem(LinkList * plList, int elem, int *priorElem, compare comp) {
int iRet = -1;
plList = plList->next;
while (plList != NULL&&plList->next != NULL) {
if (!(*comp)(&plList->next->elem,&elem)) {
*priorElem = plList->elem;
iRet = 0;
break;
}
plList = plList->next;
}
return iRet;
}
///获取当前元素的一下个元素
int GetNextListElem(LinkList * plList, int elem, int *nextElem, compare comp) {
int iRet = -1;
plList = plList->next;
while (plList != NULL && plList->next != NULL) {
if (!(*comp)(&plList->elem, &elem)) {
*nextElem = plList->next->elem;
iRet = 0;
break;
}
plList = plList->next;
}
return iRet;
}
///在位置i以前插入元素
void InsertListElem(LinkList * plList, int i, int elem) {
LinkList *head = plList;
int j = 1;
if (i < head->elem + 1) {
while (plList->next != NULL) {
if (j == i) {
LinkList *temp = (LinkList*)malloc(sizeof(LinkList));
temp->elem = elem;
temp->next = plList->next;
plList->next = temp;
head->elem++;
break;
}
plList = plList->next;
}
} else {
while (plList->next != NULL) {
plList = plList->next;
}
LinkList *temp = (LinkList*)malloc(sizeof(LinkList));
temp->elem = elem;
temp->next = NULL;
plList->next = temp;
head->elem++;
}
}
///删除第i个元素
int DeleteListElem(LinkList *plList, int i, int *elem) {
int iRet = -1;
LinkList * head = plList;
if (i <= head->elem) {
int j = 1;
while (plList->next != NULL) {
if (j == i) {
*elem = plList->next->elem;
LinkList * temp = plList->next;
plList->next = plList->next->next;
free(temp);
head->elem--;
iRet = 0;
break;
}
j++;
plList = plList->next;
}
}
return iRet;
}
///对每一个元素调用函数
void TraverseList(LinkList * plList, visit v) {
plList = plList->next;
while (plList != NULL) {
(*v)(&plList->elem);
plList = plList->next;
}
}
///初始化循环链表
CircularLinkedList * InitCircularList() {
CircularLinkedList * pclList = NULL;
pclList = (CircularLinkedList *)malloc(sizeof(CircularLinkedList));
pclList->elem = 0;
pclList->next = pclList;
return pclList;
}
///建立循环链表
void CreateCircularLinkedList(CircularLinkedList * pclList) {
int elem;
CircularLinkedList * head = pclList;
while (scanf("%d", &elem)) {
CircularLinkedList * temp = (CircularLinkedList *)malloc(sizeof(CircularLinkedList));
temp->elem = elem;
temp->next = head;
pclList->next = temp;
pclList = pclList->next;
head->elem++;
}
}
///判断循环链表是否为空
int IsCircularLinkedListEmpty(CircularLinkedList * pclList) {
int iRet = -1;
CircularLinkedList * head = pclList;
pclList = pclList->next;
if (pclList == head) {
iRet = 0;
}
return iRet;
}
///删除循环链表第i个元素
void DeleteCircularLinkedList(CircularLinkedList * pclList, int i, int *elem) {
CircularLinkedList * head = pclList;
if (i < head->elem + 1) {
int j = 1;
while (pclList->next != head) {
if (j == i) {
CircularLinkedList * temp = pclList->next;
*elem = temp->elem;
pclList->next = temp->next;
free(temp);
head->elem--;
break;
}
j++;
pclList = pclList->next;
}
}
}
///初始化双向链表
DoubleLinkedList * InitDouLinkedList() {
DoubleLinkedList * pdlList = NULL;
pdlList = (DoubleLinkedList *)malloc(sizeof(DoubleList));
pdlList->elem = 0;
pdlList->next = NULL;
pdlList->prior = NULL;
return pdlList;
}
///建立双向链表
void CreateDoubleLinkedList(DoubleLinkedList * pdlList) {
DoubleLinkedList * head = pdlList;
int elem;
while (scanf("%d", &elem)) {
DoubleLinkedList * temp = (DoubleLinkedList *)malloc(sizeof(DoubleLinkedList));
temp->elem = elem;
temp->next = NULL;
temp->prior = pdlList;
pdlList->next = temp;
pdlList = pdlList->next;
head->elem++;
}
}
///在第i个元素前插入元素
void InsertDoubleLinkedList(DoubleLinkedList * pdlList, int i, int elem) {
DoubleLinkedList * head = pdlList;
if (i < head->elem + 1) {
int j = 1;
while (pdlList->next != NULL) {
if (j == i) {
DoubleLinkedList * temp = (DoubleLinkedList *)malloc(sizeof(DoubleLinkedList));
temp->elem = elem;
temp->prior = pdlList;
temp->next = pdlList->next;
pdlList->next->prior = temp;
pdlList->next = temp;
head->elem++;
break;
}
j++;
pdlList = pdlList->next;
}
} else {
DoubleLinkedList * temp = (DoubleLinkedList *)malloc(sizeof(DoubleLinkedList));
temp->elem = elem;
while (pdlList->next != NULL) {
pdlList = pdlList->next;
}
temp->prior = pdlList;
temp->next = NULL;
pdlList->next = temp;
}
}