数据结构:双向链表1
时间:2010-10-12 来源:arkor
************************************************************************/
/* 数据结构:双向链表 */ /* 挑灯看剑[email protected] 2010-10 */ /* 云歌国际(Cloud Singers International) www.cocoral.com */ /************************************************************************/ #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include "core.h" typedef struct NODE { int data; //数据域 struct NODE* next; //后继结点 struct NODE* prior; //前驱结点 }Node, * NodePointer; //描述线性链表的头结点 typedef struct { int len; //记录结点长度 struct NODE* head; //记录第一个结点 struct NODE* tail;//记录最后一个结点 }NodeHead; void main() { /***************函数原型【开始】*************************/ void NodeInsert(NodeHead* H, int i, int e); void NodePrint(NodeHead H, char tag); void autoList(NodeHead* H, int n); Status NodeDelete(NodeHead* H, int i, Node* N); /***************函数原型【结束】*************************/ //初始化线性链表头元 NodeHead H = { 0, NULL, NULL }; Node N = { 0, NULL, NULL }; int i = 0, j = 0, e = 0; char tag = 'Y'; NodePrint(H, 'H'); autoList(&H, 10); //自动化链表 NodePrint(H, 'h'); //正向打印测试 NodePrint(H, 't'); //反向打印测试 /* //动态创建双向链表 puts("请输入插入元素位置和元素值!"); scanf("%d %d %c", &i, &e, &tag); while (tag == 'Y') { NodeInsert(&H, i, e); NodePrint(H,'H'); NodePrint(H,'T'); puts("请输入插入元素位置和元素值!"); scanf("%d %d %c", &i, &e, &tag); } */ //执行删除操作 for (j = 0; j < 5; j++) { puts("请输入要删除结点的位置:"); scanf("%d", &i); if (NodeDelete(&H, i, &N)) { puts("删除成功!"); if (N.next && N.prior) { printf("删除当前结点值:%d,其前驱结点值:%d,后继结点值:%d\n", N.data, N.prior->data, N.next->data); } else { printf("删除当前结点值:%d\n", N.data); } NodePrint(H, 'H'); NodePrint(H, 't'); } } } //在线性链表的第i个位置前面插入元素e void NodeInsert(NodeHead* H, int i, int e) { static Status NodeIsEmpty(NodeHead H); //函数原型 NodePointer p = NULL, q = NULL;//遍历指针 COUNT j = 0; //计数器 NodePointer s = (NodePointer) malloc(sizeof(Node));//为新结点分配存储空间 s->data = e; //插入前预检查 if (!NodeIsEmpty(*H)) //如果链表非空 { if (i == 1) //如果i等于1 { p = H->head;//p指向第一个结点,在p的前面插入,只需处理p前面的指针 p->prior = s; //p的后继结点保持不变 s->next = p; s->prior = NULL; H->head = s; //+++++++++++链表的尾结点重设指向次尾结点++++++++++ //查找次尾结点 for (p = H->head,j = 1; j <= H->len - 2; j++) p = p->next; //重设尾结点前驱指针 H->tail->prior = p; //+++++++++++++++++++++++++++++++++++++++++++++++++ H->len += 1; //长度加1 puts("插入成功!"); } else if (i >= 2 && i <= H->len) //如果i在2-Len区间 { //查找第i-1个结点 p = H->head;//p指向第一个结点 //q = H->tail;//q指向最后一个结点 for (j = 2; j <= i - 1; j++) //p初始化指向第1个元素,因此循环次数为i-1次 p = p->next; //p前进一位,直到指向第i-1个结点 //执行插入操作 s->next = p->next; s->prior = p; p->next = s; //在p的后面插入,其前驱指针不变 H->len += 1;//长度加1 //-----------处理头元-尾结点----------------------- for (p = H->head; p != NULL; p = p->next) H->tail = p; //------------------------------------------------- //+++++++++++链表的尾结点重设指向次尾结点++++++++++ //查找次尾结点 for (p = H->head,j = 1; j <= H->len - 2; j++) p = p->next; //重设尾结点前驱指针 H->tail->prior = p; //+++++++++++++++++++++++++++++++++++++++++++++++++ puts("插入成功!"); //NodePrint(*H, 'H'); } else { printf("当前区间:1-%d,插入位置为:%d\n", H->len, i); puts("插入位置越界,默认为链表中的第一个结点!"); p = H->head;//p指向第一个结点,在p的前面插入,只需处理p前面的指针 p->prior = s; //p的后继结点保持不变 s->next = p; s->prior = NULL; H->head = s; //链表的尾结点保持不变 H->len += 1; //长度加1 //-----------处理头元-尾结点----------------------- for (p = H->head; p != NULL; p = p->next) H->tail = p; //------------------------------------------------- //+++++++++++链表的尾结点重设指向次尾结点++++++++++ //查找次尾结点 for (p = H->head,j = 1; j <= H->len - 2; j++) p = p->next; //重设尾结点前驱指针 H->tail->prior = p; //+++++++++++++++++++++++++++++++++++++++++++++++++ puts("插入成功!"); } } else { printf("插入前链表为空,插入元素 e=%d 默认为第一个结点!\n", s->data); H->head = H->tail = s; //头指针和尾指针均指向新插入结点 H->len = 1; s->next = s->prior = NULL; //后继结点和前驱结点均为NULL puts("插入成功!"); } } /* * 判断结点是否为空 */ static Status NodeIsEmpty(NodeHead H) { if (H.len == 0 || H.head == NULL || H.tail == NULL) return TRUE; else return FALSE; } 相关阅读 更多 +