可口可乐公司建设网站的目的是什么意思,wordpress如何设置友情链接,pc做网站服务器,网站底部友情链接本文是我编写的针对计算机专业考研复习《数据结构》所用资料内容选刊。主要目的在于向复习这门课程的同学说明#xff0c;此类问题不仅仅使用顺序表#xff0c;也可以使用链表。并且#xff0c;在复习中#xff0c;两种数据结构都要掌握。 若线性表中的数据元素相互之间可以… 本文是我编写的针对计算机专业考研复习《数据结构》所用资料内容选刊。主要目的在于向复习这门课程的同学说明此类问题不仅仅使用顺序表也可以使用链表。并且在复习中两种数据结构都要掌握。 若线性表中的数据元素相互之间可以比较并且数据元素在线性表中依值非递减或非递增有序排列则称该线性表为有序表Ordered List。有序表可以使用顺序表或链表存储。
例 3.10.2 向非递减的有序表中插入一个元素。已知有序表 L 和元素 e 将 e 插入到 L 中并且 L 依然是有序表。
【解】
1用顺序表存储有序表
【算法步骤】
从表头开始遍历有序表 L比较位置 i i i 的数据元素与 e 的大小若大于 e 则找到插入位置 i i i 。将位置 i i i 及后面的元素后移一个位置将元素 e 插入在位置 i i i 。
可以将以上步骤理解为顺序表中“查找元素”和“插入元素”两种算法的合并只不过此处查找的是顺序表中元素第一个大于 e 的位置。
【算法描述】 这里的算法描述采用类 C 的伪代码。 描述 1在已经学过的算法基础上修改
//顺序表存储结构
typedef struct{ElemType *elem; //存储空间的基地址int length; //当前长度
}SqList; //顺序表的结构类型为 SqList//查找顺序表 L 中大于元素 e 的位置
int LocateElem(SqList L, ElemType e){//在顺序表 L 中查找第一个值大于 e 的数据元素并返回其序号for (i 0; i L.length; i){if (L.elem[i] e) //修改原查找算法中的 (L.elem[i] e)return i1; //查找成功返回序号 i1}return 0; //查找失败返回 0
}//在顺序表中插入元素 e024节
Status ListInsert(SqList L, int i, ElemType e){//在顺序表 L 中第 i 个位置之前插入新元素 e//i 值的合法范围是 1≤i≤L.length1if ((i 1) || (i L.length1))return ERROR; //i 值不合法if (L.length MAXSIZE)return ERROR; //当前存储空间已满for (j L.length-1; j i-1; j--)L.elem[j1] L.elem[j]; //插入位置及之后的元素后移L.elem[i-1] e; //将新元素 e 放入第 i 个位置L.length; //表长加 1return OK;
}描述 2编写新的插入算法
//顺序表存储结构
typedef struct{ElemType *elem; //存储空间的基地址int length; //当前长度
}SqList; //顺序表的结构类型为 SqListStatus ListInsert(SqList L, ElemType){int i 0, j;while(i L.length L.elem[i] e)i; //找到第一个大于 e 的位置i 是索引不是位序号//将 elem[i] 及后面的元素后移一个位置for(j L.lenght; j i; j--) L.elem[j] L.elem[j-1];L.elem[i] e; //在索引 i 处放置 eL.length;
}【算法分析】
时间复杂度 O ( n ) O(n) O(n)
2用单链表存储有序表
在单链表中插入元素不需要移动结点只需要修改指针。故只需要找到第一个大于 e 的位置即可然后通过修改指针的指向实现本题所要求的算法。
但是要注意找到的应该是第一个大于 e 的结点的前驱将 e 插入到该位置之后这样才便于修改单链表的指针。
//单链表存储结构
typedef struct LNode{ElemType data; //结点的数据域struct LNode * next; //结点的指针域
}LNode, *LinkList; //LinkList 为指向结构体 LNode 的指针类型//在有序单链表中插入元素 e
void ListInsert(LinkList L, ElemType e){LNode *pre L;//查找第一个大于 e 的结点的前驱while(pre-next ! NULL pre-next-data e)pre pre-next; //向下移动指针s new LNode; //生成新结点 *ss-data e; //将结点 *s 插入到 *pre 之后s-next pre-next; pre-next s;
}【算法分析】
时间花费在移动指针查找到插入位置。
时间复杂度 O ( n ) O(n) O(n)
特别注意在复习中务必要亲自动手写代码。每年到邻近考试的时候都听说有同学背诵代码这其实不可取。
