关于数据结构(C语言版)的问题

2025-06-22 00:15:19
推荐回答(1个)
回答1:

第一题:下面的L.listsize是顺序表在建立的时候分配的总体存储量,INCREMENT是新增加的量,都是实现已经定义好的,EType是元素的类型,到具体的程序中的时候,可以使用typedef定义类型,这里是代指某个类型;具体算法如下:
void inser_order(List &L,EType Elem)
{if(L.length>=L.listsize) //当新增加元素时,表的总体长度大于已经分配的总体大小时,要重新分配表的长度;
{list *newbase;
newbase=(EType *)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(EType));//新分配的表长
if(!newbase) exit(OVERFLOW);//分配不成功;
L.elem=newbase;L.size+=INCREMENT;
}
List *p,*q;
int i=L.length-1;
q=&(L.elem[i]);
while(i>=0)//从表的最后的元素开始比较,寻找合适的插入位置;
{
if(Elem<=L.elem[i]&&Elem>L.elem[i-1]) //插入的数值位于当前值与前面值的中间值时
{
p=&(L.elem[i]);//指向要插入的位置
break;
}
{
if(i==L.length-1) //当插入的值是比最大元素还要大时
{
p=q;//指向最后的位置
break;
}
}
i--;
}
while(q>=p)//从后往前移动各个位置的数,然后找到要插入的位置,插入
{
*(q+1)=*q;
q=q-1;
if(q==p)//找到要插入的位置
{
*(q+1)=*q;
*q=e;//插入元素
++L.length;//表长加1
}
}
}
第二题:
void deletenode(Listnode &L,EType X)
{Listnode *p,*q,*r;//p用来寻找X结点,q用来指向X结点的前驱结点的前驱结点,r指向p所指向结点的前驱结点;
p=L;//初始时,指向头结点;
q=L;
if(p->elem==X)//第一个结点就是所找的X;
{
printf("The first node is X,can't delete its precessor");
exit(1);
}
while(p->next!=NULL)//遍历链表,寻找X的位置
{
if(p->elem==X)//找到X
{
while(q->next!=r)
q=q->next;//寻找X的前驱结点
//删除结点的操作
q->next=p;
r->next=NULL;
free(r);
}
r=p; //r永远指向p所指向结点的前驱结点
p=p->next;//p往后移动
}
}