双向链表实现线性表

//程序功能：以双向链表的形式实现数据表的建立、重置、销毁，数据的查询、插入、删除等
//注意：若表中存在两个相同元素，则部分操作（如查找，返回前趋、后继等）均在第一个元素上进行
#include
#include
#include

typedef struct link //定义指针
{
int data; //数据域
struct link *prior; //指向前驱的指针域
struct link *next; //指向后继的指针域
}link;

int qs=0; //中间指针的位置
int i=0; //线性表中元素个数
link *q=NULL; //中间指针

struct link *InitList(); //构造空线性表
struct link *DestroyList(link *head); //销毁线性表
int ClearList(link *head); //重置线性表
int ListEmpty(link *head); //判断链表是否为空
int ListLength(link *head); //返回线性表中元素个数
int GetElem(link *head); //返回表中某个元素
int LocateElem(link *head); //查找表中某元素
int PriorElem(link *head); //返回某元素前驱
int NextElem(link *head); //返回某元素后继
int ListInsert(link *head); //插入新数据
int ListDelete(link *head); //删除数据
int ListTraverse(link *head); //打印表中每个元素
int ListInserts(link *head); //插入多个新数据

int OrderJudge(int seat); //比较seat与当前指针q和头指针间的距离
int InputCheck(char a[11]); //输入字符检查

int main()
{
char order[11]; //选择录入
link *head=NULL;
printf("-----------------------------------------------------------------\n");
printf("01 构造一个空的线性表 \n");
printf("02 销毁该线性表 \n");
printf("03 重置该线性表 \n");
printf("04 检查该线性表是否为空 \n");
printf("05 返回线性表中元素个数 \n");
printf("06 返回该线性表中某个值 \n");
printf("07 查找该线性表中的元素 \n");
printf("08 返回表中某元素的前驱 \n");
printf("09 返回表中某元素的后继 \n");
printf("10 在表中插入新的元素 \n");
printf("11 删除线性表中某元素 \n");
printf("12 打印表中的每个元素 \n");
printf("13 一次性插入多个元素 \n");
printf("00 退出程序 \n");
printf("-----------------------------------------------------------------\n");

do{
do{
printf("请输入目的对应的选择项（01-13）:");
scanf("%s",&order);
}while((InputCheck(order)!=0)||((strcmp(order,"00"))<0)||((strcmp(order,"13"))>0));
printf("\n");
if((strcmp(order,"00"))==0)
;
else if((strcmp(order,"01"))==0)
head=InitList();
else if((strcmp(order,"02"))==0)
head=DestroyList(head);
else if((strcmp(order,"03"))==0)
{
if(ClearList(head)==1);
else
printf("已重置\n");
}
else if((strcmp(order,"04"))==0)
ListEmpty(head);
else if((strcmp(order,"05"))==0)
ListLength(head);
else if((strcmp(order,"06"))==0)
GetElem(head);
else if((st

rcmp(order,"07"))==0)
LocateElem(head);
else if((strcmp(order,"08"))==0)
PriorElem(head);
else if((strcmp(order,"09"))==0)
NextElem(head);
else if((strcmp(order,"10"))==0)
ListInsert(head);
else if((strcmp(order,"11"))==0)
ListDelete(head);
else if((strcmp(order,"12"))==0)
ListTraverse(head);
else if((strcmp(order,"13"))==0)
ListInserts(head);
else
printf("输入错误\n");
printf("-----------------------------------------------------------------\n");
}while((strcmp(order,"00"))!=0);
return 0;
}

int InputCheck(char a[11]) //输入字符检查
{
int j=1;
if(a[0]>='0'&&a[0]<='9')
;
else if(a[0]!='-') //输入不是数字
return 1;
for(j=1;a[j]!='\0';j++)
{
if(a[j]<'0'||a[j]>'9') //输入不是数字
return 1;
else;
}
if(a[0]=='-'&&j==1) //输入为“-”
return 1;
else if(j!=2) //输入为三位及以上或一位数
return 2;
else //输入为两位数
return 0;

}

