《[工学]第02章 线性表》由会员分享，可在线阅读，更多相关《[工学]第02章 线性表（74页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 线性表线性表v线性表v顺序表 v链表v顺序表与链表的比较主要内容：一、一、线性线性表的定义表的定义n（0）个数据元素的有限序列，记作 （a1, ai-1, ai, ai+1, an）其中：ai 是表中数据元素，n 是表长度。特点: n同一线性表中元素具有相同特性。n相邻数据元素之间存在序偶关系。n除第一个元素外，其他每一个元素有一 个且仅有一个直接前驱。n除最后一个元素外，其他每一个元素有 一个且仅有一个直接后继。a1a2a3a4a5a6二、线性表的顺序表示及实现二、线性表的顺序表示及实现1、定义：将线性表中的元素相继存放在 一个连续的存储空间中。 2、存储结构：数组。 3、特点
2、：线性表的顺序存储方式。 4、存取方式：顺序访问, 可以随机存取。 5、顺序存储结构示意图45 89 90 67 40 78 0 1 2 3 4 5 6、顺序表的存储的位置关系：LOC(a i+1) = LOC( a i )+l LOC(a i) = LOC(a1)+(i-1)*l a1 a2 a i an1 2 i na a+l a+(i-1)*l a+(n-1)*l idle7、顺序表（SqList）的存储结构#define List_INIT_SIZE 100 /最大允许长度#define ListICREMENT 10 typedef struct ElemType * elem; /
3、存储空间基址int length; /当前元素个数int listsize /当前分配的存储容量 SqList;8、顺序表基本运算n初始化void InitList ( SqList if ( L.elem = NULL ) printf ( “存储分配失败!n” );exit (overflow);L.length = 0;n按值查找：在顺序表中从头查找结点值 等于给定值 x 的结点int Find ( SqList while ( i = 0 /插入不成功if(L.length=L.listsize) newbase=(ElemType*)realloc(L.data,(L.listsiz
4、e+LISTINCREMENT)*sizeo f(ElemType);if(!newbase)exit(overflow);L.data=newbase; /新的基地址L.listsize+=LISTINCREMENT; /增加存储容量ElemType *q,*p; q= /q为插入位置for(p=p=q;-p) *(p+1)=*p;*q=x;+L.length;return 1; 删除25 34 57 50 16 48 09 63 16删除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7n顺序表的删除 演示int ListDelete ( SqList /在表中查
5、找 xif ( i = 0 ) L.length - ;for ( int j = i; j next = L-next ; L-next= newnode;（插入前） （插入后）LnewnodenewnodeL5、单链表的基本操作第二种情况：在链表中间插入newnode-next = p-next;p-next = newnode；(插入前) (插入后)newnode pnewnodep第三种情况：在链表末尾插入newnode-next =Null;p-next = newnode；p(插入前) (插入后)newnodenewnode pint ListInsert ( LinkList i
6、nt j = 0;while ( p j+; /找第 i-1个结点 if ( !p |ji-1) /i小于1或大于表长return 0;s= (Lnode *) malloc ( sizeof(Lnode) );s-data=x;s-next=p-next;p_next=s;return 1; 演示n删除 在单链表中删除ai结点q = p-next; p-next = q-next;删除前删除后ai-1aiai+1pqpai-1ai+1aiint ListDelete ( LinkList int j=0;while(p-nextj+; if(!(p-next)|ji-1) return 0;
7、q=p-next;p-next=q-next; /删除结点free(q);return 1; 演示n建立 前插法建立单链表演示从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端直到读入结束符为止。LqLqvoid createList ( LinkList LinkList p;for(int i=1;idata);P-next=L-next;L-next=p; 后插法建立单链表每次将新结点加在链表的表尾；尾指针r ,总是指向表中最后一个结点，新结点 插在它的后面；qLpLPvoid createList (LinkList p=L;Lnode
8、*q, *p; for (int i=1;idata); /建立新结点P -next = q; p =q; /插入到表末端p -next = Null; 清空单链表 void ClearEmpty ( LinkList while ( L-next) p = L-next; L-next = p-next;/将表头结点后第一个结点从链中摘下free( p ); /释放 计算单链表长度int GetLength ( LinkList L ) / 取得线性单链表的长度LinkList p = L-next;/指针 p 指示第一个结点int count = 0; while ( p) /逐个结点检测
9、count+; p = p-next; return count; 按值查找Lnode * Find ( LinkList L, ElemType value ) /在链表中从头搜索其数据值为value的结点 Lnode * p = L-next;/指针 p 指示第一个结点while ( p return p; 按序号查找（定位）Lnode * Locate ( LinkList L, int i ) /返回表中第 i 个元素的地址if ( i next; int k = 0; while ( p /找第 i 个结点 if ( k = i ) return p; /返回第 i 个结点地址els
10、e return Null; 合并两个有序单链表 演示void MergeList(LinkList La,LinkList Lb,LinkList pa=La-next;pb=Lb-next;pc=Lc=La;while(papc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?:pa:pb;1ZHANG2WANG6LI4ZHAO5WU0CHEN31ZHANG2WANG3LI4ZHAO5WU00 1 2 3 4 5 601 23 4 5 6修改前修改后用一维数组描述线性链表6、单链表静态存储结构 定义 const int Ma
11、xSize = 100; /静态链表大小typedef int ElemType;typedef struc /静态链表结点ElemType data;int cur; Component,SLinkListMaxSize;链表空间初始化void InitList ( SLinkList for ( int i = 1; i ListLength ) return 0; / 参数不合理int j , p = 0; for ( j=1;jListLength(SL)+1) return 0;j=malloc(SL);/申请一个新结点if(j) SLj.data=x;for(l=1;lListLe
12、ngth(SL) return 0;for(j=1;jnext=L-prior=L;return 1; 2、双向循环链表的操作n计算双向循环链表的长度 int GetLength ( DuLinkList L ) /计算带表头结点的双向循环链表的长度int i=0;DuLNode * p =L-next;while ( p != L ) i+;p = p-next; return i; n双向循环链表的插入 (非空表)q-prior = p; q-next = p-next; p-next = q; q-next-prior = q;在结点 *p 后插入25LL314815pp31482515
13、 qn双向循环链表的插入 (空表)q-prior = p; q-next = p-next;p-next = q; q-next-prior = q; pqL25Lp在结点 *p 后插入25int ListInsert ( DuLinkList DuLinkList q, p = Locate ( L, i-1 ); /指针定位于插入位置if (! P) return 0;q=( DuLinkList) malloc( sizeof ( DuLNode ) ); /分配结点q-data = x;q-prior = p; p-next-prior = q; /在前驱方向链入新结点q-next =
14、 p-next; p-next = q;/在后继方向链入新结点return 1; n双向循环链表的删除p-next-prior = p-prior; p-prior-next = p-next;(非空表)删除48LL314815p3115int ListDelete ( DuLinkList DuLNode *p;p = Locate ( L, i ); /指针定位于删除结点位置if (! p)return 0;p-next-prior = p-prior;p-prior-next = p-next; /删除结点 pfree ( p ); /释放return 1; 四、顺序表与链表的比较1、基于空间的比较n存储分配的方式u顺序表的存储空间是静态分配的u链表的存储空间是动态分配的n存储密度 = 结点数据本身所占的存储量/结点 结构所占的存储总量u顺序表的存储密度 = 1u链表的存储密度
