数据结构(C语言版)-线性表习题详解ppt课件

1、1数数 据据 结结 构构2线性表习题课线性表习题课1)1)在非空的线性表，有且仅有一个开场结点在非空的线性表，有且仅有一个开场结点a1a1，它没，它没 有直接前趋，而仅有一个直接后继有直接前趋，而仅有一个直接后继a2a22)2)有且仅有一个终端结点有且仅有一个终端结点anan，它没有直接后继，而仅，它没有直接后继，而仅 有一个直接前趋有一个直接前趋an-1an-1；3)3)其他的内部结点其他的内部结点ai(2ai(2i in-1)n-1)都有且仅有一个直接都有且仅有一个直接 前趋前趋ai-1ai-1和一个直接后继和一个直接后继ai+1ai+1。1 1、线性表的逻辑特征：、线性表的逻辑特征：一、

2、要点回想一、要点回想d1 d2 d3 d4 d5 d6 d732 2、线性表的顺序表示和实现、线性表的顺序表示和实现#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct ElemType *elem; int length; int listsize; Sqlist; 1 1存储构造的定义存储构造的定义42 2操作的实现操作的实现Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表在顺序表L的第的第 i 个元素之前插入新的元素个元素之前插入新的元素eIf(i

3、L.Length+1) return ERROR;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 = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的

4、元素右移插入位置及之后的元素右移 *q = e; +L.length; / 表长增表长增1return OK; / ListInsert_Sq 5Status ListDelete_sq(Sqlist&L，int i，ElemType &e) /在顺序线性表在顺序线性表L中删除第中删除第i个元素，并用个元素，并用e前往其值前往其值 if(iL.length) return ERROR; p=&(L.Elemi-1);/p指示删除位置指示删除位置 e=*p; q=L.elem+L.length-1; /q指示表尾位置指示表尾位置 for(+p；p=q；+p) *(p-1)=*p; /删除位置之后

5、元素前移删除位置之后元素前移 L.length-; /表长减表长减1 return OK; / ListDelete_sq6Status LocateElem_sq(SqList L,ElemType e) /在顺序表中查找第一个值为在顺序表中查找第一个值为e的元素的位序的元素的位序 i=1; p=L.elem; while(i=L.length & *p+!=e) +i; if(inext; j=1; while(p & jnext; +j; if(!p|ji) return ERROR; e=p-data; return OK;/ GetElem_L9Status ListInsert_L

6、(LinkList &L, int i ,ElemType e) /在带头结点的单链表在带头结点的单链表L中第中第i个位置之前插入元素个位置之前插入元素e p=L; j=0; while(p& jnext;+j; /寻觅第寻觅第i -1个结点个结点 if(!p| ji-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode); s-data=e; s-next=p-next; p-next=s; return OK;/ ListInsert_L10Status ListDelete_L (LinkList &L, int i, ElemType &e)

7、 /在带头结点的单链表在带头结点的单链表L中，删除第中，删除第i个元素，并用个元素，并用e前往前往 p=L; j=0; while(p-next & jnext; +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,int n) /逆位序输入逆位序输入n个元素的值，建立带头结点的单链表个元素的值，建立带头结点的单链表 L=(LinkList)malloc (sizeof

8、)(LNode); L-next=NULL; for(i=n;i0;i-) p=(LinkList) malloc (sizeof)(LNode); scanf(&p-data); p-next=L-next; L-next=p; / CreatList_L12Status Insert_SqList(SqList &va,int x)/把把x插入递增有序表插入递增有序表va中中 if(va.length=va.listsize) return (OVERFLOW); for(i=va.length-1;va.elemix&i=0;i-) va.elemi+1=va.elemi; va.ele

9、mi+1=x; va.length+; return OK;/Insert_SqList 2.11 设顺序表设顺序表va中的数据元素递增有序。试编写一算法，将中的数据元素递增有序。试编写一算法，将x插入到顺序表的适当位置上，以插入到顺序表的适当位置上，以坚持该表的有序性。坚持该表的有序性。二、作业点评二、作业点评132.14 试写一算法在带头结点的单链表构造上实现线性表操作试写一算法在带头结点的单链表构造上实现线性表操作 LENGTH(L。int Length(LinkList L)/求链表的长度求链表的长度 p=L-next; k=0; while(p) p=p-next; k+; retu

10、rn k; 142.19知线性表中的元素以值递增有序陈列，并以单链表作存储构造。试写一高效的算法，删除表中一切值大于mink且小于maxk的元素假设表中存在这样的元素同时释放被删结点空间，并分析算法时间复杂度mink和maxk是给定参变量Status Delete_Between(Linklist &L,int mink,int maxk)/删除递增链表删除递增链表L中值大于中值大于mink且小于且小于maxk的一切元素的一切元素if(L!=NULL)q=L;p=L-next; while(p!=NULL&p-datanext;while(p!=NULL&p-datanext;free(r);

11、q- next=p; return OK;/ Delete_Between15三、习题讲解三、习题讲解例例1 1、知线性表中元素无序，且采用带头结点的单链表存储构造，要求删除一切大于、知线性表中元素无序，且采用带头结点的单链表存储构造，要求删除一切大于minmin且小于且小于maxmax的结点。的结点。Status Delete_Between(Linklist &L,int mink,int maxk)/删除无序单链表中一切大于删除无序单链表中一切大于min且小于且小于max的结点的结点q=head; p=q-next;while(p)if(p-datadata=maxk) q=p; p=p

12、-next; else q-next=p-next; free(p); p=q-next; return OK;/ Delete_Between16例例2 2、有一单链表不带头结点头指针为、有一单链表不带头结点头指针为headhead，试设计一算法使得单链表插入，试设计一算法使得单链表插入x x后仍递增有后仍递增有序。序。Status Insert(Linklist &head, Elemtype x)/不带头结点单链表插入不带头结点单链表插入x后仍递增有序后仍递增有序s=(LinkList)malloc(sizeof(Lnode);s-data=x; s-next=NULL;if(head=

13、NULL|xdata) s-next=head; head=s;else q=head;p=head-next; while(p!=NULL&p-datanext; s-next=p; q-next=s; return OK;/Insert17Status Insert(Linklist &head, Elemtype x)/带头结点单链表插入带头结点单链表插入x后仍递增有序后仍递增有序s=(LinkList)malloc(sizeof(Lnode);s-data=x; s-next=NULL;q=head;p=head-next; if(p!=NULL&p-datanext; s-next=

14、p; q-next=s;return OK;/Insert18例例3 3、试分别以不同的存储构造实现线性表的就地逆转算法，即在原表的存储空间内将线性、试分别以不同的存储构造实现线性表的就地逆转算法，即在原表的存储空间内将线性表表 a1,a2,.,ana1,a2,.,an逆置为逆置为an,an-1,.,a1an,an-1,.,a1。 1顺序存储构造顺序存储构造 /构造类型定义：构造类型定义： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int list

15、size; Sqlist; 19/算法算法void reverse(SqList &L)/顺序表的就地逆置顺序表的就地逆置 for(i=1,j=L.length-1;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 4、试在带头结点的单链表中值为、试在带头结点的单链表中值为x x的结点之后插入的结点之后插入m m个结点。个结点。/类型定义：类型定义：typedef struct LNode Elemtype data; struct LNode *next; Lnode, *LinkList;2