双向链表
双向链表的每个结点除含有数据域外,还有两个指针域,分别指向直接前驱结点和直接后继结点。因此,从双向链表中的任一结点开始,均可方便地访问其前驱结点和后继结点。
双向循环链表
双向循环链表需要注意的就是:链表为空时, 让头指向尾。
结构体
typedef int ElemType;
typedef struct Dline {
struct Line *prior; //指针域,指向直接前趋元素
ElemType data; //数据域
struct Link *next; //指针域, 指向直接后继元素
}Dline, *pDline;
初始化
//初始化
void InitDLine(pDline *head, pDline *tail) {
(*head) = (Dline *)malloc(sizeof(Dline));
(*tail) = (Dline *)malloc(sizeof(Dline));
if (!(*head) || !(*tail)) {
return;
}
(*head)->prior = NULL;
(*tail)->next = NULL;
//链表为空时, 让头指向尾
(*head)->next = (*tail);
(*tail)->prior = (*head);
}
创建结点
//为新节点开辟空间 这是一块存储空间,包括一个数据域+两个指针域
pDline NewD(ElemType data) {
pDline temp = (Dline *)malloc(sizeof(Dline));
assert(temp);
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
return temp;
}
打印
//打印
void PrintDLine(pDline head, pDline tail) {
pDline pmove = head->next;
while (pmove != tail) {
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
获取链表长度
//获取链表长度
int GetDLineLength(pDline *head, pDline *tail) {
if (!(*head) || !(*tail)) {
return -1;
}
pDline pmove = (*head)->next;
int count = 0;
while (pmove != (*tail)) {
pmove = pmove->next;
count++;
}
return count;
}
插入结点
//尾插
void InsertDLineTail(pDline *head, pDline *tail, ElemType data) {
if (!(*head) || !(*tail)) {
return;
}
pDline temp = NewD(data);
if (!temp) {
return;
}
pDline tfront = (*tail)->prior;
tfront->next = temp;
temp->prior = (*tail)->prior;
temp->next = (*tail);
(*tail)->prior = temp;
}
//头插
void InsertDLineHead(pDline *head, pDline *tail, ElemType data) {
if (!(*head) || !(*tail)) {
return;
}
pDline temp = NewD(data);
if (!temp) {
return;
}
pDline pmove = (*head)->next;
pmove->prior = temp;
temp->next = pmove;
(*head)->next = temp;
temp->prior = (*head);
}
// 指定位置pos插入data
void InsertDLinePos(pDline *head, pDline *tail, ElemType data, int pos) {
if (!(*head) || !(*tail)) {
return;
}
pDline pmove = (*head)->next;
if (pos == 1) {
InsertDLineHead(head, tail, data);
return;
}
if (pos == GetDLineLength(head, tail) + 1) {
InsertDLineTail(head, tail, data);
return;
}
else {
for (int i=1; i<pos; i++) {
pmove = pmove->next;
if (pmove == (*tail)) {
printf("超过链表长度...\n");
return;
}
}
pDline temp = NewD(data);
pDline pprior = pmove->prior;
pprior->next = temp;
temp->prior = pmove->prior;
temp->next = pmove;
pmove->prior = temp;
}
}
删除结点
//尾删
void DeleteDLineTail(pDline *head, pDline *tail) {
if (!(*head) || !(*tail)) {
return;
}
pDline pmove = (*tail)->prior;
pDline pprior = pmove->prior;
pprior->next = (*tail);
(*tail)->prior = pmove->prior;
free(pmove);
}
//首删
void DeleteDLineHead(pDline *head, pDline *tail) {
if (!(*head) || !(*tail)) {
return;
}
pDline pmove = (*head)->next;
pDline pmove_next = pmove->next;
(*head)->next = pmove_next;
pmove_next->prior = (*head);
free(pmove);
}
//删除指定位置pos的元素
void DeleteDLinePos(pDline *head, pDline *tail, int pos) {
if (!(*head) || !(*tail)) {
return;
}
pDline pmove = (*head)->next;
if (pos == 1) {
DeleteDLineHead(head, tail);
return;
}
else {
for (int i=1; i<pos; i++) {
pmove = pmove->next;
if (pmove == (*tail)) {
printf("超过链表长度...\n");
return;
}
}
pDline pmove_next = pmove->next;
pDline pprior = pmove->prior;
pprior->next = pmove_next;
pmove_next->prior = pmove->prior;
free(pmove);
}
}
查找元素
//查找元素的位置
int FindDLinePos(pDline *head, pDline *tail, ElemType data) {
if (!(*head) || !(*tail)) {
return -1;
}
pDline pmove = (*head)->next;
int pos = 1;
while (pmove) {
if (pmove->data == data) {
return pos;
}
else {
pmove = pmove->next;
pos ++;
}
}
printf("找不到...\n");
return -1;
}
按元素删除
//删除找到的第一个元素
void DeleteDLineFindData(pDline *head, pDline *tail, ElemType data) {
if (!(*head) || !(*tail)) {
return;
}
int pos = FindDLinePos(head, tail, data);
if (pos == -1) {
return;
}
else {
DeleteDLinePos(head, tail, pos);
return;
}
}
//删除所有值为data的结点
void DeleteDLineFindAllData(pDline *head, pDline *tail, ElemType data) {
if (!(*head) || !(*tail)) {
return;
}
pDline pmove = (*head)->next;
int pos = FindDLinePos(head, tail, data);
if (pos == -1) {
return;
}
while (pos != -1) {
DeleteDLinePos(head, tail, pos);
pmove = (*head)->next;
pos = FindDLinePos(head, tail, data);
}
}
逆置
//逆置
void ReverseDLine(pDline *head, pDline *tail) {
if (!(*head) || !(*tail)) {
return;
}
pDline begin = (*head);
pDline end = (*tail);
while(!(begin==end||begin->prior==end))
{
ElemType data = begin->data;
begin->data = end->data;
end->data = data;
end = end->prior;
begin = begin->next;
}
}
拼接
//拼接
void JoinDLine(pDline *Lahead, pDline *Latail, pDline *Lbhead, pDline *Lbtail) {
if (!(*Lahead) || !(*Latail)) {
return;
}
if (!(*Lbhead) || !(*Lbtail)) {
return;
}
if (*Lahead == *Latail && (*Lahead)->next != *Lbtail) {
*Lahead = *Lbhead;
*Latail = *Lbtail;
return;
}
if ((*Lahead)->next != *Latail && (*Lahead) == *Lbtail) {
return;
}
pDline pa = (*Lahead)->next;
pDline pb = (*Lbhead)->next;
if (pa->data >= pb->data) {
pDline next = pb->next;
(*Lahead)->next = pb;
pb->next = pa;
pa->prior = pb;
pa = pb;
pb = next;
}
while (pa && pb) {
if (pa->data >= pb->data) {
printf("%d %d\n", pa->data, pb->data);
pDline next = pb->next;
pDline front = pa->prior;
front->next = pb;
pb->prior = front;
pb->next = pa;
pa->prior = pb;
pa = pb;
pb = next;
}
if (pb == (*Lbtail)) {
return;
}
else {
pa = pa->next;
}
}
if (pb) {
pDline front = pa->prior;
front->next = pb;
pb->prior = front;
pa = pb;
}
}
测试函数
void test() {
Dline Dline;
pDline head = &Dline;
pDline tail = &Dline;
InitDLine(&head, &tail);
pDline head2 = &Dline;
pDline tail2 = &Dline;
InitDLine(&head2, &tail2);
InsertDLineTail(&head, &tail, 23);
PrintDLine(head, tail);
InsertDLineHead(&head, &tail, 20);
PrintDLine(head, tail);
DeleteDLineTail(&head, &tail);
PrintDLine(head, tail);
DeleteDLineHead(&head, &tail);
PrintDLine(head, tail);
InsertDLinePos(&head, &tail, 23, 1);
InsertDLinePos(&head, &tail, 30, 2);
InsertDLinePos(&head, &tail, 48, 3);
InsertDLinePos(&head, &tail, 24, 2);
InsertDLinePos(&head, &tail, 36, 4);
InsertDLineHead(&head, &tail, 23);
InsertDLineTail(&head, &tail, 23);
PrintDLine(head, tail);
DeleteDLinePos(&head, &tail, 3);
PrintDLine(head, tail);
DeleteDLineFindData(&head, &tail, 23);
PrintDLine(head, tail);
DeleteDLineFindAllData(&head, &tail, 23);
PrintDLine(head, tail);
// ReverseDLine(&head, &tail);
// PrintDLine(head, tail);
printf("head2...\n");
InsertDLineTail(&head2, &tail2, 2);
InsertDLineTail(&head2, &tail2, 10);
InsertDLineTail(&head2, &tail2, 13);
InsertDLineTail(&head2, &tail2, 23);
InsertDLineTail(&head2, &tail2, 26);
InsertDLineTail(&head2, &tail2, 60);
PrintDLine(head2, tail2);
printf("JoinDLine...\n");
JoinDLine(&head2, &tail2, &head, &tail);
PrintDLine(head2, tail2);
}
网友评论