分类： IT职场
2011-06-09 15:12:53
双链表数据结构：
struct LinkList
{
int data;
struct LinkList *pre;
struct LinkList *next;
};
(1) 后插法构造双链表
struct LinkList *CreateLinkListAfter()
{
struct LinkList *head, *tail, *newNode;
head = tail = NULL;
while (1)
{
newNode = new struct LinkList;
scanf("%d", &newNode->data);
if (newNode->data < 0)
{
delete newNode;
break;
}
if (head == NULL) //空链表
{
head = tail = newNode;
}
else
{
tail->next = newNode;
newNode->pre = tail;
tail = newNode;
}
}
if (head != NULL)
{
head->pre = NULL;
}
if (tail != NULL)
{
tail->next = NULL;
}
return head;
}
(2) 遍历双链表
void PrintLinkList(struct LinkList *head)
{
struct LinkList *p = head;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
(3) 删除链表
void FreeLinkList(struct LinkList *head)
{
struct LinkList *p = head;
while (head)
{
p = head;
head = p->next;
delete p;
}
}
(4) 双链表插入
struct LinkList *InsertLinkList(struct LinkList *head, int value)
{
struct LinkList *newNode = new struct LinkList;
newNode->data = value;
if (head == NULL) //空链表插入后就为头结点
{
head = newNode;
head->next = NULL;
head->pre = NULL;
return head;
}
else
{
struct LinkList *p = head;
while (newNode->data > p->data && p->next != NULL)
{
p = p->next;
}
if (newNode->data <= p->data) //头结点前插入
{
if (p == head)
{
head->pre = newNode;
newNode->next = head;
newNode->pre = NULL;
head = newNode;
}
else //中间节点插入
{
newNode->next = p;
p->pre->next = newNode;
newNode->pre = p->pre;
p->pre = newNode;
}
}
else //尾节点后插入
{
p->next = newNode;
newNode->pre = p;
newNode->next = NULL;
}
}
return head;
}
(5) 双链表元素删除
struct LinkList *DelLinkList(struct LinkList *head, int value)
{
if (head == NULL)
{
return head;
}
else
{
struct LinkList *p = head;
while (p->data != value && p->next != NULL)
{
p = p->next;
}
if (p->data == value)
{
if (p == head) //删除头结点
{
head = head->next;
head->pre = NULL;
delete p;
}
else if (p->next == NULL) //删除尾节点
{
p->pre->next = NULL;
delete p;
}
else //删除中间节点
{
p->pre->next = p->next;
p->next->pre = p->pre;
}
}
else //没有找到要删除的节点
{
printf("there is the element's value is %d\n", value);
}
return head;
}
}
