2.3线性表的链式表示和实现 单链表的结构 data next 带头结点的空表 (带头结点的非空表) 头结点的作用:对空表和表第元素和菲第元 素作统一处理。 ty pede struct Lnode t Elem Type data struct Lnode next 8) Lnode Linklis
2.3 线性表的链式表示和实现 • 单链表的结构 data next L ∧ L a1 a2 … an ∧ （带头结点的空表） （带头结点的非空表） 头结点的作用：对空表和非空表、第一元素和非第一元 素作统一处理。 typedef struct Lnode { ElemType data; struct Lnode *next; } Lnode, *LinkList;
2.3线性表的链式表示和实现 单链表的建立 Void Create List L(Link List &L, int n) L=(LinkList)malloc(sizeof(Lnode): >next=NULL: for(=n;1>0;-1) ip=(LinkList) malloc (sizeof(Lnode)) scanf( &p ->data); p->next=L->next; Lnext=p
2.3 线性表的链式表示和实现 • 单链表的建立 Void CreateList_L(LinkList &L, int n) { L=(LinkList) malloc (sizeof(Lnode)); L->next=NULL; for (i=n; i>0; --i) { p=(LinkList) malloc (sizeof(Lnode)); scanf(&p->data); p->next=L->next; L->next=p; } }
2.3线性表的链式表示和实现 单链表的查找 Status Getelem L(Link List L int i, Elem Type &e) & p=L->next while (p &&ji p≥p>next+j f(p‖j) return ERROR e=p->data return OK 练习查找结点数据为e的结点位置i
2.3 线性表的链式表示和实现 • 单链表的查找 Status Getelem_L(LinkList L, int i, ElemType &e) { p=L->next; j=1; while (p && j<i) { p=p->next; ++j; } if (!p || j>i) return ERROR; e=p->data; return OK; } (练习: 查找结点数据为e的结点位置i)
2.3线性表的链式表示和实现 单链表的插入 b ① LinkList) malloc(sizeof( Lnode) data=e ① next next ② enext (思考题①②顺序颠倒会怎样?)
2.3 线性表的链式表示和实现 • 单链表的插入 p a b ② ① s e s=(LinkList) malloc (sizeof(Lnode)); s->data=e; ① s->next=p->next; ② p->next=s (思考题： ① ②顺序颠倒会怎样？)
2.3线性表的链式表示和实现 单链表的删除 a lext -next=g-next ->data free (9)
2.3 线性表的链式表示和实现 • 单链表的删除 q … p a b c … q=p->next; p->next=q->next; e=q->data; free (q)