单链表

1.存储结构

typedef struct Lnode //定义单链表结点类型 { ElemType data; struct Lnode *next; //指向后继节点的指针 } LinkList;

2.建立单链表

头插法:将新节点插入到当前链的表头上， void CreateListF(LinkList *&L, ElemType a[], int n) { Listlink *s; int i; L = (LinkList *) malloc (sizeof(LinkList)); //创建头节点 L-> next = Null; for(i =0; i<n; i++) { s =(LinkList *) malloc(sizeof(LinkList)); //创建新结点 s-data = a[i] ; s-next =L->next; //将*s插入到开始节点之前，头节点之后 L->next =s; } }

头插法生成的链表中结点的次序与原数组元素的次序相反，其时间复杂度O(n)。

2.尾插法：将当前结点插入到当前链表的表尾。做法：设立尾指针，使其始终指向链表的尾结点。

void CreateListR(LinkList *&L, ElemType a[], int n) { LinkList *s, *r; int i; L =(LinkList *) malloc (sixeof((LinkList)); //创建头节点 L->next= NULL; r = L; for(i=0 ; i<n; i++) { s = (LinkList *) malloc (sixeof((Linklist)); //创建新结点 s->data = a[i]; //赋值 r->next = s; //将*s插入到*r之后 r=s; } r-next=NULL; //将终端结点指向空结点 }

其时间复杂度O(n)。

3.查找结点的算法

从单链表中开始查找第一个与e相等点，找到返还位置，否则返回0

int LocateElem(LinkList *L, ElemType e) { Linklist *p=L->next; //将指针p指向第一个结点（非头节点） int n =1; while(p!=NULL && p-data !=e) //指针不为空且当前结点数据不等于e,则循环 { p= p->next; n++; } if(p==NULL) return 0; else return (n); }

4.插入结点的算法

修改要插入位置的前一个的结点后继指针。

其关键语句是：

s->next = p->next;

p->next =s

5.删除结点的算法

找到要删除的元素，修改前驱节点指针。

关键语句：

p->next = p-next->next;