《计算机软件技术基础实验指导书》【河南科技大学】数据结构+数据库、数据结构课程设计报告

PAGEPAGE18目录TOC\o"1-1"\h\z\u实验一单链表的运算 2实验二二叉树的建立和遍历 5实验三二叉排序树的建立和查找 6实验四windows操作系统及应用 9实验五数据库建立 10实验六数据库查询 12附录 13实验一单链表的运算实验目的1．掌握单链表的基本运算：建立、插入和删除2．掌握运用C语言上机调试单链表的基本方法。实验环境操作系统和C语言系统预习要求了解单链表的建立、插入和删除算法，编写完整的程序。实验内容设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。参考算法#include<stdio.h>#include<stdlib.h>/*单链表的定义*/typedefintDataType; /*DataType可以是任何相应的数据类型如int,float或char*/typedefstructnode /*结点类型定义*/{ DataTypedata; /*结点的数据域*/ structnode*next; /*结点的指针域*/}ListNode;typedefListNode*LinkList;voidmain(){ inti; DataTypekey,x; LinkListhead; ListNode*p; LinkListCreateList(void); voidPrintList(LinkListhead); LinkListLocateNode(LinkListhead,DataTypekey); LinkListGetNode(LinkListhead,inti); voidInsertList(LinkList*head,DataTypex,inti); voidDeleteList(LinkList*head,inti);// clrscr(); head=CreateList(); /*建立单链表*/ PrintList(head); /*打印单链表*/ printf("\n输入要查找的值："); scanf("%d",&key); p=LocateNode(head,key); /*单链表查找*/ printf("\n请输入欲插入元素的位置："); scanf("%d",&i); printf("\n请输入欲插入的元素："); scanf("%d",&x); InsertList(&head,x,i); /*单链表插入*/ PrintList(head); /*打印单链表*/ printf("\n请输入欲删除结点的位置："); scanf("%d",&i); DeleteList(&head,i); /*单链表删除*/ PrintList(head); /*打印单链表*/ }/*单链表的建立,从后向前生成*/LinkListCreateList(void){LinkListhead,p;intx;head=NULL;printf("inputsomeinteagersuntil0!");scanf("%d",&x);while(x){p=(LinkList)malloc(sizeof(ListNode));/*以下三行：新建结点并初始化*/p->data=x;p->next=NULL;if(head==NULL)head=p;else{p->next=head;head=p;}scanf("%d",&x);}return(head);}/*单链表的打印*/voidPrintList(LinkListhead){LinkListp;p=head;while(p!=NULL){printf("%5d",p->data);p=p->next;}}/*单链表的查找,输入一个整数，显示该结点的位置*/LinkListLocateNode(LinkListhead,DataTypekey){/*在不带头结点的单链表head中查找其值为key的结点*/LinkListp;if(head==NULL){printf("Listisnull!");return(head);}if(head->data==key){printf("thewanteddatais:%d",head->data);return(head);}p=head;while((p->data!=key)&&((p==NULL))p=p->next;if(p!=NULL)printf("thewanteddatais:%d",p->data);elseprintf("thewanteddataisnotfound!");return(p);}/*单链表的查找2，在不带头结点的单链表head中查找第i个结点*/LinkListGetNode(LinkListhead,inti){LinkListp;intn=1;p=head;while((p!=NULL)&&(n<i)){if(n<i){n++;p=p->next;}}return(p);}/*单链表的插入*/voidInsertList(LinkList*head,DataTypex,inti){/*将值为x的新结点插入到不带头结点的单链表head的第i个结点的位置上*/LinkListp,q;p=(LinkList)malloc(sizeof(ListNode));/*以下三行：新建结点并初始化*/p->data=x;p->next=NULL;if(i<=1)/*在第一个位置插入*/{p->next=*head;*head=p;}else/*找到要插入的前一个位置，然后插入*/{q=GetNode(*head,i-1);p-next=q->next;q->next=p;}}/*单链表的删除，删除不带头结点的单链表中的第i个结点*/voidDeleteList(LinkList*head,inti){LinkListp,q;if((i<=0)||(*head=NULL)){printf("Listisnullori<=0!");return;}if(i==1){p=((*head)->next);free(*head);*head=p;return;}p=*head;while((p!=NULL)&&(--i>0)){q=p;p=p->next;}if(p==NULL)printf("i>L!");else{q->next=p->next;free(p);}}实验二二叉树的建立和遍历实验目的1．掌握二叉树的建立算法2．掌握二叉树的前序、中序和后序遍历算法。实验环境操作系统和C语言系统预习要求复习二叉树的生成及遍历算法，编写完整的程序。实验内容要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。参考算法二叉树的建立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如s[i]中存放编号为i的结点的指针，即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s[1]。当结点编号i>1时，产生一个新的结点后，也要将指向该结点的指针存入s[i]，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让s[j]->lch=s[i]；若i为奇数，则它是双亲结点的右孩子，即让s[j]->rch=s[i]。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。#include<stdio.h>#include<stdlib.h>#include<math.h>/*二叉树的定义*/typedefcharDataType;/*DataType可以是任何相应的数据类型如int,float或char*/typedefstructbtnode/*结点类型定义*/{ DataTypedata;/*结点的数据域*/ structbtnode*lchild;/*结点的左指针域*/ structbtnode*rchild;/*结点的右指针域*/}BtNode;voidmain(){ DataTypech[20]; BtNode*s[20],*bt,*p;inti=0;/*以下三行按照前中后序遍历二叉树的函数声明*/voidpretrav(BtNode*bt);voidintrav(BtNode*bt);voidpostrav(BtNode*bt);/*按满二叉树编号后的顺序输入结点字符，空的位置用'#'代替，字符个数不要超过20个*/ printf("\ninputsomecharacters:"); scanf("%s",ch);/*输入结点字符*/ for(i=0;i<20;i++) { if(ch[i]=='\0') break;/*如果输入的是结束符*/ p=(BtNode*)malloc(sizeof(BtNode));/*创建一个树结点，由p指针指向，以下三行初始化新结点*/ p->data=ch[i]; p->lchild=NULL; p->rchild=NULL; s[i]=p; if(ch[i]=='#') continue;/*如果输入的是'#'，即该位置没有结点，无需找其父节点*/ if(i>0) { if(i%2==1) s[i/2]->lchild=p;/*根据i的奇偶性，将p结点链到其父节点的（左/右？）指针上*/ elses[i/2-1]->rchild=p; }/*将p结点链到其父节点的（左/右？）指针上*/ } for(i=0;i<20&&ch[i]!='\0';i++)/*依次输出各结点及其孩子*/ { if(ch[i]=='#') continue; if(s[i]->lchild!=NULL&&s[i]->rchild!=NULL) printf("%c,%c,%c\n",s[i]->data,s[i]->lchild->data,s[i]->rchild->data); elseif(s[i]->lchild!=NULL) printf("%c,%c,%c\'srchildisNULL!\n",s[i]->data,s[i]->lchild->data,s[i]->data); elseif(s[i]->rchild!=NULL) printf("%c,%c\'slchildisNULL!,%c\n",s[i]->data,s[i]->data,s[i]->rchild->data); else printf("%c,%c\isaleaf!\n",s[i]->data,s[i]->data); }/*以下按照前中后序遍历二叉树*/printf("\npretrav!");pretrav(s[20]);printf("\nintrav!");intrav(s[20]);printf("\npostrav!");postrav(s[20]);printf("\n");while(1);}/*前序遍历二叉树*/voidpretrav(BtNode*bt){ BtNode*p; p=bt;if(p!=NULL){ printf("%c",p->data); pretrav(bt->lchild); pretrav(bt->rchild);}return;}/*中序遍历二叉树*/voidintrav(BtNode*bt){if(bt!=NULL){ intrav(bt->lchild); printf("%c",bt->data); intrav(bt->rchild);}return;}/*后序遍历二叉树*/voidpostrav(BtNode*bt){if(bt!=NULL){ postrav(bt->lchild); postrav(bt->rchild); printf("%c",bt->data);}return;}实验三二叉排序树的建立和查找实验目的1．掌握二叉排序树的建立算法2．掌握二叉排序树查找算法。实验环境操作系统和C语言系统预习要求复习二叉排序树的生成及查找算法，编写完整的程序。实验内容实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。参考算法#include<stdio.h>#include<stdlib.h>typedefintInfoType;typedefintKeyType; /*假定关键字类型为整数*/typedefstructnode /*结点类型*/{ KeyTypekey; /*关键字项*/ InfoTypeotherinfo; /*其它数据域，InfoType视应用情况而定下面不处理它*/ structnode*lchild,*rchild;/*左右孩子指针*/}BSTNode;typedefBSTNode*BSTree; /*BSTree是二叉排序树的类型*/voidmain(){ BSTNode*SearchBST(BSTreeT,KeyTypekey); voidInsertBST(BSTree*Tptr,KeyTypekey); BSTreeCreateBST(void); voidListBinTree(BSTreeT); /*用广义表表示二叉树*/ BSTreeT; BSTNode*p; intkey; printf("请输入关键字（输入0为结束标志）：\n"); T=CreateBST(); ListBinTree(T); printf("\n"); printf("请输入欲查找关键字："); scanf("%d",&key); p=SearchBST(T,key); if(p==NULL) printf("没有找到%d！\n",key); else printf("找到%d！\n",key); ListBinTree(p); printf("\n");}BSTNode*SearchBST(BSTreeT,KeyTypekey){ /*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/ if(T==NULL||key==T->key) /*递归的终结条件*/ returnT; /*若T为空，查找失败；否则成功，返回找到的结点位置*/ if(key<T->key) returnSearchBST(T->lchild,key); else returnSearchBST(T->rchild,key); /*继续在右子树中查找*/}voidInsertBST(BSTree*Tptr,KeyTypekey){ /*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/ BSTNode*f,*p=*Tptr; /*p的初值指向根结点*/ while(p){ /*查找插入位置*/ if(p->key==key)return; /*树中已有key，无须插入*/ f=p; /*f保存当前查找的结点*/ p=(key<p->key)?p->lchild:p->rchild; /*若key<p->key，则在左子树中查找，否则在右子树中查找*/ } p=(BSTNode*)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; /*生成新结点*/ if(*Tptr==NULL) /*原树为空*/ *Tptr=p; /*新插入的结点为新的根*/ else/*原树非空时将新结点*p作为*f的左孩子或右孩子插入*/ if(key<f->key) f->lchild=p; elsef->rchild=p;}BSTreeCreateBST(void){ /*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/ BSTreeT=NULL; /*初始时T为空树*/ KeyTypekey; scanf("%d",&key); /*读入一个关键字*/ while(key){ /*假设key=0是输入结束标志*/ InsertBST(&T,key); /*将key插入二叉排序树T*/ scanf("%d",&key); /*读入下一关键字*/ } returnT; /*返回建立的二叉排序树的根指针*/}思考题请思考采用其他存储结构实现的二叉排序树建立算法。实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。实验五数据库建立实验目的熟练掌握用SQL语句实现基本表的创建。熟练掌握用SQL语句实现数据插入、数据更新和数据查询。熟练掌握用SQL语句实现数据的简单查询和连接查询。实验环境SQLServer2000预习要求SQLServer2000的查询分析器和企业管理器的使用，SQL数据定义和数据操纵语言。实验内容（一）用SQL语句建立如下mySPJ数据库，包括S，P，J，和SPJ四个基本表（四张表的数据另给），要求实现关系的三类完整性。S(SNO,SNAME,STATUS,CITY);P(PNO,PNAME,COLOR,WEIGHT);J(JNO,JNAME,CITY);SPJ(SNO,PNO,JNO,QTY)供应商表S由供应商代码（SNO）、供应商姓名（SNAME）、供应商状态（STATUS）、供应商所在城市（CITY）组成。零件表P由零件代码（PNO）、零件名（PNAME）、颜色（COLOR）、重量（WEIGHT）组成。工程项目表J由工程项目代码（JNO）、工程项目名（JNAME）、工程项目所在城市（CITY）组成。供应情况表SPJ由供应商代码（SNO）、零件代码（PNO）、工程项目代码（JNO）、供应数量（QTY）组成，表示某供应商供应某种零件给某工程项目的数量为QTY。（二）分别使用插入、删除、修改的方式更新基本表中的数据。实验方法和步骤（一）使用MicrosoftSQLServer企业管理器和查询分析器建立数据库mySPJ：1.打开“开始－>程序－>MicrosoftSQLServer－>企业管理器”；2.在企业管理器左边的树标签中依次打开“MicrosoftSQLServer－>SQLServer组－>(local)(WindowsNT)－>数据库”，(local)(WindowsNT)前的红色标记转化为绿色标记表明NT服务已启动；3.从企业管理器的“工具”菜单中选择“SQL查询分析器”，打开查询分析器后，在其窗口书写创建数据库mySPJ的SQL语句，点击执行按钮（或F5键）执行该SQL语句；4.在企业管理器左边的树标签中查看数据库是否建立成功。（二）在数据库mySPJ中建立S，P，J，和SPJ四个基本表：按照实验内容给出的基本表结构在查询分析器窗口中书写SQL语句分别建立各表，并设置主键和外键约束；（三）更新表数据：1.利用Insert语句将习题中给出的示例记录插入各表。2.利用Update更新表中的记录：①将p表中的所有红色零件的重量增加5。updatepsetweight=weight+5wherecolor='红';②将spj表中所有天津供应商的QTY属性值减少10。用子查询。updatespjsetqty=qty-10wheresnoin//不能用sno=因为返回值多于一个...(selectsnofromswherecity='天津');3.利用Delete语句删除p表中的所有红色零件的记录。deletefrompwherecolor='红';实验六数据库查询(一) 完成下面的简单查询：①查询所有“天津”的供应商明细；select*fromswherecity='天津';②查询所有“红色”的14公斤以上的零件。selectpnamefrompwherecolor='红'andweight>14;③查询工程名称中含有“厂”字的工程明细。selectjno,jname,cityfromjwherejnamelike'%厂%';(二) 完成下面的连接查询：①等值连接：求s表和j表的相同城市的等值连接。select*froms,jwheres.city=j.city; ②自然连接：查询所有的供应明细，要求显示供应商、零件和工程的名称，并按照供应、工程、零件排序。selectsname,jname,pnamefroms,p,j,spj(他们之间没有直接的公共属性只有用spj表来联系他们他们的关系也在spj表中)wheres.sno=spj.snoandp.pno=spj.pnoandj.jno=spj.jno;精益 三建 螺母精益 弹簧厂 螺母精益 造船厂 螺母精益 一汽 螺栓盛锡 三建 螺丝刀盛锡 一汽 螺丝刀盛锡 造船厂 螺丝刀盛锡 机车厂 螺丝刀盛锡 三建 凸轮盛锡 一汽 凸轮东方红 三建 螺母东方红 三建 螺丝刀丰泰盛 三建 凸轮丰泰盛 弹簧厂 齿轮丰泰盛 造船厂 齿轮为民 造船厂 螺栓为民 三建 螺丝刀为民 一汽 齿轮为民 造船厂 齿轮③笛卡尔积：求s和p表的笛卡尔积select*froms,p④左连接：求j表和spj表的左连接。⑤右连接：求spj表和j表的右连接。(三) 分组查询：1. 求各种颜色零件的平均重量。selectcolor,avg(weight)frompgroupbycolor;2. 求北京供应商和天津供应商的总个数。selectcity,count(sname)fromswherecity='北京'orcity='天津'groupbycity;3. 求各供应商供应的零件总数。selectsno,sum(qty)fromspjgroupbysno;4. 求各供应商供应给各工程的零件总数。selectpno,sno,sum(qty)fromspjgroupbysno,pno;5. 求使用了100个以上P1零件的工程名称。selectjnamefromjwherejnoin(selectjnofromspjwherepno='p1'groupbyjnohavingsum(qty)>100);6. 求各工程使用的各城市供应的零件总数。selectjno,city,sum(qty)//先自然连接再分组查询第一次做的时候先分组查询再自然连结了顺序反了比较麻烦上面几个也可以先自然连结再分组查询那样就能显示具体的名字了fromspj,swheres.sno=spj.snogroupbycity,jno;(四) 嵌套查询：1. in连接谓词查询：①查询没有使用天津供应商供应的红色零件的工程名称。selectj.jnamefromjwherej.jnoin(selectj.jnofromspj,s,p,jwheres.city!='天津'andp.color!='红'ands.sno=spj.snoandp.pno=spj.pnoandj.jno=spj.jno);②查询供应了1000个以上零件的供应商名称。(having)selectsnamefromswheresnoin(selectsnofromspjgroupbysnohavingsum(qty)>1000);2. 比较运算符：求重量大于所有零件平均重量的零件名称。selectpnamefrompwhereweight>(selectavg(weight)fromp);附录实验五数据库建立用SQL语句建立如下mySPJ数据库，包括S，P，J，和SPJ四个基本表，四张表的数据如下：S表：P表：J表：SPJ表：学院计算机科学系数据结构课程设计报告设计名称：压缩器/解压器姓名：学号：专业班级：08软件技术（1）班系院）：计算机科学系设计时间：学年第二学期设计地点：六楼机房目录HYPERLINK一需求分析3HYPERLINK二概要设计3HYPERLINK三详细设计6HYPERLINK四测试与分析10五测试结果11六用户使用说明13七课程总结13八考文献14九附录一、需求分析：为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存，对于很大的文件来说，节省文件的存储空间就根相当于节省成本，只需要在存储时花费一点额外的运行时间，但在现在计算机的运行速率来说，这点时间不是问题，并且不影存储效果，这次的课程设计利用了lzw(Lemple-Ziv-Welch由三人创造，故用他们的名字命名)算法来实现。Lzw压缩算法是一种广泛应用的压缩算法，它不仅用于文本文件压缩，还用于各种图像文件压缩，而且在压缩过程中不使原文件失真，压缩效果好，特别是对一些有大量重复子串的文本文件，压缩效果更好。字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.压缩/解压器要完成的主要功能：用户登录进行选项选择。对文件进行无损失压缩.对压缩文件进行解压，并且原文件数据不丢失.二、概要分析2.1.系统功能设计：经过分析，压缩/解压器可分为四个模块。A系统主函数模块B压缩模块Yasu().C解压模块Jieya().D菜单选择模块Menu().2系统功能分析：2.2压缩/解压器用到lzw算法，其它基本概念如下：LZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(StringTable)。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节；字符串(String)：由几个连续的字符组成；前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：一个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值.以下是分别对上面几个模块进行分析：2.3菜单选择：主要是对不同选择进行响应执行。主要用到dowhile,switch,case等关键字。2.4压缩模块：先说明一下lzw的压缩原理：通过基本概念了解了字符串，先缀，后缀等概念。压缩原理：初始化一个编译表，从文本文件读第一个字符记为[ch]1，不做处理，把它作为临时字符串前缀，继续读第二字符，记为[ch]2，如果在编译表有该字符，有两种情况，在编译表有该字符或没有，把该字符和前一个字符合为一个字符串[ch]1[ch]2（一个字符串可以用一个前缀加一个后缀来表示即（前缀，后缀）前缀是一个标号，可以是原始的字符，也可以是一个代表字符串的标号，后缀则是一个字符），把[ch]2作为后缀，如果编译表中有[ch]2的标记，如果该字符在编译表中有对应编码，不做处理，现在编译表中没有该串[ch]1[ch]2，那么为[ch]1[ch]2在编译表添加一个新的标志，同时输出ch[1](前缀)中编译中对应在编号到输出流中，现在ch[1]已经输出去，所以把ch[2]变为前缀。读取第三个字符ch[3]，形成新的字符串ch[2]ch[3],如果编译表中有ch[2]ch[3],不作处理，继续添加，如果没有，则像第二步一样，在编译表中为其添加标记，同时输出前缀ch[2]，后缀ch[3]变前缀。读取第四个字符，原理都是前面一样，直到读最后一个字符。2.5解压模块原始数据ABABABABBBABABA

