第2章线性表_3.ppt

练习 /*习题2-5算法*/ int Del(SeqList *L,int i,int k) { int j; if( (i1)||(iL-last+1)|| k0 ) { printf(参数不合法！); return(ERROR); } /* 删除第i~k个元素 */ if(i-1+kL-last) /* 如果从第i个元素到表尾没有k个元素 */ L-last=i-2; /*则只需更新last即可*/ else /*否则需要移动下标从i-1+k~last之间的元素*/ { for(j=i-1+k; j=L-last; j++) L-elem[j-k]=L-elem[j]; /*向前移k个位置*/ L-last=L-last-k; } return(OK); } 练习 void main() { SeqList A; int i,m,n; A.last=-1; /* 将顺序表置为空表 */ for(i=1;i=5;i++) InsList(A,i,2*i-1); /* 向顺序表A中依次插入1,3,5,7,9*/ printf(表A为：);out(A); /* 输出表A */ printf(输入待删元素起始位置序号：); scanf(%d,m); printf(输入待删元素个数：); scanf(%d,n); if(Del(A,m,n)==OK) /* 删除表A从序号m开始的n个元素 */ { printf(删除元素后，表A为：); out(A); /* 输出表A */ } } 练习 课后题P73 习题8：已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。编写一个高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素）。分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 练习 #includestdio.h #includestdlib.h #define NULL 0 typedef int ElemType; typedef struct Node /* 结点类型定义 */ { ElemType data; struct Node *next; }Node,*LinkList;/* LinkList为结构体指针类型 */ void InitList(LinkList *L) /* 初始化一个空单链表 */ { *L=(LinkList)malloc(sizeof(Node)); /* 建立头结点*/ (*L)-next=NULL; } 练习 void CreateFromTail(LinkList L) { Node *r, *s; int num,temp; /* num为链表元素个数,temp为元素值 */ r=L; /* r指向链表的当前表尾，便于做尾插入，初始指向头结点 */ printf(请输入要建立的单链表元素个数：); scanf(%d,num); printf(请按从小到大的顺序输入%d个整数：,num); while(num0) { scanf(%d,temp); s=(Node*)malloc(sizeof(Node)); s-data=temp; r-next=s; r=s; num--; } r-next=NULL; /* 将最后一个结点的next链域置为空*/ } 练习 void output(LinkList L) { Node *p; p=L-next; while(p!=NULL) { printf(%d ,p-data); p=p-next; } printf(\n); } 练习 /*习题8，删除单链表中满足条件 minkxmaxk 的元素结点*/ void Del(LinkList L,ElemType mink,ElemType maxk) { Node *p,*q,*r; p=L-next; q=L; /* p从L的第一有效结点开始,q为p的前驱 */ while(p!=NULLp-data=mink) { q=p;p=p-next; } if(p!=NULL) /* 找到了待删的第一个结点 */ while(p!=NULLp-datamaxk) /*做新一轮循环，删除所有满足条件的结点 */ { r=p