线性表
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; // i为计数器 while (p != NULL) { if (P->data == x) { i++; } p = p->next; } // while,出循环时 i中的值即为 x结点个数 return i; } // CountX
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; }