数据结构第2章-线性表.ppt

第二章线性表第二章线性表2.1线性表的概念2.1线性表的概念2.1线性表的概念2.1线性表的概念2.1线性表的概念2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现 二、顺序表的基本操作算法插入insert(v,x,i)功能：在顺序表v中的第i(1=i=n+1)个数据元素之前插入一个新元素x,插入前线性表为(a1,a2,a3,…,ai-1,ai,,…an) 插入后,线性表长度为n+1,线性表为(a1,a2,a3,…,ai-1,x,ai,,…an)2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现2.3线性表的链式存储和实现2.3.1线性链表2.3.1线性链表2.3.1线性链表2.3.1线性链表2.3.1线性链表2.3线性链表 2.2线性链表2.3.1线性链表2.3.1线性链表建立链表NODE*create_next(n)/*建立有n个结点的线性单链表的算法{NODE*head,*p,*q; inti; p=(NODE*)malloc(sizeof(NODE));head=p; for(i=I;I=n;i++) {q=(NODE*)malloc(sizeof(NODE)); q-data=i;q-next=NULL; p-next=q;p=q; } return(head); }插入结点q=(NODE*)malloc(sizeof(NODE));q-deta=‘a’; q-next=p-next; p-next=q;2.3.1线性链表2.3.1线性链表Intinsert_next(NODE*head,intx,inti) {NODE*p,*s;intj; p=head;j=0; while((p!=NULL)(ji-1)) {p=p-next;j++;} if(p==NULL)return(0); s=(NODE*(malloc(sizcof(NODE)); s-data=x; s-next=p-next; p-next=s; return(1);}删除结点q=p-next; p-next=q-next; free(q);2.3.1线性链表在线性链表中删除第i个结点Intdelete_next(NODE*head,inti) {NODE*p,*q;intj; p=head;j=0; while((p!=NULL)(ji-1)) {p=p-next;j++;} if(p==NULL)return(0); q=p-next;p-next=q-next;free(q); return(1);}2.3.1线性链表?2.3.1线性链表2.3.1线性链表小结2.4单向循环链表2.4单向循环链表2.4单向循环链表2.5双向链表2.5双向链表2.5双向链表2.5双向链表2.6一元多项式的表示及相加2．4一元多项式的表示及相加2．6一元多项式的表示及相加2．6一元多项式的表示及相加2．4一元多项式的表示及相加2．6一元多项式的表示及相加2．6一元多项式的表示及相加一元多项式的相加算法（算法2.8）续续第二章线性表小结本章学习了线性表的顺序存储结构——顺序表，链式存储结构,线性链表,循环链表,双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在