Linear table
1. The linear table with known length n adopts sequential storage structure. Write an algorithm to delete all elements with the value of x in the linear table.
Method 1: record the number of elements equal to X in the sequence table l with k, count k while scanning L, move the elements not equal to x forward k positions, and finally modify the length of 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;
}
Method 2: use k to record the number of elements not equal to X in the sequence table L (i.e. the number of elements to be saved), count k while scanning L, move the elements not equal to x forward k positions, and finally modify the length of 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. Design an efficient algorithm to invert all elements of sequence table L.
Algorithm idea: scan the first half of the elements of the sequence table L. for the element L.data i , exchange it with the corresponding element L.data[L.length-i-1] in the second half.
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. Count the number of nodes in the single linked list HL whose value is equal to the given value X.
int CountX(LNode *HL, ElemType x)
{
int i = 0;
LNode *p = HL; // i is the counter
while (p != NULL)
{
if (P->data == x)
{
i++;
}
p = p->next;
} // while, the value in i is the number of x nodes when the loop is out
return i;
} // CountX
4. There are two sets A and B. It is required to design an algorithm to generate set C=A ∩ B, in which sets A, B and C are represented by chain storage structure.
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. Design an algorithm to delete redundant nodes with the same value in the single linked list
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. Assuming that there are only three types of data elements (capital letters, numbers and other characters) in the single linked list, it is required to use the node space in the original single linked list to design the algorithm of three single linked lists, so that each single linked list contains only similar characters.
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. Design the merge sorting algorithm of two ordered single linked lists.
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. Design an algorithm to judge whether the elements in the single linked list are incremental.
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);
}
strand
9. Design and implement the substring algorithm on the sequential storage structure.
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';
}
}
array
10. Design an algorithm to move all odd numbers to all even numbers
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;
}
Tree and binary tree
11. Design an algorithm to find the parent node of node x in binary tree.
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. Design an algorithm to exchange the left and right subtrees of all nodes in the binary tree on the chain storage structure.
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. Establish a binary sort tree on the chain storage structure.
#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. Design an algorithm to judge whether two binary trees are the same.
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. Design an algorithm to judge whether the binary tree is a binary sort tree.
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. Design an algorithm to count the number of nodes in the binary tree on the chain storage structure.
void countnode(bitree *bt, int &count)
{
if (bt != 0)
{
count++;
countnode(bt->lchild, count);
countnode(bt->rchild, count);
}
}
17. Design an algorithm to calculate the sum of all node values in binary tree.
void sum(bitree *bt, int &s)
{
if (bt != 0)
{
s = s + bt->data;
sum(bt->lchild, s);
sum(bt->rchild, s);
}
}
chart
18. Design an algorithm to convert the adjacency matrix of undirected graph into the corresponding adjacency table.
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;
}
}
}
}
lookup
19. Design an algorithm to realize binary search in sequential table.
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);
}
sort
20. There is a set of initial record keyword sequence (K1, K2,..., Kn). It is required to design an algorithm to divide the linear table into two parts within the time complexity of O(n), in which each keyword in the left half is less than Ki and each keyword in the right half is greater than or equal to 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. Design a direct insertion sorting algorithm on the chain storage structure
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. Design and implement a simple selection sorting algorithm on the chain structure.
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. Node sorting algorithm in binary tree design.
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. Design the algorithm of merging and sorting on the chain storage structure.
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. Design an algorithm to find node X on binary sort tree.
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. Let the keyword sequence (k1, k2,..., kn-1) be the heap, and design an algorithm to adjust the keyword sequence (k1, k2,..., kn-1, x) to the heap.
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;
}