线性表
1.已知长度为n的线性表采用顺序存储结构。写一个算法，删除线性表中所有值为x的元素。
方法一:用k记录顺序表L中等于x的元素个数，边扫描L边统计k, 并将不等于x的元素前移k个位置，最后修改L的长度。
void del_x_1(SqList &l, ElemType x)
{
int k = 0, i = 0;
while (i < L.length)
{
if (L.data[i] == x)
{
k++;
}
else
{
L.data[i - k] = L.data[i];
}
i++;
}
L.length = L.length - k;
}
方法二：用k记录顺序表L中不等于x的元素个数(即需要保存的元素个数), 边扫描L边统计k,并将不等于x的元素向前移动k个位置，最后修改L的长度。
void del_x_2(SqList &l, ElemType x)
{
int k=0;
for(i=0;i<L.length;i++)
{
if(L.data[i]!=x)
{
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
}
2.设计一个高效算法，将顺序表L的所有元素逆置。
算法思想:扫描顺序表L的前半部分元素，对于元素L.datai, 将其与后半部分的对应元素L.data[L.length-i-1]进行交换。
void Reverse(SqList &L)
{
ElemType temp;
for (i = 0; i < L.length / 2; i++)
{
temp = L.data[i];
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1] = temp;
}
}
3.统计出单链表 HL中结点的值等于给定值X的结点数。
int CountX(LNode *HL, ElemType x)
{
int i = 0;
LNode *p = HL;
while (p != NULL)
{
if (P->data == x)
{
i++;
}
p = p->next;
}
return i;
}
4.设有两个集合 A和集合 B，要求设计生成集合 C=A∩B的算法，其中集合 A、B和 C用链式存储结构表示 。
typedef struct node
{
int data;
struct node *next;
} lklist;
void intersection(lklist *ha, lklist *hb, lklist *&hc)
{
lklist *p, *q, *t;
for (p = ha, hc = 0; p != 0; p = p->next)
{
for (q = hb; q != 0; q = q->next)
{
if (q->data == p->data)
{
break;
}
}
if (q != 0)
{
t = (lklist *)malloc(sizeof(lklist));
t->data = p->data;
t->next = hc;
hc = t;
}
}
}
5.设计在单链表中删除值相同的多余结点的算法
typedef int datatype;
typedef struct node
{
datatype data;
struct node *next;
} lklist;
void delredundant(lklist *&head)
{
lklist *p, *q, *s;
for (p = head; p != 0; p = p->next)
{
for (q = p->next, s = q; q != 0;)
{
if (q->data == p->data)
{
s->next = q->next;
free(q);
q = s->next;
}
else
{
s = q, q = q->next;
}
}
}
}
6.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
typedef char datatype;
typedef struct node
{
datatype data;
struct node *next;
} lklist;
void split(lklist *head, lklist *&ha, lklist *&hb, lklist *&hc)
{
lklist *p;
ha = 0, hb = 0, hc = 0;
for (p = head; p != 0; p = head)
{
head = p->next;
p->next = 0;
if (p->data >= 'A' && p->data <= 'Z')
{
p->next = ha;
ha = p;
}
else if (p->data >= '0' && p->data <= '9')
{
p->next = hb;
hb = p;
}
else
{
p->next = hc;
hc = p;
}
}
}
7.设计两个有序单链表的合并排序算法。
void mergelklist(lklist *ha, lklist *hb, lklist *&hc)
{
lklist *s = hc = 0;
while (ha != 0 && hb != 0)
if (ha->data < hb->data)
{
if (s == 0)
{
hc = s = ha;
}
else
{
s->next = ha;
s = ha;
}
ha = ha->next;
}
else
{
if (s == 0)
{
hc = s = hb;
}
else
{
s->next = hb;
s = hb;
}
hb = hb->next;
}
if (ha == 0)
{
s->next = hb;
}
else
{
s->next = ha;
}
}
8.设计判断单链表中元素是否是递增的算法。
int isriselk(lklist *head)
{
if (head == 0 || head->next == 0)
{
return (1);
}
else
{
for (q = head, p = head->next; p != 0; q = p, p = p->next)
{
if (q->data > p->data)
{
return (0);
}
}
}
return (1);
}
串
9.设计在顺序存储结构上实现求子串算法。
void substring(chars[], longstart, longcount, chart[])
{
long i, j, length = strlen(s);
if (start < 1 || start > length)
{
printf("The copy position is wrong");
}
else if (start + count - 1 > length)
{
printf("Too characters to be copied");
}
else
{
for (i = start - 1, j = 0; i < start + count - 1; i++, j++)
{
t[j] = s[i];
}
t[j] = '\0';
}
}
数组
10.设计将所有奇数移到所有偶数之前的算法
void quickpass(int r[], int s, int t)
{
int i = s, j = t, x = r[s];
while (i < j)
{
while (i < j && r[j] % 2 == 0)
{
j = j - 1;
}
if (i < j)
{
r[i] = r[j];
i = i + 1;
}
while (i < j && r[i] % 2 == 1)
{
i = i + 1;
}
if (i < j)
{
r[j] = r[i];
j = j - 1;
}
}
r[i] = x;
}
树和二叉树
11.设计一个求结点 x在二叉树中的双亲结点算法。
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
} bitree;
bitree *q[20];
int r = 0, f = 0, flag = 0;
void preorder(bitree *bt, char x)
{
if (bt != 0 && flag == 0)
if (bt->data == x)
{
flag = 1;
return;
}
else
{
r = (r + 1) % 20;
q[r] = bt;
preorder(bt->lchild, x);
preorder(bt->rchild, x);
}
}
void parent(bitree *bt, char x)
{
int i;
preorder(bt, x);
for (i = f + 1; i <= r; i++)
if (q[i]->lchild->data == x || q[i]->rchild->data)
{
break;
}
if (flag == 0)
{
printf("not found x\n");
}
else if (i <= r)
{
printf("%c", bt->data);
}
else
{
printf("not parent");
}
}
12.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
typedef struct node
{
int data;
struct node *lchild, *rchild;
} bitree;
void swapbitree(bitree *bt)
{
bitree *p;
if (bt == 0)
{
return;
}
swapbitree(bt->lchild);
swapbitree(bt->rchild);
p = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = p;
}
13.在链式存储结构上建立一棵二叉排序树。
#define n 10
typedef struct node
{
int key;
struct node *lchild, *rchild;
} bitree;
void bstinsert(bitree *&bt, intkey)
{
if (bt == 0)
{
bt = (bitree *)malloc(sizeof(bitree));
bt->key = key;
bt->lchild = bt->rchild = 0;
}
else if (bt->key > key)
{
bstinsert(bt->lchild, key);
}
else
{
bstinsert(bt->rchild, key);
}
}
void createbsttree(bitree *&bt)
{
int i;
for (i = 1; i <= n; i++)
{
bstinsert(bt, random(100));
}
}
14.设计判断两个二叉树是否相同的算法。
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
} bitree;
int judgebitree(bitree *bt1, bitree *bt2)
{
if (bt1 == 0 && bt2 == 0)
{
return (1);
}
else if (bt1 == 0 || bt2 == 0 || bt1->data != bt2->data)
{
return (0);
}
else
{
return (judgebitree(bt1->lchild, bt2->lchild) * judgebitree(bt1->rchild, bt2->rchild));
}
}
15.设计判断二叉树是否为二叉排序树的算法。
int minnum = -32768, flag = 1;
typedef struct node
{
int key;
struct node *lchild, *rchild;
} bitree;
void inorder(bitree *bt)
{
if (bt != 0)
{
inorder(bt->lchild);
if (minnum > bt->key)
{
flag = 0;
}
minnum = bt->key;
inorder(bt->rchild);
}
}
16.设计一个在链式存储结构上统计二叉树中结点个数的算法。
void countnode(bitree *bt, int &count)
{
if (bt != 0)
{
count++;
countnode(bt->lchild, count);
countnode(bt->rchild, count);
}
}
17.设计计算二叉树中所有结点值之和的算法。
void sum(bitree *bt, int &s)
{
if (bt != 0)
{
s = s + bt->data;
sum(bt->lchild, s);
sum(bt->rchild, s);
}
}
图
18.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
typedef struct
{
int vertex[m];
int edge[m][m];
} gadjmatrix;
typedef struct node1
{
int info;
int adjvertex;
struct node1 *nextarc;
} glinklistnode;
typedef struct node2
{
int vertexinfo;
glinklistnode *firstarc;
} glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix g1[], glinkheadnode g2[])
{
int i, j;
glinklistnode *p;
for (i = 0; i <= n - 1; i++)
{
g2[i].firstarc = 0;
}
for (i = 0; i <= n - 1; i++)
{
for (j = 0; j <= n - 1; j++)
{
if (g1.edge[i][j] == 1)
{
p = (glinklistnode *)malloc(sizeof(glinklistnode));
p->adjvertex = j;
p->nextarc = g[i].firstarc;
g[i].firstarc = p;
p = (glinklistnode *)malloc(sizeof(glinklistnode));
p->adjvertex = i;
p->nextarc = g[j].firstarc;
g[j].firstarc = p;
}
}
}
}
查找
19．设计在顺序有序表中实现二分查找的算法。
struct record
{
int key;
int others;
};
int bisearch(struct recordr[], int k)
{
int low = 0, mid, high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (r[mid].key == k)
{
return (mid + 1);
}
else if (r[mid].key > k)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return (0);
}
排序
20.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在 O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki，右半部分的每个关键字均大于等于 Ki。
void quickpass(int r[], int s, int t)
{
int i = s, j = t, x = r[s];
while (i < j)
{
while (i < j && r[j] > x)
{
j = j - 1;
}
if (i < j)
{
r[i] = r[j];
i = i + 1;
}
while (i < j && r[i] < x)
{
i = i + 1;
}
if (i < j)
{
r[j] = r[i];
j = j - 1;
}
}
r[i] = x;
}
21．在链式存储结构上设计直接插入排序算法
void straightinsertsort(lklist *&head)
{
lklist *s, *p, *q;
int t;
if (head == 0 || head->next == 0)
{
return;
}
else
{
for (q = head, p = head->next; p != 0; p = q->next)
{
for (s = head; s != q->next; s = s->next)
{
if (s->data > p->data)
{
break;
}
}
if (s == q->next)
{
q = p;
}
else
{
q->next = p->next;
p->next = s->next;
s->next = p;
t = p->data;
p->data = s->data;
s->data = t;
}
}
}
}
22.设计在链式结构上实现简单选择排序算法。
void simpleselectsorlklist(lklist *&head)
{
lklist *p, *q, *s;
int min, t;
if (head == 0 || head->next == 0)
{
return;
}
for (q = head; q != 0; q = q->next)
{
min = q->data;
s = q;
for (p = q->next; p != 0; p = p->next)
{
if (min > p->data)
{
min = p->data;
s = p;
}
}
if (s != q)
{
t = s->data;
s->data = q->data;
q->data = t;
}
}
}
23.设计求结点在二叉排序树中层次的算法。
int lev = 0;
typedef struct node
{
int key;
struct node *lchild, *rchild;
} bitree;
void level(bitree *bt, int x)
{
if (bt != 0)
{
lev++;
if (bt->key == x)
{
return;
}
else if (bt->key > x)
{
level(bt->lchild, x);
}
else
{
level(bt->rchild, x);
}
}
}
24.设计在链式存储结构上合并排序的算法。
void mergelklist(lklist *ha, lklist *hb, lklist *&hc)
{
lklist *s = hc = 0;
while (ha != 0 && hb != 0)
{
if (ha->data < hb->data)
{
if (s == 0)
{
hc = s = ha;
}
else
{
s->next = ha;
s = ha;
}
ha = ha->next;
}
else
{
if (s == 0)
{
hc = s = hb;
}
else
{
s->next = hb;
s = hb;
}
hb = hb->next;
}
}
if (ha == 0)
{
s->next = hb;
}
else
{
s->next = ha;
}
}
25.设计在二叉排序树上查找结点 X的算法。
bitree *bstsearch1(bitree *t, int key)
{
bitree *p = t;
while (p != 0)
if (p->key == key)
{
return (p);
}
else if (p->key > key)
{
p = p->lchild;
}
else
{
p = p->rchild;
}
return (0);
}
26.设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。
void adjustheap(int r[], int n)
{
int j = n, i = j / 2, temp = r[j - 1];
while (i >= 1)
{
if (temp >= r[i - 1])
{
break;
}
else
{
r[j - 1] = r[i - 1];
j = i;
i = i / 2;
}
}
r[j - 1] = temp;
}
|