什么是双向链表?
之前接触的链表都是有一个指针域指向后继元素,现在还有另一种做法,就是在节点内额外加多一个指针域,一个指针域用来指向他的上一个节点地址,另一个指针域用来指向下一个节点的地址,这样的链表我们称之为双向链表。
首先,创建结构体和头文件等
typedef struct Link{ int data; struct Link *up; struct Link *next;}link;link * insertLine(link * head,int newElem,int add);link * editLine(link * head,int newElem,int edit);link * delLine(link * head,int delElem);复制代码
初始化链表
link *initLink(int n){ link *head = (link*)malloc(sizeof(link));//申请空间定义头节点 int i; head->data = 1; head->up = NULL; head->next = NULL; link *tempLink = head; for (i=2; iup = tempLink;//指针域指向上一个节点 a->data = i; a->next = NULL; tempLink->next = a;//指针域指向下一个节点 tempLink->up = tempLink; tempLink = a; } return head;}复制代码
增加一个元素
link * insertLine(link * head,int newElem,int add){ link *tempLink = (link*)malloc(sizeof(link));//申请空间,插入一个元素 tempLink->data = newElem; tempLink->next = NULL; tempLink->up = NULL; if (add == 1) { //如果插入的地方是头部 tempLink->next = head;//它的后指针域指向head head->up = tempLink;//它的前指针域指向它自己 head = tempLink;//将指针域再次移到头节点 } else { int i; link *body = head; for (i=1;inext;//找到要插入结点的前一个结点 } if (body->next==NULL) { //如果插入的地方是最后一个位置 body->next = tempLink; tempLink->up = body; } else { body->next->up = tempLink;//更改插入位置的下一个节点的前趋针域 tempLink->next = body->next;//将自己节点的后指针域指向 未插入前自己上一个节点的后继指针 body->next = tempLink;//更改上一个节点的后继指针地址 tempLink->up = body;//将自己节点的前趋指针 指向上一个节点的地址 } } return head;}复制代码
删除一个元素
link * delLine(link * head,int delElem){ link *tempLink = head; while (tempLink->next) { if (tempLink->data == delElem) { //找到要删除的地址 tempLink->up->next = tempLink->next;//更改它上一个的后继指针地址 tempLink->next->up = tempLink->up;//更改它下一个节点的前趋指针地址 free(tempLink);//释放内存 return head; } tempLink = tempLink->next; }}复制代码
打印链表
void showLink(link *head){ link * temp=head; while (temp) { if (temp->next==NULL) { printf("%d\n",temp->data); }else{ printf("%d->",temp->data); } temp=temp->next; }}复制代码
修改一个元素
link * editLine(link * head,int newElem,int edit){ link *tempLink = head; int i; for (i=1;inext; } tempLink->data = newElem; return head;}复制代码
运行
int main(){ int n; n = 10; link *head = initLink(n); printf("初始化链表\n"); showLink(head); printf("添加\n"); insertLine(head,4,2); showLink(head); printf("修改\n"); editLine(head,5,2); showLink(head); printf("删除\n"); delLine(head,5); showLink(head);}复制代码