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

1、数 据 结 构 主讲人：米晓红 ,线性表习题课,1)在非空的线性表，有且仅有一个开始结点a1，它没 有直接前趋，而仅有一个直接后继a2 2)有且仅有一个终端结点an，它没有直接后继，而仅 有一个直接前趋an-1； 3)其余的内部结点ai(2in-1)都有且仅有一个直接 前趋ai-1和一个直接后继ai+1。,1、线性表的逻辑特征：,一、要点回顾,2、线性表的顺序表示和实现,#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; Sqli

2、st;,（1）存储结构的定义,（2）操作的实现,Status ListInsert_Sq(SqList / ListInsert_Sq,Status ListDelete_sq(Sqlist / ListDelete_sq,Status LocateElem_sq(SqList L,ElemType e) /在顺序表中查找第一个值为e的元素的位序 i=1; p=L.elem; while(i=L.length /LocateElem_sq,3、线性表的单链表存储结构,typedef struct LNode Elemtype data; struct LNode *next; Lnode, *

3、LinkList;,（1）存储结构的定义,（2）操作的实现,Status GetElem_L(LinkList L,int i,ElemType / GetElem_L,Status ListInsert_L(LinkList / ListInsert_L,Status ListDelete_L (LinkList / ListDelete_L,void CreateList_L(LinkList / CreatList_L,Status Insert_SqList(SqList /Insert_SqList,2.11 设顺序表va中的数据元素递增有序。试编写一算法，将x插入到顺序表的适当位置

4、上，以保持该表的有序性。,二、作业点评,2.14 试写一算法在带头结点的单链表结构上实现线性表操作 LENGTH(L）。,int Length(LinkList L)/求链表的长度 p=L-next; k=0; while(p) p=p-next; k+; return k; ,2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析算法时间复杂度（mink和maxk是给定参变量）,Status Delete_Between(Linklist / Delete_Betw

5、een,三、习题讲解,例1、已知线性表中元素无序，且采用带头结点的单链表存储结构，要求删除所有大于min且小于max的结点。,Status Delete_Between(Linklist / Delete_Between,例2、有一单链表（不带头结点）头指针为head，试设计一算法使得单链表插入x后仍递增有序。,Status Insert(Linklist /Insert,Status Insert(Linklist /Insert,例3、试分别以不同的存储结构实现线性表的就地逆转算法，即在原表的存储空间内将线性表 （a1,a2,.,an）逆置为（an,an-1,.,a1）。,（1）顺序存储结

6、构 /结构类型定义： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; Sqlist;,/算法 void reverse(SqList /reverse,（2）链式存储结构单链表,/结构类型定义：,typedef struct LNode Elemtype data; struct LNode *next; Lnode, *LinkList;,voidconvert(linklisthead) /带头结点的单链表head就地逆置LNode*p,*q;p=head-next;/指向开始结点head-next=NULL;/逆置后初表为空while(p)/p为NULL，表示已经全部逆置q=p-next;/p指向下一个需要逆置的结点 p-next=head-next;/将需要逆置结点插入头结点后面 head-next=p; p=q; return OK;/convert,/算法,例4、试在带头结点的单链表中值为x的结点之后插入m个结点。,/类型定义： typede