分类： IT业界
2011-06-09 15:11:00
1、单链表的数据结构：包括数据域和指针域
struct LinkList
{ int data;
struct LinkList *next;
};
2、单链表的构造有前插法和后插法
(1) 前插法构造链表,输入的数据小于零则退出
struct LinkList *CreateLinkBefore()
{
struct LinkList *head = NULL, *newNode;
while (1)
{
newNode = new struct LinkList;
scanf("%d", &newNode->data);
newNode->next = NULL;
if (newNode->data < 0)
{
delete newNode;
break;
}
if (head == NULL) //链表为空
{
head = newNode;
}
else //链表非空
{
newNode->next = head;
head = newNode;
}
}
return head;
}
(2) 后插法构造链表
struct LinkList *CreateLinkListAfter()
{
struct LinkList *head, *tail, *newNode;
head = tail = NULL;
while (1)
{
newNode = new struct LinkList;
scanf("%d", &newNode->data);
newNode->next = NULL;
if (newNode->data < 0)
{
delete newNode;
break;
}
if (head == NULL) //链表为空
{
head = tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
}
return head;
}
3 链表长度计算
int GetLinkListLen(struct LinkList *head)
{
int len = 0;
struct LinkList *p = head;
while (p)
{
len++;
p = p->next;
}
return len;
}
4 遍历链表中的数据
void PrintLinkList(struct LinkList *head)
{
struct LinkList *p = head;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
5 释放链表空间：从头结点开始往后删，在删除前一个节点前，必须将下一个节点的地址保存。
void FreeLinkList(struct LinkList *head)
{
while (head != NULL)
{
struct LinkList *p = head;
head = p->next;
delete p;
}
}
6 删除链表中第一个值为num的节点
struct LinkList *DelLinkList(struct LinkList *head, int value)
{
struct LinkList *p,*pre;
p = head;
if (p != NULL)
{
while (p->data != value && p->next != NULL)
{
pre = p;
p = p->next;
}
if (p->data == value)
{
if (p == head) //删除的节点为头结点
{
head = p->next;
delete p;
}
else
{
pre->next = p->next;
delete p;
}
}
else
{
printf("there is no record's value is equal to %d\n", value);
}
}
return head;
}
7 插入元素到链表
struct LinkList *InsertLinkList(struct LinkList *head, int value)
{
struct LinkList *newNode, *pre, *p;
p = head;
newNode = new struct LinkList;
newNode->data = value;
if (p)
{
while (newNode->data > p->data && p->next != NULL)
{
pre = p;
p = p->next;
}
if (newNode->data <= p->data)
{
if (p == head) //插入的节点值比小于等于头结点的值
{
newNode->next = p;
head = newNode;
}
else //插入的节点位置在中间位置
{
newNode->next = p;
pre->next = newNode;
}
}
else //插入节点值大于尾节点，即插入在链表尾部
{
p->next = newNode;
newNode->next = NULL;
}
}
return head;
}
8链表元素逆置有两种方法非递归与递归
(1) 链表元素逆置的非递归
struct LinkList *ReverseLinkList(struct LinkList *head)
{
struct LinkList *p1, *p2, *p3;
p1 = head;
if (p1 == NULL || p1->next == NULL)
{
return head;
}
p2 = p1->next;
while (p2)
{
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
head->next = NULL;
head = p1;
return head;
}
(2) 链表元素逆置，递归实现
struct LinkList *ReverseLinkListDiGui(struct LinkList *&head, struct LinkList *p)
{
if (p == NULL || p->next == NULL)
{
head->next = NULL;
head = p;
return p;
}
else
{
struct LinkList *tmp = ReverseLinkListDiGui(head, p->next);
tmp->next = p;
return p;
}
}
9、判断链表中是否有环，其基本思想是设两个指针从同一个位置出发，一个指针一次前进一步，另外一个指针一次前进两步, 如果链表中存在环，则经过一定的移动后，两个指针一定会再次在某个节点相遇.
bool CirCleLinkList(struct LinkList *head)
{
if (head == NULL || head->next == NULL)
{ return false; }
else
{
struct LinkList *p1, *p2;
p1 = p2 = head;
do
{
p1 = p1->next;
p2 = p2->next->next;
}while(p2 != NULL && p2->next != NULL && p1 != p2);
if (p1 == p2)
return true;
else
return false;
}
}
10、已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同）
非递归：
