第三课 第二章 线性表.ppt

唐山师范学院数学与信息科学系 数据结构 第二章 线性表 教学目标：掌握线性表的逻辑结构；线性表的顺序表示和实现；线性表的链式表示和实现，重点是是插入和删除算法。 2．1 线性表的类型定义 2．2 线性表的顺序表示与实现 2．3 线性表的链式表示与实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 1.a.(4),(1) b.(7),(11),(8),(4),(1) c.(5),(12) d.(11),(9),(1),(6) 2.a.(11),(3),(4) b.(10),(12),(8),(11),(3),(14) c.(10),(12),(7),(3),(14) d.(12),(11),(3),(14) e.(12),(9),(11),(3),(14) 3.Status reverse(linklist L) {p=L-next; L-next=NULL; While(p) {q=p-next; p-next=L-next; L-next=p; p=q; } return OK; } 4.Status insert(linklist L,int i,elemtype e) {p=L; s=(linklist)malloc(sizeof(lnode)); s-data=e; if(i==1) {s-next=L;L=s;} else {while(--i1)p=p-next; s-next=p;p-next=s; } return OK; } 静态链表 #Define MAXSIZE 1000 Typedef struct {ElemType data; int cur;}component,SlinkList[MAXSUZE]; 在静态链表中实现定位函数LlocateElem Int LocateElem_SL(SLinkList s,ElemType e) {i=S[0].cur; While(Is[i].data!=e)I=s[i].cur; Return i; } 将整个数组空间初始化成一个链表 Void initSpace_SL(Slinklist space) {for(i=0;iMAXSIZE-1;++i) space[i].cur=i+1; Space[MAXSIZE-1].cur=0; } void difference(SLinkList space,int *S) /* 算法2.17 */ { /* 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)∪(B-A) */ /* 的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为备用空间的头指针 */ int r,p,m,n,i,j,k; ElemType b; InitSpace(space); /* 初始化备用空间 */ *S=Malloc(space); /* 生成S的头结点 */ r=*S; /* r指向S的当前最后结点 */ printf(请输入集合A和B的元素个数m,n:); scanf(%d,%d%*c,m,n); /* %*c吃掉回车符 */ printf(请输入集合A的元素（共%d个）:,m); for(j=1;j=m;j++) /* 建立集合A的链表 */ { i=Malloc(space); /* 分配结点 */ scanf(%c,space[i].data); /* 输入A的元素值 */ space[r].cur=i; /* 插入到表尾 */ r=i; } scanf(%*c); /* %*c吃掉回车符 */ space[r].cur=0; /* 尾结点的指针为空 */ printf(请输入集合B的元素（共%d个）:,n); for(j=1;j=n;j++) { /* 依次输入B的元素,若不在当前表中,则插入,否则删除 */ scanf(%c,b); p=*S; k=space[*S].cur; /* k指向集合A中的第一个结点 */ while(k!=space[r].curspace[k].data!=b) { /* 在当前表中查找 */ p=k; k=space[k].cur; } if(k==space[r].cur) { /* 当前表中不存在该元素，插入在r