数据结构——双向链表简单操作(C语言)

xiaoxiao2021-02-28  17

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status是函数的类型,其值是函数结果状态码 typedef int Status; typedef int ElemType; //顺序表存储元素类型, 考虑到可移植性, 若改变存储类型, 只需修改这一处,比较方便 typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList; Status InitList(DuLinkList *L); Status ListInsert(DuLinkList L, int i, ElemType e); int ListLength(DuLinkList L); void Traverse(DuLinkList L); DuLinkList GetElemP(DuLinkList L, int i); void ClearList(DuLinkList L); Status Destroy(DuLinkList *L); void vd(ElemType c) ; void ListTraverse(DuLinkList L,void(*visit)(ElemType)) ; void Re_Traverse(DuLinkList L); void main() { DuLinkList L; int i; InitList(&L); for(i=1; i<=4; i++) ListInsert(L,i, i); //在第i个结点之前插入i printf("正序输出链表:\n"); Traverse(L); printf("L = %d\n", ListLength(L)); printf("逆序输出链表:\n"); Re_Traverse(L); Destroy(&L); } //初始化一个空的双链表 Status InitList(DuLinkList *L) { (*L) = (DuLinkList)malloc(sizeof(DuLNode)); if(L == NULL) { printf("内存分配失败!\n"); return FALSE; } (*L)->prior = (*L)->next = (*L); //使头结点的两个指针域指向本身 return OK; } //在带头结点的双向循环链表L中第i个位置之前插入元素e, // 1 < i < 表长+1 Status ListInsert(DuLinkList L, int i, ElemType e) { DuLinkList s; DuLinkList p; if(i < 1 || i > ListLength(L)+1) return ERROR; p = GetElemP(L, i - 1); //使p指向第i个元素的位置 if(!p) return ERROR; s = (DuLinkList)malloc(sizeof(DuLNode)); //s为存储新插入元素的结点 if(!s) exit(OVERFLOW); s->data = e; s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; return OK; } //返回双向链表的长度 int ListLength(DuLinkList L) { DuLinkList p; int i; p = L->next; //使p指向头结点 i = 0; while(p != L) { i++; p = p->next; } return i; } //返回指向第i个结点的指针 DuLinkList GetElemP(DuLinkList L, int i) { DuLinkList p; int j; p = L; for(j = 1; j <= i; j++) p = p->next; return p; } //遍历结点正序输出 void Traverse(DuLinkList L) { DuLinkList p; int i; i = 0; p = L->next; while(p != L) { i++; printf("第%d个结点的数据是:%d\n", i, p->data); p = p->next; } } //遍历结点逆序输出 void Re_Traverse(DuLinkList L) { DuLinkList p; int i; i = ListLength(L); p = L->prior; while(p != L) { printf("第%d个结点的元素是:%d\n", i, p->data); i--; p = p->prior; } } void ListTraverse(DuLinkList L,void(*visit)(ElemType)) { //操作结果:由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit() DuLinkList p = L->next; while(p!=L) { visit(p->data); p = p->next; } printf("\n"); } void vd(ElemType c) { printf("%d ",c); } //将双向链表L重置为空表 void ClearList(DuLinkList L) { DuLinkList p, q; p = L->next; while(p != L) { q = p->next; free(p); p = q; } L->prior = L->next = L; //使头结点的两个指针域都指向自己 } //销毁双向链表L Status Destroy(DuLinkList *L) { DuLinkList p, q; p = (*L)->next; while(p != (*L)) { q = p->next; free(p); p = q; } free((*L)); (*L) = NULL; return OK; }
转载请注明原文地址: https://www.6miu.com/read-2450044.html

最新回复(0)