数据结构经典程序代码

《数据结构》上机练习题

1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。

2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，

将它插入到序列中使它仍然有序，并输出排序后的序列。

3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“ NO”，

否则，将它从序列中删除它，并输出删除后的序列。

4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果

是有序的。

12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在

链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。

13、编写栈的压栈 push、弹栈 pop 函数，从键盘输入一组数据，逐个元素压入堆栈，然

后再逐个从栈中弹出它们并输出。

14、编写栈的压栈 push、弹栈 pop 函数，用它判别（）的匹配问题。

15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法 6、4），输出二叉树中序

遍历的结果。

16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法 6、4），输出二叉树先序

遍历的结果。

17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法 6、4），输出二叉树后序

高度。

21、给出一个无向图的邻接矩阵，输出各个顶点的度。

22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。

23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，

否则输出“NO”。

24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。

25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。

26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。

27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。．

答案：

//链表的存储结构

int data;

struct LNode *next;

}LNode,*list;

void creatList(list &l,int n)

{

int i;

list p,q;

p=l; //指针 p 指向头结点

for(i=0;i<n;i++)

{

q=(list)malloc(sizeof(LNode)); //新的结点

scanf("%d",&q->data);

p->next=q; //p 的下一个结点指向新开辟的结点 q

p=q; //将 p 指针指向 q

lc=pc=la; //默认将 la 做为 lc 的头结点（lb 亦可）

while(pa&&pb)

{ //让 pc 接到数据小的结点上，直到 pa,pb 两者有一指向空结点

if(pa->data<=pb->data)

{ pc->next=pa;pc=pa;pa=pa->next; }

else

{ pc->next=pb;pc=pb;pb=pb->next; }

}

pc->next=pa?pa:pb; //如果最后 la 有剩余结点，即将其直接加入到 lc 中，反之将 lb

的剩余结点加到 lc 中

void printList(list l)

p=l->next;

while(p)

{ printf("%d ",p->data);p=p->next;}

}

void main()

{

list la,lb,lc;

creatList(la,N);

creatList(lb,N);

mergeList(la,lb,lc);

}

//创建链表

void creatList(list &l,int n)

{

list p,q;

l=(list)malloc(sizeof(LNode));

p=l;

for(int i=0;i<n;i++)

p=q;

}

//判断元素 e 是否在链表中

int inList(list l,int e)

{

list p;

p=l->next;

while(p)

{

if(p->data==e)

p=p->next; //否则指针后移,继续找

}

return ERROR; //未找到，返回假值（没有执行 return OK;语句）

//插入元素

list p,q,s; //q 为新插入的元素开辟一个存储空间的指针，s 为 p 前一个指针，方便插入

{

while(s->next!=p) s=s->next; //找到 p 前的一个指针

q->next=p; // 画图好好理解 --->s--->p--->

s->next=q; // q--->

break;

}

p=p->next;

}

}

//输出链表

while(p)

{ printf("%d ",p->data); p=p->next;}

void main()

{

list l;

int e;

creatList(l,N);

scanf("%d",&e);

if(inList(l,e))

printf("YES ");

else

{

insertList(l,e);

}

#define ERROR 0

}LNode,*list;

//创建链表

void creatList(list &l,int n)

{

list p,q;

l=(list)malloc(sizeof(LNode));

p=l;