双向循环链表简单实现
DLoopLinkList.h
//// DLoopLinkList.h// 双向循环链表 2013/03//#ifndef DLOOP_LINK_LIST_H#define DLOOP_LINK_LIST_Htypedef int ElemType;typedef struct DLoopLinkList{ struct DLoopLinkList *prior; ElemType data; struct DLoopLinkList *next;}DLoopLinkList, *PtrDLoopLinkList;void InitDLoopLinkList(PtrDLoopLinkList);void DestoryDLoopLinkList(PtrDLoopLinkList);void InsertDLoopLinkList(PtrDLoopLinkList, int, ElemType);void ShowDLoopLinkList(PtrDLoopLinkList);void Append(PtrDLoopLinkList, ElemType);void Delete(PtrDLoopLinkList, int, ElemType *);#endif?DLoopLinkList.c
#include <stdlib.h>#include <stddef.h>#include <stdio.h>#include "DLoopLinkList.h"void InitDLoopLinkList(PtrDLoopLinkList ptrDLL){ ptrDLL->prior = ptrDLL; ptrDLL->next = ptrDLL;}typedef PtrDLoopLinkList PDLLL;void DestoryDLoopLinkList(PtrDLoopLinkList ptrDll){ PDLLL pite; // 用于遍历的指针 PDLLL temp; // 用于存放要删除的节点的临时指针 pite = ptrDll->next; // 指向首元节点 while(pite != ptrDll) { temp = pite; pite = pite->next; free(temp); } ptrDll->prior = NULL;}//// index表示插入到index之前//void InsertDLoopLinkList(PDLLL ptrDll, int index, ElemType data){ // 构建新节点 PDLLL newNode = NULL; PDLLL pIte = NULL; // 用来循环的指针 PDLLL pHead = ptrDll; // 头指针 int i = -1; newNode = (PDLLL)malloc(sizeof(DLoopLinkList)); newNode->data = data; pIte = pHead; // 初始化指向首元节点 // 遍历找到第i-1个节点 while(i < index - 1) { pIte = pIte->next; ++i; } //printf("i = %d, data = %d", i, pIte->data); if(i == index - 1) { //printf("call insert\n"); newNode->prior = pIte; pIte->next->prior = newNode; newNode->next = pIte->next; pIte->next = newNode; }}void ShowDLoopLinkList(PDLLL dllList){ PDLLL pIte; pIte = dllList->next; //printf("pIte = %p\n", pIte); while(pIte != dllList) { printf("%-4d",pIte->data); pIte = pIte->next; } printf("\n");}void Append(PtrDLoopLinkList pdl, ElemType data){ // 创建一个节点 PDLLL newNode = (PDLLL)malloc(sizeof(DLoopLinkList)); newNode->data = data; newNode->next = pdl->prior->next; pdl->prior->next = newNode; newNode->prior = pdl->prior; pdl->prior = newNode;}void Delete(PtrDLoopLinkList pdl, int index, ElemType * pData){ int i = 0; PDLLL pIte = pdl->next; while(i < index && pIte != pdl) { pIte = pIte->next; ++i; } if(i == index && pIte != pdl) { *pData = pIte->data; pIte->prior->next = pIte->next; pIte->next->prior = pIte->prior; free(pIte); }}?main.c
#include <stdio.h>#include "DLoopLinkList.h"#define Insert InsertDLoopLinkListint main(int argc, char* argv[]){ DLoopLinkList dl; int i = 0; ElemType e; InitDLoopLinkList(&dl); for(; i < 100; ++i) { Append(&dl, i); } Insert(&dl, 100, 100); Insert(&dl, 0, 100); Insert(&dl, 1, 101); Delete(&dl, 0, &e); printf("The element which be deleted:%d\n", e); Delete(&dl, 101, &e); printf("The element which be deleted:%d\n", e); ShowDLoopLinkList(&dl); printf("<<ShowDLoopLinkList>> ends.\n"); DestoryDLoopLinkList(&dl);}?