//循环链表(容易忽略尾指针所指向的尾节点)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Ndoe{
int data;
struct Ndoe *next;
} Linklist;
bool InitList(Linklist** L)//构造一个空的循环链表（注：L表示尾指针）
{
(*L) = (Linklist *)malloc(sizeof(Linklist));//创建头结点，并使尾指针指向头结点。
if((*L)==NULL)
return false;
(*L)->next = (*L);
return true;
}
void DestoryList(Linklist **L)//销毁循环链表(包括头结点)。
{
Linklist *p,*q;
p = (*L)->next;//p指向头结点
while((*L)!=p->next)
{
q = p->next;//q指向第一个结点
free(p);
p = q;
}
free(p);
(*L) = NULL;//因为此处修改了尾指针，故参数类型为Linklist **。
}
void ClearList(Linklist **L)//将循环链表清空（不包括头结点）成功的标志是尾指针指向头结点
{
Linklist *p,*q;
p = (*L)->next->next;//让p指向第一个有效结点
while(p!=(*L))
{
q = p;//q此时指向第一个有效结点
p = p->next;
free(q);
}
*L = p->next;//释放掉尾节点
free(p);
}
bool ListEmpty(Linklist *L)//判断线性表是否为空
{
if(L->next==L)//当尾指针指向头结点时才会出现这种效果，也即循环链表为空。
{
return true;
}
else
{
return false;
}
}
int ListLength(Linklist *L)//返回循环链表中数据元素个数
{
int i = 0;
Linklist *p;
p = L->next->next;//指向第一个有效结点
while(p!=L)
{
i++;
p = p->next;
}
return i+1;//加1表示尾指针所指向的那个节点
}
int GetElem(Linklist *L,int item)//返回线性表第item个元素的值
{
Linklist *p;
int i;
p = L->next->next;//让p指向第一个有效结点
for(i=1;i<item;i++)
{
if(p!=L->next){
p = p->next;
}
else{
printf("指定查询的位置不存在!\n");
return -1;
}
}
if(p!=L->next)//此步不能少
return p->data;
else
return -1;
}
int LocateElem(Linklist *L,int item)//返回线性表第一个与给定参数匹配的元素的位序，不存在则返回-1
{
Linklist *p;
int i = 0;
p = L->next->next;
while(p!=L->next)
{
i++;
if(p->data==item)
return i;
p = p->next;
}
return -1;//表示返回指定位置元素失败
}
int PriorElem(Linklist *L,int item)//返回线性表中，指定参数的前驱
{
Linklist *p,*before;
p = L->next->next;//p此时指向第一个有效元素
while(p->next!=L->next)//从第二有效元素开始遍历（第一有效元素的数据域即使和item相等，也不存在前驱。）
{
before = p;
p = p->next;//p此时指向第二个有效元素
if(p->data==item)
return before->data;
//p = p->next;
}
return -1;//表示返回指定位置元素失败
}
int NextElem(Linklist *L,int item)//返回线性表中，指定参数的后继
{
Linklist *p,*tail;
p = L->next->next;//p此时指向第一个有效元素
while(p->next!=L->next)//如果一个链表只有一个有效结点同样不存在后继
{
tail = p->next;
if(p->data==item)//最后一个元素是不存在后继的
return tail->data;
p = tail;
}
return -1;//表示返回指定位置元素失败
}
bool ListInsert(Linklist **L,int loc,int item)//向线性表指定位置插入元素
{
Linklist *p,*New;
int i=1;//设置为1，很重要哦
if((*L)==NULL||loc>ListLength(*L)+1||loc<1)//销毁后就不能插入数据了
return false;
p = (*L)->next;//指向头结点
while(i<loc)//获取第loc-1位置地址
{
p = p->next;
i++;
}
New = (Linklist *)malloc(sizeof(Linklist));
New->data = item;
New->next = p->next;
p->next = New;
if(p==(*L))
(*L) = New;//改变了尾指针，所以使用Linklist **类型。
return true;
}
bool ListDelete(Linklist **L,int loc,int *e)//删除线性表第i个位置的元素，并把删除元素返回
{
Linklist *p,*q;
int i=1;
if(*L==NULL||loc>ListLength(*L)||loc<1)
return false;
p = (*L)->next;//指向头结点
while(i<loc)//获取第loc-1位置地址
{
p = p->next;
i++;
}
q = p->next;//指向位于loc位置的结点
(*e) = q->data;
p->next = q->next;
if((*L)==q)
(*L) = p;
free(q);
return true;
}
void ListTraverse(Linklist *L)//将线性表进行遍历
{
Linklist *p;
p = L->next->next;//指向第一个有效结点
while(p!=L->next)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
int main()
{
Linklist* L;
int i,e;
if(!InitList(&L))//初始化线性表
{
printf("抱歉，内存分配失败！\n");
}
for(i=1;i<=13;i++)//向线性表中插入新元素
{
//printf("插入的位置:%d\n",i);
if(!ListInsert(&L,i,i))
{
printf("插入失败\n");
return 0;
}
}
//ListInsert(L,2,6666);
ListTraverse(L);//遍历线性表
//DestoryList(&L);//销毁线性表（破坏表结构）
//ListTraverse(L);//遍历线性表
//ClearList(L);/清空线性表（不破坏表结构）
ListDelete(&L,2,&e);//删除线性表指定位置元素
printf("线性表被删除的元素是：%d\n",e);
printf("执行删除操作后的线性表:");
ListTraverse(L);//遍历线性表
if(PriorElem(L,3)!=-1)//获取值为3的元素的前驱
{
printf("元素3的前驱为：%d\n",PriorElem(L,3));
}
else
{
printf("查询的元素可能不存在或者位于线性表的第一个位置不存在前驱！\n");
}
if(NextElem(L,3)!=-1)//获取值为3的元素的后继
{
printf("元素3的后继为：%d\n",NextElem(L,3));
}
else
{
printf("查询的元素可能不存在或者位于线性表的最后一个位置不存在后继！\n");
}
if(LocateElem(L,3)!=0)//查询指定元素在线性表中的位置
{
printf("值为3的元素在线性表中的位置：%d\n",LocateElem(L,3));
}
else
{
printf("你所查询的元素不存在\n");
}
return 0;
}
网友评论