数据结构3线性表.ppt

2．3 线性表的链式表示与实现 顺序表示的优点是随机存取表中的任意元素； 顺序表示的弱点是在作插入或删除操作时，需移动大量元素。 链式表示 ---- 没有顺序表示的弱点，也失去了顺序表示的优点。 2．3．1 线性链表 线性表的链式表示------是可以用一组任意的存储单元存储线性表的数据元素。 例： 线性表 （赵，钱，孙，李，周，伍，张，王） 的链式表示 （赵，钱，孙，李，周，伍，张，王）的链式表示 链表相关的名称 数据域、指针域 结点、头结点 指针(链) 链表、单链表(线性链表) 线性表的单链表存储结构 插入结点：指针p所指的结点后插入指针s所指的结点 s-next = p-next; p-next = s; 插入结点程序 删除结点：删除指针p所指的结点后的结点 p-next = p-next -next; 删除结点程序删除第i个元素，并由e返回其值 2．3．2 循环链表 循环链表的特点 ---- 表中的最后一个结点的指针域指向头结点, 整个链表形成一个环。 从表的任意结点出发可以找到表中其它结点。 2．3．3 双向链表 双向链表的特点 ---- 表中的每个结点有两个指针域，一个指向后继结点，一个指向前趋结点, 整个链表形成两个环。 从表的任意结点出发可以通过正向环（或反向环）找到表中其它结点。 typedef struct DuLnode{ ElemType data; Struct DuLnode *prior; Struct DuLnode *next; }DuLnode, *DuLinklist; 插入结点：指针p所指的结点前插入指针s所指的结点 s-prior = p-prior; p- prior -next = s; s-next = p; p-prior = s; 插入结点程序 删除结点：删除指针p所指的结点 删除结点程序删除第i个元素，并由e返回其值 顺序存储线性表的插入和删除的一个完整C程序实例 typedef int ElemType; typedef int Status; #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; int length; int listsize; }Sqlist main(){ Sqlist Lst; int i, n=101; ElemType e; if(InitList_Sq(Lst)==OK){ // 线性表Lst 初始化成功 for(i=1;i=n;i++) if(ListInsert_Sq(Lst,i,i)!=OK) break; // 插入值1 到 n printf(“\n”); // 换行 for(i=0;iLst.length;i++) printf(i,e=%d,%d\n,i,Lst.elem[i]); // 打印值1到n getch(); // 等待键盘响应 if(ListDelete_Sq(Lst,5,e)==OK){ // 删除第5个元素 printf(delete_elem=%d\n,e); // 打印被删除的元素 getch(); // 等待键盘响应 for(i=0;iLst.length;i++) printf(i,e=%d,%d\n,i,Lst.elem[i]); // 打印线性表Lst的所有元素 } } } Status InitList_Sq(Sqlist *L) // 算法2.3 { // 构造一个空的线性表L L-elem=(ElemType *)malloc (LIST_INIT_SIZE *sizeof(ElemType)); if(!L-elem)exit(OVERFLOW); // 存储分配失败 L-length=0; // 空表长度为0 L-listsize=LIST_I