7.c

数据结构168个实验程序,很全面

#define TRUE 1
#define FALSE 0
typedef int status;
#include<malloc.h>
#include<stdio.h>
#define MAXSIZE 10000        //字符空间的最大容量
#define MAXLEN   20         //单词的最大长度
#define MAXNUM   16          //一行中单词最多个数
typedef struct {
	char stores[MAXSIZE];
	int freep;
}HeapSpace;
HeapSpace sp;         //单词所占的堆空间，初始化令sp.freep=0

typedef struct {
	int stadr;        //单词所含字符在堆空间的起始位置

	int len;          //单词的长度
}WordType;

typedef struct {
	char ch[MAXLEN];
	int size;
}Sequence;
status NewWord(WordType &nw,Sequence cha);
void DestroyWord(WordType &wd);
//销毁单词的wd结构(令wd.stadr=wd.len=0)
void CopyWord(WordType &newd,WordType oldw);
//生成一个和oldw相同的单词（newd.stadr=oldw.stadr;newd.len=oldw.len）
int WordCmp(WordType wd1,WordType wd2);
//若wd1<wd2,则返回-1；若wd1==wd2,，则返回0；否则返回1
void PrintWord(WordType wd);

status NewWord(WordType &nw,Sequence cha){
	if(sp.free+cha.size>=MAXSIZE)
		return FALSE;//存储单词的堆空间已满
	else {
		i=sp.freep;sp.freep=sp.freep+cha.size;
		for (k=0;k<cha.size;k++)
			sp.stores[i+k]=cha.ch[k];
		nw.stadr=i;ne.len=cha.size;return TRUE;
	}
}
int WordCmp(WordType wd1,WordType wd2) {
	si=wdl.stadr;sj=wda.stadr;k=0;
	while (k<wd1.len &&k<wd2.len)
		if (sp.stores[si+k]==sp.stores[sj+k])  k++;
		else if (sp.stores[si+k]<sp.stores[sj+k])   return -1;
		else return 1;
		if (wd1.len==wd2.len)  return 0;
		else if (wd1.len<wd2.len)  return -1;
		else return 1;
}

typedef WordType ElemType;
typedef struct NodeType {
	ElemType data;
	NodeType *next;
}NodeType,*LinkType;  //结点类型，指针类型
status MakeNode(LinkType &p,ElemType e) {
//分配由p指向的数据元素e 后继为空的结点，并返回TRUE，若分配失败，则返回FALSE
	p=(LineType)malloc(sizeof(NodeType));
	if(!p) return FALSE;
	p->data=e; p->next=NULL; return TRUE;
}
void FreeNode(LinkType &p);
//释放p所指向结点空间，首先DestroyWord(p->data)
ElemType Elem(LinkType p);
//若指针p!=NULL,则返回p所指结点的数据元素（单词），否则返回'#'
LinkType SuccNode(LinkType p);
//若指针p!=NULL，则返回p所指结点的后继元素的指针，否则返回NULL

//有序表采用有序链表实现。链表设头尾两个指针和表长数据域，并附设头结点，头结点的数据域没有实在意义
typedef struct{
	LinkType head,tail;  //
	int size;
}OrderedList;//有序链表类型
typedef struct { //记录匹配成功的单词在目标词汇表中的位置
	int eqelem[MAXNUM];
	int last;
}EqelemList;

status InitList(OrderedList &L);
//构造一个带头结点的空的有序链表L,并返回TRUE;若分配空间失败，则
//令L.head为NULL,并返回FALSE
void DestroyList(OrderedList &L);
//销毁有序链表L，并释放链表中每个结点所占空间
status ListEmpty(OrderedList L);
//若L不存在或L为空表，则返回TRUE，否则返回FALSE
int ListLength(OrderedList L);
//返回链表的长度，若链表不存在，其长度为零
OrderedList GetElemPos(OrderedList L,int pos);
//返回链表中第pos个元素的位置
status LocateElem(OrderedList L,ElemType e,LinkType &q);
//若有序链表L存在且表中存在元素e,则q指示L中第一个值为e的结点的位置，并返回TRUE；
//否则q指示第一个大于e的元素的前驱的位置，并返回FALSE
void InsertAfter(OrderedList &L,LinkType q,LinkType s);
//在已存在的有序链表L中q所指示的结点之后插入指针s所指结点
void ListCompare(OrderedList La,OrderedList Lb,EqulemList &s);
//将La和Lb中共有的s.size个单词在La中的序号记录再线性表s中
void TraverseList(LinkType p,status(* visit)());
//从p(p!=NULL)指示的结点开始，依次对每个结点调用函数visit()

