admin管理员组文章数量:1597850
【数据结构
有序表是指其中的所有元素以递增或递减方式有序排列。为了简单,假设有序表以递增排列。
有序表的基本运算
- InitLIst(&L):初始化有序表L
- DestoryList(&L):销毁有序表L
- ListEmpty(L):判断空表
- ListLength(L):求有序表L的元素个数
- DispList(L):输出表L
- GetElem(L, i, &e):求有序表L的第i个元素
- LocateElem(L, e):返回第一个元素为e的序号
- ListInsert(&L, e):插入一个元素值为e的元素
- ListDelete(&L, i, &e):删除第i个元素,并返回删除元素值
由于有序表中元素之间的逻辑关系与线性表中的完全相同,所以可以采用顺序表(SqList)和链表(单链表LinkNode、双链表DLinkNode)进行存储。
有序表的ListInsert()算法
1. 用顺序表
存储有序表
// 在有序表里插入元素e
void ListInsert(SqList *&L, ElemType e) { int i=0, j;while(i<L->length && L->data[i]<e) { // 找到小于e的位置i++;}for(j=ListLength(L); j<i; j--) { // 将data[i]及后面的元素向后移动一位L->data[i+1] = L->data[i];}L->data[i] = e;L->length++;
}
2. 用单链表
存储有序表
void ListInsert(LinkNode *&L, ElemType e) {LinkNode *p=L, *s;while(p->next->data<e && p->next!=NULL) { // 找到小于e的位置p = p->next;}s = (LinkNode *)malloc(sizeof(LinkNode)); // 新建一结点,将e元素存入结点s的数据域中,再将s结点插入该位置s->next = NULL;s->data = e;s->next = p->next;p->next = s;
}
有序表的归并算法
假设有两个有序表LA和LB,设计一个算法,将它们合并成一个有序表LC(假设每个有序表中和两个有序表间均不存在重复元素),要求不破坏原有表LA和LB.
思路:将两个有序表合并成一个有序表可以采用二路归并算法。
分别扫描LA和LB两个有序表,当两个有序表都没有遍历完时循环:比较LA和LB的当前元素,将其中较小的元素放入LC中,再从较小元素所在的有序表中取下一个元素。重复这一过程,直到LA或LB遍历完毕,最后将未遍历完的有序表中余下的元素放入LC中。
举例:LA=(1,3, 5),LB=(2, 4, 8, 10),以下是其二路归并过程。
1. 顺序表
存放有序表
时的二路归并算法
void UnionList(SqList *LA, SqList *LB, SqList *&LC) {int i=0, j=0, k=0; // i, j分别是LA, LB的下标,k为LC元素的个数LC=(SqList *)malloc(sizeof(SqList));while(i<LA->length && j<LB->length) { // 比较i和j对应的元素if(LA->data[i] < LB->data[j]) {LC->data[k] = LA->data[i];k++;i++;}else{LC->data[k] = LA->data[j];k++;j++;}}while(i<LA->length){ // LA没有遍历完,将其余的元素全部放入LC中LC->data[k] = LA->data[i]; k++;i++;}while(j<LB->length){ // LB没有遍历完,将其余的元素全部放入LC中LC->data[k] = LB->data[j]; k++;j++;}LC->length = k;}
2. 单链表
存放有序表
时的二路归并算法
void UnionList(LinkNode *LA, LinkNode *LB, LinkNode *&LC) {LinkNode *pa=LA->next, *pb=LB->next, *r, *s; LC = (LinkNode *)malloc(sizeof(LinkNode));r = LC;while(pa!=NULL && pb!=NULL) {if(pa->data < pb->data) {s = (LinkNode *)malloc(sizeof(LinkNode));s->data = pa->data; // 复制pa结点r->next = s; // 连接到LC头结点后面r = s;pa = pa->next;}else{s = (LinkNode *)malloc(sizeof(LinkNode));s->data = pb->data; // 复制pb结点r->next = s; // 连接到LC头结点后面r = s;pb = pb->next;}}while(pa!=NULL) { // LA剩余s = (LinkNode *)malloc(sizeof(LinkNode));s->data = pa->data; // 复制pa剩下的结点r->next = s; // 连接到LC头结点后面r = s;pa = pa->next;}while(pb!=NULL) { // LB剩余s = (LinkNode *)malloc(sizeof(LinkNode));s->data = pb->data; // 复制pb剩下的结点r->next = s; // 连接到LC头结点后面r = s;pb = pb->next;}r->next = NULL; // 将LC表的尾结点的next域置空
}
两种算法的设计思路相同,我们来计算一下它们的时间复杂度。
第1个while循环在最坏情况下的执行次数为O(ListLength(LA)+ListLength(LB)),第2个while循环在最坏情况下的执行次数为O(ListLength(LA)),第3个while循环在最坏情况下的执行次数为O(ListLength(LB)),所以算法的时间复杂度为O(ListLength(LA)+ListLength(LB))。
有序表的应用
算法1:留下三个表数据值相同的结点
例题
已知3个单链表存储的有序表LA,LB,LC,元素值依次递增,使链表LA中仅留下3个表中均包含的数据元素的结点,且没有数据值相同的结点,并释放LA中其他结点。要求算法的时间复杂度为O(m+n+p),其中m,n,p分别为3个表的长度。(假设每个单链表不存在数据值相同的结点,但3个单链表中可能存在数据值相同的结点)
思路
先以单链表LA的头结点作为一个空表,r指向新建单链表的尾结点,以pa遍历单链表LA中的数据结点,判断它是否在单链表LB,LC中,若同时在,则为公共元素,将其连在r结点后面,否则删除它。
算法
void Commnode(LinkNode *&LA, LinkNode *LB, LinkNode *LC){LinkNode *pa=LA->next, *pb=LB->next, *pc=LC->next, *q, *r;LA->next = NULL;r = LA; // r指向新单链表的尾结点while(pa!=NULL) { // 查找公共结点并建立新链表LAwhile(pb!=NULL && pa->data > pb->data) { // pa结点与LB中的pb结点比较pb=pb->next;}while(pc!=NULL && pa->data > pc->data) { // pa结点与LC中的pc结点比较pc=pc->next;}if(pb!=NULL && pc!=NULL && pa->data == pb->data && pa->data == pc->data){ // 若pa结点是公共结点r->next = pa;r = pa;pa = pa->next;}else{ // 若pa结点不是公共结点,删除pa结点q = pa;pa = pa->next;free(q);}}r->next=NULL;
}
算法2:删除值域重复的结点
例题
已知一个有序单链表L(允许出现值域重复的结点),设计一个高效的算法删除值域重复的结点。
思路
有序单链表中,相同值域的结点都是相邻的。用p遍历递增单链表,所指结点的值域=后继结点值域,则删除后者。
算法
void dels(LinkNode *&L){LinkNode *p=L->next, *q;while(p->next!=NULL) {if(p->data==p->next->data){ // 找重复值域的结点q = p->next;p->next = q->next;free(q);}else{p = p->next;}}
}
该算法的时间复杂度为O(n),其中n为等长有序单链表L中数据结点的个数。
算法3:找出两个序列的中位数
例题
一个长度为n(n>1)的升序序列S,处在第n/2个位置的数称为S的中位数。现有两个等长的升序序列A和B,设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。假设升序序列采用顺序表存储。
思路
当升序序列采用顺序表存储,一个升序序列S的中位数就是S->data[S->length/2]元素。而两等长升序序列的中位数,是将它们二路归并后的一个升序序列S的中位数。实际上不需要求出S的全部元素,用k记录当前归并的元素的个数,当k=S1->length时,进行归并的那个元素就是中位数。
算法
ElemType M_Search(SqList *A, SqList *B){ // A、B长度相同int i=0, j=0, k=0;while(i<A->length && j<B->length){ // 两个序列均没有扫描完k++; // 当前归并的元素个数+1if(A->data[i] < B->data[j]){ // 归并较小的元素 A->data[i]if(k==A->length){return A->data[i];}i++;}else{ // 归并较小的元素 B->data[j]if(k==B->length){return B->data[j];}j++;}}
}
该算法的时间复杂度为O(n),空间复杂度为O(1),其中n为等长有序顺序表A、B中元素的个数。
本文标签: 数据结构
版权声明:本文标题:【数据结构 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1716956475a525028.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论