第 2?章 线性表
2.1 线性表的定义
? ? ? ? 线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为L=(a1,a2,···,ai,ai+1,···,an)，式中a1是唯一的第一个数据元素，又称表头元素；an是唯一的最后一个元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
? ? ? ? ?线性表的特点：
- 表中元素的个数有限
- 表中元素具有逻辑上的顺序性，表中元素有先后次序
- 表中元素都是数据元素，每个元素都是单个元素。
- 表中元素的数据类型都相同，即每个元素占有相同大小的存储空间。
- 表中元素具有抽象性，即仅讨论元素的逻辑关系，而不考虑元素的内容。
?注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系，顺序表和链表是指存储结构，两者属于不同层面的概念。
2.2?线性表的基本操作
- InitList(&L)：初始化表。构造一个空的线性表。
- Length(L)：求表长。返回线性表的L的 长度，即L中数据元素的个数。
- LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
- GetElem(L,i)：按位查找操作。获取表L中第 i 个位置的元素的值。
- ListInsert(&L,i,e)：插入操作。在表L中的第 i 个位置上插入指定元素e。
- ListDelete(&L,i,&e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。
- PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
- Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
- DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
?2.3 顺序表
?2.3.1 顺序表的定义
? ? ? ? 线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧接着存储的是第 i+1 个元素，称 i 为元素ai在线性表中的位序。因此，顺序表的特点就是表中元素的逻辑顺序与其物理顺序相同。
? ? ? ? 假设线性表的元素类型为ElemType，则线性表的顺序存储类型描述为
#define MaxSize 50 //定义线性表的最大长度
typedef struct{
ElemType data[MaxSize]; //顺序表的元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
?注意：上机运行时需要将ElemType更换为具体的数据类型。
?动态分配时，线性表的顺序存储类型描述为
#define InitSize 100 //表长度的初始定义
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize,length; //数组的最大容量和当前个数
}SqList; //动态分配数组顺序表
?C的初始动态分配语句为
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
??C++的初始动态分配语句为
L.data = new ElemType[InitSize];
?2.3.2 顺序表上的基本操作
初始化操作
//方式一
void initlist(SqList *L)
{
L->data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
L->length=0;
L->MaxSize=InitSize;
}
//方式二
void initlist(SqList L)
{
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
L.length=0;
L.MaxSize=InitSize;
}
?注意：使用*L时，用（L->）来取元素，使用L时，用（L.）来取元素。
?求表长操作
int getlen(SqList *L)
{
return L->length;
}
?取元素操作
int getelemz(SqList *L,int i,ElemType *e)
{
if(i<1 || i>L->length)
return 0;
*e=L->data[i-1];
return 1;
}
?元素定位操作
int LocateElem(SqList *L,ElemType e)
{
int i;
for(i=0;i<L->length;i++)
if(L->data[i]==e)
return i+1;
return 0;
}
?插入操作
int ListInsert(SqList *L,int i,ElemType e)
{
int j;
if(i<1 || i>L->length+1) //判断i的范围是否有效
return 0;
if(L->length==L->MaxSize) //存储空间不够，增加一个存储空间
{
//重置存储空间长度
L->data = (ElemType*)realloc(L->data,(L->length+1) * sizeof(ElemType));
L->MaxSize++;
}
for(j=L->length;j>=i;j--)
//将序号为i及之后的数据元素后移一位
L->data[j]=L->data[j-1];
L->data[i-1]=e; //在位置i处放入e
L->length++; //顺序表长度加1
return 1;
}
?删除操作
int ListDelete(SqList *L,int i,ElemType *e)
{
int j;
if(i<1 || i>L->length) //判断i的范围是否有效
return 0;
*e=L->data[i-1]; //将删除的元素赋值给e
for(j=i;j<L->length;j++) //将第i个位置后的元素前移
L->data[j-1]=L->data[j];
L->length--; //顺序表长度减1
return 1;
}
输出操作
void list(SqList *L)
{
int i;
for(i=0;i<L->length;i++)
printf("%5d",L->data[i]);
printf("\n");
}
在主函数中调用以上函数
SqList L;
int E;
//初始化一个空的顺序表
initlist(&L);
//调用 ListInsert(SqList *L,int i,ElemType e)向空表中加入数据元素
ListInsert(&L,1,1);
ListInsert(&L,2,2);
ListInsert(&L,3,3);
ListInsert(&L,4,4);
//显示当前顺序表中的所有数据元素
printf("当前顺序表的元素\n");
list(&L);
//获取当前的顺序表的长度
printf("调用getlen(&L)的结果:%d\n",getlen(&L));
//取顺序表中的第1个元素并输出该元素的值
printf("调用getelem(&L,1,&E)的结果:%d\n",getelem(&L,1,&E));
printf("E=%d\n",E);
//输出指定元素第一次出现在顺序表中的位置
printf("调用LocateElem(&L,2)的结果:%d\n",LocateElem(&L,2));
//调用 ListInsert(SqList *L,int i,ElemType e)在顺序表指定位置中加入数据元素
printf("调用ListInsert(&L,2,3)的结果:%d\n",ListInsert(&L,2,3));
//显示当前顺序表中的所有数据元素
printf("当前顺序表的元素\n");
list(&L);
//删除顺序表中指定位置的元素并将输出该位置的数据元素
printf("调用ListDelete(&L,2,&E)的结果:%d\n",ListDelete(&L,2,&E));
printf("E=%d\n",E);
//显示当前顺序表中的所有数据元素
printf("当前顺序表的元素\n");
list(&L);
?2.4 链表
?2.4.1 单链表
? ? ? ? ?线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素本身的信息外，还需要存放一个指向其后续的指针。
? ? ? ? 单链表中结点类型的描述如下：
typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}slink;
?2.4.2 单链表上的基本操作
?头插法建立单链表-方法一
void List_HeadInsert(slink *L)
{
slink *s;
int n;
L->next=NULL; //初始为空表
scanf("%d",&n); //输入结点值
while(n!=9999) //输入9999表示结束
{
s=(slink *)malloc(sizeof(slink));//创建新结点
s->data=n;
s->next=L->next;
L->next=s;
scanf("%d",&n);
}
}
//调用该函数创建链表需在主函数中先初始化指针L，如下
int main()
{
slink *L;
L=(slink *)malloc(sizeof(slink)); //创建头结点
List_HeadInsert(L);
return 0;
}
?头插法建立单链表-方法二?
slink * List_HeadInsert()
{
slink *s,*L;
int n;
L=(slink *)malloc(sizeof(slink)); //创建头结点
L->next=NULL; //初始为空表
scanf("%d",&n); //输入结点值
while(n!=9999) //输入9999表示结束
{
s=(slink *)malloc(sizeof(slink));//创建新结点
s->data=n;
s->next=L->next;
L->next=s;
scanf("%d",&n);
}
return L;
}
//在主函数中使用如下方式调用
int main()
{
slink *L;
L=List_HeadInsert();
return 0;
}
?尾插法建立单链表
slink * List_TailInsert(slink * L)
{
slink *s,*r; //r为表尾指针
int n;
L=(slink *)malloc(sizeof(slink)); //创建头结点
r=L;
scanf("%d",&n); //输入结点值
while(n!=9999) //输入9999表示结束
{
s=(slink *)malloc(sizeof(slink));//创建新结点
s->data=n;
r->next=s;
r=s;
scanf("%d",&n);
}
r->next=NULL;
return L;
}
//在主函数中调用该函数的方法如下
int main()
{
slink *L;
L=List_TailInsert(L);
return 0;
}
?建立单链表
slink * CresList(int n)
{
slink *L,*p,*s; //p用于指向新链入结点，s用于指向新开辟结点
int i;
p=L=(slink *)malloc(sizeof(slink)); //创建头结点
for(i=1;i<=n;i++)
{
s=(slink *)malloc(sizeof(slink));//创建新结点
scanf("%d",&s->data); //输入结点值
p->next=s; //将新结点连接到p所指结点的后面
p=s; //p指向新链入结点
}
p->next=NULL; //尾结点指针域置为空
return L;
}
//在主函数中调用该函数的方法如下
int main()
{
slink *L;
L=CresList(5);
return 0;
}
?求表长操作
int getlen(slink *L)
{
slink *p;
int n;
p=L->next;
n=0;
while(p!=NULL)
{
n++;
p=p->next;
}
return n;
}
?取元素操作
int getlem(slink *L,int i,ElemType *e)
{
slink *p;
int j;
if(i<1) return 0; //参数i不合理，取元素失败，返回0
p=L->next;
j=1;
while(p!=NULL&&j<i) //从第1个结点开始查找第i个结点
{
p=p->next;
j++;
}
if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0
*e=p->data;
return 1; //取元素成功，返回1
}
?按值查找结点
slink * GetElem(slink *L,ElemType e)
{
slink *p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p;
}
插入操作
int insert(slink *L,int i,ElemType e)
{
slink *p,*q;
int j;
if(i<1) return 0; //参数i不合理，取元素失败，返回0
p=L;
j=0;
while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点
{
p=p->next;
j++;
}
if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0
q=(slink *)malloc(sizeof(slink));
q->data=e;
q->next=p->next;
p->next=q;
return 1;
}
?删除操作
int delete(slink *L,int i,ElemType *e)
{
slink *p,*q;
int j;
if(i<1) return 0; //参数i不合理，取元素失败，返回0
p=L;
j=0;
while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点
{
p=p->next;
j++;
}
if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0
q=p->next; //指向第i个结点
p->next=q->next; //指向被删结点的下一个结点
*e=q->data; //保存被删结点的数据值
free(q); //释放被删除结点占用的空间
return 1;
}
?输出操作
void list(slink *L)
{
slink *p;
p=L->next;
while(p!=NULL)
{
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
?2.4.3 双链表
? ? ? ? ?为了能快速方便的找到任意一个结点的前驱和后继，在结点中再增设一个指针域，指向该结点的前驱结点，这样形成的链表就有两条不同方向的链，称为双向链表，简称双链表。
? ? ? ? 双链表的结点类型定义如下：
typedef struct DNode{
ElemType data;
struct DNode *prior;
struct DNode *next;
}dlink;
?2.4.4 双链表上的基本操作
建立双链表
dlink * credlink(int n)
{
dlink *L,*p,*s; //p用于指向新链入结点，s用于指向新开辟结点
int i;
p=L=(dlink *)malloc(sizeof(dlink)); //创建头结点
for(i=1;i<=n;i++)
{
s=(dlink *)malloc(sizeof(dlink)); //s指向新开辟结点
scanf("%d",&s->data); //新结点数据域赋值
s->prior=p;
p->next=s; //将新结点连接到p指向结点的后面
p=s; //p指向新链入结点
}
p->next=L->prior=NULL; //头结点的前驱域和尾结点的后继域置为空
return L; //返回头指针
}
?求表长、取元素、定位操作与单链表一样，只需要将slink替换为的dlink即可。
插入操作
int insert(dlink *L,int i,ElemType e)
{
dlink *p,*q;
int j;
if(i<1) return 0; //参数i不合理，取元素失败，返回0
p=L;
j=0;
while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点
{
p=p->next;
j++;
}
if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0
q=(dlink *)malloc(sizeof(dlink));
q->data=e;
q->next=p->next;
q->prior=p;
if(p->next!=NULL)
p->next->prior=q; // 若恰好在表尾插入，因为没有后继结点，则不需要这一步
p->next=q;
return 1;
}
?删除操作
int delete(dlink *L,int i,ElemType *e)
{
dlink *p,*q;
int j;
if(i<1) return 0; //参数i不合理，取元素失败，返回0
p=L;
j=0;
while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点
{
p=p->next;
j++;
}
if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0
q=p->next; //指向第i个结点
p->next=q->next; //指向被删结点的下一个结点
if(p->next!=NULL)
q->next->prior=p;
*e=q->data; //保存被删结点的数据值
free(q); //释放被删除结点占用的空间
return 1;
}
?输出操作
void list(dlink *L)
{
dlink *p;
p=L;
while(p->next!=NULL) //正向输出链表元素值
{
p=p->next;
printf("%4d",p->data);
}
printf("\n");
while(p!=L) //反向输出链表元素值
{
printf("%4d",p->data);
p=p->prior;
}
printf("\n");
}
?2.4.5 循环链表
?循环单链表
? ? ? ? 循环单链表与单链表的区别在于表中最后一个结点的指针不是NULL，而是指向头结点。循环单链表的判空条件不是头结点的指针为空，而是它是否等于头指针。
? ? ? ? 循环单链表的结点类型定义和单链表是一样的，此外，在循环单链表上的基本操作和单链表是基本一致，只需要将单链表中的判定条件p->next=!NULL、p->next=NULL分别改为p->next=!L、p->next=L即可。
循环双链表
? ? ? ? 将双链表的最后一个结点的后继指针域的值由空改为指向头结点，头结点中的前驱指针域的值由空改为指向尾结点，这样的双向链表称为双向循环链表。
????????循环双链表的结点类型定义和双链表是一样的，此外，在循环双链表上的基本操作和双链表是基本一致，只需要将双链表中的判定条件p->next=!NULL、p->next=NULL、p->prior=NULL分别改为p->next=!L、p->next=L、L->prior=p即可。
2.4.6 静态链表
?????????用数组描述的链表，即称为静态链表。静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标 CUR。这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
? ? ? ? 注意：静态链表在数组存储数据是从数组的第3个位置开始的，即数组下标为2存储的是链表的第一个元素的值。
? ? ? ? 静态链表结构类型的描述如下：
typedef int ElemType; //在实际中，根据需要定义所需的数据类型
#define MaxSize 50 //静态链表中的最大长度
typedef struct{
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}stalink[MaxSize];
?初始化操作
void initlist(stalink space)
{
int i;
for(i=0;i<MaxSize-1;i++)
space[i].next=i+1;
space[MaxSize-1].next=0;
}
?获取结点操作
int allocnode(stalink space)
{
int i;
i=space[0].next;
if(i==0) return 0; //链表空间已空，分配空间失败
space[0].next=space[i].next;
return i;
}
?回收结点操作
void freenode(stalink space,int i)
{
space[i].next=space[0].next;
space[0].next=i;
}
?建立静态链表
int crestalink(stalink space,int n)
{
int L,k,s,i;
k=L=allocnode(space);
for(i=1;i<=n;i++)
{
s=allocnode(space);
scanf("%d",&space[s].data);
space[k].next=s;
k=s;
}
space[k].next=0;
return L;
}
?求表长操作
int getlen(stalink space,int head) //head为链表头结点的下标
{
int i,k;
k=space[head].next;
i=0;
while(k!=0)
{
i++;
k=space[k].next;
}
return i;
}
?取元素操作
int getlem(stalink space,int head,int i,ElemType *e)
{
int j,k;
if(i<1) return 0;
j=0;
k=head;
while(k!=0&&j<i)
{
j++;
k=space[k].next;
}
if(k==0) return 0;
*e=space[k].data;
return 1;
}
?定位操作
int locate(stalink space,int head,ElemType e)
{
int k;
k=space[head].next;
while(k!=0&&space[k].data!=e)
k=space[k].next;
return k; //k表示的是在数组的下标，若想返回的是在链表中的第几个则用k-1;
}
?插入操作
int insert(stalink space,int head,int i,ElemType e)
{
int j,k,m;
if(i<1) return 0;
k=head;
j=0;
while(k!=0&&j<i-1)
{
j++;
k=space[k].next;
}
if(k==0)
return 0;
m=allocnode(space);
if(m!=0)
{
space[m].data=e;
space[m].next=space[k].next;
space[k].next=m;
return 1;
}
else return 0;
}
?删除操作
int delete(stalink space,int head,int i,ElemType *e)
{
int j,k,m;
if(i<1) return 0;
k=head;
j=0;
while(k!=0&&j<i-1)
{
j++;
k=space[k].next;
}
if(k==0) return 0;
m=space[k].next;
space[k].next=space[m].next;
*e=space[m].data;
freenode(space,m);
return 1;
}
?输出操作
void list(stalink space,int head)
{
int i;
i=space[head].next;
while(i!=0)
{
printf("%4d",space[i].data);
i=space[i].next;
}
printf("\n");
}
|