数据结构----循环链表

CycLinkList.h

#ifndef __CYCLINKLIST_H #define __CYCLINKLIST_H #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> typedef int ElemType; typedef struct Node //定义结点 { ElemType data; struct Node *next; }Node; /* //定义带头结点的链表 typedef struct Linklist { struct Node head; int count; }Linklist, *pList; */ //定义不带头结点的链表 typedef struct Linklist { struct Node *head; int count; }Linklist, *pList; void InitLinkList(pList list); void InsertLinkList(pList list, ElemType val, int pos); void InsertHeadLinkList(pList list, ElemType val); void InsertTailLinkList(pList list, ElemType val); void DeleteLinkList(pList list, int pos); void DeleteHeadLinkList(pList list); void DeleteTailLinkList(pList list); void ShowLinkLIst1(pList list); void ShowLinkLIst2(pList list); #endif

CycLinkList.c

#include"CycLinkList.h" //不带头结点的循环链表 void InitLinkList(pList list)//初始化链表 { list->count = 0; list->head = NULL; } static Node *BuyNode(ElemType val, Node *next) { Node *p = ( Node *)malloc(sizeof(Node)); assert( p != NULL); p->data = val; if( next == NULL)//考虑链表中没有结点时的情况 { p->next = p; return p; } p->next = next; return p; } void InsertLinkList(pList list, ElemType val, int pos) //插入结点 { if( pos < 0 || pos > list->count) { printf("pos is error\n"); return ; } if(list->head == NULL)//考虑链表中没有结点时的插入 { list->head = BuyNode(val, NULL); //给头结点赋值 list->count++; return; } Node *p = list->head; int tmpos = pos == 0 ? list->count : pos;//若为头插则相当于尾插后前移头指针 while( tmpos > 1) { p =p->next; tmpos --; } Node *s = BuyNode(val, p->next); p->next = s; if(pos == 0) //如果pos为0即为头插,则改变头指针位置 { list->head = s; } list->count++; //增加结点个数 } void InsertHeadLinkList(pList list, ElemType val) //头插 { InsertLinkList(list, val, 0); } void InsertTailLinkList(pList list, ElemType val) //尾插 { InsertLinkList(list, val, list->count); } void DeleteLinkList(pList list, int pos) //删除结点 { assert(list != NULL); if(pos < 1 || pos > list->count) { printf("pos is error\n"); return ; } if(list->count == 1) { free(list->head); list->head = NULL; list->count--; } Node *p = list->head; if( pos == 1) { while( p->next != list->head) { p = p->next; } list->head = list->head->next; } else { while( pos > 2) { p = p->next; pos --; } } Node *q = p->next; p->next = q->next; free(q); list->count--; } void DeleteHeadLinkList(pList list) //头删 { DeleteLinkList(list, 1); } void DeleteTailLinkList(pList list) //尾删 { DeleteLinkList(list, list->count); } void ShowLinkLIst1(pList list) //输出打印 { assert(list != NULL); Node *p = list->head; while( p->next != list->head) { printf("%3d",p->data); p = p->next; } printf("%3d\n",p->data); } void ShowLinkLIst2(pList list) { assert(list != NULL); Node *p = list->head; int tmp = list->count; while(tmp > 0) { printf("%3d",p->data); p =p->next; tmp --; } printf("\n"); }

main.c

#include "CycLinkLIst.h" int main() { Linklist list; InitLinkList(&list); for( int i = 0; i < 5; i++) { InsertLinkList(&list, i * 10, i); } ShowLinkLIst1(&list); for( int j = 3; j > 0; j--) { DeleteLinkList(&list, j); ShowLinkLIst1(&list); } ShowLinkLIst2(&list); return 0; }