算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)

Slides:



Advertisements
Similar presentations
时间与我们的世界 Pb 段心蕊.
Advertisements

主題:你看你看月亮的臉 課程:幼兒科學 教師:許衷源 組員:湘琳、鈺蓓、麗金、菊光
走過光陰 ── 眷村 三平 2號 何苡瑄.
数据结构概论 第2章 线性表 董黎刚 浙江工商大学信电学院
第四章 借贷记账法 在制造业中的应用.
第二章 线性表 £2.4 线性表的应用 £2.1 线性表的类型定义 £2.2 线性表的顺序存储结构 £2.3 线性表的链式存储结构
第二章 线性表 2.1 线性表的逻辑结构 一. 线性表定义如下:
9.1 概述 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 各种内部排序的比较
目 錄 壹、緣由 貳、問題解析 參、問題歸納 肆、因應對策 伍、評鑑獎勵 陸、追蹤考核 1.
第二章 线性表 ⒈教学内容:2.1 线性表逻辑结构; 2.2 线性表的顺序存储及运算实现; 2.3 线性表的链式存储和实现。
第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例.
第二章 线性表.
第2章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加.
铅(Pb) 低水平铅中毒:恶心、暴躁; 大剂量铅中毒:脑损伤; 贫血——便血——肾损伤——尿蛋白; 孕妇:畸胎、死胎、流产。
电磁干扰 在电子产品的外部和内部存在着各种电磁干扰,干扰会影响或破坏产品的正常工作。
Linked List Operations
第2章 线性表 线性结构 是一个数据元素的有序集合。.
其他类型的链表主要内容 静态链表 循环链表 双向链表.
第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较.
数据结构 第2章 线性表 吴忠华.
第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.
·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法
第2章 线性表(三) 1/.
数据结构 第二章 线性表.
制作:崔广才
数据结构 Data Structure 中南大学 主讲人:王国军,郑瑾 中南大学信息院计科系
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用 2.5 有序表 本章小结.
本 章 说 明 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.4 循环链表和双向链
西安交通大学计教中心 ctec.xjtu.edu.cn
第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例.
第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例.
第2章 线性表 丽水学院工学院.
第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示.
线性表是一种最简单的线性结构 线性结构的基本特征为: 线性结构 是 一个数据元素的有序(次序)集 1.集合中必存在唯一的一个“第一元素”;
第 3 讲 线性表(一).
第二章 线性表.
第一章 绪论.
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
内容回顾 线性表的定义和特点 线性表的顺序存储及查找、插入和删除.
第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加.
(知识点三) 2.3 线性表的链式表示和实现 本节将介绍线性表的另一存储结构—— 链式存储及其对应的操作。
线性表练习.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
第四讲 线性表(三) 1/.
第九章 查找 2019/2/16.
第三章 栈和队列.
顺序表的插入.
王玲 第 2 章 线性表 王玲 2019/2/25.
第2章 线性表 本章主要介绍下列内容 线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例.
第二章 线性表.
3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用
严蔚敏、吴伟民编著 清华大学出版社 学习网站:中国网页设计
顺序表的删除.
香港傳統的農村生活.
线性结构 线性结构的特点: 线性结构的种类 在数据元素的非空有限集中, (1)存在唯一的一个被称做“第一个”的数据元素;
第 四 讲 线性表(二).
第二章 线性表.
第三章 数据组织与处理.
3.16 枚举算法及其程序实现 ——数组的作用.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
問題解決與流程圖 高慧君 台北市立南港高中 2006年12月22日.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.
戒波罗蜜多.
Chapter 2 Entity-Relationship Model
第二章 线性表 线性表是一种最简单的线性结构 线性结构是一个数据元素的有序(次序)集.
由一个佯谬看涡旋电流的存在 PB 田鸿翔 指导老师 万树德.
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
Presentation transcript:

算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE) L.elem=new ElemType[msize]; L.listsize=msize; //顺序表的最大容量 L.length=0; // 顺序表初始时的元素数是0 }// end InitList_sq