struct link *InitList() //构造空线性表
{
link *head;
head=(link*)malloc(sizeof(link));
q=(link*)malloc(sizeof(link));
if((q==NULL)||(head==NULL))
{
printf("内存不足\n");
exit(0);
}
else
{
head->data=0; //头结点初始化
head->next=NULL;
head->prior=NULL;
q=head; //中间指针指向头结点
printf("空线性表构造成功\n");
i=0;
}
return head;
}

struct link *DestroyList(link *head) //销毁线性表
{
if(head==NULL)
printf("线性表不存在\n");
else
{
if(head->next==NULL); //空表
else
ClearList(head);
head=NULL;
printf("已销毁\n");
}
return head;
}

int ClearList(link *head) //重置线性表
{
link *pr=head,*p=NULL;
if(head==NULL)
{
printf("线性表不存在\n");
return 1;
}
else if(head->next==NULL) //空表
return 0;
else //清空
{
pr=pr->next; //头结点指向第一位元素
while((pr->next)!=NULL)
{
p=pr;
pr=pr->next;
p->prior->next=pr;
pr->prior=p->prior;
free(p);
i=i-1;
}
pr->prior->next=NULL;
free(pr);
i=i-1;
q=head;
qs=0;
return 0;
}
}

int ListEmpty(link *head) //判断链表是否为空
{
if(head==NULL)
{
printf("线性表不存在\n");
return 1;
}
else if(head->next==NULL)
{
printf("线性表为空\n");
return 1;
}
else
{
printf("表中元素个数为%d\n",i);
return 0;
}
}

int ListLength(link *head) //返回线性表中元素个数
{
if(head==NULL)
{
printf("线性表不存在\n");
return 1;
}
else
{
printf("表中元素个数为%d\n",i);
return 0;
}
}

