考试复习文档
- 格式：doc
- 大小：67.50 KB
- 文档页数：9
1.线性表的逻辑特征：对于非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2,；有且只有一个终端结点an,它没有直接后继，而仅有一个直接前趋a(n-1);其余的内部结点ai(2<=i<=n-1)都有且只有一个直接前趋a(i-1)和一个直接后继a(i+1)2.例题2.1利用线性表的基本运算实现清除表L中多余的重复结点PURGE(L)Linear_list*L;{Int i=1,j,x,y;While(i<LENNGTH(L)){x=GET(L,i);j=i+1;while(j<=LENNGTH(L)){y=GET(L,j);if(x= =y)DELETE(L,j);elsej++;}i++;}}3.顺序表定义：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称为顺序表4. 用向量描述顺序表typedef int datatype; /*datatype 为任何类型，这里假设为int*/#define maxsize 1024typedef struct{datatype data[maxsize];int last;}sequenlist;5．.顺序表的基本运算○1插入int INSERT(L,x,i) /*将新结点x插入顺序表L的第i个位置上*/sequenlist *L;int i;{int j;if(((*L).last)>=maxsize-1){printf(“overflow!!!”);return NULL; /*表空间溢出*/}elseif((i<1)||(i>(*L).last-1)){printf(“error!!!”);return NULL;}else{for(j=(*L).last;j>=i-1;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i-1]=x;(*L).last=(*L).last+1;}return(1);}注释：结点后移方向必须从表中最后一个结点开始后移，直至将第i个结点后移为止○2删除int DELETE(L,i)sequenlist *L;int i;{int j;if(i<1||i>((*L).last)+1){printf(“error!!!”);return NULL;}else{for(j=1;j<=(*L).last;j++) /*第i个结点的下标是i-1*/(*L).data[j-1]=(*L).data[j]; /*结点前移*/(*L).last--; /*表长减1*/}}6．顺序表的优点和缺点优点：（1）无须为表示结点间逻辑关系而增加额外的存储空间（2）可以方便的随机存取表中任一结点缺点：（1）插入或者删除运算不方便，除表尾的位置外，在表的其他位置插入或者删除操作都必须移动大量的结点，其效率较低（2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配）。
所以当表长度变化较大时，难以确定合适的存储规模。
若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用7.链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以不是连续的。
8.为了正确的表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息，这个信息称为指针或链data nextdata域是数据域，用来存放结点的值；next是指针域，用来存放结点的直接后继的地址9. 单链表：每个结点只有一个指针域的链表称为单链表10.malloc：P=malloc(sizeof(linklist));函数malloc分配一个类型为node的结点变量的空间，并将其地址放入指针p中。
11.单链表上的基本运算：(1).建立单链表:头插法建表linklist * CREATLISTF（）{char ch;linklist *head,*s;head=NULL;ch=getchar（）;while（ch!='$'）{s=malloc（sizeof（linklist））;s->data=ch;s->next=head;head=s;ch=getchar（）；}}尾插法建表linklist *CREATLISTR（）{char ch;Llinklist *head,*s,*r;head=NULL;r=NULL;ch=getchar（）；while （ch!='$'）{s=malloc（sizeof（linklist））;s->data=ch;if（head==NULL）head=s;else r->next=s;r=s;ch=getchar（）；}if（r!=NULL）r->next=NULL;return head;}（2）查找运算：○1按序号查找linklist *GET(head,i)linklist *head;int i;{int j;linklist *p;p=head;j=0;/*从头结点开始扫描*/ while ((p->next!=NULL)&&(j<i)) {p=p->next;/*扫描下一个结点*/j++；}if (i==j)/*找到了第i个结点*/ return p;else return NULL;}○2按值查找linklist*LOCATE(head,key)linklist *head;datatype key;{linklist *p;p=head->next;while (p!=NULL)if(p->data!=key)p=p->next;elsebreak;return p;}}(3)插入运算○1后插操作INSERTAFTER(p,x)/*将值为x的新结点插入*P之后*/ linklist *p;datatype x;{linklist *s;s=malloc(sizeof(linklist));/*生成新结点*/s->data=x;s->next=p->next;p->next=s;}○2前插操作INSERTBEFORE(head,p,x)linklist *head,*p;datatype x;{linklist *s,*q;s=malloc(sizeof(linklist));/*生成新结点*/s->data=x;q=head;/*从头指针开始*while （q->next!=p）q=q->next;/*查找*p的前趋结点*q*/s->next=p;q->next=s;}注：改进后的前插操作INSERTBEFORE(p,x)linklist *p;datatype x;{linklist *s;s=malloc(sizeof(linklist));s->data=p->data;s-next=p->next;p->data=x;p->next=s;}(4)删除操作DELETEAFTER(p)/*删除*p的后继结点*r,假设*r存在*linklist *p;{linklist*r;r=p->next;p->next=r->next;/*将结点*r从链上摘下*/free（r）;/*释放结点*/}12.循环链表？（1）什么叫循环链表？循环链表是一种首尾相接的链表。
其特点是无需增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
（2）循环链表同普通单链表的区别：当需要从头到尾扫描整个链表时，判断是否到表尾的条件不同，在单链表中以指针域是否为空作为判断表尾结点的条件，而在循环链表中则以结点指针域是否等于头指针作为判断表尾结点的条件。
例题：下列叙述中属于单链表和循环链表的区别的是（D ）A、结点的结构不同B、对存储空间连续性的要求不同C、查找结点的算法中，循环结束条件不同D、对是否包含头结点的要求不同13.一元多项式的加法多项式结点形式：coef exp next系数指数指针其中指针指向下一项的位置结点类型：typedef struct pnode{float coef;int exp;struct pnode *next;}polynode;14.双链表：链表中有两条方向不同的链形式描述：typedef struct dnode{datatype data;struct dnode *peior,*next;/*peior是指向其前趋的指针域*/} dlinklist;dlinklist *head;结点结构：peior d ata next第三章15.栈:栈是限制仅在表的一端插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。
（栈为后进先出的线性表，简称LIFO表）16.栈的顺序结构简称为顺序表，它是运算受限的顺序表17.顺序栈的定义：typedef int datatype;#define maxsize 64typedef struct{datatype data[maxsize];int top; /*top为栈顶指针*/}seqstack;seqstack *s;18.s->data[0]为栈底元素，栈顶指针s->top是正向增长的，进栈时s->top加1；退栈时减1，s->top<0表示空栈，s->top<maxsize-1，栈满；栈满时进行进栈运算必定产生空间溢出，称“上溢”，栈空时进行退栈运算也将溢出，称“下溢”19.顺序栈的五种基本算法○1置空栈：SETNULL(s)seqstack *s;{s->top=-1;}○2判栈空int EMPTY(s)seqstack *s;{if(s->top>=0)return FALSE;elsereturn TRUE;}○3进栈seqstack *PUSH(s,x) /*将元素x插入顺序栈s的顶部*/ seqstack *s;datatype x;{if(s->top==maxsize-1)print(“overflow”);return NULL;else{s->top++;s->data[s->top]=x;}}return s;○4。
