单循环链表的另一种实现方式【虽然不如教材的经典,希望大家帮挑下缺点】
#include<stdio.h>#include<stdbool.h>
#include<stdlib.h>
typedef struct circularlinklist{
//数据域
int data;
//指针域
struct circularlinklist *pNext;
} CirLinkList,*pCirLinkList;
//创建一个空的循环链表
pCirLinkList CreateEmptyCircularLinkList(void);
//判断循环链表是否为空
_Bool is_empty(pCirLinkList pnode);
//获取相对于pnode节点偏移i个节点的地址,i必须满足条件:i>=0
pCirLinkList GetNodeAddress(pCirLinkList pnode, int i);
//在相对于pnode节点偏移i个节点的后面插入1个节点,i必须满足条件:i>=0
void InsertNode(pCirLinkList pnode, int i);
//在相对于pnode节点偏移i个节点的后面插入n个节点,必须满足条件:i>=0 && n>=0
void InsertnNode(pCirLinkList pnode, int i, int n);
//统计循环链表的当前节点总数并返回计数值
int NodeSumCount(pCirLinkList pnode);
//返回相对于pnode节点偏移i个节点中的数据域,必须满足条件:i>=0
int GetNodeData(pCirLinkList pnode, int i);
//往节点中填充随机数据
void InputData(pCirLinkList pnode);
//函数功能:删除相对于pnode节点偏移的第i个节点,必须满足条件:i>=1
//如果为空循环链表,则无视后2个参数,等效于销毁操作,销毁完成后将*ppnode置为NULL
//如果pnode指向将要被删除的节点,则删除完成后,该函数会将*ppnode置为被删除节点的下一个节点的地址
//如果pnode没有指向要删除的节点,则删除完成后,该函数不会改变*ppnode中的值
void DeleteNode(pCirLinkList pnode, pCirLinkList *ppnode, int i);
//函数功能:删除相对于pnode节点偏移的第i个节点后的n个节点(包括第i个节点在内)
//如果为空循环链表,则无视后3个参数,等效于销毁操作,销毁完成后将*ppnode置为NULL
//如果i>=1&&i<=节点总数-1,则必须满足条件:i>=1+节点总数*m && i<=节点总数-1+节点总数*m && n>=1 && n<=节点总数-i(其中 m=0,1,2...)
//如果i>节点总数-1,则必须满足条件:i>=1+节点总数*m && i<=节点总数-1+节点总数*m && n>=1 && n<=节点总数-(i-节点总数*t)(其中 t满足i=k+节点总数*t,k>=1&&k<=节点总数-1)
void DeletenNode(pCirLinkList pnode, pCirLinkList *ppnode, int i, int n);
int main(void)
{
pCirLinkList pnode = CreateEmptyCircularLinkList();
InsertnNode(pnode, 0, 9);
InputData(pnode);
for (int i = 0; i <= 9; i++)
{
printf("%4d\t", GetNodeData(pnode, i));
}
DeletenNode(pnode, &pnode, 3, 7);
printf("\n\n");
for (int i = 0; i <= 9; i++)
{
printf("%4d\t", GetNodeData(pnode, i));
}
printf("\n\n");
printf("当前节点总数=%d\n", NodeSumCount(pnode));
system("pause");
return 0;
}
pCirLinkList CreateEmptyCircularLinkList(void)
{
pCirLinkList pnode = (pCirLinkList)malloc(sizeof(CirLinkList));
pnode->pNext = pnode;//使节点的pNext指针指向该节点本身
return pnode;
}
_Bool is_empty(pCirLinkList pnode)
{
if (pnode == pnode->pNext)
{
return true;
}
else
{
return false;
}
}
pCirLinkList GetNodeAddress(pCirLinkList pnode, int i)
{
if (i < 0)
{
return NULL;
}
for (int j = 1; j <= i; j++)
{
pnode = pnode->pNext;
}
return pnode;
}
void InsertNode(pCirLinkList pnode, int i)
{
if (i < 0)
{
return;
}
pCirLinkList pfront = GetNodeAddress(pnode, i);
pCirLinkList pback = GetNodeAddress(pnode, i + 1);
pfront->pNext = (pCirLinkList)malloc(sizeof(CirLinkList));
pfront->pNext->pNext = pback;
return;
}
void InsertnNode(pCirLinkList pnode, int i, int n)
{
if (i < 0 || n < 0)
{
return;
}
for (int j = i; j <= i + n - 1; j++)
{
InsertNode(pnode, j);
}
return;
}
int NodeSumCount(pCirLinkList pnode)
{
int i = 0;
while (i == 0 || GetNodeAddress(pnode, i) != pnode)
{
i++;
}
return i;
}
int GetNodeData(pCirLinkList pnode, int i)
{
if (i < 0)
{
return -32767;
}
return GetNodeAddress(pnode, i)->data;
}
void InputData(pCirLinkList pnode)
{
int len = NodeSumCount(pnode), i;
srand(time(NULL));
for (i = 0; i <= len - 1; i++)
{
GetNodeAddress(pnode, i)->data=rand()%90+10;
}
return;
}
void DeleteNode(pCirLinkList pnode, pCirLinkList *ppnode, int i)
{
if (is_empty(pnode))//如果为空表,则等效于销毁操作
{
free(GetNodeAddress(pnode, 0));
*ppnode = NULL;
return;
}
if (i < 1)
{
return;
}
pCirLinkList pfront = GetNodeAddress(pnode, i - 1);
pCirLinkList pback = GetNodeAddress(pnode, i + 1);
pCirLinkList pmiddle = GetNodeAddress(pnode, i);
free(GetNodeAddress(pnode, i));
pfront->pNext = pback;
if (pnode == pmiddle)//pnode指向被删除的节点的情况
{
*ppnode = pback;
}
return;
}
void DeletenNode(pCirLinkList pnode, pCirLinkList *ppnode, int i, int n)
{
int k, m;
int sum = NodeSumCount(pnode);
if (is_empty(pnode))//如果为空表,则等效于销毁操作
{
DeleteNode(pnode, ppnode, 0);
return;
}
for (k = 1; k <= sum - 1; k++)//检测i是否等于k+节点总数*m
{
if ((i - k) % sum == 0 && i >= 1)
{
m = (i - k) / sum;//存储整数倍率
break;
}
}
if (k == sum)//如果k==sum,说明i!=k+节点总数*m || i<1
{
return;
}
if (i >= 1 && i <= sum - 1)
{
if (n<1 || n>NodeSumCount(pnode) - i)
{
return;
}
}
else if (i > sum - 1)
{
if (n<1 || n>NodeSumCount(pnode) - (i - sum*m))
{
return;
}
}
for (int j = i + n - 1; j >= i; j--)
{
DeleteNode(pnode, ppnode, j);
}
return;
}
支持 就是来顶 支持 楼主注意 下 格式 这样 可以看得更清楚点啊
页:
[1]