下载文档原格式
DataStructure大纲目标:剥离实现细节，对数据结构的基本思想有所了解SIMPLE SET DEEP NO-CLICHE数据结构ADT&实现性能分析常用算法技巧算法设计策略、模式一．数据结构ADT&实现线性表ADT**ADT接口【对pos和rank 的重载】【部分冗余】**ADT实现**ADT公共部分实现【遍历Traverse：对L中所有元素（的数据域）依次实施visit()操作】【visit()即一个以数据域内容为参数的函数，可以修改数据域】【合并Union：求两个不可重复线性表的并集】【涉及m次locate()，locate()花费O(n)；故复杂度为O((1+n)(1+m))】【归并Merge：将两个非降序可重复线性表合并为一个】【n+m次的取值、比较、插入，均为常数操作；故为O(n+m)】**线性表的数组实现【存储结构连续】【可在O(1)时间内访问任意元素，但是不易插入、删除】【O(n)操作有，关键是Insert&Delete】Locate(value, comparator)Find(value, comparator)Insert(rank, value)Delete(rank)Traverse()【扩容策略：一旦溢出，容量加倍】**线性表的链表实现【删除插入一个节点，KEY：用header/trailer去控制前后，保证修改时的联系，从而可以任意次序修改；以冗余换方便，可靠】**两种实现时间复杂度比较栈ADT**ADT接口StackInit()StackDestroy()StackEmpty()StackSize()StackTraverse()Top()Push()Pop()**ADT的线性表实现【为LIST的子集，直接按LIST实现】【数组、双链表实现：后端为栈顶，遍历从栈底到栈顶】【单链表实现：前端为栈顶，遍历从栈顶到栈底】**栈的自我实现【基本元素】【注意栈满增加策略】**栈混洗【DEF】【进栈肯定是按从小到大，但是通过不同时刻出栈达到混洗目的】【如下图，纵轴为入栈，横轴为出栈，同时累计n次结束，且过程中不能出现出的比入得多的情况，即不能低于y=x直线】【长度n序列，混洗总数SP(n) = Catalan(n) = (2n)! / (n+1)! / n!】【混洗数量<n!；因为任意含类似‚312‛序列的均不是混洗列，即当3在2、1前出，且1、2肯定在3前入栈，说明此时1、2还在栈中，且2压在1上，故不可能出现1先出，2后出的状况】**用栈解决不确定问题【不确定：问题规模不断增长，最后方能归纳确定，前步结果需储存】**进制转换问题【进制转换问题：将值转换为base进制表达式；key：不知有几位】【将取余所得低位结果不断压入栈，最后从栈顶到栈底即结果】【逆问题：将一个base进制表达式转换为值，KEY：长度确定，无需用栈，从左到右依次根据权累加即可】**括号匹配问题【关键仍是需要暂存左括号，等待未知时刻匹配】**表达式求值问题：【用栈实现的KEY：通过计算优先级高的表达式，不断化简表达式，但是前步结果必须储存PUSH，且现有内容随时可能更新POP】【具体算法如下，其中优先计算匹配根据运算符号优先级表得到】【栈顶’*’当前，通过判断二者关系决定栈顶是否可优先计算】\0栈中当前为空时，栈顶任意运算符都优先，但\0碰\0即运算结束（）消括号栈顶的）优先级绝对的高**RPN后缀算式，祛除优先级问题【KEY：将一个算式按照优先级变换为顺序上的先后】【普通算式改写为RPN算式，用元字符间隔操作符和操作数】【RPN栈式计算：按先后顺序依次入栈，遇到操作符则POP相应操作数并且将结果PUSH，最后栈中所余数即结果】【程序实现RPN算式转换，KEY：任何优先计算的运算符立即接到RPN后面】**实现试探-回溯【相当于Theseus的绳子，可以PUSH伸长试探，POP回收回溯】【迷宫问题，KEY：用栈记录路径】队列ADT**先进先出【一种资源分配方式，先到先得，类似排队，比较公平】【银行窗口业务模拟】串ADT**串的特征【长度很大】【元素来源有限，通常是有限字符集SIGMA】**串ADT【子串、前缀、后缀的定义：注意k=0即空串】**定长存储实现【CORE：定长数组】【注意+1处即每个串的0元素存储串长度】【最大串长有限制：空间浪费+ 截断】【串操作都基于‚字符序列的复制‛；O(n)】**堆分配实现【CORE：动态数组】【头指针加长度】【最大串长无限制,无截断现象】【串操作仍然基于‚重分配‛和‚字符序列的复制‛；O(n)】【数组耗资源基操：Insert, Concat, Substring, Copy】【数组基操e.g：插入——重新分配，再分别复制到各自位臵】**块链实现【由指针相连的固定长度的块，CORE：将耗资源操作限制在块内】【tail指针方便串接】【每个块不一定满】【CHUNK_SIZE大则存储占用小！！！！！】树ADT**ADT**树def【如何衡量树的规模：n/m均可，节点数|V|=n，边数|E|=m；n-1=m】【有根树：若V非空，则可以指定任一节点为根节点：root(T) 属于V】【k称为r的出度，记作deg(r) = k，即与之相连儿子节点的数量】【一棵树的度数和：m条边对度数和的正贡献= 2m；非树根的父亲不算出度造成的负贡献=-( n-1)；一棵树的总度数和=2m-n+1=m，即度数和==边数】【路径π：|π|=k称作路径长度，即边数】【叶子&内部节点：没有孩子的节点称作叶子，否则为内部节点】【树=无环连通图=极小连通图=极大无环图，减一边则不连通，加一边则有环】【树深度：depth(v)=|π(r, v)|；且约定：depth(空树)=-1】【树高度：为T中所有节点的最大深度height(T)=max{depth(v) | v属于V} 】【depth(v) + height(v) <=height(T)，当v含最深节点时等号成立】**存储结构——父亲节点表示法【每个节点记住自己的父亲是谁】**存储结构——孩子节点表示法【每个节点知道自己的孩子是谁】【采用动态单链表，克服孩子数不一致；ELSE采用静态设臵同构最大为d时，最大节点数受限制而且空间利用率m/(n *d) < 1/d】【此时，LeftChild()很快，Parent()很慢；故增加父亲域如下】**存储结构——孩子+兄弟表示法【CORE：化为经纬结构；】【经：firstChild：指向第一个孩子；纬：nextSibling：指向下一个兄弟】【增设parent域，指向父节点】【性能】二叉树**ADT**二叉树特点【其中每个节点度数都不超过2 】**Full binary tree【数学特征，从上到下为2k数列；紧凑连续性】【求和是2k+1-1；最后一项为2k；用深度定义FBT】**Complete Binary Tree【从满树右下剥离一些叶子，仍然具有从左到右，从上到下的紧凑连续性】【；；如何用高度定义】**满/完全二叉树的顺序存储【满树和完全树有紧凑连续性，可以线性存储，达到O(1)访问】**一般二叉树【1度节点在二叉树中无意义，将其抽掉对0度节点、2度节点数量无影响】【每层不一定满；节点数下界为单枝，上界为满树；0度点与2度点关系】**关于任意二叉树的数学结论【边数==节点数-1==出度和】【A0=A2+1】【A0+A1+A2-1=A1+2*A2带入上式可得本式恒成立，故有A1无约束】【一棵二叉树，当节点数确定，A1确定，则A0，A1确定】【0=<A1<=n-1；即满树上界，单枝下界】**非紧凑二叉树的强制连续存储【强制要求满足以下】【最坏：开满树的空间，只占了单枝，仍有O(1)访问效率存在】**链式存储结构**二叉树的生成【先序输入data，递归生成】**树的销毁【为何要先左后右】**树的遍历【半线性：不是简单的线性结构，但在确定某种次序之后，具有线性特征】【遍历就是转为线性】***先序遍历*****先序SHOW CASE【看法一：递归地看，根左右，深入迭代时，做未访问标记】【看法二：根据迭代次序，45度庖丁解牛法，123/45/6/7】**先序递归实现【遍历时根先，且先左后右】**先序迭代实现——紧凑【根先，入栈时右先左后】【为何可以改写为迭代：用到了栈？？？】【入栈顺序SHOW CASE】【效率】**先序迭代实现——45度庖丁解牛版本【基本方式】【基础步：一直走到DNALB，将沿途碰到的右孩子压入栈】【跳跃步：进入本子树最深的右小子树，即最后入栈的那个】【caution：不是所有的元素都入栈！右孩子only！】***中序遍历*****SHOW CASE【递归地看】【对某子树确定访问入口次序，由DNALB到根节点；依次访问该访问入口和其右子树；】【依据BST节点按‚左值<根值<右值‛的特征：从左到右即中序】**递归实现**中序迭代实现【难度在于：尽管对右子树的递归遍历是尾递归，左子树却不是】【对某子树确定访问入口次序，由DNALB到根节点；依次访问该访问入口和其右子树；原问题就被分解为依次对若干个右子树的遍历问题】沿途祖先入栈定次**中序迭代入栈SHOW CASE【入栈的是各子树按入口次序：ba/fdc/e/g】【出栈按访问次序，每次迭代出栈一个】【每次迭代可能入栈几个，出栈必定一个，故可能入出交错】**中序另外两种迭代实现**树的查找【可快速插入、删除；也可快速查找】***后序*****SHOW CASE【递归的看：左右根】【迭代：从根到HVLFL确定次序，根据次序依次访问，碰到右孩子时进入处理】**递归方法**迭代方法【次：沿着根到HVLFL的最左路径，如果有右孩子下移前将其入栈】【沿这个次的倒序遍历，碰到父亲，左孩时直接访问，否则处理右孩子】**栈SHOW CASE：【入栈何时入：当且仅当当前-栈顶==左-右兄弟(6-5)时，进入栈顶子树需要入栈】【入栈怎么入：沿着根到HVLFL的最左路径，如果有右孩子下移前将其入栈】【出栈：每次迭代出栈一个，左-父/右-父(4-3/2-1)直接出，左右(6-5)出右子树的HVLEF】**前序中序后序时间效率【前O(n)/中后O(nlogn)，关键是单次迭代是不是O(1)】1) 每次迭代，都有一个节点出栈并被访问//满足2) 每个节点入栈一次且仅一次//满足3) 每次迭代可能前序（非庖丁解牛算法）O(1)/中后序为O(n)时间（需要找）**广度优先遍历【确保更高更左的节点更早入队，则其更早出队=；O(n)】**表达式树【如何创建？？？】【按后序遍历后即RPN】BST**BST优越性【查找、插入、删除都是logn？？？】**BST定义【二叉树】【无重复、中序遍历严格单调】【空树/其左右子树（L和R）都是BST；L非空，max{L} < r；R非空，r < min{R}】**存储实现**BST搜索算法【任意次：深度+1；最可怕：高度+1】**BST插入算法**BST删除算法删除52交换52与其左子树最大（右）节点删掉交换过来的52**性能分析【树高越小，最坏情况下的查找时间最短】【越是平衡，树高越小】【每棵BST都有越来越失衡的倾向】AVL【节点数量固定的BST，越是平衡，最坏情况下的查找速度越快】【O(logn)的查找速度、插入和删除效率】【平衡iff树高= O(logn)】【n个节点构成的AVL树，高度h = O(logn)】【高度为h的AVL树中，至少包含F- 1个节点】h+3**平衡因子【引入平衡因子：bf(v) = height(lc(v)) - height(rc(v))】【能插入节点的位臵的平衡因子插入前后只有可能是(0,〒1)/(〒1,0)】【插入后有可能失衡的最深元素是祖父】【删除后父亲即有可能失衡】**旋转【旋转后要求仍然是BST，而且是AVL树】【单旋CCW：b的左孩子给a；a成为b的左孩子；b成为树根】【双旋：先将bc逆时针，即b右孩给c做左孩;c为b右孩子；b为c右孩子;再来一次单旋即OK】【插入算法】【插入节点的祖父是第一个失衡的】【经过不超过两次旋转之后，g(x)将重新平衡，而且更重要的是平衡后g(x)的高度也复原】【局部将恢复平衡，而且全局也将恢复平衡】。
数据结构（DataStructure）说明：elt=ElemType一、线性表1、顺序表Typedef struct{ElemeType data[Maxlen];int len;} Sqlist;ElemType GetElem(Sqlist L, int I, ElemType &e) Status ListInsert(Sqlist &L, int I,ElemType e) Status ListDelete(Sqlist &L, int I, elt e)2、单链表Typedef struct LNode{elt data;Struct LNode *next;}LNode,*Linklist;3、静态链表#define MAX 100typedef struct{elt data;int cur;}SLinklist[MAX];4、循环双链表typedef struct DulNode{elt data;struct DulNode *prior;struct DulNode *next;}DulNode, *DulLinklist;操作：elt GetElem(DulLinklist L,int i)status ListInsert(DulLinklist &L,int i,elt e)status ListDelete(DulLinklist &L,int i)5、顺序栈typedef struct{elt *base;elt *top;int stacksize;}SqStack;6、链栈typedef struct SNode{elt data;struct SNode *next;}SNode,*SLinklist;7、链队列typedef struct QNode{elt data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front,rear;}LinkQueue;8、循环队列typedef struct{elt *base;int front,rear;}SqQueue;SqQueue Q; //定义一个循环队列，后面要进行初始化 InitQueue(Q); Q.rear==Q.front //判断队空(Q.rear+1)%maxsize==Q.front //判断队满二、二叉树和树1、二叉树的顺序存储#define MAX_TREE_SIZE 100elt treenodesdata[MAX_TREE_SIZE];2、二叉树二叉链表存储typedef struct Node{elt data;struct Node *lchild;struct Node *rchild;}Node,*BinTree;3、线索二叉树typedef enum{Link, Thread} PointerTag;typedef struct BinThrNode {elt data;struct BinThrNode *lchild,*rchild;PointerTag ltag,rtag;}BinThrNode,*BinThrTree;4、求二叉树的深度int depth(BinTree T){if(T==NULL)return 0;else{if((ldepth=depth(T.lchild) > rdepth=depth(T.rchild))return ldepth+1;else return rdepth+1;}}5、二叉树层次遍历(辅助队列）void LevelOrderTraverse(BinTree L){Queue Q;BinTree bt;if(T!=NULL){Visit(T);if(T.lchild !=NULL)Enqueue(Q,T.lchild);if(T.rchild !=NULL)Enqueue(Q,T.rchild);}bt=Dequeue(Q);LevelOrderTraverse(bt);}6、树的双亲表示#define MAX 100typedef struct Node{elt data;int parent;}Node;typedef struct {Node nodes[MAX];int n;}Ptree;7、树的孩子兄弟表示法存储typedef struct CSNode{elt data;struct CSNode *firstchild,*nextsibling;}CSNode,*CSTtree;三、图1、邻接矩阵（数组表示法)#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN}GKind;typedet struct ArcCell{VRType adj;InfoType *info;}ArcCell,AdjMatrix[ MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM]; //顶点数组AdjMatrix arcs; //边或弧的数组，二维int vexnum,arcnum; //顶点数、边数GKind kind; //图的类型，GKind是枚举类型}MGraph;2、邻接表#define MAX_VERTEX_NUM 20typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;InfoType *info;}ArcNode;typedef struct VNode{VertextType data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{AdjList vertices;int vexnum,arcnum;GKind kind;}ALGraph;。
什么是堆堆是一种满足以下条件的树：堆中的每一个节点值都大于等于（或小于等于）子树中所有节点的值。
或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值。
大家可以把堆(最大堆)理解为一个公司,这个公司很公平,谁能力强谁就当老大,不存在弱的人当老大,老大手底下的人一定不会比他强。
这样有助于理解后续堆的操作。
!!!特别提示：•很多博客说堆是完全二叉树，其实并非如此，堆不一定是完全二叉树，只是为了方便存储和索引，我们通常用完全二叉树的形式来表示堆，事实上，广为人知的斐波那契堆和二项堆就不是完全二叉树,它们甚至都不是二叉树。
•（二叉）堆是一个数组，它可以被看成是一个近似的完全二叉树。
——《算法导论》第三版大家可以尝试判断下面给出的图是否是二叉树？第1个和第2个是堆。
第1个是最大堆，每个节点都比子树中所有节点大。
第2个是最小堆，每个节点都比子树中所有节点小。
第3个不是，第三个中，根结点1比2和15小，而15却比3大，19比5大，不满足堆的性质。
堆的用途当我们只关心所有数据中的最大值或者最小值，存在多次获取最大值或者最小值，多次插入或删除数据时，就可以使用堆。
有小伙伴可能会想到用有序数组，初始化一个有序数组时间复杂度是O(nlog(n))，查找最大值或者最小值时间复杂度都是O(1)，但是，涉及到更新（插入或删除）数据时，时间复杂度为O(n)，即使是使用复杂度为O(log(n))的二分法找到要插入或者删除的数据，在移动数据时也需要O(n)的时间复杂度。
相对于有序数组而言，堆的主要优势在于更新数据效率较高。
堆的初始化时间复杂度为O(nlog(n))，堆可以做到O(1)时间复杂度取出最大值或者最小值，O(log(n))时间复杂度插入或者删除数据，具体操作在后续章节详细介绍。
堆的分类堆分为最大堆和最小堆。
二者的区别在于节点的排序方式。
- 最大堆：堆中的每一个节点的值都大于等于子树中所有节点的值 - 最小堆：堆中的每一个节点的值都小于等于子树中所有节点的值如下图所示，图1是最大堆，图2是最小堆堆的存储之前介绍树的时候说过，由于完全二叉树的优秀性质，利用数组存储二叉树即节省空间，又方便索引（若根结点的序号为1，那么对于树中任意节点i，其左子节点序号为2\*i，右子节点序号为2\*i+1）。
数据结构（Date Structure)上机报告学号201427187姓名杨荣庆班级信息143时间2015.11.28（一）上机目的1.掌握栈的插入、删除、栈的初始化及取栈顶元素等基本操作。
2.理解栈的特点，掌握栈的定义和基本操作。
3.掌握栈的顺序存储结构。
（二）实验要求1. 源代码（包括主要结构、主要语句、函数注释说明）。
2. 运行结果（包括程序如何使用，输入数据和输出结果）。
3. 实验体会和问题分析。
（三）基本知识和原理按设定的初始量进行第一次存储分配，base 可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base 的值为NULL ，则表明栈结构不存在。
称top 为栈顶指针，其初值指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1；删除栈顶元素时，指针top 减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
A 出栈（top-1）toptoptoptopbase A 入栈 base B 入栈 base B 出栈（top-1） base入栈过程 出栈过程AB AB AA（三）程序算法分析及实现#include<iostream.>using namespace std;# define STACK_INIT_SIZE 100# define STACKINCREMENT 10typedef struct{int * base;int * top;int stacksize;//当前栈可使用的最大容量} SqStack;void InitStack(SqStack &S)//构造一个空栈{S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base) {cout<<"存储分配失败!"<<endl<<endl;} else{S.top=S.base;S.stacksize=STACK_INIT_SIZE;cout<<"构造成功!"<<endl;}}void Push(SqStack &S,int e)//插入元素e为栈顶元素{if(S.top-S.base>=S.stacksize){S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base) cout<<"存储分配失败!"<<endl<<endl;else{S.stacksize+=STACKINCREMENT;S.top=S.base+S.stacksize;}}*S.top++=e;}void DisplayStack(SqStack &S) //从栈底到栈顶逐次显示栈中的元素{int *p;p=S.base;if(S.base==S.top) cout<<"当前栈为空栈!"<<endl<<endl;else{cout<<"当前栈内元素为: ";while(p!=S.top){cout<<*(p)<<" ";p++;}cout<<endl;}}void pop(SqStack &S,int &e) //出栈{if (S.top==S.base) cout<<"操作失败!"<<endl<<endl;else{e=*--S.top;DisplayStack(S);}}void ClearStack(SqStack &S)//清空{int b;while(S.top!=S.base) b=*--S.top;if(S.top==S.base) cout<<"顺序栈已清空!"<<endl<<endl; }void StackEmpty(SqStack S)//判空{if(S.top==S.base) cout<<"顺序栈为空!"<<endl<<endl;else cout<<"顺序栈不为空!"<<endl<<endl;}void DestroyStack(SqStack &S){S.base=NULL;cout<<"顺序栈已销毁!"<<endl<<endl;}void GetTop(SqStack S,int &e)//返回栈顶元素{if(S.top==S.base) cout<<"操作失败!"<<endl<<endl;else{cout<<"栈顶元素为: ";e=*(S.top-1);cout<<e<<endl<<endl;}}int main(){cout<<" │◎◎☆201427187 杨荣庆信息143☆◎◎│"<<endl;cout<<"╭*****╳╳╳1、构造一个空栈╳╳╳*****╮"<<endl; cout<<"╭*****╳╳╳2、输入栈的元素╳╳╳*****╮"<<endl; cout<<"╭*****╳╳╳3、输出栈的元素╳╳╳*****╮"<<endl; cout<<"╭*****╳╳╳4、求栈顶元素╳╳╳*****╮"<<endl; cout<<"╭*****╳╳╳5、删除栈顶元素╳╳╳*****╮"<<endl; cout<<"╭*****╳╳╳6、清空存在的栈╳╳╳*****╮"<<endl; cout<<"╭*****╳╳╳7、判断栈是否为空╳╳╳*****╮"<<endl;cout<<"╭*****╳╳╳0、销毁栈╳╳╳*****╮"<<endl;int n,k;SqStack S;for(n=0;n<15;n++){cout<<"请选择0-7: ";cin>>k;if(k==0) {DestroyStack(S);n=15;}if(k==1) InitStack(S);if(k==2){int a;cout<<"输入栈S的元素为: ";cin>>a;Push(S,a);DisplayStack(S);}if(k==3) DisplayStack(S);if(k==4) {int c;GetTop(S,c);}if(k==5) {int b;pop(S,b);}if(k==6) ClearStack(S);if(k==7) StackEmpty(S);}return 0;}（四）结果分析及测试相关记录运行页面构建空栈及插入元素求栈顶元素删除栈顶元素清空顺序栈销毁栈（五）实验体会和学习感悟在程序的编写过程中，有许许多多的错误，导致程序不能正常运行，在进行对书的翻看和网上搜索后终于解决了问题。
第三章栈和队列试题一、单项选择题1.栈的插入和删除操作在（）进行。
A. 栈顶B. 栈底C. 任意位置D. 指定位置2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A. top++;B. top--;C. top = 0;D. top;3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。
A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 24.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。
A. 前一个B. 后一个C. 当前D. 后面5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。
A. n-2B. n-1C. nD. n+16.从一个顺序存储的循环队列中删除一个元素时，需要（）。
A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所指的元素7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。
A. front+1 == rearB. rear+1 == frontC. front == 0D. front == rear8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。
A. front == rearB. front != NULLC. rear != NULLD. front == NULL9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。
若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行操作（）。
A. top->link = s;B.s->link = top->link; top->link = s;C. s->link = top; top = s;D. s->link = top; top = top->link;10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。
数据结构（Datastructure）：⽤链表实现多项式的表⽰和运算（C语⾔）0.简介（在以下环境下运⾏通过）：运⾏环境：Linux(ubuntu12.10); 编译器：gcc; 语⾔：C语⾔； 作者：Catcher24。
1.问题描述： 使⽤链表实现多项式的表⽰和运算（加法、减法、乘法）。
2.数据结构描述与设计： 2.1 使⽤链表的原因： 有两个多项式： P1 = 6x^4+4x^2-x; P2 = -7x^5+x^2; 如果要对两个多项式进⾏操作（多项式相加、除法等等......），可以采⽤数组的存储⽅式。
设多项式P(n) = a1x n+a2x n-1+...a n;如果采⽤数组A[n]来存储P(n)的系数，当P(n)中有的a i为0时，数组储存在空间上会带来很⼤的浪费。
⽽采⽤链表存储，每个节点存储系数和指数信息。
⽤链表来表⽰多项式，节点信息如下图：图：链表节点信息 2.2 多项式的链表实现： 下⾯给出polynomial.h⽂件，⾥⾯包含了节点的定义和函数定义；1 #include <stdlib.h>2 #include <stdio.h>34 #ifndef _List_H5 typedef int bool;6 typedef int exp_type;7 typedef float coe_type;8#define true 19#define false 010 typedef struct node {11 coe_type coefficient;12 exp_type exponent;13struct node* next;14 }node;15 typedef struct node* polynomial;1617 node* init(node* l);18 node* make_empty(node* l);19bool is_empty(node* l);20bool is_last(node* p,node* l);21 node* find(coe_type x,node* l);22 node* find_previous(coe_type x,node *l);23void delete_node(coe_type x, node* l);24void insert(coe_type x,exp_type y,node* l);25void delete_list(node* l);26 node* header(node* l);27 node* first(node* l);28void print_list(node* l);2930 polynomial create(polynomial poly,coe_type coe[],exp_type exp[],int n);32 polynomial sub_poly(const polynomial poly1,const polynomial poly2,polynomial polyprod);33 polynomial mult_poly(const polynomial poly1,const polynomial poly2,polynomial polyprod);34void print_poly(const polynomial poly);3536#endif 其中通过create()函数创建⼀个新的多项式，⽤⼀个float类型的数组来表⽰多项式的系数，⽤int型的数组来表⽰多项式的指数。