A

C

DACDAD

CABAAABAB待解压的数据流为:AB68B109AACD1416DC8解压的过程是以一对一对数据来处理的。首先原始数据的位数。第一步：取第一个和第二个数据，是（A，B），不认得，令6＝（A，B），把前缀A放入输出流中，后缀B变成前缀；第二步，取第三个数据，现在变为（B，6）。不认得，压缩过程，定义一个新的标志，前缀可以是一个代表子串的标号，但是后缀都是一个单个的数据的，所以这里也不能让后缀是一个字串标号。把6展开，6是AB，那么这里原来的字串就是BAB，其实7＝（B，A），那么7的后缀就是6代表的字符串的第一个字符。把B放入输出流。第三步，取第四个数据。由于上一步已经把标号排到7了，7是3位的最大数值，所以从这一步以后，就应该把字长加一位，所以这里取4位，就是1000，也就是8。现在得到的是（6，8）。不认得，定义7的时候，取的后缀是6的第一个字符，那么这里8的后缀也应该是8的第一个字符，8的前缀是6，那么8的第一个字符也就是6的第一个字符。也就是A。所以8＝（6，A），现在把6代表的字符串AB放入输出流，让前缀变为8；第四步，取第五个数，现在是（8，B），让9＝（8，B），把8＝6A＝ABA放入输出流，前缀为B。第五步，取第六个，（B，10），同第三步，令10＝（B，10的第一个字符）＝（B，B），把B放入输出流最后得到原始数据2.5w压缩过程的算法流程图2.5解压模块Lzw解压原理：通过上面压缩原理，大概可以知道了解到压缩过程就是不找子串，旧的子串不作处理，新的子旧就为其添加新的标记，交输出前缀到输出流。解压其实就是压缩的逆过程，因为lzw是动态生成编译表，所以本人认为解压过程就相对难解理一些，下面说明一下解压过程：开始开始读入字符（直到文件结束）读入字符（直到文件结束）赋给后缀赋给后缀是否大于基本标志是否大于基本标志否是是否在编译表是否在编译表中后缀变前缀是后缀变前缀遍历编译表遍历编译表后缀变前缀否后缀变前缀前缀+后缀（当前字符）前缀+后缀（当前字符）添加当前字符到编译添加当前字符到编译表输出输出三、祥细设计3.1lzw压缩的实现：压缩的基本原理在概要分析已经讲述过，在这里主要是把每个步聚祥细的说一编，并且把此模块的主要功能实现过程与核心代码解释一遍。以下是具体过程：在讲之前，还要说明几个名词以及它们的作用，为了区别编译表中串值与单个字符，要用到清除标志CLEAR和结束标志end,比如说，基本标志有8位，能表示的基本单个字符范围就是256（0-255），如果超过256，就要有新的标志，为了区别原来的标志与新的标志，就要用清除标志CLEAR和结束标志end，清除标志CLEAR一般比单个字符最大标志大1，而结束标志end又比清除标志CLEAR大1，所以8位基本标志的清除标志CLEAR和结束标志end分别为256，257。如果有新的标志就从258开始。LZW压缩码长度最长是12bits。超过这个长度将要重新开始编码解码。事实上压缩一个文件时，常常要对串表进行多次初始化，往往一文件中出现的第一次出现的基本字符串个数会超过4096个，在压缩过程中只要字符串的长度超过了4096，就要将当前前缀和当前码输入代码流，并向代码流中加入一个清除码，初始化串表，继续按上述方法进行压缩。例如：有一个字符串，是由A、B、C、D四个字符构成的，那么就可以用0123来表示，两位就够了。ABAD