算法3.4 void DestroyList_sq(SqList &L) {//销毁顺序表L delete [] L.elem; // 释放数组空间 L.length=0; L.listsize=0; }// end DestroyList_sq

算法3.5 /3.6/ 3.7 bool ListEmpty_sq(SqList L) { return (L.lenth==0); } bool ListFull_sq(SqList L) return (L.lenth==L.listsize); int ListLength_sq(SqList L) return L.lenth;

算法3.8 int LocateItem_sq(SqList L,Elemtype e) for(i=1;i<=L.length;i++) //依次查找每个元素 if(L.elem[i-1]==e)return i; //找到位序为i的元素 return 0; //没有找到值为e的元素 }// end LocateItem_sq

算法3.9 void GetItem_sq(SqList L,int i,Elemtype &e) {//将顺序表L中位序为i的元素值赋予e. e=L.elem[i-1]; }// end GetItem_sq

算法3.10 void ListInsert_sq(SqList &L,int i,Elemtype e) {//在顺序表L中位序为i的元素前插入一个新的元素e //同时需要考虑i的合法性和满状态 if(i<1||i>L.length+1){ErrorMsg(“i值非法!”);return;} if(L.length==L.listsize)Increment(L); //当前L已满 for(j=L.length-1;j>=i-1;j--) //由后往前逐个后移元素 L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; //在L.elem[i-1]放入e ++L.length; }// end ListInsert_sq

算法3.11 #define LIST_INC_SIZE 20 void Increment(SqList &L,int inc_size=LIST_INC_SIZE) { //增加顺序表L的容量为listsize+inc_size ElemType *a; a=new ElemType[L.listsize+inc_size]; // 给a指针分配内存 if(!a){ErrorMsg(“分配内存错误!”);return;} for(i=0;i<L.length;i++)a[i]=L.elem[i]; // 将原数组的元素复制到新数组 delete [] L.elem; // 释放原数组空间 L.elem=a; // 将新的数组赋予顺序表的指针 L.listsize+=inc_size; // 顺序表的容量增加inc_size }// end ListInsert_sq

算法3.12 void ListDelete_sq(SqList &L,int i,Elemtype &e) {//从顺序表L中删除位序为i的元素并把值赋予e if(i<1||i>L.length){ErrorMsg(“i值非法!”);return;} e=L.elem[i-1]; //保存L.elem[i-1]到e for(j=i;j<=L.length-1;j++) //由前往后逐个前移 L.elem[j-1]=L.elem[j]; L.length--; }// end ListDelete_sq

算法3.13 void Union_sq(SqList &La,SqList &Lb) {//实现顺序表A和B所表示的集合的并,结果放在A,销毁B for(i=0;i<Lb.length;i++){ //逐个处理Lb的元素 e=Lb.elem[i]; //取Lb中第i个元素 j=0; while(j<La.length&&La.elem[j]!=e)++j; //在La中查找e if(j==La.length){ //La中没有找到e La.elem[La.length]=e; //e插入到La的最后 La.length++; //La长度增加1 }//if }//for delete [] Lb.elem; //释放Lb内存 Lb.length=0;Lb.listsize=0; }// end Union_sq

算法3.25 void exchange(SqList &L,int m,int n) {//实现L中前m个元素和后n个元素的交换。 for(k=1;k<=n;k++){ //对b1,b2,...,bn逐个处理 w=L.elem[m+k-1]; //移出bk for(j=m+k-1;j>=k;j--) //a1,a2,...am均后移 L.elem[j]=L.elem[j-1]; L.elem[k-1]=w; //bk放到a1前 }//for }// end exchange

算法3.26 void invert(ElemType &R[],int s,int t) {//实现数组R中从下标s到t的逆置 for(k=s;k<=(s+t)/2;k++){ w=R[k]; //交换R[k]和R[t-k+s] R[k]=R[t-k+s]; R[t-k+s]=w; }//for }// end invert

算法3.27 void exchange2(SqList &L,int m,int n) {//利用invert实现L中前m个元素和后n个元素的交换 invert(L.elem,0,m+n-1); invert(L.elem,0,n-1); invert(L.elem,n,m+n-1); }// end exchange2

算法3.14 void InitList_L(LinkList &L) {//初始化链表L L=NULL; }// end InitList_L

算法3.15 Int ListLength_L(LinkList L) {//求链表L的长度 p=L;k=0; while(p){ k++;p=p->next; }//while return k; }// end ListLength_L

算法3.16 {//在链表L中查找元素e p=L; while(p&&p->data!=e)p=p->next; LNode * LocateItem_L(LinkList L,ElemType e) {//在链表L中查找元素e p=L; while(p&&p->data!=e)p=p->next; return p; }// end LocateItem_L

算法3.17 void ListInsert_L(LinkList &L,LNode *p,LNode *s) {//在链表L中,在p所指结点前插入s所指的结点 if(p==L){ //p是第一个结点 s->next=L; L=s; }//if else { //p不是第一个结点 q=L; while(q&&q->next!=p)q=q->next;//找后继是p的结点 if(q){q->next=s;s->next=p;} //在p前插入s else ErrorMsg(“p不是L中的结点”); }//else }// end ListInsert_L

算法3.18 void ListDelete_L(LinkList &L,LNode *p,ElemType &e) {//在链表L中,删除p所指结点 if(p==L)L=p->next; //p是第一个结点 else { //p不是第一个结点 q=L; while(q&&q->next!=p)q=q->next;//找后继是p的结点 if(q)q->next=p->next; //使p的原前驱直接指向p的后继 else ErrorMsg(“p不是L中的结点”); // p不在L中 }//else e=p->data;delete p; //保存被删除的元素值,释放空间 }// end ListDelete_L

算法3.24 void Purge(SqList &L) {//把顺序有序表L中相同的元素删除。 i=-1;j=0; while(j<L.length){ if(j==0||L.elem[j]!=L.elem[i]) L.elem[++i]=L.elem[j]; j++; }//while L.length=i+1; }// end Purge

算法3.28 void union_ord(LinkList &La,linkList &Lb) {//有序循环链表La、Lb表示的集合A、B,求表示集合A∪B的链表Lc,结果存储在La pa=La->next->next; pb=Lb->next->next; rc=La->next; ha=La->next; hb=Lb->next; //保留头结点指针 while(pa!=ha && pb!=hb){ if(pa->data < pb->data){ //pa所指结点值小 rc->next=pa;rc=pa;pa=pa->next; //pa链入Lc } else if(pa->data > pb->data){ //pb所指结点值小 rc->next=pb;rc=pb;pb=pb->next; //pb链入Lc else{ rc->next=pa;rc=pa;pa=pa->next; //pa链入Lc qb=pb;pb=pb->next;delete qb; //删除pb所指结点 }//while if(pb==hb)rc->next=pa; //Lb结束直接链入La剩余部分 rc->next=pb; //直接链入Lb剩余部分 Lb->next=ha;La=Lb; }//else delete hb; //释放Lb头结点,结果在La中 }// end union_ord