答是要 3.1线形表的基本概念 存结构顺序存储结构顺序表和链式存備结构链表 3.2顺序表 饭序表的定义 饭序表的数据类型定义 版序表的基本操作 3.3链表 单链表 静态链表 循环链表 双向链表 34广义表
内容提要 3.1 线形表的基本概念 • 存储结构:顺序存储结构(顺序表)和链式存储结构(链表) 3.2 顺序表 • 顺序表的定义 • 顺序表的数据类型定义 • 顺序表的基本操作 3.3 链表 • 单链表 • 静态链表 • 循环链表 • 双向链表 3.4 广义表
3线坐表的 线性表:B=(AR,A=白a=1,2,…,ny 只={a1,aN|i=2,3…n 起始元素:a 终止元素:a 数据元素的位序: 线性表的长度 空表:n为的的线性表 常见的操作 访问元素删除元素插入元素 查找元素排序合并拆分 存情结构:顺序存储结构顺序表 链式存角结构链表
3.1 线性表的基本概念 线性表：B=(A,R), A={ai |i=1,2,..,n}, R={|i=2,3,…,n} 起始元素：a1 终止元素： an 数据元素的位序：i 线性表的长度：n 空表：n为0时的线性表 常见的操作： 存储结构：顺序存储结构(顺序表) 链式存储结构(链表) 访问元素 删除元素 插入元素 查找元素 排序 合并拆分
3.2所序表 版序表:用一组地址连续的存倍单元按线性表的元 素间的逻舞版序一次存放数据元素。它是一种随即存取 结构 数据元素的逻辑顺序与在内存中的存储顺序完全一致, 必需要额外存储数据元素之间的关系 顺序表的数据类型定义 #define maXsize 100 /*顺序表的最大长度* typedef struct i elemtype elem MAXSIE: /* ' elemtype可以根据实际需要而定* int len;/*顺序表当前的长度* ISQLIST;
3.2 顺序表 顺序表：用一组地址连续的存储单元按线性表的元 素间的逻辑顺序一次存放数据元素。它是一种随即存取 结构。 顺序表的数据类型定义： 数据元素的逻辑顺序与在内存中的存储顺序完全一致， 必需要额外存储数据元素之间的关系 #define MAXSIZE 100 /*顺序表的最大长度*/ typedef struct { elemtype elem[MAXSIZE]; /*elemtype可以根据实际需要而定*/ int len; /*顺序表当前的长度*/ }SQLIST;
1、顺序表的基本操作(创建 (1)线性表的创建 时间复亲度:Omn) void createsqlist(SQLIST*l) int i: printi(请输入元素个数in"): scanf("%d",&L→ylen) printf("请输入%d个元素n"); for(i=0;ielemi]. key) 略去了其他数据项的输入*
顺序表(cont’d) 1、顺序表的基本操作(创建) void createsqlist(SQLIST *L) { int i; printf("请输入元素个数\n"); scanf("%d",&L→len); printf("请输入%d个元素\n"); for(i=0;i<L→len;i++) scanf("%d",&L→elem[i].key); /*略去了其他数据项的输入*/ } (1) 线性表的创建 时间复杂度：O(n)
1、顺序表的基本操作(查 (2) 版序查找 的间复亲度:O(n) f Sqsearch(SQLIST L,int aidkey t s int for(j=0水<Llen;j++) if(.elem[jl.key==aidkey) return J; return-1;
顺序表(cont’d) int Sqsearch(SQLIST L,int aidkey) { int j; for(j=0;j<L.len;j++) if(L.elem[j].key==aidkey) return j; return -1; } (2) 顺序查找 时间复杂度：O(n) 1、顺序表的基本操作(查找)
1、顺序表的基本操作删除 (3)删除第个元素 时间复杂度:O( void Sqdel(sqlist l, int i) for(j=i+;jlen;j ++ L→>elem[j-1l=L→>elem[jl: /*上面语句从第i+1个元素开始,一次前移* L→len
顺序表(cont’d) 1、顺序表的基本操作(删除) void Sqdel(SQLIST *L, int i) { int j; for(j=i+1;j<L→len;j++) L→elem[j-1]=L→elem[j]; /*上面语句从第i+1个元素开始，一次前移*/ L→len--; } (3) 删除第i个元素 时间复杂度：O(n)
1、顺序表的基本操作插入 (4)在第个元素后插入 时间复杂度:O(m) int Sqins(sQLIST *L, int i, elemtype x) f int j; if(L→len= MAXSIZE) return-1;/*插入失败* for(j=L→≯en-1;j>=i+1;j-) Elem[j+1Fl-elemjl; L→>elem[i+1=x; L→>len++; return i+l
顺序表(cont’d) 1、顺序表的基本操作(插入) (4) 在第i个元素后插入 时间复杂度：O(n) int Sqins(SQLIST *L ,int i, elemtype x) { int j; if(L→len==MAXSIZE) return -1; /*插入失败*/ for(j=L→len-1;j>=i+1;j--) L→elem[j+1]=L→elem[j]; L→elem[i+1]=x; L→len++; return i+1; }
2、顺序表的操作实例 【例线性表的合并②、时复杂度,0+m void Sqmerge(sQLiST La SQLIST Lb, 依次将La,Lb SOLIST *Lc 中的较小者 续接到c中 i int i=0,j=0, k=0, m, n; 将La或Lb中n=Laen;m= Lb.len;Le-len=m+n; 的剩余部分 whiler(in&&jm) 续接到_c if(Laelemi]. key elema++]= Laelem[i计++l; else lc->elem[k++==Lb elem[j++; while(ielem[k++=Laelemi++ while(j<m)Lc-elem( k++|=Lb elem[j++
顺序表(cont’d) 2、顺序表的操作实例 【例】线性表的合并 时间复杂度：O(n+m) void Sqmerge(SQLIST La,SQLIST Lb, SQLIST *Lc) { int i=0,j=0,k=0,m,n; n=La.len;m=Lb.len;Lc→len=m+n; while(i<n&&j<m) if(La.elem[i].key<=Lb.elem[j].key) Lc→elem[k++]=La.elem[i++]; else Lc→elem[k++]=Lb.elem[j++]; while(i<n)Lc→elem[k++]=La.elem[i++]; while(j<m)Lc→elem[k++]=Lb.elem[j++]; } 将La或Lb中 的剩余部分 续接到Lc 依次将La,Lb 中的较小者 续接到Lc中
2、顺序表的操作实例 例】线性表的合并 例如,设 LA=(3,5,8,11)→ LB=(2,6,8,9,11,15,20)->j LC=(2,3,56,8.8,9,11,11,15,20)→>k
顺序表(cont’d) 2、顺序表的操作实例 【例】线性表的合并 例如，设 LA = (3,5,8,11) → i LB = (2,6,8,9,11,15,20) → j 则 LC = (2,3,5,6,8,8,9,11,11,15,20) → k
3.3无之单键表 1、单链表定义 结点:数据元素与指向后继的指针存信在一起称为结点 数据域:结点中存放数据元素的部分 指针域:结点中存放指针的部分 单链表:结点中只有一个指针的链表 链表需要有个指向首结点的指针来标识; 或者用头结点来标识 head a2 a3 an 头结点 a1l12a3…-an
3.3 链表之单链表 1、单链表定义 结点：数据元素与指向后继的指针存储在一起称为结点 数据域：结点中存放数据元素的部分 指针域：结点中存放指针的部分 单链表：结点中只有一个指针的链表 链表需要有个指向首结点的指针来标识； 或者用头结点来标识 a1 a2 a3 an ^ head a1 a2 a3 an ^ L 头结点