CABAAAAB首先要扩充一位，变成3位，定义Clear＝4，End＝5。那么以后的标号就从6开始。缩过程中要用的主要字段与函数：A最在标志：p(p<=65535)BASSCII代码的数量256表的基本标志Cvoidhashinit(void)//表初始化Dvoidhashinsert(Elementelement)//表的插入EstructElement//hash表中的元素{intkey;intcode;Element*next;}*table[MAX];//表Fhashfind(intkey,Element&element)//表的查找fclose(fp1);//文件关闭fclose(fp2);同时还在用到文件的输入输出：FILE*fp1,*fp2;用到的文件读写函数：fwrite(file1,20,1,fp2);ch=fgetc(fp1);下面是压缩过程的具体过程：：InitializeStringTable;[.c.]=Empty;[.c.]k=FirstCharacterinCharStream;while([.c.]k!=EOF){if([.c.]kisintheStringTable){[.c.]=[.c.]k;}else{add[.c.]ktotheStringTable;OutputtheIndexof[.c.]intheStringTabletotheCodeStream;[.c.]=k;}[.c.]k=NextCharacterinCharStream;}OutputtheIndexof[.c.]intheStringTabletotheCodeStream;lzw解压过程：在解压前先说明一下，读出一个字符时，如果小于基本标志（前面压缩的定义为0-255），就直接输出》如果大基本标志（258，有清除与结束标志），并在编译表中存在代码值时，就到编译表找到中它对应的字符，并输出。如果没找到，就把前缀的第1个字符作为当前字符，把这个当前字符和前缀同时输出，并且把他们存储在编译表中》以下是具体的解压步骤：读取第一个字符，输出它，并且把它赋给前缀。读取下一个字符，如果没有结束，把它赋给当前字符，同时判断是否大于基本标志N。如果大于N，有两种情况：在编译表中或不在。没在编译表中，把前缀与后缀组成的当前字符的第一个字符输出，并把当前字符存储到编译表中，同时把当前字符赋给前缀，回到2重新执行。在编译表中，遍历编译表的所有标记所对应的字符，并且输出它，把当前字符赋给前缀，并回到2重新执行。如果小于N，输出当前字符，并且把当前字符赋给前缀，回到2重新执行。直到最后一个字符，输出标记同时结束。下面是压缩过程的该心过程：InitializeStringTable;[code]