实现顺序表的各种基本运算的算法

1. 实验1：实现顺序表的各种基本运算的算法

实验内容： 编写一个程序sqlist.cpp,实现顺序表的各种基本运算和整体建表算法（假设顺序表的元素类型为Elem Type为char），并在次基础上设计一个程序exp1-1.cpp，完成以下功能。

（1）初始化顺序表L。

（2）依次插入a、b、c、d、e元素。

（3）输出顺序表L。

（4）输出顺序表L的长度。

（5）判断顺序表L是否为空。

（6）输出顺序表L的第3个元素。

（7）输出元素a的位置。

（8）在第四个元素的位置上插入f元素。

（9）输出顺序表L。

（10）删除顺序表L的第3个元素。

（11）输出顺序表L。

（12）释放顺序表L。

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct DNode
{
ElemType data;
struct DNode *prior; //指向前驱结点
struct DNode *next; //指向后继结点
} DLinkNode; //声明双链表结点类型
void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建双链表
{
DLinkNode *s;
L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
L->prior=L->next=NULL;
for (int i=0;i<n;i++)
{
s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
s->data=a[i];
s->next=L->next; //将结点 s 插在原开始结点之前,头结点之后
if (L->next!=NULL) L->next->prior=s;
L->next=s;s->prior=L;
}
}
void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建双链表
{
DLinkNode *s,*r;
L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
L->prior=L->next=NULL;
r=L; //r 始终指向终端结点,开始时指向头结点
for (int i=0;i<n;i++)
{
s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
s->data=a[i];
r->next=s;s->prior=r; //将结点 s 插入结点 r 之后
r=s;
}
r->next=NULL; //尾结点 next 域置为 NULL
}
void InitList(DLinkNode *&L) //初始化线性表
{
L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
L->prior=L->next=NULL;
}
void DestroyList(DLinkNode *&L) //销毁线性表
{
DLinkNode *pre=L,*p=pre->next;
while (p!=NULL)
{
free(pre);
pre=p; //pre、p 同步后移一个结点
p=pre->next;
}
free(p);
}
bool ListEmpty(DLinkNode *L) //判线性表是否为空表
{
return(L->next==NULL);
}
int ListLength(DLinkNode *L) //求线性表的长度
{
DLinkNode *p=L;
int i=0; //p 指向头结点,i 设置为 0

while (p->next!=NULL) //找尾结点 p
{
i++; //i 对应结点 p 的序号
p=p->next;
}
return(i);
}
void DispList(DLinkNode *L) //输出线性表
{
DLinkNode *p=L->next;
while (p!=NULL)
{
printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
bool GetElem(DLinkNode *L,int i,ElemType &e) //求线性表中第 i 个元素值
{
int j=0;
DLinkNode *p=L;
if (i<=0) return false; //i 错误返回假
while (j<i && p!=NULL) //查找第 i 个结点 p
{
j++;
p=p->next;
}
if (p==NULL) //没有找到返回假
return false;
else //找到了提取值并返回真
{
e=p->data;
return true;
}
}
int LocateElem(DLinkNode *L,ElemType e)//查找第一个值域为 e 的元素序号
{
int i=1;
DLinkNode *p=L->next;
while (p!=NULL && p->data!=e) //查找第一个值域为 e 的结点 p

{
i++; //i 对应结点 p 的序号
p=p->next;
}
if (p==NULL) //没有找到返回 0
return(0);
else //找到了返回其序号
return(i);
}
bool ListInsert(DLinkNode *&L,int i,ElemType e) //插入第 i 个元素
{
int j=0;
DLinkNode *p=L,*s; //p 指向头结点,j 设置为 0
if (i<=0) return false; //i 错误返回假
while (j<i-1 && p!=NULL) //查找第 i-1 个结点 p
{
j++;
p=p->next;
}
if (p==NULL) //未找到第 i-1 个结点
return false;
else //找到第 i-1 个结点 p
{
s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点 s
s->data=e;
s->next=p->next; //将结点 s 插入到结点 p 之后
if (p->next!=NULL) 
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
}
bool ListDelete(DLinkNode *&L,int i,ElemType &e) //删除第 i 个元素
{ int j=0;
DLinkNode *p=L,*q; //p 指向头结点,j 设置为 0
if (i<=0) return false; //i 错误返回假
while (j<i-1 && p!=NULL) //查找第 i-1 个结点 p
{ j++;
p=p->next;

}
if (p==NULL) //未找到第 i-1 个结点
return false;
else //找到第 i-1 个节 p
{ q=p->next; //q 指向第 i 个结点
if (q==NULL) //当不存在第 i 个结点时返回 false
return false;
e=q->data;
p->next=q->next; //从双链表中删除结点 q
if (p->next!=NULL) //若 p 结点存在后继结点,修改其前驱指针
p->next->prior=p;
free(q); //释放 q 结点
return true;
}
}
int main()
{
DLinkNode *h;
ElemType e;
printf("双链表的基本运算如下：\n");
printf(" (1)初始化双链表 h\n");
InitList(h);
printf(" (2)依次采用尾插法插入 a,b,c,d,e 元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf(" (3)输出双链表 h：");
DispList(h);
printf(" (4)双链表 h 长度：%d\n",ListLength(h));
printf(" (5)双链表 h 为%s\n",(ListEmpty(h)?"空":"非空"));
GetElem(h,3,e);
printf(" (6)双链表 h 的第 3 个元素：%c\n",e);
printf(" (7)元素 a 的位置：%d\n",LocateElem(h,'a'));
printf(" (8)在第 4 个元素位置上插入 f 元素\n");
ListInsert(h,4,'f');
printf(" (9)输出双链表 h：");
DispList(h);
printf(" (10)删除 h 的第 3 个元素\n");
ListDelete(h,3,e);
printf(" (11)输出双链表 h：");
DispList(h);
printf(" (12)释放双链表 h\n");
DestroyList(h);
return 1;
}