《数据结构-2-线性表》由会员分享，可在线阅读，更多相关《数据结构-2-线性表（65页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加2.1 线性表的类型定义n线性结构的特点：在数据元素的非空有限集中，1）有且 仅有一个开始结点；2）有且仅有一个终端结 点；3）除第一个结点外，集合中的每个数据 元素均有且只有一个前驱；4）除最后一个结 点外，集合中的每个数据元素均有且只有一 个后继。n线性序列：线性结构中的所有结点按其关系 可以排成一个序列，记为(a1,ai,ai+1,an) 2.1 线性表的类型定义1. 线性表1）线性表是n(n 0)个数据元素的有限序列。2）线性表是一种最常用且最简单的数据
2、结构。含有n个数据元素的线性表是一个数据结构：List = (D,R)其中：D = ai | aiD0,i=1,2,n,n0R = N, N = | ai-1 , ai D0 , i = 2,3,nD0 为某个数据对象数据的子集u特性：均匀性，有序性（线性序列关系）2.1 线性表的类型定义1. 线性表3）线性表的长度及空表u线性表中数据元素的个数n（n0）定义为线性表的长度u当线性表的长度为0 时，称为空表。u ai 是第i个数据元素，称i为ai 在线性表中的位序。2. 线性表的基本操作 p19p201）InitList(int length; SqList; SqList L;2.顺序存储线
3、性表的描述v C语言中静态分配描述求置空表Status ClearList( return OK;2.顺序存储线性表的描述求长度Status List length( SqList L )length= L. length;return OK;2.顺序存储线性表的描述初始化Status InitList_ SqList( SqList L )L.elem=(*int) malloc(LIST_MAX_LENGTH*sizeof(int) );if(!L.elem) exit(Overflow) ; L. length=0;return OK;2.顺序存储线性表的描述2. 顺序表的描述 1) C
4、语言中动态分配描述 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem;int length;int listsize;SqList; SqList L;n说明：elem数组指针指向线性表的基地址；length指示线性 表的当前长度；listsize指示顺序表当前分配的存储空间大 小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType)2) 几个基本操作 初始化np23算法2.3 Status InitList_SqList(SqList
5、 if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK; 插入 p24算法2.4 Status ListInsert_sq(SqList if (L.length = L.listsize) newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.elem = newbase;L.listsize+=LISTINCREMENT;n需将
6、第n(即L.length)至第i个元素向后移动一个位置。 注意：C语言中数组下标从0开始，则表中第i个数据 元素是L.elemi-1。插入 p24算法2.4 函数realloc的格式及功能格式： void *realloc(void *p,unsigned size)功能：将p所指向的已分配内存区域的大小改为size。size可以比原来分配的空间大或小。插入（续）q=for (p=p=q;-p)*(p+1) = *p;*q=e;+L.length;return OK; 删除 p24p25算法2.5 Status ListDelete_sq(SqList p=e=*p;q=L.elem+leng
7、th-1;/表尾for (+p;p= La.listsize) return OVERFLOW; while (i= i;j-) La.elemj+1 = La.elemj; La.elemi= x; La.length+; return OK;递减插入Status DeOrderInsert_Sq(SqList if (La.length = La.listsize) return OVERFLOW; i=La.length-1; while (i=0 j-) La.elemj+1 = La.elemj; La.elemi+1= x; La.length +; return OK; 4. 顺
8、序表的分析1）优点u顺序表的结构简单u顺序表的存储效率高，是紧凑结构u顺序表是一个随机存储结构（直接存取结构）2）缺点u在顺序表中进行插入和删除操作时，需要移动数据 元素，算法效率较低。u对长度变化较大的线性表，或者要预先分配较大空 间或者要经常扩充线性表，给操作带来不方便。u原因：数组的静态特性造成2.3 线性表的链式表示和实现 1. 线性链表n特点：在内存中用一组任意的存储单元来存储线性 表的数据元素，用每个数据元素所带的指针来确定 其后继元素的存储位置。这两部分信息组成数据元 素的存储映像，称作结点。n结点：数据域 + 指针域（链域）n链式存储结构：n个结点链接成一个链表n线性链表（单链
9、表）：链表的每个结点只包含一个 指针域。datanext单链表单链表 ( (Singly Linked ListSingly Linked List) )nfirst 头指针nlast 尾指针 n 指针为空n单链表由头指针唯一确 定，因此常用头指针的 名字来命名。如表first.单链表的存储映像单链表的存储映像1）线性链表的描述 p28typedef struct LNodeElemType data;Struct LNode *next; LNode, *LinkList;LinkList L; /L是LinkList类型的变量，表示单链表的头指针2）术语n头指针：指向链表中第一个结点n第一
10、个数据元素结点（开始结点）n头结点：有时在单链表的第一个数据元素结点 之前附设一个结点，称之头结点。u说明：头结点的next域指向链表中的第一个数据 元素结点。u对于头结点数据域的处理：a.加特殊信息 b.置空 c.如数据域为整型，则在该处存放链表长度信息 。3）带头结点的单链表示意图 p28图2.7n由于开始结点的位置被存放在头结点的指针域中，所以 对链表第一个位置的操作同其他位置一样，无须特殊处 理。n无论链表是否为空，其头指针是指向头结点的非空指针 ，因此对空表与非空表的处理也就统一了，简化了链表 操作的实现。非空表非空表 空表空表2. 基本操作1）取元素 p29 算法2.8 2）插入元
11、素 p30 算法2.9 3）删除元素 p30 算法2.10 4）建立链表 p30p31 算法2.11 5）有序链表的合并 p31 算法2.12 6）查找（按值查找） 7）求长度 8）集合的并运算取元素（按序号查找） p29 算法2.8 从链表的头指针出发，顺链域next逐个结点往下搜索， 直至找到第i个结点为止（j=i)Status GetElem_L(LinkList L, int i,ElemType p=L-next; int j=1; while (p +j; if (!p | ji) return ERROR; e=p-data; return OK; 插入元素p30 算法2.9 在
12、第i个元素之前插入，先找到第i-1个结点Status ListInsert_L(LinkList p=L; int j=0; while (p +j; if (!p | j i-1) return ERROR; s = (LinkList) malloc( sizeof (LNode); s-data = e; s-next = p-next; p-next = s; return OK; esP-next=s(2)(3)ps-next=p-nexta(1)b在带表头结点的单链表在带表头结点的单链表第一个结点前插入新结点第一个结点前插入新结点newnodenext = pnext;if ( p
13、next =NULL ) last = newnode;pnext = newnode;删除元素p30 算法2.10Status ListDelete_L(LinkList p=L; int j=0; while (p-next +j; if (!(p-next) | j i-1) return ERROR; q=p-next;p-next = q-next; e=q-data;free(q); return OK; q = pnext;pnext = qnext;delete q;if ( pnext = NULL ) last = p;从带表头结点的单链表中删除第一个结点从带表头结点的单链
14、表中删除第一个结点建立链表（头插法建表）p31 算法2.11 在链表表头插入新结点，结点次序与输入次序相反。void CreateList_L(LinkList L=(LinkList)malloc(sizeof(LNode); L-next = NULL; for (int i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(“%d“, p-next = L-next; L-next=p; 尾插法建表：将新结点插到链表尾部，须增设一个尾指针last，使其始终指向当前链表的尾结点。 合并有序链表p31 算法2.12void MergeList_
15、L(LinkList La,LinkList Lb,LinkList pa = La-next; pb= Lb-next; Lc = pc = La; while (pa pc=pa; pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb; free(Lb); 查找（按值查找）int LinkLocate_L (LinkList L, int x) int i; LinkList p;p=L-next; i=1;while (p!=NULL i+;if (!p) printf (“Not found! n“); return(0); else printf (“i=%dn“,i);return (i); 求长度int LinkLength_L (LinkList L) int j; LinkList p;p=L-next; j=0;while (p) p=p-next;j+;return(j); 注意：p=NULL与p-next =NULL是不同的。n总结：带头结点：链表置空 L-next
