数据结构与算法第三章简单数据结构new.ppt
3/2/20231第三章 简单数据结构3/2/20232第3章 简单数据结构l3.13.1 顺序表顺序表l3.2 3.2 链表链表l3.33.3 栈栈l3.43.4 队列队列l3.53.5 * *广义表广义表3/2/20233线性结构的特点 存在唯一的被称为“第一个”的或“起始”的数据元素； 存在唯一的被称为“最后一个”的或“终端”的数据元素； 除第一个元素之外，集合中的每一个数据元素均有且仅有一个前趋； 除最后一个元素之外，集合中的每一个数据元素均有且仅有一个后继。3/2/202343.1 顺序表l3.1.1 线性表的基本概念线性表是n（n0)个数据元素的有限序列，记为：L=（a1,a2,ai,an）林鹏黄龙张艺谋张三丰（A,B,C,D,E,Z)字母表登记表3/2/20235线性表的基本运算 初始化setnull(L)，建立一个空的线性表L； 求表长length(L)，函数返回L中的元素个数； 取第i个元素get(L,i)，其中1ilength(L)，否则返回NULL；求前趋prior(L,x)，返回元素x的前趋；求后继next(L,x)，返回元素x的后继定位locate(L,x)，返回元素x在L中的位置，若x不存在，返回0或NULL；插入元素x到第i个元素之前 insert(L,x,i)，其中1ilength(L)+1，否则插入失败；删除第i个元素delete(L,i)，其中1ilength(L)；3/2/202363.1.2 线性表的顺序存储顺序表l顺序表：用一组地址连续的存储单元依次存储线性表的元素，用数组实现 例：（A,B,C,D,E,Z)ABCDEZ线性表的第i个元素的存储地址为Loc(ai)=Loc(a1)+(i-1)*k 3/2/20237顺序表数据类型的定义/定义每一个结点，根据具体情况变化typedef struct int yinyu; /英语 int shuxue ;/数学 elemtype; /定义顺序表#define maxsize 1024typedef struct /顺序表最多容纳maxlen个元素 elemtp datamaxsize; int last; / 指示当前表长 sequenlist;89907868985566775588英语数学last=5maxlen3/2/202383.1.3 顺序表上的基本运算（1）顺序表元素插入操作的算法：A1A2AiAn-1An在第i个位置插入需移动次数为n-i+1次，每个位置插入的概率为1/(n+1)平均移动次数： (n-i+1)/(n+1)=n/2 (其中i=1.n+1) 算法的时间复杂度 T(n)=O(n) maxsize3/2/202393.1.3 顺序表上的基本运算（1）顺序表元素插入操作的算法：void insert(sequenlist *L,elemtype x,int i) int j; if(i(L-last+1) printf(“插入位置不正确插入位置不正确n”); else if(L-last=MAXSIZE) printf(“表已满，发生上溢表已满，发生上溢n”); else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-last=L-last+1; /*insert*/3/2/2023103.1.3 顺序表上的基本运算（2）顺序表元素删除操作的算法：A1A2A3AiAn删除第i个元素需要移动n-i次平均移动次数： (n-i)/n (其中i=0.n-1) 算法的时间复杂度T(n)=O(n) 3/2/2023113.1.3 顺序表上的基本运算（2）顺序表元素删除操作的算法： void delete(sequenlist *L, int i) int j; if(iL-last) printf(“删除位置不正确删除位置不正确n”); else for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last=L-last-1; 3/2/202312举例删除顺序表中的重复元素l算法思路：从顺序表中第一个元素起，逐个检查它后面是否有值相同的其它元素，若有便删除之；直到表中所有元素都已无重复元素为止。为此，算法中需设两重循环，外层控制清除的趟数，内层控制每趟的检查范围。3/2/202313举例删除顺序表中的重复元素void Purge(sequenlist *L) int i,j,k; i=1; while(ilast)/每个元素都要比较每个元素都要比较 j=i+1; while(jlast) if(L-dataj=L-datai)/相等则删相等则删除除 for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/delete(L,j)3/2/2023143.2 链表l顺序表存储的缺点1）预先分配连续的空间2）不能根据需要动态分配3）插入删除等操作需要移动大量数据HELLO3/2/2023153.2 链表l单链表单链表 l循环链表循环链表 l双向链表双向链表 3/2/2023163.2.1单链表l单链表的组成及定义HELLO数据域 指针域结点组成结点组成结点定义：结点定义：typedef struct node elemtp data; struct node *next;LinkList;L头指针头指针3/2/2023173.2.1单链表l头结点，头指针，第一个结点（首元结点）HELLO第一个结点第一个结点head头结点头结点头指针头指针3/2/2023183.2.1单链表l动态生成一个结点 LinkList *H; H=(LinkList *) malloc(sizeof(LinkList);l 对结点中域的访问 H-elemtp和H-next 或 (*H).elemtp和(*H).nextl释放结点占用的空间 free(H) 3/2/2023193.2.2单链表上的基本运算（1）单链表建立： /尾插法建表尾插法建表：输入：输入n个字符建立链表个字符建立链表,直到输入为直到输入为*结束结束LinkList *CreateLinkList() char ch; LinkList *head;/*head为头结点指针为头结点指针*/ LinkList *r,*P; head=(LinkList *)malloc(sizeof(LinkList); head-next=NULL; r=head; /*尾指针初始化尾指针初始化*/ ch=getchar(); while(ch!=*) /*“*”为输入数据结束符号为输入数据结束符号*/ P=(LinkList *)malloc(sizeof(LinkList); P-data=ch; P-next=NULL; r-next=P; r=r-next; ch=getchar(); return head; HELLO头结点头结点head思考：头插法建表怎么建？rprp3/2/2023203.2.2单链表上的基本运算（2）求表长int LengthLinkList(LinkList *L) LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长返回表长*/ HELLO头结点头结点head3/2/202321（3）单链表元素的查找/查找元素为查找元素为X的结点的结点LinkList *LocateLinkList(LinkList *L，elemtyPe x;) LinkList *P; P=L-next; while(P!=NULL)&(P-data!=x) P=P-next; return P; /*返回找到的结点位置或返回找到的结点位置或NULL*/ /*LocateLinkList*/3/2/202322（3）单链表元素的查找/查找第查找第i个结点个结点LinkList *GetLinkList(LinkList *L,int i) LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; /*GetLinkList*/3/2/2023233.2.2单链表上的基本运算（4）单链表元素插入操作linklist_insert(linknode *L,int i,elemtp x)HELLOLwPq=(LinkList*)malloc(sizeof(LinkList);q-data=x;q-next=p-next;/修改指针修改指针p-next=q;q3/2/2023243.2.2单链表上的基本运算（3 3）单链表元素插入操作）单链表元素插入操作intlinklist_insert(linknode*L,inti,elemtpx)linknode*p,*q;intj=0;p=L;while(p-next!=NULL)&(j+next;if(j=i-1)q=(LinkList *)malloc(sizeof(LinkList);/建立新建立新结点结点q-data=x;q-next=p-next;/修改指针修改指针p-next=q;return(1);elsereturn(0);/插入位置无效插入位置无效3/2/2023253.2.2单链表上的基本运算（5）单链表元素删除操作linklist_del(linknode *L,int i)HELLOLPq=p-next;p-next=q-next; free(p); 3/2/202326删除单链表L中的第i个结点算法LinkList *deleteLinkList(LinkList *L,int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第查找第i-1个结点个结点*/ if(P=NULL) Printf(“第第i-1个元素不存在，参数个元素不存在，参数i 有错有错n”); else S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 该算法的时间复杂度为该算法的时间复杂度为O(n)3/2/2023273.2.3循环链表和双向链表1.循环链表HHELLOH非空循环链表非空循环链表思考：如何判断是最后一个元素？如何判断是空表？思考：如何判断是最后一个元素？如何判断是空表？空表空表head-next=head；3/2/2023283.2.3循环链表和双向链表2.双向链表前驱 数据 后继双链表结点格式Lhel格式定义：typedef struct dbnode elemtp data; struct dbnode *prior,*next;dblinknode;h空表空表L3/2/202329双向链表l插入结点将S结点插入P之前Lhel S-prior=P-prior; S-next=P; P-prior-next=s; P-prior=S; pAS3/2/202330双向链表l2.删除结点思考：双向如何添加删除双链表结点Lhelp-piror-next=p-next;p-next-piror=p-piror;free(p);p3/2/2023313.2.4两一元多项式相加的算法 已经两多项式A,B A=X -6X3 + 3X4 -6X5B=1+5X3+6X5+9x6求A+B;系数 指数 next格式定义：typedef struct node double coef; / 表示系数 int exp; / 表示指数 struct node *next;polynode; 3/2/202332多项式相加算法的思路l不产生新结点而利用原有结点空间，设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点，依次比较两指针所指结点的指数项。l若
