#include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct DLNode { ElemType data; struct DLNode* prior, * next; }DLNode; //尾插法 void Tail(DLNode*& DL, int a[], int count) { DL = (DLNode*)malloc(sizeof(DLNode)); DL->next = NULL; DL->prior = NULL; DLNode* s, * r = DL; int i; for (i = 0; i < count; i++) { s = (DLNode*)malloc(sizeof(DLNode)); s->data = a[i]; r->next = s; s->prior = r; r = r->next;//r = s; } r->next = NULL; } //头插法 void Head(DLNode*& DL, int a[], int count) { DL = (DLNode*)malloc(sizeof(DLNode)); DL->next = NULL; DL->prior = NULL; DLNode* s; int i; for (i = 0; i < count; i++) { s = (DLNode*)malloc(sizeof(DLNode)); s->data = a[i]; s->next = DL->next; ///如果链表中除了头结点外还有其他结点，则还进行如下操作。 if (DL->next) DL->next->prior = s; s->prior = DL; DL->next = s; } } //按序号值查找结点 DLNode* GetElem(DLNode* DL, int pos) { int i = 1; DLNode* p = DL; //pos=0 if (pos < 0) return NULL; while (p && i <= pos) //pos>=1 { p = p->next; i++; } return p; } //新结点插入第pos个位置 bool Insert(DLNode* DL, int pos, ElemType elem) { DLNode* p = GetElem(DL, pos - 1); //当pos的值大于链表中除了空结点的结点个数的时候会执行此if语句 if (!p) //Note：p为头结点的时候，并不会进入此if块 return false; DLNode* s = (DLNode*)malloc(sizeof(DLNode)); s->data = elem; s->next = p->next; //这个判断保证了：如果除了头结点外还有3个元素且pos值为4的时候，不会发生异常。 if (p->next) p->next->prior = s; s->prior = p; p->next = s; return true; } //删除第pos个结点 bool Delete(DLNode* DL, int pos) { DLNode* p = GetElem(DL, pos - 1); if (!p || !p->next) return false; DLNode* q = p->next; p->next = p->next->next;//p->next = q->next; if (q->next) q->next->prior = p; free(q); return true; } //正序遍历 void Show(DLNode* DL) { DL = DL->next; int length = 0; while (DL) { printf("]", DL->data); DL = DL->next; length++; } printf("\n链表长度为：%d\n", length); } //自己写的逆序遍历 两种有点小差别，思路一样 void ReverseTraversal(DLNode* DL) { DLNode* p = DL->next; //这种加了额外的 p->next 不为空的判断， //是因为逆序输出是要将指针停留在最后一个结点上， //而顺序输出，则可以放心的将指针放在最后一个结点的后继(NULL)上。 while (p && p->next) p = p->next; while (p && p->prior) { printf("]", p->data); p = p->prior; } //DLNode* p = DL; //while (p->next) // p = p->next; //while (p && p->prior) //{ // printf("]", p->data); // p = p->prior; //} } int main() { DLNode* DL; int a[] = { 1,5,9,5,3 }; printf("===========头插法：\n"); Head(DL, a, 5); Show(DL); printf("===========头插法：\n"); Tail(DL, a, 5); Show(DL); printf("===========查找元素：\n"); int pos = 2; DLNode* elem = GetElem(DL, pos); if (elem) printf("查找位置：%d，值：%d\n", pos, elem->data); else printf("查找失败！\n"); printf("===========插入第pos个位置：\n"); pos = 6; Insert(DL, pos, 599); printf("插入位置：%d\n", pos); Show(DL); printf("===========删除第pos个位置的结点：\n"); pos = 4; Delete(DL, pos); printf("删除位置：%d\n", pos); Show(DL); printf("\n\n==============\n"); ReverseTraversal(DL); return 0; }
