建设银行泰安分行网站,四川招标采购信息网官网,淄博住房和城乡建设局网站,天津建设厅官方网站线性表的定义
线性表#xff1a;零个或多个数据元素的有限序列。
1#xff09;线性表是一个序列。即元素之间是有顺序的#xff0c;若元素存在多个#xff0c;则第一个元素无前驱#xff0c;最后一个元素无后继#xff0c;其他每个元素都有且只有一个前驱和后继。
2零个或多个数据元素的有限序列。
1线性表是一个序列。即元素之间是有顺序的若元素存在多个则第一个元素无前驱最后一个元素无后继其他每个元素都有且只有一个前驱和后继。
2线性表强调是有限的元素个数也是有限的。事实上在计算机中处理的对象都是有限的那么无限的数列只存在于数学的概念中。 注意位序是从1开始的。
在较复杂的线性表中一个数据元素可以由若干个数据项组成。
线性表的抽象数据类型 注 当你传递一个参数给函数的时候这个参数是否在函数内被改动决定了使用什么参数形式。 1如果需要被改动则需要传递指向这个参数的指针。 2如果不用被改动可以会直接传递这个参数。
线性表的顺序存储结构
线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表的每个数据元素的类型都相同可以使用C语言的一维数组来实现顺序存储结构。
随着数据的插入线性表的长度开始变大不过线性表的当前长度不能超过存储容量即数组的长度。
定义
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定这里假设为int */
typedef struct
{ElemType data[MAXSIZE]; /* 数组存储数据元素 */int length; /* 线性表当前长度 */
}SqList;顺序存储结构需要3个属性 1存储空间的起始位置数组data它的存储位置就是存储空间的存储位置。 2线性表的最大存储容量数组长度MAXSIZE。 3线性表的当前长度length。
注1区别数组长度和线性表长度 线性表的长度是线性表中数据元素的个数随着线性表插入和删除操作的进行这个量是变化的。 线性表的长度数组的长度。
注2线性表的第i个元素是要存储在数组下标为i-1的位置上 存储器中的每个存储单元都有自己的编号这个编号称为地址。
假设占用的是c个存储单元那么线性表中第i1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系 LOC表示获得存储位置的函数。 通过上述公式可以随时算出线性表中任意位置的地址且都是相同的时间因此它的存取时间性能为O(1)这类存储结构称为随机存取结构。
优缺点
优点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间可以快速地存取表中任一位置的元素
缺点
插入和删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量造成存储空间的“碎片”
代码 #include stdio.h #include stdlib.h
#include math.h
#include time.h#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定这里假设为int */
typedef struct
{ElemType data[MAXSIZE]; /* 数组存储数据元素 */int length; /* 线性表当前长度 */
}SqList;typedef int Status; /* Status是函数的类型,其值是函数结果状态代码如OK等 */Status visit(ElemType c)
{printf(%d ,c);return OK;
}/* 初始化顺序线性表 */
Status InitList(SqList *L)
{ L-length0;return OK;
}/* 初始条件顺序线性表L已存在。操作结果若L为空表则返回TRUE否则返回FALSE */
Status ListEmpty(SqList L)
{ if(L.length0)return TRUE;elsereturn FALSE;
}/* 初始条件顺序线性表L已存在。操作结果将L重置为空表 */
Status ClearList(SqList *L)
{ L-length0;return OK;
}/* 初始条件顺序线性表L已存在。操作结果返回L中数据元素个数 */
int ListLength(SqList L)
{return L.length;
}/* 初始条件顺序线性表L已存在1≤i≤ListLength(L) */
/* 操作结果用e返回L中第i个数据元素的值,注意i是指位置第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{if(L.length0 || i1 || iL.length)return ERROR;*eL.data[i-1];return OK;
}/* 初始条件顺序线性表L已存在 */
/* 操作结果返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在则返回值为0 */
int LocateElem(SqList L,ElemType e)
{int i;if (L.length0)return 0;for(i0;iL.length;i){if (L.data[i]e)break;}if(iL.length)return 0;return i1;
}/* 初始条件顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果在L中第i个位置之前插入新的数据元素eL的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{ int k;if (L-lengthMAXSIZE) /* 顺序线性表已经满 */return ERROR;if (i1 || iL-length1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */return ERROR;if (iL-length) /* 若插入数据位置不在表尾 */{for(kL-length-1;ki-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */L-data[k1]L-data[k];}L-data[i-1]e; /* 将新元素插入 */L-length;return OK;
}/* 初始条件顺序线性表L已存在1≤i≤ListLength(L) */
/* 操作结果删除L的第i个数据元素并用e返回其值L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{ int k;if (L-length0) /* 线性表为空 */return ERROR;if (i1 || iL-length) /* 删除位置不正确 */return ERROR;*eL-data[i-1];if (iL-length) /* 如果删除不是最后位置 */{for(ki;kL-length;k)/* 将删除位置后继元素前移 */L-data[k-1]L-data[k];}L-length--;return OK;
}/* 初始条件顺序线性表L已存在 */
/* 操作结果依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{int i;for(i0;iL.length;i)visit(L.data[i]);printf(\n);return OK;
}/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void unionL(SqList *La,SqList Lb)
{int La_len,Lb_len,i;ElemType e; /*声明与La和Lb相同的数据元素e*/La_lenListLength(*La); /*求线性表的长度 */Lb_lenListLength(Lb);for (i1;iLb_len;i){GetElem(Lb,i,e); /*取Lb中第i个数据元素赋给e*/if (!LocateElem(*La,e)) /*La中不存在和e相同数据元素*/ListInsert(La,La_len,e); /*插入*/}
}int main()
{SqList L;SqList Lb;ElemType e;Status i;int j,k;iInitList(L);printf(初始化L后L.length%d\n,L.length);for(j1;j5;j)iListInsert(L,1,j);printf(在L的表头依次插入15后L.data);ListTraverse(L); printf(L.length%d \n,L.length);iListEmpty(L);printf(L是否空i%d(1:是 0:否)\n,i);iClearList(L);printf(清空L后L.length%d\n,L.length);iListEmpty(L);printf(L是否空i%d(1:是 0:否)\n,i);for(j1;j10;j)ListInsert(L,j,j);printf(在L的表尾依次插入110后L.data);ListTraverse(L); printf(L.length%d \n,L.length);ListInsert(L,1,0);printf(在L的表头插入0后L.data);ListTraverse(L); printf(L.length%d \n,L.length);GetElem(L,5,e);printf(第5个元素的值为%d\n,e);for(j3;j4;j){kLocateElem(L,j);if(k)printf(第%d个元素的值为%d\n,k,j);elseprintf(没有值为%d的元素\n,j);}kListLength(L); /* k为表长 */for(jk1;jk;j--){iListDelete(L,j,e); /* 删除第j个数据 */if(iERROR)printf(删除第%d个数据失败\n,j);elseprintf(删除第%d个的元素值为%d\n,j,e);}printf(依次输出L的元素);ListTraverse(L); j5;ListDelete(L,j,e); /* 删除第5个数据 */printf(删除第%d个的元素值为%d\n,j,e);printf(依次输出L的元素);ListTraverse(L); //构造一个有10个数的LbiInitList(Lb);for(j6;j15;j)iListInsert(Lb,1,j);unionL(L,Lb);printf(依次输出合并了Lb的L的元素);ListTraverse(L); return 0;
}
线性表的链式存储结构
定义 我们把链表中第一个结点的存储位置叫做头指针。 线性链表的最后一个结点指针为“空”通常用NULL或“”符号表示 有时我们为了更加方便地对链表进行操作会在单链表的第一个结点前附设一个结点称为头结点。头结点的数据域可以不存储任何信息也可以存储如线性表的长度等附加信息头结点的指针域存储指向第—个结点的指针。
头结点与头指针的区别 代码
typedef struct Node
{ElemType data;struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */#include stdio.h
#include string.h
#include ctype.h
#include stdlib.h #include math.h
#include time.h#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;/* Status是函数的类型,其值是函数结果状态代码如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定这里假设为int */Status visit(ElemType c)
{printf(%d ,c);return OK;
}typedef struct Node
{ElemType data;struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList *//* 初始化链式线性表 */
Status InitList(LinkList *L)
{ *L(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */if(!(*L)) /* 存储分配失败 */return ERROR;(*L)-nextNULL; /* 指针域为空 */return OK;
}/* 初始条件链式线性表L已存在。操作结果若L为空表则返回TRUE否则返回FALSE */
Status ListEmpty(LinkList L)
{ if(L-next)return FALSE;elsereturn TRUE;
}/* 初始条件链式线性表L已存在。操作结果将L重置为空表 */
Status ClearList(LinkList *L)
{ LinkList p,q;p(*L)-next; /* p指向第一个结点 */while(p) /* 没到表尾 */{qp-next;free(p);pq;}(*L)-nextNULL; /* 头结点指针域为空 */return OK;
}/* 初始条件链式线性表L已存在。操作结果返回L中数据元素个数 */
int ListLength(LinkList L)
{int i0;LinkList pL-next; /* p指向第一个结点 */while(p) {i;pp-next;}return i;
}/* 初始条件链式线性表L已存在1≤i≤ListLength(L) */
/* 操作结果用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{int j;LinkList p; /* 声明一结点p */p L-next; /* 让p指向链表L的第一个结点 */j 1; /* j为计数器 */while (p ji) /* p不为空或者计数器j还没有等于i时循环继续 */{ p p-next; /* 让p指向下一个结点 */j;}if ( !p || ji ) return ERROR; /* 第i个元素不存在 */*e p-data; /* 取第i个元素的数据 */return OK;
}/* 初始条件链式线性表L已存在 */
/* 操作结果返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在则返回值为0 */
int LocateElem(LinkList L,ElemType e)
{int i0;LinkList pL-next;while(p){i;if(p-datae) /* 找到这样的数据元素 */return i;pp-next;}return 0;
}/* 初始条件链式线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果在L中第i个位置之前插入新的数据元素eL的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{ int j;LinkList p,s;p *L; j 1;while (p j i) /* 寻找第i个结点 */{p p-next;j;} if (!p || j i) return ERROR; /* 第i个元素不存在 */s (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */s-data e; s-next p-next; /* 将p的后继结点赋值给s的后继 */p-next s; /* 将s赋值给p的后继 */return OK;
}/* 初始条件链式线性表L已存在1≤i≤ListLength(L) */
/* 操作结果删除L的第i个数据元素并用e返回其值L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{ int j;LinkList p,q;p *L;j 1;while (p-next j i) /* 遍历寻找第i个元素 */{p p-next;j;}if (!(p-next) || j i) return ERROR; /* 第i个元素不存在 */q p-next;p-next q-next; /* 将q的后继赋值给p的后继 */*e q-data; /* 将q结点中的数据给e */free(q); /* 让系统回收此结点释放内存 */return OK;
}/* 初始条件链式线性表L已存在 */
/* 操作结果依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{LinkList pL-next;while(p){visit(p-data);pp-next;}printf(\n);return OK;
}/* 随机产生n个元素的值建立带表头结点的单链线性表L头插法 */
void CreateListHead(LinkList *L, int n)
{LinkList p;int i;srand(time(0)); /* 初始化随机数种子 */*L (LinkList)malloc(sizeof(Node));(*L)-next NULL; /* 先建立一个带头结点的单链表 */for (i0; in; i) {p (LinkList)malloc(sizeof(Node)); /* 生成新结点 */p-data rand()%1001; /* 随机生成100以内的数字 */p-next (*L)-next; (*L)-next p; /* 插入到表头 */}
}/* 随机产生n个元素的值建立带表头结点的单链线性表L尾插法 */
void CreateListTail(LinkList *L, int n)
{LinkList p,r;int i;srand(time(0)); /* 初始化随机数种子 */*L (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */r*L; /* r为指向尾部的结点 */for (i0; in; i) {p (Node *)malloc(sizeof(Node)); /* 生成新结点 */p-data rand()%1001; /* 随机生成100以内的数字 */r-nextp; /* 将表尾终端结点的指针指向新结点 */r p; /* 将当前的新结点定义为表尾终端结点 */}r-next NULL; /* 表示当前链表结束 */
}int main()
{ LinkList L;ElemType e;Status i;int j,k;iInitList(L);printf(初始化L后ListLength(L)%d\n,ListLength(L));for(j1;j5;j)iListInsert(L,1,j);printf(在L的表头依次插入15后L.data);ListTraverse(L); printf(ListLength(L)%d \n,ListLength(L));iListEmpty(L);printf(L是否空i%d(1:是 0:否)\n,i);iClearList(L);printf(清空L后ListLength(L)%d\n,ListLength(L));iListEmpty(L);printf(L是否空i%d(1:是 0:否)\n,i);for(j1;j10;j)ListInsert(L,j,j);printf(在L的表尾依次插入110后L.data);ListTraverse(L); printf(ListLength(L)%d \n,ListLength(L));ListInsert(L,1,0);printf(在L的表头插入0后L.data);ListTraverse(L); printf(ListLength(L)%d \n,ListLength(L));GetElem(L,5,e);printf(第5个元素的值为%d\n,e);for(j3;j4;j){kLocateElem(L,j);if(k)printf(第%d个元素的值为%d\n,k,j);elseprintf(没有值为%d的元素\n,j);}kListLength(L); /* k为表长 */for(jk1;jk;j--){iListDelete(L,j,e); /* 删除第j个数据 */if(iERROR)printf(删除第%d个数据失败\n,j);elseprintf(删除第%d个的元素值为%d\n,j,e);}printf(依次输出L的元素);ListTraverse(L); j5;ListDelete(L,j,e); /* 删除第5个数据 */printf(删除第%d个的元素值为%d\n,j,e);printf(依次输出L的元素);ListTraverse(L); iClearList(L);printf(\n清空L后ListLength(L)%d\n,ListLength(L));CreateListHead(L,20);printf(整体创建L的元素(头插法));ListTraverse(L); iClearList(L);printf(\n删除L后ListLength(L)%d\n,ListLength(L));CreateListTail(L,20);printf(整体创建L的元素(尾插法));ListTraverse(L); return 0;
}
注 1若线性表需要频繁查找很少进行插入和删除操作时宣采用顺序存储结构。 2当线性表中的元素个数变化较大或者根本不知道有多大时最好用单链表结构。
静态链表
我们让数组的元素都是由两个数据域组成data和cur。也就是说数组的每个下标都对应一个data和一个cur。数据域data用来存放数据元素也就是通常我们要处理的数据而cur相当于单链表中的next指针存放该元素的后继在数组中的下标我们把cur叫做游标。
我们把这种用数组描述的链表叫做静态链表。
另外我们对数组第一个和最后—个元素作为特殊元素处理不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素即下标为0的元素的cur就存放备用链表的第一个结点的下标而数组的最后—个元素的cur则存放第一个有数值的元素的下标相当于单链表中的头结点作用当整个链表为空时则为0。
