清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter3 Lists

chapter 3 Lists 8 1 AbStract Data Type(adt) (Definition Data Type = Objects ]U[ Operations Example〗int={0,±1,±2,…, NT MAX, INT MIN} (Definition An Abstract Data Type(ADT)is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations
CHAPTER 3 Lists §1 Abstract Data Type (ADT) 【Definition】Data Type = { Objects } { Operations } 〖Example〗 int = { 0, 1, 2, , INT_MAX, INT_MIN } { +, −, , , , } 【Definition】An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations

s2 The List ADt ADT. Objects:(item, item,., itemN-1) Operations: 9 Finding the length, N, of a list. Cg Printing all the items in a list 9 Making an empty list C Finding the k-th item from a list,0<k<N. Inserting a new item after the k-th item of a list, 0sk<N. C Deleting an item from a list C Finding next of the current item from a list e Finding previous of the current item from a list
§2 The List ADT Objects: ( item0 , item1 , , itemN−1 ) Operations: Finding the length, N, of a list. Printing all the items in a list. Making an empty list. Finding the k-th item from a list, 0 k < N. Inserting a new item after the k-th item of a list, 0 k < N. Deleting an item from a list. Finding next of the current item from a list. Finding previous of the current item from a list. ❖ ADT:

1. Simple Array implementation of lists(seqlist) array i=item Address Content array+i item; Sequential mapping -array+i+1 item;1 Maxsize has to be estimated Find Kth takes o(1)time. Insertion and Deletion not only take o(N time, but also involve a lot of data movements which takes time
1. Simple Array implementation of Lists (seqlist) array[ i ] = itemi MaxSize has to be estimated. Address Content array+i itemi array+i+1 itemi+1 …… …… …… …… Sequential mapping Find_Kth takes O(1) time. Insertion and Deletion not only take O(N) time, but also involve a lot of data movements which takes time

Seqlist's(顺序表 definition #define listsize 100 /max length typedef int ListData; typedef struct i ListData x data: //base address int length: //current items lengt th 3 Seqlist
SeqList ’s(顺序表)definition #define ListSize 100 //max length typedef int ListData; typedef struct { ListData * data; //base address int length; //current items’ length } SeqList ;

Basic operation of seqlist Initialize void InitList( Seq list &l)i L data=( ListData *) malloc Listsize s sizeof List Data ))i if (Ldata== NULL)( printf(“存储分配失败!n”); exit (1); length =0
Basic operation of SeqList ◼ Initialize void InitList ( SeqList & L ) { L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data == NULL ) { printf ( “存储分配失败!\n” ); exit (1); } L.length = 0; }

Find value find the position of x in the SeqList, return position of x in L, -1 if not found int Find( seqlist &l, listData x)i inti=0 while (i< Length & L data!=x) i++ if (i< Llength ) return 1; else return-l
▪ Find value:find the position of x in the SeqList,return position of x in L,-1 if not found. int Find ( SeqList &L, ListData x ) { int i = 0; while ( i < L.length && L.data[i] != x ) i++; if ( i < L.length ) return i; else return -1; }

Find value whether x is in L int IsIn( Seqlist &l, ListDatax) t inti=0, found=0 while(i< Llength &&l found if(L data!=x)i++ else found=l return found:
Find value:whether x is in L int IsIn ( SeqList &L, ListData x ) { int i = 0, found=0; while ( i < L.length &&!found ) if(L.data[i] != x ) i++; else found=1; return found; }

Solve the length of seq list int Length( Seq list &l)i return Length Find k th: return the k th data in ListData GetData( Seq list &l, int i)t if (i>=0&&i< Llength return Ldata; e print(“参数i不合理!Ⅶn”); eIs
◼ Solve the length of SeqList int Length ( SeqList & L ) { return L.length; } ◼ Find k_th:return the k_th data in l ListData GetData ( SeqList &L, int i ) { if ( i >= 0 && i < L.length ) return L.data[i]; else printf ( “参数 i 不合理!\n” ); }

Findsucceed int Next( Seq List &l, listData x)t int i= Find (x) if(i>0 & i0 & i< Llength )return i-1 else return -l
▪ FindSucceed int Next ( SeqList &L, ListData x ) { int i = Find(x); if ( i >0 && i 0 && i < L.length ) return i-1; else return -1; }

■ Insertion 56 25345716480963 Insert x 50 D 34567 2534575016480963 The average moving number of times(AM if it is equal probability to insert the new element into all positions AMN- I ∑(n-i)=—(n+…+1+0) n+1 n+1 1n(n+1) (n+1)2
▪ Insertion 2 2 ( 1) ( 1) 1 ( 1 0) 0 1 1 ( ) 1 1 = n n n n n n i n n i n = + + = + + + = + − = + AMN 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 50 Insert x 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 50 i The average moving number of times(AMN) if it is equal probability to insert the new element into all positions
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 2 ALGORITHM ANALYSIS.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 8 THE DISJOINT SET ADT.ppt
- 华中师范大学计算机科学系:《数据结构》第6章 二叉树和树.ppt
- 华中师范大学计算机科学系:《数据结构》第2章 线性表.ppt
- 华中师范大学计算机科学系:《数据结构》第8章 查找表.ppt
- 华中师范大学计算机科学系:《数据结构》第7章 图和广义表.ppt
- 华中师范大学计算机科学系:《数据结构》第5章 串和数组.ppt
- 华中师范大学计算机科学系:《数据结构》第4章 栈与队列.ppt
- 华中师范大学计算机科学系:《数据结构》第3章 排序.ppt
- 华中师范大学计算机科学系:《数据结构》第1章 绪论(王敬华).ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)实验一.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第三章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)三元组表示的稀疏矩阵加法.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter4 Stacks Queues.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter5 trees.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter6 Graph Algorithms.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter7 Search.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter8 Sorting.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter9 String.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验二.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)二叉树试验三.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验一.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验四.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验模板.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验五.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)复习2007级.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)2004级计算机B卷.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第九章 排序.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第1章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第2章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第3章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第4章 串.ppt