郑州知名网站推广实验教学中心网站建设

一、单链表的基本操作的实现

1.建立单链表：头插法----元素插入在链表头部，也叫头插法。

1.从一个空表开始，重复读取数据。
2.生成新结点，将读入数据存放到新结点的数据域中。
3.从最后一个结点开始，依次将各结点插入到链表的最前端。

void CreateList(LinkList& L, int n) {L = new LNode;L->next = NULL;//先创建一个带头结点的单链表LinkList p;int i;for (i = n; i > 0; --i) {p = new LNode;//生成新结点p = (LNode*)malloc(sizeof(LNode));cin >> p->data;//输入元素值scanf(&p->data);p->next = L->next;L->next = p;}
}

2.建立单链表：尾插法----元素插入在链表尾部，也叫尾插法。

1.从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
2.初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

void CreateList(LinkList& L, int n) {L = new LNode;L->next = NULL;int i;LinkList r = L;//尾指针r指向头结点for (i = 0; i < n; ++i) {LinkList p = new LNode;cin >> p->data;//生成新结点，输入元素值p->next = NULL;r->next = p;//插入到表尾r = p;//r指向新的尾结点}
}

二、线性表的链式表示和实现

1.循环列表

循环列表：是一种头尾相连的链表（即：表中的最后一个结点的指针域指向头指针，整个链表形成一个环）。

优点：从表中任一结点出发均可找到表中的其他结点。
注意：由于循环指针没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是他们是否等于头指针。
p != L;
P -> next != L;

头指针表示单循环链表：①找a1的时间复杂度：O（1）；②找an的时间复杂度：O（n）。
注意：表的操作常常在表的首尾进行。
尾指针表示单循环链表：①a1的存储位置：R->next->next;
②an的存储位置是：R。时间复杂度都是O（1）。

2.带尾指针的循环链表合并（将Tb合并在Ta之后）

分析的操作：
①p存表头结点（p=Ta->next）
②Tb表头连接在Ta表尾(Ta->next = Tb->next->next)
③释放Tb表结点(delete Tb->next)
④修改指针(Tb->next = p)

LinkList Connect(LinkList Ta, LinkList Tb) {//假设Ta和Tb都是非空的单循环链表LinkList p;p = Ta->next;//p存表头结点Ta->next = Tb->next->next;//Tb表头连接Ta表尾delete Tb->next;//释放Tb的头结点Tb->next = p;//修改指针return Tb;
}