数据结构---线性表
2021-07-28 本文已影响0人
喜忧参半
2.1 线性表及其基本运算
一、线性表
线性表是n个数据元素的优先序列，记为L=(a1,a2,…)
数据元素之间的关系是:
ai-1领先于ai, ai领先于ai+1。
称ai-1是a;的直接前驱元素: ai+1是a;的直接后继元素。
除a外，每个元素有且仅有一一个直接前驱元素，
除a外，每个元素有且仅有一一个直接后继元素。
线性表中数据元素的个数n(n>=0)称为线性表的长度，当n=0时，称为空表。
线性表是最常用且最简单的一种数据结构。
ai领先于ai+1。
称ai-是a;的直接前驱元素: ai+1是a;的直接后继元素。
除a外，每个元素有且仅有一一个 直接前驱元素，
除a外，每个元素有且仅有一一个直接后继元素。
线性表中数据元素的个数n(n>=0)称为线性表的长度，当n=0时，称为空表。
二、基本运算
| 函数名 | 操作 | 内容 |
|---|---|---|
| Initiate(L) | 初始化操作 | 设定一个空的线性表 |
| Length(L) | 求长度函数 | 函数值为线性表L中数据元素的个数 |
| Get(L,i) | 取元素函数 | i∈[1,length]时返回L中第i个数据元素，否则为空元素NULL。i为该元素的位序。 |
| Prior(L,elm) | 求前驱函数 | elm为L中的一个数据元素，若它位序大于1，则函数值为elm的前驱元素，否则为NULL。 |
| Next(L,elm) | 求后继函数 | 若elm的位序小于表长n，则函数值为elm的后继，否则为NULL。 |
| Locate(L,x) | 定位函数 | 给定值x，若x不在表中，则返回0，否则返回在表中第一次出现时的位序。 |
| Insert(L,i,b) | 前插操作 | 在第i个元素之前插入新元素b，i的取值范围为：i∈(1,n+1)；i=n+1表示在表尾插入，n为表长。 |
| Delete(L,i) | 删除操作 | 删除线性表L中位序为i的元素。i∈(1，n)； |
| Empty(L) | 判空表操作 | 若L为空表，则返回布尔值"ture",否则返回布尔值"false" |
| Clear(L) | 表置空操作 | 将L置为空表，没有返回值。 |
线性表中每个操作的单独实现
--------------------定义顺序线性表 -------------------
#include<stdio.h>
// 线性表 长度 存放元素类型
typedef int Ele;/* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
Ele data[30]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
//Ele data[20]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}List;
------------------初始化顺序线性表 -------------------
int Initiate(List *L)
{
L->length=20;
return 0;
}
--------------------求长度函数 -----------------------
int Length(List *L)
{
printf("%d\n",L->length); /返回线性表中数据元素的个数
return 0;
}
---------------------取元素操作------------------------
int Get(List L,int i)
{
if (L.length==0||i<1||i>L.length)
{
printf("Error\n");
}else{
printf("%c\n",L.data[i-1]);
}
return 0;
}
---------------------求前驱元素------------------------
int Prior(List L,int i)
{
if((i-1)!=0)
{
int k;
for(k=0;k<i;k++)
printf("%2d",L.data[k]);
printf("\n");
}else{printf("该元素没有前驱元素！\n");}
return 0;
}
---------------------求后继元素-------------------------
int Next(List L,int i)
{
int k;
if(i<L.length)
{
for(k=i;k<=L.length;k++)
printf("%3d",L.data[k]);
printf("\n");
}else{printf("该元素没有后继元素！\n");}
return 0;
}
---------------------定位元素-------------------------
int Locate(List L,int x)
{
int k=-1;
for(int i=0;i<L.length;i++)
if(x==L.data[i])
{
k=i+1;
}
if (k!=-1)
{
printf("该元素是第%d个元素\n",k);
}else{
printf("该元素不存在！\n");
}
return 0;
}
---------------------前插元素-------------------------
int Insert(List *L,int i,int x)
{
if(i<1||i>L->length+1)
{
printf("Error\n");
}else
{
int k;
for(k=L->length;k>=i;k--)
L->data[k+1]=L->data[k];
}
L->data[i]=x;
L->length++;
return 0;
}
---------------------删除元素-------------------------
int Delete(List *L,int i)
{
if(i<0||i>L->length)
{
printf("删除不合法,Error\n");
}else{
int k;
for(k=i;k<L->length;k++)
L->data[k]=L->data[k+1];
}
L->length--;
return 0;
}
---------------------判空操作-------------------------
int Checkout(List L)
{
int i;
for(i=0;i<L.length+1;i++)
{
if(L.data[i])
printf("表非空\n");
break;
}
return 0;
}
---------------------清空表操作------------------------
int Clear(List *L)
{
int i;
for(i=0;i<L->length+1;i++)
if(L->data[i]!=0)
L->data[i]=0;
return 0;
}
例：求两个集合的并，即A=A∪B
分析：设A、B分别由两个线性表LA和LB表示，要求将LB中存在而LA中不存在的DE插入到表LA中。
算法思想：
①依次从LB中取出一个DE;
②判在LA中是否存在;
③若不存在，则插入到LA中。
例：归并两个有序的线性表LA和LB为一一个新的有序线性表LC。
算法思想：
①初始化:置LC为空表，设置变量i， j,初值为1,分别指向LA和LB的第一个DE, k表示LC的长度，初值为0.
②当i<=LENGTH(LA) AND j<=LENGTH(LB)时，判断:若i所指的元素<=j所指的元素，则将i所指的元素插入在LC的k+1前，并且i, k的值分别加1;
否则，将j所指的元素插入在LC的k+1前，并且j，k的值分别加1。
③重复②直到某个表的元素插入完毕。
④将未插入完的表的余下的元素，依次插入在LC后。
void merge_list(LA,LB,LC){
Initiate(LC);//初始化线性表LC
int i=1;j=1;k=0;//初始化位序值
while((i<=length(LA))&&(j<=length(LB))) //分别指向LA和LB位序为1的元素
{
if(Get(LA,i)<=Get(LB,j)) //当LA的第i个元素＜LB的第j个元素时
Insert(LC,k+1,Get(LA,i)),k++,i++; //把LA的第i个元素插入到LC末尾，并且位序+1
else
Insert(LC,k+1,Get(LB,i)),k++,j++; //把LB的第j个元素插入到LC末尾，并且位序+1
}
while(i<=length(LA)) //若LA的位序数小于LA数组总长
{
Insert(LC,k+1,Get(LA,i)),k++,i++; //将LA的元素，插入到LC末尾，位序+1
}
while(i<=length(LB)) //若LB的位序数小于LB数组总长
{
Insert(LC,k+1,Get(LB,j)),k++,j++; //将LB的元素，插入到LC末尾，位序+1
}
}
2.2 线性表顺序存储结构
用一组地址连续的存储单元依次存储线性表的元素。
设线性表的每个元素占用k个存储单元，则第i个元素ai的存储位置为: Loc(ai)- Loc(ai)+(i-1)*k其中， Loc(ai)为线性表的起址。
2.2 线性表链式存储结构
用一组任意的存储单元(不要求地址连续)来存储线性表的元素。每个元素对应一组存储单元（称为结点）。
每个结点包括两个域:存储数据元素信息的数据域和存储直接后继所在位置的指针域。
N个结点通过指针域组成的表,称为线性链表(单链表）。
单链表中每个操作的单独实现
--------------------定义结点 -------------------
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct Node
{
ElemType data; //数据域
struct Node *next; //指针域
}Node;
typedef struct Node *Linklist;
---------------------链表初始化 ----------------------
int Create(Linklist *L)
{
*L=(Linklist)malloc(sizeof(Node));
//创建了一个结点，并且用L指向了这个结点
if(!(*L))
return ERROR;
(*L)->next=NULL;
return OK;
}
--------------------求长度函数 -----------------------
int Length(Linklist L)
{
int i=0;
Linklist p;
p=L->next; //指向的第一个结点
while(p)
{
i++;
p=p->next; //指向下一个结点
}
return i;
}
---------------------取元素操作-----------------------
int Get(Linklist L,int i)//ElemType *e)
{
int j;
Linklist p;
p=L->next;
j=1;
while(p && j<i)
{
j++;
p=p->next;
}
if (!p|| j>i)
return ERROR;
//*e= p->data;
return p->data;
}
---------------------定位元素-------------------------
int Locate(Linklist L,ElemType e)
{
int i=1;
Linklist p;
p=L->next;
while(p)
{
if (p->data==e)
return i;
p=p->next;
i++;
}
return ERROR;
}
---------------------前插元素-------------------------
int Insert(Linklist *L,int i,ElemType e)
{
int j;
Linklist p,s;
p= *L;
j=1;
while(p && j<i)
{
p=p->next;
j++;
}
if(!p|| j>i)
return ERROR;
s=(Linklist)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
---------------------删除元素-------------------------
int Delete(Linklist *L,int i)
{
int j;
Linklist p,q;
p= *L;
j=1;
while(p->next && j<i)
{
p=p->next;
j++;
}
if(!(p->next)||j>i)
return ERROR;
q=p->next;
p->next=q->next;
free(q);
return OK;
}
---------------------判空操作-------------------------
int Check(Linklist *L)
{
Linklist p;
p=*L;
if(p->next)//头指针是否为空？
printf("链表非空！\n");
return OK;
}
---------------------清空表操作-----------------------
int Clear(Linklist *L)
{
Linklist p;
p =*L;
while(p->next)
{
p=p->next;
p->data=0;//只是数据清零，并非释放内存
}
return OK;
}
执行后：
这就是关于线性表的一些基本操作。
