数据结构实验报告
第四次实验
学号：20141060106 姓名：叶佳伟
一、实验目的
1、复习线性表、栈、队列的逻辑结构、存储结构及基本操作；
2、掌握顺序表、（带头结点）单链表、顺序栈、链队列；
3、了解有顺表、链栈、循环队列。
3、了解有顺表、链栈、循环队列。
二、实验内容
1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：
（ 1） OrderInsert(&L, e, int (*compare)(a, b))//根据有序判定函数compare，在有序表L的适当位置插入元素e；
（ 2） OrderInput(&L, int (*compare)(a, b))//根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L；
（ 3） OrderMerge(&La, &Lb, &Lc, int (*compare)())//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。
2、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作：（ 1） Status InitStack (&S) //构造空栈S；
（ 2） Status Push(&S, e) //元素e入栈S；
（ 3） Status Pop(&S, &e) //栈S出栈，元素为e。
3、（必做题）假设队列中数据元素类型是字符型，请采用链队列实现队列的以下基本操作：（ 1） Status InitQueue(&Q) //构造空队列Q；
（ 2） Status EnQueue(&Q, e) //元素e入队列Q；
（ 3） Status DeQueue (&Q, &e) //队列Q出队列，
元素为e。
三、算法描述
（采用自然语言描述）
⒈⑴分别插入第一个链表和第二个链表的数据；
⑵根据有序判定函数compare，将两个有序表La和Lb归并为个有序表。
⑶输出归并后的有序表。
2.
⑴构造一个栈的结构体
⑵利用函数initstack构造空栈
⑶Push函数将元素依次存储到栈里
⑷利用pop函数输出栈顶元素
⑴构造Queueptr的结构体
⑵构造一个队列的结构体
⑶利用函数InitQueue构造空队列
⑷EnQueue函数将元素依次存储到栈里
⑸利用DeQueue函数输出栈顶元素
四、详细设计
（画出程序流程图）
五、程序代码
（给出必要注释）
第一题：#include
#include
typedef struct LNode
{int date;
struct LNode *next;
} LNode,*Link;
typedef struct LinkList
{Link head;
int len;
} LinkList;
int compare (LinkList *L,int e)
{int Lc=0;
Link p;
p=L->head;
p=p->next;
while(p!=NULL)
{if(e>p->date)
{p=p->next; Lc++;}
else
return Lc;
}
return Lc;
}
void OrderInsert (LinkList *L,int e,int (*compare)())
{Link temp,p,q;
int Lc,i;
temp=(Link)malloc(sizeof(LNode));
temp->date=e;
p=q=L->head;
p=p->next;
Lc=(*compare)(L,e);
if(Lc==L->len)
{while(q->next!=NULL)
{q=q->next;}
q->next=temp;
temp->next=NULL;
}
else
{for(i=0; i{p=p->next;q=q->next;}
q->next=temp;temp->next=p;
}
++L->len;
}
void OrderMerge (LinkList *La,LinkList *Lb,int (*compare)()) {int i,Lc=0;
Link temp,p,q;
q=La->head->next;
while(q!=NULL)
{p=Lb->head;
temp=(Link)malloc(sizeof(LNode));
temp->date=q->date;
Lc=(*compare)(Lb,q->date);
if(Lc==Lb->len)
{while(p->next!=NULL)
{p=p->next;}
p->next=temp;
temp->next=NULL;
}
else
{for(i=0; i{p=p->next;}
temp->next=p->next;
p->next=temp;
}
q=q->next;
++Lb->len;
}
}
LinkList *Initialize (LinkList *NewList)
{int i;
Link temp;
NewList=(LinkList *)malloc((2+1)*sizeof(LinkList));
for(i=0; i<2+1; i++)
{temp=(Link)malloc(sizeof(LNode));
temp->date=0;
temp->next=NULL;
(NewList+i)->head=temp;
(NewList+i)->len=0;
}
return NewList;
}
void Insert (LinkList *NewList)
{int a,i;
char c;
printf("在第1个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据\n"); for(i=0; i<2; i++)
{while(1)
{scanf("%d",&a);
c=getchar();
if(c=='.')
