//双向链表
#include<stdio.h>
#include<malloc.h>
typedef struct Node{
int data;
struct Node *prior;
struct Node *next;
}* Linklist,DuLNode;
bool InitList(Linklist *L)//构造一个空的双向链表
{
(*L) = (Linklist)malloc(sizeof(DuLNode));//创建头结点，并使头指针指向头结点。
if((*L)==NULL)
return false;
(*L)->next = (*L);
(*L)->prior = (*L);
return true;
}
void DestoryList(Linklist *L)//销毁线性表(包括头结点)。
{
Linklist p,q;
p = (*L)->next;//指向第一个结点
while((*L)!=p)
{
q = p->next;
free(p);
p = q;
}
free(*L);
(*L) = NULL;
}
void ClearList(Linklist L)//将线性表清空（不包括头结点）
{
Linklist p,q;
p = L->next;//让p指向第一个结点
while(p!=L)
{
q = p->next;
free(p);
p = q;
}
L->next = L;
L->prior = L;
}
bool ListEmpty(Linklist L)//判断线性表是否为空
{
if(L->next==L->prior)
{
return true;
}
else
{
return false;
}
}
int ListLength(Linklist L)//返回线性表中数据元素个数
{
int i = 0;
Linklist p;
p = L->next;//头结点不作为链表的有效元素,p此时指向第一个结点。
while(p!=L)
{
i++;
p = p->next;
}
return i;
}
int GetElem(Linklist L,int item)//返回线性表第item个元素的值
{
Linklist p;
int i;
p = L->next;//让p指向第一个有效结点
for(i=1;i<item;i++)
{
if(p!=L)
p = p->next;
else{
printf("指定查询的位置不存在!\n");
return -1;
}
}
return p->data;
}
int LocateElem(Linklist L,int item)//返回线性表第一个与给定参数匹配的元素的位序，不存在则返回-1
{
Linklist p;
int i = 0;
p = L->next;
while(p!=L)
{
i++;
if(p->data==item)
return i;
p = p->next;
}
return -1;//表示返回指定位置元素失败
}
int PriorElem(Linklist L,int item)//返回线性表中，指定参数的前驱
{
Linklist p,before;
p = L->next;//p此时指向第一个有效结点
while(p->next!=L)//从第二有效结点开始遍历（第一有效结点的数据域即使和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;//p此时指向第一个有效元素
while(p->next!=L)
{
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-1)//获取第loc-1位置地址
{
p = p->next;
i++;
}
New = (Linklist )malloc(sizeof(DuLNode));
New->data = item;
New->next = p->next;
New->prior = p;
p->next = New;
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-1)//获取第loc-1位置地址
{
p = p->next;
i++;
}
q = p->next;//指向位于loc位置的结点
(*e) = q->data;
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
void ListTraverse(Linklist L)//将线性表进行遍历
{
Linklist p;
p = L->next;//指向第一个有效结点
while(p!=L)
{
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++)//向线性表中插入新元素
{
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;
}
网友评论