在双链表中,前面一部分遍历输出之后后面一部分无法运行,直接跳过,结束程序
下面是完整完整代码
#include
#include
#include
typedef struct DNode
{
int data;
struct DNode *next,*prior;
}DNode,*DLinkList;
//函数说明
DLinkList List_TailInsert(DLinkList &L);
bool Empty(DLinkList L);
void PrintList(DLinkList L);
DNode *GetElem(DLinkList L, int i);//查找表中某一结点
bool InsertNextDNode(DLinkList L,DNode *p,DNode *s);//插入结点
bool DeleteNextNode(DLinkList L, DNode* q);//删除结点
int main(void)
{
DLinkList L;
L = NULL;
DLinkList A = L;
printf("输入链表的值\n");
L = List_TailInsert(L);
printf("链表的取值为:\n");
PrintList(L);
int i;
printf("请输入您想查找结点的位置\n");
scanf("%d",&i);
DNode *p = GetElem(A, i);
DNode *s = NULL;
InsertNextDNode(A,p,s);
printf("插入结点之后链表的取值\n");
PrintList(L);
int e;
printf("请输入您想要q结点的位置\n");
scanf("%d",&e);
DNode *q = GetElem(L, i);
DeleteNextNode(L,q);
PrintList(L);
return 0;
}
DLinkList List_TailInsert(DLinkList &L)
{
L = (DLinkList)malloc(sizeof(DNode));//动态分配一个内存,创建了一个头结点,L指向头结点
if(NULL == L)
{
printf("动态内存分配失败,结束程序!\n");
exit(-1);
}
L->next = NULL;//最开始头结点的后继指针中地址为空
L->prior = NULL;//头结点的前驱指针地址一直为空
DNode *r = L;//定义一个指针也是指向头结点
DNode *s;
int e;
scanf("%d",&e);
while(e != 9999)
{
s = (DNode *)malloc(sizeof(DNode));
if(NULL == s)
{
printf("动态内存分配失败,结束程序!\n");
exit(-1);
}
s->data = e;//将输入的值赋值给s指针指向结点的指针域
r->next = s;//将s挂在r的后面,就相当于将s指向结点的地址给r指向结点的后继指针域中,这样两个结点就可以通过指针连接在一起
s->prior = r;//s指向的那个结点的前驱指针域放s指向那个结点的地址,这样s指向的那个结点就可以直接找到它的前驱结点
r = s;//将s的地址赋值给r,这样r就指向了s指向的那个结点
scanf("%d",&e);
}
return L;
}
//遍历输出
void PrintList(DLinkList L)
{
if(Empty(L))
{
printf("数组为空!\n");
}
else
{
DNode *p = L->next;
while(NULL != p)
{
printf("%d\n",p->data);
p = p->next;
}
printf("\n");
}
return;
}
//判断链表是否为空
bool Empty(DLinkList L)
{
if(NULL == L->next)//L指向的是头结点,头结点中的后继指针域就是头结点连接的那个结点的地址,如果为NULL,则为空链表
return true;
else
return false;
}
//按序号查找结点
DNode *GetElem(DLinkList L, int i)//i为位序,是从1开始的
{
if(i<1)
return NULL;
int j = 1;
DNode *p = L->next;//第一个结点指针赋给p,表示p指向第一个结点
while(p != NULL && jnext;
++j;
}
return p;
}
//后插结点:在p结点后插入结点
bool InsertNextDNode(DLinkList L,DNode *p,DNode *s)
{
s = (DNode*)malloc(sizeof(DNode));
if(NULL == s)
{
printf("动态内存分配失败,结束程序!\n");
exit(-1);
return false;
}
printf("请输入您要插入结点的值:\n");
int x;
scanf("%d",&x);
s->data = x;
if(NULL == p)
return false;
s->next = p->next;//如果p不为空的时候,将p指向的那个结点的直接后继结点的地址赋值给s指向的那个结点的后继指针域中,这样s指向的那个结点就可以1和p指向的结点的直接后继结点连接
if(NULL != p->next)//可能p后面没有结点,则直接跳到p->next = s继续执行
p->next->prior = s;//如果不为空,需要改变p指向结点的后继节点的前项指针
p->next = s;//将s地址赋值给p->next,这样就是这两个结点相连接
s->prior = p;//将p地址指向的结点的前项指针域
return true;
}
//删除p结点的后继节点
bool DeleteNextNode(DLinkList L, DNode* q)
{
if(NULL == q)//先判断q是否为空,若是空就没有该节点,自然返回false
return false;
DNode *r = q->next;//定义一个结点使其指向q指向的那个结点的后继结点
if(NULL == r)//如果q后面也没有结点自然也无法删除
return false;
q->next = r->next;//将r指向结点的后面一个结点的地址赋值给q指向结点的指针域,这样q指向结点就可以和那个结点相连接
if(NULL != r->next)//如果不为空则表明r就不是最后一个结点
r->next->prior = q;//就是r后面的那个结点的前指针指向q
free(r);//释放r的空间
return true;
}
在创建链表的函数里面应该加上r->next=NULL;
在这个函数的while循环里面应该加上s->next=NULL
因为之前没有加上去所以所创建的链表的尾结点的指针域没有指向NULL,所以导致遍历输出的时候根本就无法达到结束条件,所以运行的时候很慢,然后直接结束。并且要将A=L那个也去掉,其余的A全部换成L,这样就可以运行成功。
这段代码有一个问题是 i 在循环内被重新赋值,会导致循环条件 i < len(lst) 失效,从而导致 IndexError 异常。
假设 lst 是一个长度为 4 的列表,当 i 的值为 3 时,程序执行到 lst.pop(i) 时会将 lst 列表的最后一个元素弹出,也就是将 lst 的长度从 4 缩减到了 3,此时 i 的值也变成了 3。接下来,由于循环条件 i < len(lst) 已经不成立了,所以程序会跳出循环。但是 lst 中仍然有最后一个元素没有被遍历到,这就导致了数据的丢失。