Skip to content

Instantly share code, notes, and snippets.

Created October 3, 2013 02:12
Show Gist options
  • Save anonymous/6803633 to your computer and use it in GitHub Desktop.
Save anonymous/6803633 to your computer and use it in GitHub Desktop.
2.16③ 已知指针la和lb分别指向两个无头结点单链表中
的首元结点。 下列算法是从表la中删除自第i个元素起共
len个元素后,将它们插入到表lb中第i个元素之前。试问
此算法是否正确? 若有错,则请改正之。
实现下列函数:
Status DeleteAndInsertSub(LinkList &la, LinkList &lb,
int i, int j, int len);
// la和lb分别指向两个单链表中第一个结点, */
/* 本算法是从la表中删去自第i个元素起共len个元素,*/
/* 并将它们插入到lb表中第j个元素之前, */
/* 若lb表中只有j-1个元素,则插在表尾。 */
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.17② 试写一算法,在无头结点的动态单链表上实现
线性表操作INSERT(L,i,b),并和在带头结点的动态单
链表上实现相同操作的算法进行比较。
实现下列函数:
void Insert(LinkList &L, int i, ElemType b);
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.18② 同2.17题要求。试写一算法,
实现线性表操作DELETE(L,i)。
实现下列函数:
void Delete(LinkList &L, int i);
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
◆2.19③ 已知线性表中的元素以值递增有序排列,并以
单链表作存储结构。试写一高效的算法,删除表中所有值
大于mink且小于maxk的元素(若表中存在这样的元素)同时
释放被删结点空间,并分析你的算法的时间复杂度(注意:
mink和maxk是给定的两个参变量,它们的值可以和表中的
元素相同,也可以不同)。
实现下列函数:
void DeleteSome(LinkList &L, ElemType mink, ElemType maxk);
/* Delete all the elements which value is between mink and */
/* maxk from the single sorted LinkList with head pointer L.*/
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.20② 同2.19题条件,试写一高效的算法,删除表中所
有值相同的多余元素 (使得操作后的线性表中所有元素的
值均不相同) 同时释放被删结点空间,并分析你的算法的
时间复杂度。
实现下列函数:
void Purge(LinkList &L);
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
◆2.21③ 试写一算法,实现顺序表的就地逆置,
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。
实现下列函数:
void Inverse(SqList &L);
顺序表类型定义如下:
typedef struct {
ElemType *elem;
int length;
int listsize;
} SqList;
◆2.22③ 试写一算法,对单链表实现就地逆置。
实现下列函数:
void Inverse(LinkList &L);
/* 对带头结点的单链表L实现就地逆置 */
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.23③ 设线性表A=(a1,...,am), B=(b1,...,bn),试写
一个按下列规则合并A、B为线性表C的算法,即使得
C=(a1,b1,...,am,bm,bm+1,...,bn) 当m≤n时;
或者 C=(a1,b1,...,an,bn,an+1,...,am) 当m>n时。
线性表A、B和C均以单链表作存储结构,且C表利用A表和
B表中的结点空间构成。注意:单链表的长度值m和n均未
显式存储。
实现下列函数:
void Merge(LinkList ha, LinkList hb, LinkList &hc)
/* 依题意,合并带头结点的单链表ha和hb为hc */
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
◆2.24④ 假设有两个按元素值递增有序排列的线性表
A和B,均以单链表作存储结构,请编写算法将A表和B表
归并成一个按元素值递减有序(即非递增有序,允许表
中含有值相同的元素)排列的线性表C, 并要求利用原
表(即A表和B表)的结点空间构造C表。
实现下列函数:
void Union(LinkList &lc, LinkList la, LinkList lb);
/* 依题意,利用la和lb原表的结点空间构造lc表 */
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.26④ 假设以两个元素依值递增有序排列的线性表
A和B分别表示两个集合(即同一表中的元素值各不相
同),现要求另辟空间构成一个线性表C,其元素为A
和B中元素的交集,且表C中的元素也依值递增有序排
列。试对单链表编写求C的算法。
实现下列函数:
void Intersect(LinkList &hc, LinkList ha, LinkList hb);
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.31② 假设某个单向循环链表的长度大于1,且表
中既无头结点也无头指针。已知s为指向链表中某个
结点的指针,试编写算法在链表中删除指针s所指结
点的前驱结点。
实现下列函数:
ElemType DeleteNode(LinkList s);
/* 删除指针s所指结点的前驱结点,并返回被删结点的元素值 */
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.32② 已知有一个单向循环链表,其每个结点中
含三个域:prev、data和next,其中data为数据域,
next为指向后继结点的指针域,prev也为指针域,
但它的值为空(NULL),试编写算法将此单向循环链
表改为双向循环链表,即使prev成为指向前驱结点
的指针域。
实现下列函数:
void PerfectBiLink(BiLinkList &CL);
双向循环链表类型定义如下:
typedef struct BiNode {
ElemType data;
int freq; // 2.38题用
struct BiNode *prev,
*next;
} BiNode, *BiLinkList;
◆2.33③ 已知由一个线性链表表示的线性表中含有
三类字符的数据元素(如:字母字符、数字字符和其
它字符),试编写算法将该线性链表分割为三个循环
链表,其中每个循环链表表示的线性表中均只含一类
字符。
实现下列函数:
void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);
单链表类型定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
2.37④ 设以带头结点的双向循环链表表示的线性
表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的
算法,将L改造为L=(a1,a3,...,an,...,a4,a2)。
实现下列函数:
void ReverseEven(BiLinkList &L);
双向循环链表类型定义如下:
typedef struct BiNode {
ElemType data;
int freq; // 2.38题用
struct BiNode *prev,
*next;
} BiNode, *BiLinkList;
◆2.38④ 设有一个双向循环链表,每个结点中除有
prev、data和next三个域外,还增设了一个访问频度
域freq。在链表被起用之前,频度域freq的值均初始
化为零, 而每当对链表进行一次LOCATE(L,x)的操作
后, 被访问的结点(即元素值等于x的结点)中的频
度域freq的值便增1, 同时调整链表中结点之间的次
序,使其按访问频度递减的次序顺序排列,以便始终
保持被频繁访问的结点总是靠近表头结点。试编写符
合上述要求的LOCATE操作的算法。
实现下列函数:
BiLinkList Locate(BiLinkList dh, ElemType x);
双向循环链表类型定义如下:
typedef struct BiNode {
ElemType data;
int freq;
struct BiNode *prev,
*next;
} BiNode, *BiLinkList;
◆2.39③ 试对稀疏多项式Pn(x)采用存储量同多项式项
数m成正比的顺序存储结构,编写求Pn(x0)的算法(x0为
给定值),并分析你的算法的时间复杂度。
实现下列函数:
float Evaluate(SqPoly pn, float x);
/* pn.data[i].coef 存放ai, */
/* pn.data[i].exp存放ei (i=1,2,...,m) */
/* 本算法计算并返回多项式的值。不判别溢出。 */
/* 入口时要求0≤e1<e2<...<em,算法内不对此再作验证*/
多项式的顺序存储结构:
typedef struct {
int coef;
int exp;
} PolyTerm;
typedef struct {
PolyTerm *data;
int length;
} SqPoly;
◆2.41② 试以循环链表作稀疏多项式的存储结构,
编写求其导函数的算法,要求利用原多项式中的结
点空间存放其导函数(多项式),同时释放所有无
用(被删)结点。
实现下列函数:
void Difference(LinkedPoly &pa);
/* 稀疏多项式 pa 以循环链表作存储结构, */
/* 将此链表修改成它的导函数,并释放无用结点 */
链式多项式的类型定义:
typedef struct PolyNode {
int coef;
int exp;
struct PolyNode *next;
} PolyNode, *PolyLink; // 多项式元素(项)结点类型
typedef PolyLink LinkedPoly; // 链式多项式
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment