《线性表的顺序存储.doc》由会员分享，可在线阅读，更多相关《线性表的顺序存储.doc（8页珍藏版）》请在三一文库上搜索。
1、线性表的顺序存储将线性表中的所有数据元素按照其逻辑顺序依次存储到从计算机内存储器中指定存储位置开始的一块连续的存储区域中。数据元素之间的逻辑关系通过数据元素的存储位置直接反映。 定义3：动态存储 #define LIST_Init_Size 100 (线性表存储空间的初始分配量) #define LISTINCREMENT 10 (线性表存储空间的分配增量) Typedef Struct ElemType *elem; /存储区域基地址 int length; /当前有效长度 int listsize；/当前分配的存储容量 SqList, *PSqList; SqList L; /定义顺序表P
2、SqList PL=&L;插入数据元素ListInsert(L,i,e)int ListInsert(PSqList PL,int i,ElemType e) /在顺序表L中第i个元素前插入数据元素e if (iPL-length+1)return ERROR; /i值不合法 if(PL-Length=PL-Listsize) /当前分配已满，增加空间 newbase=(ElemType*) realloc(PL-elem, (PL-Listsize+LISTINCREMENT）*sizeof(ElemType); if (!newbase) exit(OVERFLOW); /存储分配失败 P
3、L-elem=newbase; PL-listsize+=LISTINCREMENT; q=&(PL-elemi-1); /q为插入位置 for (p=&(PL-elemL.length-1; p=q; -p) *(p+1)=*p; /元素后移 *q=e; + PL-length /顺序表长度增1 return OK;删除数据元素ListDelete(L,i,e)int ListDelete(PSqList PL, int i, ElemType e) if (iPL-length) return ERROR; p=&(PL-elemi-1); e=*p; q=PL-elem+PL-lengt
4、h-1; /表尾的位置 for (+p; plength;/顺序表长度减1 return Ok;(算法)将两个有序(从小到大)的顺序表合并成一个有序的顺序表。 （1）初始化一个线性表Lc；（2）分别取La和Lb的当前数据元素ai和bj；（3）若aibj，则将ai插入到Lc，i+； 否则将bj插入到Lc中，j+。（4）重复第（2）和（3）步直到其中一个表的数据元素 取完为止。（5）将未取完的表中所剩数据元素，全部复制到Lc中。void SqListmerge(SqList p, SqList q， PSqList Pr) i=j=k=0; InitList(Pr); while (ip.leng
5、th & jq.length) /归并 if (p.elemielemk=p.elemi; i+; k+; else Pr-elemk=q. elemj; j+; k+; /end of (ip.length & jq.length)while (ielemk=p.elemi; i+;k+; while (jelemk=q.elemj; j+;k+; Pr-length=k; /或p.length+q.length顺序表应用实例例1设计一个算法,将x插入到一个有序(从小到大排序)的顺序表中,并保持顺序表的有序性。 void InsertList(PSqList PL, ElemType x)
6、i=0; if(x= PL-elemPL-length-1) PL-elemPL-length =x; / 插入表尾 else while (ilength & PL-elemilength-1;j=i;j-) PL-elemj+1=PL-elemj; PL-elemi=x; / 插入到表的第i个位置 PL-length+; 例2 已知长度为n的顺序表A,设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法, 删除A中所有值为item的数据元素。 A=(10,15,16,18,19,23,16,17,25,2710151618192316172527void delnode(PSqList
7、 PA, ElemType item) i=0; while (ilength) if (PA-elemi=item) for(j=i+1;jlength;j+) PA-elemj-1= PA-elemj; PA-length=PA-length-1; else i+; 改进后的算法void delnode(PSqList PA, ElemType item) i=0, j; while (ilength & PA-elemi!=item) i+; for(j=i+1;jlength;j+) if (PA-elemj != item) PA-elemi=PA-elemj; i+; PA-len
8、gth = i; 改进后的算法void delnode(PSqList PA, ElemType item) k=0,i=0; /k记录值等于item的元素个数 while (ilength) if (PA-elemi=item) k+; else /当前元素前移k个位置 PA-elemi-k=PA-elemi; i+; PA-length=PA-length-k; /顺序表A的长度递减 数据结构的链式存储用一组地址任意的存储单元存放数据元素。每个存储结点不仅包含数据元素本身的信息(称之为数据域),而且包含元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息(称为指针域),这样可以通过前
9、驱结点的指针域方便地找到后继结点的位置。 结点和单链表的C语言实现： typedef struct LNode ElemType data; struct LNode *next; /指向直接后继结点 LNode, *LinkList; LinkList LList; /表为空时LList=NULL单链表的特点空间上：可以使用离散的存储空间，提高了存储空间利用率时间上：只能从头指针开始顺序访问，不能随机访问。在单链表中,由于每个结点只包含有一个指向后继结点的指针,所以当访问过一个结点后,只能接着访问它的后继结点,而无法访问它的前驱结点。 插入数据元素ListInsert(&L,i,e)思路：先
10、在单链表L中找到第i-1个结点p,若存在这样的结点,将值为e的结点s插入到其后。 int ListInsert(LinkList LList, int i, ElemType e) p=LList; j=0; while (jnext; if (!p|ji-1) return ERROR; /i小于1或大于表长+1 s=(LinkList)malloc(sizeof(LNode); /建新结点ss-data=e; s-next=p-next; /将s插入到p之后 p-next=s; return OK;删除数据元素ListDelete(&L,i,&e)思路:先在单链表L中找到第i-1个结点p,
11、若存在这样的结点,且也存在后继结点,则删除该后继结点。 int ListDelete(LinkList LList,int i,ElemType &e) j=0; p=LList; while (jnext) /查找第i-1个结点或遍历到表尾 j+; p=p-next; if (!(p-next)|ji-1) return ERROR; /位置不合理 q=p-next; /q指向要删除的结点 p-next=q-next;/从单链表中删除q结点 free(q); /释放q结点 return OK;遍历算法DispList(L)void DispList(LinkList LList) p=LLi
12、st-next; while (p!=NULL) /判断是否到表尾 printf(“%c”,p-data); /随结点数据域类型而改变 p=p-next; printf(n); 线性表L中指定位置的某个数据元素GetElem(L,i, e)int GetElem(LinkList LList, int i, ElemType *e) p=LList; j=0;while (jnext;if (ji|p=NULL) return 0; /不存在第i个数据结点else /存在第i个数据结点 *e=p-data; return 1;按元素值查找LocateElem(L,e)int LocateEle
13、m(LinkList LList, ElemType e) p=LList-next; n=1; while (p!=NULL & p-data!=e) /判断是否到找到或者遍历到表尾 p=p-next; n+; if (p=NULL) return(0); else return(n); 应用实例例1：有一个带头结点的单链表head,其ElemType类型为char,设计算法使其元素递增有序。 解:若单链表中有一个或以上的数据结点,先构造只含一个数据结点的有序表(只含一个数据结点的单链表一定是有序表)。扫描原单链表余下的结点p(直到p=NULL为止),在有序表中通过比较找到插入p的前驱结点q
14、,然后将p插入到q之后(这里实际上采用的是直接插入排序方法)。 void Sort(LinkList head) p=head-next;if (p!=NULL) /head有一个或以上的数据结点 r=p-next; /r保存 p结点后继结点的指针 p-next=NULL; /构造只含一个数据结点的有序表 p=r; while (p!=NULL) /是否遍历到表尾 r=p-next;/r保存 p结点后继结点的指针 q=head; while (q-next!=NULL & q-next-datadata) q=q-next; /在有序表中找插入 p的前驱结点 q p-next=q-next;/
15、将 p插入到 q之后 q-next=p; p=r; /扫描原单链表余下的结点 /end of while /end of if /end of Sort例2有一个线性表（a1,a2,a3,an），采用带头结点的单链表L存储,设计一个算法将其就地逆置。所谓逆置指辅助空间应为O(1)。算法思想： 1)将p指针首先指向第一个有效结点。 2)将头结点L的next域置为NULL而变为空表。 3)并用p扫描（遍历）原单链表，依次将*p结点采用头插法插入到链表L中。void Reverse_1(LinkList LList) LinkList p = LList-next,q; LList-next = N
16、ULL; while(p != NULL) /是否遍历到表尾 q= p-next ; p-next = LList-next ; /头插法 L-next = p p= q; void Reverse_2(LinkList L) LinkList p,q,r; if(L-next != NULL) /非空链表 p = L-next /初始化当前结点 q = NULL ; /初始化新前驱结点 while(p != NULL) /是否遍历到表尾 r= p-next ; /保存当前结点的原后继结点 p-next = q; /逆置，即将当前结点的前驱改为后继 /*更新新前驱结点和当前结点*/ q=p;
17、p=r; L-next = q; /退出while后q指向原单链表的尾结点 例3：两个有序链表合并成一个有序链表void MergeList_L(LinkList La, LinkList Lb, LinkList Lc)/归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 pa=La-next; pb=Lb-next; Lc=pc=La; /用La的头结点作为Lc的头结点 while (pa & pb) /两个链表都没扫描到表尾 if (pa-datadata) /pa插入新表尾，并后移指针 pc-next=pa; pc=pa; pa=pa-next; else / pbb插
18、入新表尾，并后移指针 pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; /插入剩余段 free(Lb); /释放Lb的头结点 /MergeList_L顺序表的优点： u 存取数据速度快,数据元素的存储地址可以通过一个简单的解析式计算出来，可随机存取数据元素.u 占用的存储空间小(只需存放数据元素本身的信息，而无其他空间开销顺序表的缺点：u 存储分配需要事先进行。u 需占用连续存储空间u 插入操作需移动元素链表的优点： u 不需占用连续存储空间u 插入删除操作不需移动元素链表的缺点： u 存储数据麻烦、速度慢u 占用的存储空间大1基于时间的考虑（1）顺序表的是一种随机存取结构，而链表中的结点都需要从头指针开始遍历链表。（2）在链表中任何位置上插入与删除都只需修改指针，而顺序表需要移动表中将近一半的元素。尤其是对于结点信息量较大的表，开销很大。（3）对于只进行访问型操作的线性表，宜采用顺序存储，对于加工型线性表，则考虑使用链表。2. 基于空间的考虑（1）顺序表的存储空间在程序执行之间必须明确规定它的存储规模（静态分配），若表的变化较大，则存储规模难以确定（估计过大则容易造成空间的浪费，估计太小，将使得存储扩充增多）。 （2）链表的存储空间动态分配，只要内存空间尚有空闲，就不会溢出，适合于表长变化较大的情况。