int OrderJudge(int seat) //比较seat与当前指针q和头指针间的距离且移动相应指针位置
{
if(seat>i)//元素插在链表末端
{
while(q->next!=NULL){
q=q->next;
qs=qs+1;
}
return 1;
}
else if(qs

在seat之前
{
while(qs!=(seat-1)){
q=q->next;
qs=qs+1;
}
return 2;
}
else if((qs>=seat)&&((qs-seat){
while(qs!=(seat-1)){
q=q->prior;
qs=qs-1;
}
return 3;
}
else //移动头指针插入新元素
return 4;
}

int GetElem(link *head) //输入元素位次返回表中某个元素
{
int k,seat;
int j=0;
link *pr=head;
if(ListEmpty(head)==1) //调用函数判断链表是否存在
; //链表不存在或为空
else
{
do{
printf("输入想要返回元素的位次：");
scanf("%d",&seat);
}while((seat<1)||(seat>i));
k=OrderJudge(seat);
if((k==1)||(k==2)||(k==3))
{
q=q->next;
qs=qs+1;
printf("第%5d个数据为%10d\n",qs,q->data);
}
else
{
while(j!=(seat-1)){
pr=pr->next;
j=j+1;
}
pr=pr->next;
printf("第%5d个数据为%10d\n",seat,pr->data);
}
}
return 0;
}

int LocateElem(link *head) //查找表中某元素
{
int data,j=1;
link *pr=head;
if(ListEmpty(head)==1) //调用函数判断链表是否存在
; //链表不存在或为空则退出
else
{
printf("输入想要查找的数据：");
scanf("%d",&data);
pr=pr->next;
while(((pr->data)!=data)&&((pr->next)!=NULL)){
pr=pr->next;
j=j+1;
}
if((pr->data)==data)
printf("数据%10d是表中第%5d个元素\n",data,j);
else
printf("该数据不存在\n");
}
return 0;
}

int PriorElem(link *head) //返回某元素前驱
{
int data;
link *pr=head;
if(ListEmpty(head)==1) //调用函数判断链表是否存在
; //链表不存在或为空则退出
else
{
printf("输入截止数据：");
scanf("%d",&data);
pr=pr->next; //头结点指向第一个元素
while(((pr->data)!=data)&&((pr->next)!=NULL)){
pr=pr->next;
}
if((pr->data)==data)
{
if(pr->prior==head) //该元素为第一个元素
printf("该元素无前驱\n");
else
{
printf("该元素前驱为：\n");
do{
pr=pr->prior;
printf("%10d\n",pr->data);
}while((pr->prior)!=head);
}
}
else
printf("该元素不存在\n");
}
return 0;
}

int NextElem(link *head) //返回某元素后继
{
int data;
link *pr=head;
if(ListEmpty(head)==1) //调用函数判断链表是否存在
; //链表不存或为空在则退出
else
{
printf("输入起始数据：");
scanf("%d",&data);
pr=pr->next;
while(((pr->data)!=data)&&((pr->next)!=NULL)){
pr=pr->next;
}
if((pr->data)==data)
{
if(pr->next==NULL)
printf("该元素无后继\n");
else
{
printf("该元素后继为：\n");
do{
pr=pr->next;
printf("%10d\n",pr->data);
}while((pr->next)!=NULL);
}
}
else
printf("该元素不存在\n");
}
return 0;
}

int ListInsert(link *head) //插入新数据
{

int newdata,seat,k; //新数据及其位次及OrderJudge返回值
int j=0;
link *pr=head,*p=NULL;
if(ListLength(head)==1) //调用函数判断链表是否存在
return 1; //链表不存在则退出
else
{
p=(link*)malloc(sizeof(link));
if(p==NULL)
{
printf("内存不足\n");
exit(0);
}

do{
printf("希望新数据的位置为（如：第一位请输入1，停止插入请输入-1）：");
scanf(" %d",&seat);
}while((seat<(-1))||(seat>(i+1))||(seat==0)); //seat至多比链表元素数多一
if(seat==(-1)) //停止插入
return 1;
else
{
printf("输入想要插入线性表中的新数据为：");
scanf(" %d",&newdata);
p->data=newdata;
p->next=NULL;
p->prior=NULL;

k=OrderJudge(seat);
if(k==1) //元素插在链表末端
{
q->next=p;
p->prior=q;
qs=i;
}
else if((k==2)||(k==3))
{
p->next=q->next;
p->prior=q;
q->next=p;
p->next->prior=p;
}
else //移动头指针插入新元素
{
while(j!=(seat-1)){
pr=pr->next;
j=j+1;
}
p->next=pr->next;
pr->next=p;
p->next->prior=p;
p->prior=pr;
}
printf("添加成功\n");
i=i+1;
return 0;
}
}
}

int ListDelete(link *head) //删除数据
{
int seat,k;
int j=0;
link *pr=head,*p=NULL;
if(ListEmpty(head)==1)
;
else
{
do{
printf("输入想要删除的元素位次（如：第一位请输入1，退出请输入-1）：\n");
scanf(" %d",&seat);
}while((seat<(-1))||(seat>i)||(seat==0));
if(seat==(-1)) //停止插入
;
else
{
k=OrderJudge(seat+1);
if(k==1) //删除链表末端元素
{
p=q;
q=q->prior;
q->next=NULL;
qs=qs-1; //中间指针q的位置qs向前移动一位
}
else if((k==2)||(k==3)) //中间指针q已移动到要删除元素
{
p=q;
q=q->prior;
qs=qs-1;
q->next=p->next;
p->next->prior=q;
}
else //移动头指针删除元素
{
while(j!=(seat-1)){
pr=pr->next;
j=j+1;
}
p=pr->next; //头指针移动到要删除元素前一位
pr->next=p->next;
p->next->prior=pr;
}
free(p);
printf("删除成功\n");
i=i-1;
}
}
return 0;
}

int ListTraverse(link *head) //打印表中每个元素
{
link *pr=head;
if(ListEmpty(head)==1) //调用函数判断链表是否存在
; //链表不存在或为空则退出
else
{
int j=1;
pr=pr->next; //指针由头结点指向第一位元素
while(pr!=NULL){
printf("第%5d个数据为%10d\n",j,pr->data);
pr=pr->next;
j++;
}
}
return 0;
}

int ListInserts(link *head) //插入多个新数据
{
int j=0;
while(j!=1){
j=Li

stInsert(head); //调用插入函数
}
return 0;
}