《线性表---链表的基本操作》

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0
typedef int Status; //函数结果状态
typedef int ElemType; //数据元素类型
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

//逆序输入n个元素的值，创建一个带头结点的单链表L
void CreatList_L(LinkList &L,int n)
{
int i;
LinkList p;
L = (LinkList)malloc(sizeof(LNode));
L->data = 0; //令表头的数据域内的数据值为0
//（表头数据域内的值记录了此带头结点的单链表中的数据元素个数）
L->next = NULL; //先建立一个带头结点的单链表
for(i = n;i>0;--i)
{
p = (LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next = L->next;
L->next = p;
L->data++; //增加带头结点的单链表中的数据元素个数
}
}

//带表头结点的单链表的插入
Status ListInsert_L(LinkList &L,int i,ElemType e)
{//在带头结点的单链线性表L中的第i个位置之前插入元素e
LinkList p,s;
int j;
p = L;
j = 0;
while(p && j<i-1)
{//寻找第i-1个结点
p = p->next;
++j;
}
if(!p || j>i-1)
//i小于1或者大于表长加1
return ERROR;
s = (LinkList)malloc(sizeof(LNode)); //生产新结点
s->data = e;
s->next = p->next;
p->next = s;
L->data++; //累加带头结点的单链表L中数据的个数
return OK;
}

//带表头节点的删除
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
LinkList p,q;
p = L;
int j = 0;
while(p->next && j<i-1)
{//寻找第i个结点，并令p指向其前驱
p = p->next;
++j;
}
if(!(p->next) || j>i-1)
return ERROR;
q = p->next;
p->next = q->next;
e = q->data;
free(q); //释放结点q
L->data--;
return OK;
}

//求带头结点的单链表的长度
Status LengthList_L(LinkList L)
{
int num = 0;
LinkList p;
p = L->next;
while(p)
{
num++;
p = p->next;
}
return num;
}

//遍历带头结点的单链表
Status PrintList_L(LinkList L)
{
LinkList p;
p = L->next;
//printf("这个单链表中有%d个数据 ",L->data);
while(p)
{
printf("%4d->",p->data);
p = p->next;
}
printf("NULL ");
return OK;
}

//查找带头结点单链表的元素
Status GetElem_L(LinkList L,int i,ElemType &e)
{//查找单链表中第i个元素，若存在，其值赋给e，并输出其值
LinkList p;
p = L->next;
int j = 1;
while(p && j<i)
{
p = p->next;
++j;
}
if(!p || j>i)
return ERROR; //第i个元素不存在
e = p->data;
return e;
}

//删除指定两个位置之间的数据(链表中的元素递增有序排列)
Status DeleteListBetween_L(LinkList &L,int mink,int maxk)
{
LinkList p,q;
p = L;
while(p->next && p->next->data<=mink)
p = p->next; //p是最后一个不大于mink的元素
if(p->next) //如果还有比mink更大的元素
{
q = p->next;
while(q->data<maxk)
q = q->next; //q是第一个不小于maxk的元素
p->next = q;
}
return OK;
}

//主函数
int main()
{
LinkList L;
int n = 8,i_1,i_2,e_1,e_2,e_3,e_4,e_5;

//调用CreatList_L函数，创建一个单链表
printf("请输入初始化单链表中元素的个数：");
scanf("%d",&n);
printf("请输入初始单链表的数据：(由大到小依次输入，以空格键分开) ");
CreatList_L(L,n);
printf("带头结点的单链表已初始化完毕... ");

//调用GetElem_L函数，查找带头结点单链表第i个元素
printf("请输入你要查找的元素的序号：");
scanf("%d",&i_1);
printf("你查找的第%d个元素是:%d",i_1,(GetElem_L(L,i_1,e_1)));
printf(" ");

//调用ListInsert_L函数，向带头结点的单链表中插入元素
printf("请输入插入的位置：");
scanf("%d",&i_2);
printf("请输入要插入的元素：");
scanf("%d",&e_2);
ListInsert_L(L,i_2,e_2);
printf(" ");

//调用LengthList_L函数，求出此时带头结点的单链表的长度
printf("此时单链表的长度为：%d",LengthList_L(L));
printf(" ");

//调用PrintList_L函数，遍历带头结点的单链表
printf("当前带头结点的单链表中的数据元素如下： ");
PrintList_L(L);
printf(" ");

//调用ListDelete_L函数，删除指定位置的元素
printf("请输入你要删除的位置：");
scanf("%d",&e_3);
ListDelete_L(L,e_3,e_4);
//调用LengthList_L函数，求出此时带头结点的单链表的长度
printf("此时单链表的长度为：%d",LengthList_L(L));
printf(" ");
//调用PrintList_L函数，遍历带头结点的单链表
printf("当前带头结点的单链表中的数据元素如下： ");
PrintList_L(L);
printf(" ");

//调用DeleteListBetween_L函数，删除指定两个位置之间的元素
printf("删除a和b之间的元素，请输入：");
scanf("%d%d",&e_4,&e_5);
DeleteListBetween_L(L,e_4,e_5);
//调用LengthList_L函数，求出此时带头结点的单链表的长度
printf("此时单链表的长度为：%d",LengthList_L(L));
printf(" ");
//调用PrintList_L函数，遍历带头结点的单链表
printf("当前带头结点的单链表中的数据元素如下： ");
PrintList_L(L);
printf(" ");

return 0;
}