《线性表习题课》由会员分享，可在线阅读，更多相关《线性表习题课（23页珍藏版）》请在金锄头文库上搜索。
1、1数 据 结 构主讲人：米晓红 2线性表习题课v1)在非空的线性表，有且仅有一个开始结点a1，它没 有直接前趋，而仅有一个直接后继a2v2)有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；v3)其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。1、线性表的逻辑特征：一、要点回顾d1 d2 d3 d4 d5 d6 d732、线性表的顺序表示和实现#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef structElemType *elem; int length; int
2、listsize; Sqlist; （1）存储结构的定义4（2）操作的实现Status ListInsert_Sq(SqList if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType);if (!newbase) exit(OVERFLOW);L.elem=newbase; L.listsize+=LISTINCREMENT; q = / q 指示插入位置 for (p = p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右
3、移*q = e; +L.length; / 表长增1 return OK; / ListInsert_Sq 5Status ListDelete_sq(Sqlistp=/p指示删除位置e=*p;q=L.elem+L.length-1; /q指示表尾位置for(+p；pnext; j=1;while(p +j;if(!p|ji) return ERROR;e=p-data;return OK; / GetElem_L9Status ListInsert_L(LinkList j=0;while(p+j; /寻找第i -1个结点if(!p| ji-1) return ERROR;s=(LinkLi
4、st)malloc(sizeof(Lnode);s-data=e; s-next=p-next;p-next=s;return OK; / ListInsert_L10Status ListDelete_L (LinkList j=0;while(p-next +j;if(!(p-next) | ji-1) return ERROR;q=p-next; p-next=q-next;e=q-data; free(q);return OK; / ListDelete_L 11void CreateList_L(LinkList L-next=NULL;for(i=n;i0;i-)p=(LinkLi
5、st) malloc (sizeof)(LNode);scanf(p-next=L-next; L-next=p;/ CreatList_L12Status Insert_SqList(SqList for(i=va.length-1;va.elemixi-)va.elemi+1=va.elemi;va.elemi+1=x;va.length+;return OK; /Insert_SqList 2.11 设顺序表va中的数据元素递增有序。试编写一算法，将x 插入到顺序表的适当位置上，以保持该表的有序性。二、作业点评132.14 试写一算法在带头结点的单链表结构上实现线性表操作 LENGTH(
6、L）。int Length(LinkList L)/求链表的长度 p=L; k=0; while(p-next) p=p-next; k+; return k; 142.19已知线性表中的元素以值递增有序排列，并以单链表作存储 结构。试写一高效的算法，删除表中所有值大于mink且小于maxk 的元素（若表中存在这样的元素）同时释放被删结点空间，并分 析算法时间复杂度（mink和maxk是给定参变量）Status Delete_Between(Linklist p=L-next; while(p!=NULLwhile(p!=NULLfree(r);q- next=p; return OK;/ D
7、elete_Between15三、习题讲解例1、已知线性表中元素无序，且采用带头结点的单链表存储结 构，要求删除所有大于min且小于max的结点。Status Delete_Between(Linklist p=L-next; while(p) if(p-datadata=maxk)q=p; p=p-next;elseq-next=p-next; free(p);p=q-next; return OK; / Delete_Between16例2、有一单链表（不带头结点）头指针为head，试设计一算 法使得单链表插入x后仍递增有序。Status Insert(Linklist s-data=x;
8、 s-next=NULL; if(head=NULL|xdata) s-next=head; head=s; else q=head;p=head-next;while(p!=NULLs-next=p; q-next=s; return OK; /Insert17Status Insert(Linklist s-data=x; s-next=NULL; q=head;p=head-next;if(p!=NULLs-next=p; q-next=s; return OK; /Insert18例3、试分别以不同的存储结构实现线性表的就地逆转算法， 即在原表的存储空间内将线性表 （a1,a2,.,a
9、n）逆置为 （an,an-1,.,a1）。 （1）顺序存储结构/结构类型定义：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemType *elem; int length; int listsize; Sqlist; 19/算法void reverse(SqList inext; /指向开始结点head-next=NULL; /逆置后初表为空while(p) /p为NULL，表示已经全部逆置q=p-next; /p指向下一个需要逆置的结点p-next=head-next; /将需要逆置结点插入头结点后面head-next=p;p=q; return OK;/convert/算法22例4、试在带头结点的单链表中值为x的结点之后插入m个结点。/类型定义： typedef struct LNodeElemtype data;struct LNode *next;LNode, *LinkList;23/算法实现 Status Insert (Linklist if(p=NULL) return ERROR; elsewhile( p-data!=x) p=p-next;q=p-next;for(i=1;idata=y; p-next=s; p=s;s-next=q;return OK; /Insert