status InitList(OrderedList &L)
{
	if(MakeNode(L.head,wd)){ //头结点的虚设元素为 “空词”
		L.tail=L.head; size=0;return TRUE;
	}
	else { L.head=NULL;return FALSE;}
}//InitList
void DestroyList(OrderedList &L)
{
	p=L.head;
	while(p) {q=p;  p=SuccNode(p);  FreeNode(q);}
	L.head=L.tail=NULL;
}//DestroyList
status LocateElem (OrderedList L,ElemType e,LinkType &p)
{
	if(!L.head)  return FALSE;
	pre=L.head; p=pre->next;  //pre指向p^的前驱，p指向第一个元素结点
	while(p&&WordCmp(p->data,e)==-1)
	{ pre=p;p=SuccNode(p); }
	if (p&&WordCmp(p->data,e)==0)  return TRUE;
	p=pre; return FALSE;
}//LocateElem
void InsertAfter (OrderList  &L,LinkType q,LinkType s)
{
	if (L.head&&q&&s) {
		s->next=q->next;  a->next=s;
		if (L.tail==q) L.tail=s;
		L.size++;
	}
}//InsertAfter
void ListCompare(OrderedList La,OrderedList Lb,EqulemList &s)
{
	//将La和Lb中共有的s.last个单词在La中的序号记录在线性表中
	if(La.head&&Lb.head) {
		pa=SuccNode(La.head); pb=SuccNode(Lb.head);
		s.last=pos=0; //pos指示当前比较的单词在La中的序号
		while (pa&&pb)
			if (WordCmp(Elem(pa),Elem(pb)==0) {
				s.eqelem[s.last++]=pos++;
				pa=SuccNode(pa); pb=SuccNode(pb);
			}
			else if (WordCmp(Elem(pa),Elem(pb)==-1)
			{  pa=SuccNode(pa); pos++; }
			else pb=SuccNode(pb);
	}
}
typedef void (*VisitFunc)(LinkType p,int n);//访问结点的过程类型
void ListTraverse(LinkType p,VisitFunc visit)
{
	while (p) {visit(p);  p=SuccNode(p); }
}//ListTraverse

typedef struct Node{
	int elem; //被测试单词在文件中的行号
	Node  *next;
}Node,*Link;
typedef struct {
	WordType data;  //被测试的单词
	int count;  //再文件中出现的次数
	Link next;  //记录所有“行号”的链表的头指针
}HeadNode;
void GetAWord (FILE *f,Sequence &st);  //从文件指针所指字符起提取一个单词的字符序列st
status ExtractWords(FILE *f,OrderedList &ta);
//提取文件指针所指行中所有单词，并构成单词的有序表ta,同时返回TRUE；之后
//文件指针指向下一行的第一个字符；若空间不足生成链表，则返回FALSE;
status match(FILE *f,OederedList pat,ResultType &rs);
//文件已打开，文件指针指向文件中的第一个字符；
//pat为包含所有待查寻单词的有序表，rs为查询结果
int feoln(FILE *f)
{
//	辅助函数，判定文件行结束
	char cha=fgetc(f); ungetc(cha, f);
	if (cha=='\n') return TRUE;
	return FALSE;
}
status ExtractWords(FILE *f, OrderedList &ta)
{
	//从文本文件指针当前所指字符起提取一行中所有单词
	if (!InitList(ta))  return FALSE;
	while (!feof(f)&&!feoln(f)) {
		GetAWord(f,str);
		if(str.size!=0)
			if(NewWord(nwd,str))
				if(!LocateElem(ta,nwd,p))
					if(MakeNode(s,nwd))InserAfter(ta,p,s);
	}
	if(feoln(f)) lendch=getc(f); //滤去行结束符
	return TRUE;
}
status match(FILE *f,OederedList pat,ResultType &rs)
{
	linenum=1;  //linenum 指示当前被查询的行号
	failed=FALSE;
	do {
		if(!ExtractWords(f,sa))  failed=TRUE; //查询不能继续进行
		else
			ListCompare(pat,sa,eqlist); //将当前行中单词和给定待查寻单词进行比较
		for (i=0;i<eqlist.last;i++){
			k=eqlist.eqelem[i];  //该行中含有目标词汇表中第k个单词
			p=(Link)malloc(sizeof(Node));
			if (!p) return FALSE;
			p->elem=linenum; p->next=rs[k].next;
			rs[k].next=p;  rs[k].count++;
		}
		DestroyList(sa);  //销毁本行的单词链表
		linenum++;  //准备查询下一行
	}  while (!feof(f)&&!failed);
	return !failed;
}

void main()
{
	sp.freep=0;
	do {
		Initialization(fr);  //输入文件名并打开文件fr
		InputWords(pt);  //输入待匹配单词并建立有序链表pt
		if (&&!ListEmpty(pt)) {
			InitRList(rs,pt);  //初始化统计结果线行表rs
			if (match(fe,pt,rs)) OutResult (rs,ListLength(tp));//输出统计结果
			else 
				DestroyList(pt); //释放待匹配单词链表的空间
		}
		输出是否继续的提示信息；
	}while(回答为“是”)
}//main
void InputWords(OrderedList &pt)
{
	//连续输入单词，建立有序链表pt,输入以两个连续的单引号为结束标志。
	if(InitList(pt)){
		printf(提示输入的信息);
		do{
			cc=getche();
			while(cc!=('\''))cc=getche();  //滤去其他非单引号字符接收一个以单引号结束的字符序列ws.ch;
			if (ws.size!=0)
				if(NewWord(nwd,ws))
					if(!LocateElem(pt,nwd,q))
						if(MakeNode(p,nwd)) InsertAfter(pt,q,p);
		} while (ws.size!=0);
	}
}//InputWords

void IntRList (ResultList &rs,OrderedList pat)
{ 
	//对存储查询结果的线性表rs进行初始化
	p=succNode(pat.head);
	for (k=0;k<ListLength(pat);k++)  {
		CopyWord(rs[k].data,Elem(p));  //复制单词
		rs[k].next=NULL; rs=[k].count=0; p=SuccNode(p);
	}
}
void OutResult (ResuleType rslist,int n)
{
	//输出n个单词的统计结果
	for (i=0;i<n;i++) {
		printf("The word'");
		PrintWord(rslist[i].data);
		printf("'appeared in the file%d times",rslist[i].count);
		if(rslist[i].count!=0) 输出指针rslist[i].next所指链表中的行号；
	}
}//OutResult