Skip to content

Instantly share code, notes, and snippets.

@bcho

bcho/anyview

Forked from anonymous/anyview
Created October 3, 2013 02:13
Show Gist options
  • Save bcho/6803640 to your computer and use it in GitHub Desktop.
Save bcho/6803640 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
anyview
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